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

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 ?

• Let $B$ and $C$ be disjoint, and set $A=B\cup C$ for a counterexample. For the fault in the proof: which of the cases that hold (1 or 2) might not be the same for all points in $A$. It's true that you have an arbitrary $x$, but it stops being completely arbitrary once you assume one of the cases. Dec 24, 2014 at 19:28
• @Arthur I'm already convinced about the counterexample as stated in the question. What i'm not able to do is find a flaw in the proof.
– Sibi
Dec 24, 2014 at 19:31

$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)

• Is A for both sides of the expression intentional ?
– Sibi
Dec 24, 2014 at 19:53
• No, thank you! I fixed it. Dec 24, 2014 at 19:58

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.

• How x is not a free variable in assumption 4 ?
– Sibi
Dec 24, 2014 at 19:47
• @Sibi - step 6) [previous 4] is not an assumption; in any case, in it $x$ is bounded by the $\forall$ quantifier. Dec 24, 2014 at 20:06
• Thinking more about this, it seems hard for me to convince myself why Step 6 is wrong (even though I agree with you). I have seen proofs in the book in which if $A \subseteq B \cap C$, then they are introducing $\forall$ in that step without any problem. I understand why it works in that case but doing the same here isn't working. Any tips on how to deal with these situations ?
– Sibi
Dec 24, 2014 at 22:53
• @Sibi - step 6) is wrong because we cannot "generalize" a free variable used in an assumption (step 5) exactly because you get inconsistent results. The above proof amount to : pick an $x$ whatever in $A$; it is in $B$ or $C$. Pick the $x$ in $B$ ... this is no more an $x$ "whatever"; it is an $x \in A$ that belongs to $B$. Thus we cannot "generalize" on it, concluding that what we have found holds for all $x \in A$, because it is not true, i.e. it is not true that, for all $x \in A$, $x \in B$ ... Dec 25, 2014 at 8:20
• Thanks for your patience. Let me give you an another example in which we have to prove this theorem: Suppose $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$. For the proof of this theorem we can accept that $x$ is an arbitrary element in $A$ and then show that $x \in C$ and finally conclude that $\forall x \in A(x \in c)$. So, my question was we are able to generalize $x$ here but in the above case.
– Sibi
Dec 25, 2014 at 8:54