If $A\subseteq B\cup C$ then $A\subseteq B$ or $A\subseteq C$.

Question

The question is to prove or disprove

If $A\subseteq B\cup C$ then $A\subseteq B$ or $A\subseteq C$.

I know that this is wrong and can easily be disproved with an example, but I tried to prove it and I actually came up with proof that I know is wrong but I don't know why it's wrong, I started by converting it to this: $$x\in A\implies x\in B\cup C$$ $$x\notin A\lor x\in B\lor x\in C$$ $$(P\lor P\equiv A,A\lor B\equiv B\lor A)\text{ so}$$ $$x\notin A\lor x\in B\lor x\notin A\lor x\in C$$ $$(x\in A\implies x\in B)\lor(x\in A\implies x\in C)$$ $$A\subseteq B\lor A\subseteq C$$ and I want to know why this proof is wrong and where exactly is my mistake.

Answer 1

Everything down to your fifth line is essentially correct (modulo the typo in line 4).

However, you're missing quantifiers. $A \subseteq B \cup C$ is not equivalent to $x \in A \implies x \in B \cup C$: the latter has an unbound $x$ in it, whereas the former doesn't. It is instead equivalent to $\forall x (x \in A \implies x \in B \cup C)$. Continuing that through to the end, we get, in line five, $\forall x ((x \in A \implies x \in B) \vee (x \in A \implies x \in C))$. That is not the same as $(\forall x (x \in A \implies x \in B)) \vee (\forall x (x \in A \implies x \in C)),$ which is what is equivalent to $A \subseteq B$ or $A \subseteq C$.

And, indeed, the result is false: let $B$ and $C$ be such that neither $B \subseteq C$ nor $C \subseteq B$. Then with $A := B \cup C$, we obviously have $A \subseteq B \cup C$, but we cannot have $A \subseteq B$ (else we'd have $C \subseteq B$) or $A \subseteq C$ (else $B \subseteq C$).

Answer 2

Line 4 contains a typo ($B$ should be $C$). Your mistake is that you neglect quantifiers. Essentially, your mistake is that you used

$$\forall x: (P(x) \lor Q(x))\implies (\forall x: P(x)) \lor (\forall x: Q(x))$$

But this is definitely not true.