Where is this power set proof wrong if I can find a counterexample?

84 Views Asked by At

Suppose I want to prove (or disprove):

$$\newcommand{\powerset}[1]{\mathcal P(#1)} \powerset{A - B} \subseteq \powerset{A} - \powerset{B}$$

I came up with:

Assume $X \in \powerset{A - B}$. Then it follows that $X \subseteq A - B$, which, by definition, means that $X \subseteq A$ but $X \not\subseteq B$. Thus, $X \in \powerset{A}$ and $X \not\in \powerset{B}$, giving us $X \in \powerset{A} - \powerset{B}$ proving the statement.

But this proof is invalid because I can find a counterexample to the original statement. Suppose $A = \{1,2\}, B = \{2\}$, which means we want to get $\powerset{\{1\}} \subseteq \powerset{\{1,2\}} - \powerset{\{2\}}$. But this is false:

$$\powerset{\{1\}} = \{\emptyset, \{1\}\}$$ $$\powerset{\{1,2\}} - \powerset{\{2\}} = \{\emptyset, \{1\}, \{2\}, \{1,2\}\} - \{\emptyset, \{2\}\} = \{\{1\}, \{1,2\}\}$$

And:

$$\{\emptyset, \{1\}\} \not\subseteq \{\{1\}, \{1,2\}\}$$

Since this counterexample involved the empty set, does this have to do with $X \not\subseteq B$ not necessarily being true just because $X \subseteq A - B$ is true?

1

There are 1 best solutions below

0
On

Then it follows that $X \subseteq A - B$, which, by definition, means that $X \subseteq A$ but $X \not\subseteq B$.

This is not "by definition" at all! The definition of $A-B$ is that $x\in A-B$ means that $x\in A$ and $x\not\in B$. You cannot just replace $\in$ with $\subseteq$ because they are different relations.