3
$\begingroup$

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 ?

$\endgroup$
2
  • $\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, 2014 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, 2014 at 19:31

2 Answers 2

3
$\begingroup$

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

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

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.

$\endgroup$
8
  • $\begingroup$ How x is not a free variable in assumption 4 ? $\endgroup$
    – Sibi
    Dec 24, 2014 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$ Dec 24, 2014 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, 2014 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$ Dec 25, 2014 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, 2014 at 8:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .