$A \subseteq B \cup C$ $\rightarrow$ $x \in B$ or $x \in C$.

Question

This is one of the problem I have been working from Velleman's How to Prove it book:

Theorem: Suppose $A$, $B$, and $C$ are sets and $A \subseteq B \cup C$. Then either $A \subseteq B$ or $A \subseteq C$. Is the theorem correct?

Proof. Let $x$ be an arbitrary element of $A$. Since $A \subseteq B \cup C$, it follows that either $x \in B$ or $x \in C$.

Case $1.$ $x \in B$. Since $x$ was an arbitrary element of $A$, it follows that $\forall x \in A(x \in B)$, which means that $A \subseteq B$.

Case $2.$ $x \in C$. Similarly, since $x$ was an arbitrary element of $A$, we can conclude that $A \subseteq C$. Thus, either $A \subseteq B$ or $A \subseteq C$.

After reading the proof, I was pretty much convinced that everything is fine unless I saw the answer where they give the counterexample of this theorem. Now even seeing the counterexample, when I read this proof I'm not able to find any errors in it ? Can somebody point me out in the right direction ?

Answer 1

It is correct to deduce that, for an arbitrary element $x$ of $A$, since $A ⊆ B \cup C$, it follows that either $x \in B$ or $x \in C$.

But we can have $x_1 \in A$ such that $x_1 \in B$ and $x_2 \in A$ such that $x_2 \in C$, and both $x_1, x_2 \in B \cup C$.

The wrong step is to conclude from $x \in B$, since $x$ was an arbitrary element of $A$, that $∀x (x \in A \rightarrow x ∈ B)$.

The fallacious step is clear if we "formalize" the proof:

1) $\forall x [(x \in A) \rightarrow (x \in B \lor x \in C)]$ --- premise : it is the definition of : $A ⊆ B \cup C$

2) $(x \in A) \rightarrow (x \in B \lor x \in C)$ --- from 2) by $\forall$-elimination

3) $x \in A$ --- assumption

4) $x \in B \lor x \in C$ --- from 2) and 3) by $\rightarrow$-elimination (modus ponens)

5) $x \in B$ --- assumed for $\lor$-elimination

6) $x \in A \rightarrow x \in B$ --- from 3) and 5) by $\rightarrow$-introduction

7) $\forall x(x \in A \rightarrow x \in B)$ --- from 7) by $\forall$-introduction [wrong !], that is the definition of : $A \subseteq B$.

The last step is wrong because there is still an assumption left (the n°5) with $x$ free.

Answer 2

$A \subseteq B \cup C$, so $x\in B$ or $x\in C$ for all $x\in A$, but there is no reason to think, that ALL $x\in A$ are in $B$ or ALL are in $C$. Some might be in $B$, others in $C$.

Specifically: $$\forall x\in A : x\in B \text{ or }x\in C$$ does not imply: $$\forall x \in A : x\in B\text{ or } \forall x \in A : x\in C$$ (but the other direction works)