Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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 4

up vote 4 down vote accepted

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

share|improve this answer
    
"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? –  Stavros 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? –  Stavros 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.

share|improve this answer

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?

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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