4
$\begingroup$

And yet here I am, "proving" the impossible!

My reasoning is as follow:

$X \in P(A \cup B) \iff X \subset A \cup B \iff x \in X \to x \in A \cup B \iff x\in X \to x \in A \vee x \in B \iff (x \in X \to x \in A) \vee (x \in X \to x \in B) \iff X \subset A \vee X \subset B \iff X \in P(A) \vee X \in P(B) \iff X\in P(A) \cup P(B)$

I know that this breaks down at least as soon as $ (x \in X \to x \in A) \vee (x \in X \to x \in B)$ but since $P \to Q \vee R \iff (P \to Q) \vee (P \to R)$, I don't know how to avoid it.

Hints or answer would welcomed.

4 Answers 4

8

The $x$ that enters in the first line must be quantified somehow. If you write the quantifiers explicitly, you'll find a point where you implicitly reinterpret $\forall x.(\phi(x)\lor \psi(x))$ to $(\forall x.\phi(x))\lor(\forall x.\psi(x))$. That is unsound.

  • 1
    Seems there's a limit to how naive one can be without inviting error. Who'd have thought explicit quantifiers had a use beyond looking profound and keeping students in their place?2012-12-30
7

The false step is

$x\in X\to(x\in A\lor x\in B)\iff(x\in X\to x\in A)\lor(x\in X\to x\in B)\;:$

the lefthand side says that $X\subseteq A\cup B$; the righthand side, on the other hand, says that $X\subseteq A$ or $X\subseteq B$ (or both). The latter is clearly a stronger statement than the former: if $A=\{0\},B=\{1\}$, and $X=\{0,1\}$, the lefthand side is true, but the righthand side is not.

It’s easy to make this kind of mistake when you omit quantifiers. Every statement in your argument really ought to be preceded by $\forall x$; $\forall x\big(x\in X\to(x\in A\lor x\in B)\big)\;,$ for instance, or simply $\forall x\in X(x\in A\lor x\in B)\;.$ This has the form $\forall x\in X\big(\varphi(x)\lor\psi(x)\big)$: every $x\in X$ has at least one of the properties $\varphi$ and $\psi$. Your righthand side, on the other hand, has the form $\forall x\in X\big(\varphi(x)\big)\lor\forall x\in X\big(\psi(x)\big)$: either every $x\in X$ has the property $\varphi$, or every $x\in X$ has the property $\psi$. This no longer allows the possibility that some $x\in X$ have $\varphi$ but not $\psi$, while the rest have $\psi$ but not $\varphi$.

3

The problem is at the step $(x\in X\to x\in A \vee x\in B )\iff (x\in X\to x\in A)\vee (x\in X\to x\in B)$ If $P(x)$ implies ($Q(x)$ or $R(x)$) for all $x$, it does not mean that it must either be the case that $P(x)$ implies $Q(x)$ for all $x$, or that $P(x)$ implies $R(x)$ for all $x$. For example, consider $P(x)=$ "$x$ is an integer", $Q(x)=$ "$x$ is an even integer ", and $R(x)=$ "$x$ is an odd integer".

  • 0
    Hmm, I never considered how that quantifier changes things. You're absolutely correct!2012-12-30
1

Try instantiating it through a counterexample.

Take $A=\{0\}$ and $B=\{1\}$, and take $X=\{0,1\}\in\mathcal P(A\cup B)$. You see that indeed $x\in X\rightarrow x\in A\lor x\in B$, but this need not imply that $(x\in X\rightarrow x\in A)\lor(x\in X\rightarrow x\in B)$.