# I shouldn't be able to prove the power-set of union is equal to union of power-sets.

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.

-

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.

-
Thanks. The absence of quantifier can be explained by the fact that this problem emerged in the context of Hamos' Naive Set Theory, which makes no use of quantifier and very little of first order logic. It was asked to prove that $P(A) \cup P(B) \subset P(A \cup B)$, and I decided to test the converse, which we aren't asked to do. – TheCoconutChef Dec 30 '12 at 3:07
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? – Henning Makholm Dec 30 '12 at 9:55

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

-

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

-
And yet "$P\to (Q\lor R)$" is tautologically equivalent to "$(P\to Q)\lor(P\to R)$". It only becomes a fallacy when there's a (here, implied) quantifier breaking up the formulas. – Henning Makholm Dec 30 '12 at 0:08
Hmm, I never considered how that quantifier changes things. You're absolutely correct! – Zev Chonoles Dec 30 '12 at 0:16

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

-