5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – J. W. Tanner Sep 4 '19 at 22:49
  • 1
    $\begingroup$ A simple countra example is disjoint A and B. $\endgroup$ – William Elliot Sep 4 '19 at 23:07
  • $\begingroup$ 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. $\endgroup$ – Ted Shifrin Sep 4 '19 at 23:18
  • 1
    $\begingroup$ "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. $\endgroup$ – fleablood Sep 4 '19 at 23:22
  • $\begingroup$ You got the formula right $\endgroup$ – Shaun Sep 4 '19 at 23:47
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – J. W. Tanner Sep 4 '19 at 23:30
7
$\begingroup$

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:

enter image description here

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.