Is the axiom of choice really related to choice?

Does the standard proof that the power set of a set is strictly larger than the set rely on the axiom of choice?

• Here's the proof: First, we note that there's a one-to-one function from SSS to 2S2S2^S given by x↦{x}x↦{x}x \mapsto \{x\}. Now we assume that there's a bijection Ï•Ï•\phi between SSS and 2S2S2^S.  Then there is some x∈Sx∈Sx \in S such that Ï•(x)={x:x∉ϕ(x)}Ï•(x)={x:x∉ϕ(x)}\phi(x) = \{x : x \notin \phi(x)\}.  By the same reasoning as in Russell's paradox, x∈ϕ(x)x∈ϕ(x)x \in \phi(x) if and only if x∉ϕ(x)x∉ϕ(x)x \notin \phi(x), so there can be no such bijection Ï•Ï•\phi. Since there's a one-to-one function from SSS to 2S2S2^S and no one-to-one function the other way, we conclude that |S|<∣∣2S∣∣|S|<|2S||S| I've heard at least a couple people claim that this argument relies on the axiom of choice, but I don't see it.  Are they right?

• Answer:

  No, this proof does not require the Axiom of Choice (AC). But it's very difficult to work with cardinalities without AC. For example, it's very intuitive and very useful to say that for any two sets A and B, exactly one of the following holds: |A|=|B|,|A|<|B|,|A|>|B|.|A|=|B|,|A|<|B|,|A|>|B|.|A|=|B|, |A||B|. But this, the principle of trichotomy, is equivalent to AC! Many proofs implicitly use this (but the specific proof you gave above doesn't rely on this).