Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer

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

share|cite|improve this answer
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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.