# A ⊆ B ∪ C -> x ∈ B or x ∈ 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 ⊆ B ∪ C. Then either A ⊆ B or A ⊆ C. Is the theorem correct?

Proof. Let x be an arbitrary element of A. Since A ⊆ B ∪ C, it follows that either x ∈ B or x ∈ C.

Case 1. x ∈ B. Since x was an arbitrary element of A, it follows that ∀x ∈ A(x ∈ B), which means that A ⊆ B.

Case 2. x ∈ C. Similarly, since x was an arbitrary element of A, we can conclude that A ⊆ C. Thus, either A ⊆ B or A ⊆ 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. – Arthur Dec 24 '14 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 '14 at 19:31

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 '14 at 19:47
• @Sibi - step 6) [previous 4] is not an assumption; in any case, in it $x$ is bounded by the $\forall$ quantifier. – Mauro ALLEGRANZA Dec 24 '14 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 '14 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$ ... – Mauro ALLEGRANZA Dec 25 '14 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 '14 at 8:54

$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 '14 at 19:53
• No, thank you! I fixed it. – Stefan Perko Dec 24 '14 at 19:58