# Why is this proof invalid?

I don't understand why this theorem is false.

Suppose that $$A \subseteq C$$, $$B \subseteq C$$, and $$x \in A$$. Then $$x \in B$$.

Invalid Proof:

Suppose that $$x \notin B$$. Since $$x \in A$$ and $$A \subseteq C$$, $$x \in C$$. Since $$x \notin B$$ and $$B \subset C$$, $$x \notin C$$. But now we have proven both $$x \in C$$ and $$x \notin C$$, so we have reached a contradiction. Therefore $$x \in B$$.

I'm thinking that $$\forall x(x \in B \implies x \in C) = \forall x(x \notin B \vee x \in C)$$

It's true that $$x \notin B$$, so this statement is true, and can't be used to prove through contradiction that $$x \in B$$. But I'm not completely sure, so any clarification would help here. Thanks.

• Welcome to Mathematics Stack Exchange. Here is a MathJax tutorial. $x\not\in B$ and $B\subseteq C$ does not imply $x\not\in C$ – J. W. Tanner Sep 4 '19 at 22:49
• A simple countra example is disjoint A and B. – William Elliot Sep 4 '19 at 23:07
• Try $C$ the set of all integers, $A$ the set of even integers, and $B$ the set of odd integers. Always try to play with concrete examples. Sometimes pictures (like Venn diagrams, in this situation) are instructive. – Ted Shifrin Sep 4 '19 at 23:18
• "Since $x \not \in B$ and $B\subset C$, $x \not \in C$". This is not valid. $B\subset C$ so all the elements in $B$ are in $C$ but not all the elements in $C$ are in $B$. ANd if an element is not in $B$ there is utterly no reason it can't be one of the elements in $C$ that aren't in $B$. Consider: Penguins $\subset$ Birds. Now Daffy Duck $\not \in$ Penguins. And Penguins $\subset$ Birds. So you are claiming that therefore Daffy Duck $\not \in$ Birds. But Daffy Duck could be (and is) a bird that is not a penguin. – fleablood Sep 4 '19 at 23:22
• You got the formula right – Shaun Sep 4 '19 at 23:47

"since $$x \notin$$ B and $$B \subseteq C, x \notin C$$" That's the mistake. that implication is wrong. Remember the definition of subsets. If $$B \subseteq C$$, this means that for all elements in $$B$$, they are also in $$C$$. Or with symbols $$x \in B \rightarrow x\in C$$. this statement says nothing about $$x$$ not being in $$B$$, so if an element is not in $$B$$, you can't deduce anything. that's why that implication is wrong. Look, here's a simple example. Let $$C = \{w, x, y, z\}$$ and $$B = \{x, y\}$$, so $$B$$ is a subset of $$C$$. The element $$z$$ is not in $$B$$ but it is in $$C$$.

• It might be easier to understand this if in the example at the end you use $C$ rather than $A$ and also use different letters for the set elements – J. W. Tanner Sep 4 '19 at 23:30

Since $$x \not\in B$$ and $$B \subseteq C$$, $$x \not\in C$$.

Actually, if $$x \not\in B$$ and $$B \subseteq \color{blue}{C}$$, both $$\color{red}{x \in C}$$ and $$\color{magenta}{x \not\in C}$$ are possible. In a picture: Here's a counter model . . .

Let $$A=\{1\}, B=\{2\}, C=\{1,2\}$$. Then $$A\subseteq C$$ and $$B\subseteq C$$ with $$1\in A$$ but $$1\notin B$$.

Consider:

$$C= \{1,2,3,4,5,6,7,8,9,10,11,12\}$$, all the integers up to $$12$$.

And $$A = \{2,4,6,8,10,12\}$$, all the even numbers up to $$12$$.

And $$B = \{1,4,9\}$$, all the perfect squares up to $$12$$.

We note that $$A\subset C$$ and $$B\subset C$$.

That theorem says that if $$x\in A$$ then $$x \in B$$.

This is clearly not true. We have $$2,6,8,10,12$$ all in $$A$$ yet none of them is in $$B$$.

Let's assume $$x \in A$$. So $$x = 2,4,6,8,10,$$ or $$12$$.

Let's go to the proof.

Suppose $$x \not \in B$$

(okay, so $$x \ne 1,4,9$$ in particular $$x \ne 4$$ but $$x$$ could be $$2,6,8,10,12$$ still.)

Since $$x \in A$$ and $$A \subset C$$, $$x \in C$$.

(This follows. If $$x=2,6,8,10$$ or $$12$$ we do have $$x \in C$$.)

Since $$x \not \in B$$ and $$B\subset C$$ then $$x \not \in C$$.

Does that actually make sense? $$x\ne 1,4,9$$ and $$1,4,9\in C$$ but there are other things in $$C$$ as well other than those. We could have $$x=2,6,8,10$$ or $$12$$.

There is a concept of $$C\setminus B = \{x\in C$$ but where $$x \not \in B\}$$. As we know that $$x\not \in B$$ that if $$x\in C$$ then we must have $$x\in C\setminus B$$. But $$C\setminus B$$ certainly doesn't have to be empty!

So that doesn't follow at all!

But now we have proven both $$x ∈ C$$ and $$x \not \in C$$.so we have reached a contradiction. Therefore $$x ∈ B$$.

Except we haven't proven $$x \not \in C$$. We have reached no contradiction. And $$x$$ need not be in $$B$$. $$x\in C$$ so $$x$$ could be in $$C \cap B$$ or $$x$$ could be in $$C\setminus B$$. But we have no way of telling.