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 ?

  • $\begingroup$ 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. $\endgroup$ – Arthur Dec 24 '14 at 19:28
  • $\begingroup$ @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. $\endgroup$ – 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.

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

  • $\begingroup$ Is A for both sides of the expression intentional ? $\endgroup$ – Sibi Dec 24 '14 at 19:53
  • $\begingroup$ No, thank you! I fixed it. $\endgroup$ – Stefan Perko Dec 24 '14 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.