# An incorrect proof by exhaustion

Consider the following putative theorem.

Theorem? Suppose A, B, and C are sets and $A \subseteq B \cup C$. Then either $A \subseteq B$ or $A \subseteq C$.

What's wrong with the following proof?

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

I have proved that the theorem is incorrect but I can't understand why the above proof is not correct.

-
As I stated below, the error is "Since $x$ was an arbitrary element of $A$". It was not; $x \in B$, which is not generally true of elements in $A$. – Eric Tressler Jul 31 '13 at 2:00

## 4 Answers

When you choose cases, you lose the supposition that $x$ is arbitrary. In the first case, $x \in B$ and in the second, $x \in C$. In those respects, $x$ is not an arbitrary member of $A$.

-
"When you choose cases, you lose the supposition that x is arbitrary." Now consider the statement $\forall x \in R \exists y \in R(xy^2 \neq y - x)$. To prove it, I assume that x is an arbitrary real number. Then I consider the following cases: Case 1. $x = 0$, Case 2. $x \neq 0$. Do I restrict what my x can be in this particular case? – user21530 Jul 31 '13 at 2:17
Yes. In case 1, your $x$ cannot be nonzero, and in case 2, your $x$ cannot be zero. If you wrote "Case 1. $x = 0$. Since $x$ is arbitrary, all $x \in \mathbb{R}$ are zero", you would be committing the same mistake as in the original post. In the context of case 1, $x$ is not arbitrary; $x$ is zero. – Eric Tressler Jul 31 '13 at 2:50
In both cases I prove that $\exists y \in R(xy^2 \neq y - x)$. Then I say that since was arbitrary, $\forall x \in R \exists y \in R(xy^2 \neq y - x)$. Is that all right? – user21530 Jul 31 '13 at 10:24
@Stavros Yes, it is. If in each case, you make the same conclusion, $P(x)$ then there is no problem in concluding $\forall x\,P(x)$ (assuming that your cases are exhaustive). – Alraxite Jul 31 '13 at 12:18

It is true that for each element of $A$ you are in case 1 or case 2. But for some elements of $A$ you can be in case 1 while for others you are in case 2.

-

The error is when you switch to your cases. You start with

$$\forall x \in A:\ x \in B \text{ or } x \in C$$

and then go to cases where you act as if the above said

$$(\forall x:\ x \in B) \text{ or } (\forall x:\ x \in C).$$

See the problem?

-

If $x$ satisfies $P(x)$, then you can conclude that $\forall x\, P(x)$ is true if your $x$ was truly arbitrary, i.e. you did not make any assumptions of what your $x$ was. When considering cases, you restrict what your $x$ can be and hence the conclusion that it is true for all $x$ is false.

-