$A\subset (B\cup C)$ $\implies$ $A\subset B $ or $A\subset C$

Question

Clearly, it is not true that $A\subset (B\cup C)$ implies $A\subset B $ or $A\subset C$, since if $A=\{b,c\}, B=\{a,b\}, \text{ and }C=\{c,d\}$, then $A\subset B\cup C =\{a,b,c,d\}$ but $A\not\subset B$ and $A\not\subset C.$

However, if one tries to prove the above statement, where does the proof go wrong?

Proof:

Let $x\in A$. Since $A\subset B\cup C, x\in A\implies x\in B\cup C\implies x\in B$ or $x\in C. $ Since $x\in A\implies x\in B$ or $x\in C$ is equivalent to $x\in A\implies x\in B$ or $x\in A\implies x\in C$, this shows $A\subset B$ or $A\subset C. \blacksquare$

Answer 1

In propositional calculus, $P\implies (Q\lor R)$ may imply $(P\implies Q)\lor (P\implies R),$ but the statement you have is of the form:

$$\forall x: \left(P(x)\implies (Q(x)\lor R(x))\right)\tag1$$

You cannot change this to: $$\left(\forall x: P(x)\implies Q(x)\right)\lor \left(\forall x: P(x)\implies R(x)\right)$$

You can say: $$\forall x:( P(x)\implies Q(x))\lor (P(x)\implies R(x))$$

but you can’t conclude (1) from this.

The thing about propositional calculus is that it is about one statement at a time. $P\implies Q$ is not what we intuitively think of as an implication. You can’t say, “If it rains, the ground will be wet.” You can say, “If it rained yesterday at this spot, the ground was wet at this spot.”

You can’t express rules in propositional calculus.

It is best to treat $P\implies Q$ as $\lnot P\lor Q,$ because of this, at least until you get used to this. it is definitely confusing.

Answer 2

That is true for that $x$ but it is not true for all $x$.

Answer 3

Note that what you have proved is $$\forall x(x\in A\implies(x\in B\lor x\in C)),$$ where as what you have to prove to show $A\subset B$ or $A\subset C$ is $$(\forall x(x\in A\implies x\in B))\lor(\forall x(x\in A\implies x\in C)).$$

The lesson is, be careful where the quantifiers ($\forall$ and $\exists$) are! Wrong placements can and do change meaning.