4

I've been trying to challenge myself but with no luck. Maybe one of you will have a better idea. How can it be proven that there can't be a set which contains its own powerset, using only russell's paradox? I've managed to prove it with other principles or axioms, such as that a set can not belong to itself, or that a powerset cannot belong to itself.

Discreter1203
  • 109

3 Answers3

6

It is more complicated than necessary.

Let $A$ be a set with $P(A)\subseteq A$. Then, let $B = \{ S \in A \mid S\notin S \}$. That is in fact a set by axiom schema of specification.

Now, notice that from $B \subseteq A$ follows $B\in P(A) \subseteq A$. If $B\in B$, then we have $B\notin B$. If $B\notin B$, then we have $B\in B$. Just like in the Russell's Paradox.

Note:

For sake of completeness, here is the contradiction to regularity: $$ A\in P(A) \subseteq A. $$

user251257
  • 9,229
  • 5
    For further completeness, I note that this critically depends on the comprehension scheme available. There are theories whose axioms don't guarantee the existence of ${S\in A|S\notin S}$ and similar sets, in which you can end up with $\mathcal{P}(A)=A$. – Malice Vidrine Nov 24 '16 at 21:01
  • @Abdel. I think the OP asks whether we can prove that if $P(X)$ exists then $P(X)\not \in X$ without any set-theory axioms, just as Russell's Paradox is proved : $[;\exists X;\forall Y ;(Y\in X\iff Y\not \in Y)) ;]\implies \exists X;(X\in X\land X \not \in X)$ without any additional assumptions. – DanielWainfleet Nov 24 '16 at 21:17
  • I don't see how this proves anything about power sets. You can conclude that $B\notin A$ from the above construction, but not much else. Can't comment on the bit about regularity. – Dan Christensen Nov 29 '16 at 05:34
  • 1
    @DanChristensen I don't see the problem. By definition, $B\subseteq A$. Assuming $P(A)\subseteq A$, we have that $B\in P(A)$, so $B\in A$. But then (by definition of $B$, using the fact that $B\in A$) we have $B\in B$ iff $B\not\in B$. This is a contradiction, so our assumption that $P(A)\subseteq A$ must be false. So this seems completely right to me. Or am I missing something? – Noah Schweber Nov 29 '16 at 06:04
  • 2
    To add to Malice Vidrine's comment, the theory New Foundations (NF) is one theory in which $P(A)\subseteq A$ can happen. – Noah Schweber Nov 29 '16 at 06:05
  • @NoahSchweber Thanks for clearing that up somewhat, but I think you left out some key points. – Dan Christensen Nov 29 '16 at 17:10
  • @DanChristensen Such as what? I don't see where I left anything out. – Noah Schweber Nov 29 '16 at 17:18
  • @NoahSchweber The contradiction $B\in A$ and $B\notin A$. – Dan Christensen Nov 29 '16 at 17:21
  • @DanChristensen That's not how the argument needs to go. In my comment, and in the answer, we get $B\in A$ since $B\subseteq A$, and then directly conclude a la Russell that $B\in B\iff B\not\in B$. This is completely airtight; I don't understand your objection. – Noah Schweber Nov 29 '16 at 17:23
  • 1
    @DanChristensen that isn't true. – user251257 Nov 29 '16 at 17:23
  • @NoahSchweber Perhaps I missed some subtlety in your argument, but the contradiction $B\in B \iff B \notin B$ only gets you $B\notin A$. – Dan Christensen Nov 29 '16 at 17:32
  • @NoahSchweber You need to obtain a second contradiction, $B\in A$ and $B\notin A$, to obtain the final result. Maybe I am being too picky, but such a key point should probably be made more explicit. – Dan Christensen Nov 29 '16 at 17:59
  • 1
    @DanChristensen No, that's not correct. We assume $P(A)\subseteq A$ for contradiction. We then prove $B\in A$, and from that prove that $B\in B\iff B\not\in B$; this means our assumption, $P(A)\subseteq A$, was false. There's no need to do anything else; this is just straight proof by contradiction. – Noah Schweber Nov 29 '16 at 19:13
  • @NoahSchweber For what it is worth, here is my machine-verified formal proof at http://www.dcproof.com/PowerSetNotSubset.htm . Note the two contradictions on lines 25 and 42. Enjoy! – Dan Christensen Nov 29 '16 at 22:22
  • @DanChristensen I'm not saying you can't do two contradictions, I'm saying you don't need to. Do you understand that? – Noah Schweber Nov 29 '16 at 22:24
  • @NoahSchweber I understand what you mean, but I'm not convinced. – Dan Christensen Nov 29 '16 at 22:27
  • @DanChristensen What step of the proof that's been given do you doubt? Assume for contradiction that $P(A)\subseteq A$. Let $B={a\in A: a\not\in a}$. By definition, $B\subseteq A$, so - by our assumption for contradiction - $B\in A$. But then (since by definition of $B$, for all $x\in A$ we have $x\in B\iff x\not\in x$) we have $B\in B\iff B\not\in B$; contradiction, so our assumption was incorrect - that is, $P(A)\not\subseteq A$. Exactly what part of this isn't clear? – Noah Schweber Nov 29 '16 at 22:28
  • 1
    @DanChristensen Seriously? Wow. OK, I'm done here. Let me know if you have an actual objection. – Noah Schweber Nov 29 '16 at 22:44
  • @NoahSchweber How about this: In your second to last sentence, I think you have identified incorrect assumption to be negated. Maybe you got confused by the set-builder notation in your definition of $B$. I use $\forall x:[ x\in B \iff x \in A \land x\notin x$]. You can only get $B\in B\iff B\notin B$ by first assuming that $B\in A$. That is the assumption you should be negating at that point. – Dan Christensen Nov 29 '16 at 23:26
  • 2
    @DanChristensen "$B\in A$" doesn't need to be separately assumed: it follows immediately from the fact that $B\subseteq A$ (by definition), together with the assumption that $P(A)\subseteq A$. I'm not getting confused by set-builder notation. – Noah Schweber Nov 29 '16 at 23:29
  • @NoahSchweber Right you are. Thank you for your patience. – Dan Christensen Nov 30 '16 at 00:11
1

By definition a power set is generated by subsets of the given set. So you can make a cardinality argument.

  • 1
    This doesn't really answer the question, which specifies that they're looking for an answer using (the reasoning behind) Russell's paradox. – Noah Schweber Nov 29 '16 at 06:03
1

(EDIT: Borrowing from Noah)

Suppose to the contrary that for set $A$, we have $P(A)\subset A$.

Now, by an axiom of set theory, there exists a subset $B\subset A$ such that $\forall a:[a\in B\iff a\in A \land a\notin a]$.

Since $B\subset A$ and $P(a) \subset A$, we must have $B\in A$.

Along the lines of RP, we obtain the contradiction $B\in B\iff B\notin B$, thus negating our initial assumption.

See my machine-verified formal proof (updated).

Perhaps more intuitively satisfying (without $a\notin a$ and such) would be:

If $X \subset Y$ then there exists the obvious injection $f:X \to Y$, i.e. $f(x)=x$. And, for any set $S$, there cannot exist an injection $f :P(S)\to S$. So, we cannot have $P(S)\subset S$.

Masacroso
  • 30,417
Dan Christensen
  • 14,529