Difference between seemingly identical statements

Question

Someone asked the following question, but deleted it for some reason. I think it's a nice subtle point to make.

In propositional calculus, $$ ((P\Rightarrow Q)\lor (P\Rightarrow R))\iff P\Rightarrow (Q\lor R). $$ However, for set inclusion it is false that $$ A\subseteq B \ \mathrm{or}\ A\subseteq C \iff A\subseteq B\cup C.$$ $⟹$ is true, while counterexamples for $⟸$ are easy to come up with.

Why is only $⟹,$ but not $⟸,$ true?

My intuition immediately says that this is because the set inclusion statement is quantified as $$ \forall x (x\in A \Rightarrow x\in B) \ \lor \forall x(x\in A \Rightarrow x\in C) \Longrightarrow \forall x(x\in A \Rightarrow x\in B\cup C)$$ but there is no $\Longleftarrow$. Is there some elegant way to better articulate this point?

Answer 1

My intuition is to immediately say there is a difference because the set inclusion statement is quantified as follows.

Yes, your intuition is correct: the issue is due to the presence of universal quantifiers.

If we rewrite the set formula avoiding them, the result will be:

$[(x∈A⇒x∈B)∨(x∈A⇒x∈C)]⟺[x∈A⇒(x∈B∨x∈C)]$

and the bi-conditional holds exactly because it has the "propositional form" above.

But when we universally quantify both sides, what we get will be:

$∀x[(x∈A⇒x∈B)∨(x∈A⇒x∈C)]⟺∀x[x∈A⇒(x∈B∨x∈C)]$

that is different from your formula, because - in general - $∀$ does not distribute over $∨$.

---

Note: the above example is a perfect counter-example to show that $\forall$ does not distribute over $\lor$.

$A \subseteq B \cup C$ means that every $x$ that belongs to $A$ will belong either to $B$ or to $C$.

But this does not imply that: either all elements of $A$ belong to $B$ or all elements of $A$ belong to $C$.

Answer 2

In propositional calculus $$ P\Rightarrow (Q\lor R) \quad\stackrel{*}{\large\color{green}{\boldsymbol\equiv}}\quad ((P\Rightarrow Q)\lor (P\Rightarrow R)). $$

But $$ A\subseteq B \:\:\mathrm{or}\:\: A\subseteq C \quad\kern.9em\not\kern-.9em\iff\quad A\subseteq B\cup C.$$

Indeed, \begin{align}& A\subseteq B \:\:\mathrm{or}\:\: A\subseteq C \\\iff{}& \forall x\; (x\in A ⇒ x\in B) \;\lor\; \forall y\;(y\in A ⇒ y\in C) \\\large{\models}\quad{}& \forall z\; \Big((z\in A ⇒ z\in B) \;\lor\; (z\in A ⇒ z\in C)\Big) \\{\stackrel{*}{\large\color{green}{\boldsymbol\equiv}}}\quad{}& \forall z\; \big(z\in A ⇒ z\in B \,\lor\, z\in C \big) \\\iff{}& \forall z\; \big(z\in A ⇒ z\in B \cup C \big) \\\iff{}& A\subseteq B\cup C,\end{align} but \begin{align}& A\subseteq B\cup C \\\iff{}& \forall z\; \big(z\in A ⇒ z\in B \cup C \big) \\\iff{}& \forall z\; \big(z\in A ⇒ z\in B \,\lor\, z\in C \big) \\{\stackrel{*}{\large\color{green}{\boldsymbol\equiv}}}\quad{}& \forall z\; \Big((z\in A ⇒ z\in B) \;\lor\; (z\in A ⇒ z\in C)\Big) \\\color{red}{\kern.6em\not\kern-.6em\implies}\,{}& \forall x\; (x\in A ⇒ x\in B) \;\lor\; \forall y\;(y\in A ⇒ y\in C) \\\iff{}& A\subseteq B \:\:\mathrm{or}\:\: A\subseteq C.\end{align}

In particular, notice that while $$\forall z\; \big(z\in A ⇒ z\in B\big) \;\lor\; \forall z\;\big(z\in A ⇒ z\in C\big)$$ logically entails $$\forall z\; \Big(\big(z\in A ⇒ z\in B\big) \;\lor\; \big(z\in A ⇒ z\in C\big)\Big),$$ the converse entailment holds neither logically (regardless of interpretation) nor under the axioms of set theory.