Set Theory Jottings 19. GCH implies AC.

Prev TOC Next

Sierpiński’s Theorem: GCH implies AC

I had a look at the version of the proof in Cohen (§IV.12). Sierpiński was a clever fellow, and he came up with a few tricks that would be hard to motivate.

Here I will try to imagine how Sierpiński could have devised his proof. Cohen does offer one bit of intuition:

The GCH is a rather strong assertion about the existence of various maps since if we are ever given that A≤B≤P(A) then there must be a 1–1 map either from B onto A or from B onto P(A). Essentially this means that there are so many maps available that we can well-order every set.

Let A be the set we wish to well-order. Let’s write A≤B to mean there is an injection from A into B. GCH tells us that for any U,

A≤U≤P(A) implies U≡A or U≡𝒫(A)

If U is well-ordered, then U≡A and U≡𝒫(A) both imply that A can be well-ordered, the latter because A is naturally imbedded in 𝒫(A). But this is too simple an approach: A≤U already makes A well-ordered for a well-ordered U, so if we could show the antecedent we’d be done—we wouldn’t need GCH to finish the job.

Let’s not assume U is well-ordered, but instead suppose it contains a well-ordered set. Say we could show that

A≤W+A≤𝒫(A)

for a well-ordered set W, where ‘+’ stands for disjoint union. (That is, W×{0}∪A×{1}, or some similar trick to insure disjointness.) Then we’d have

W+A≡𝒫(A) or W+A≡A

Now, if W+A≡𝒫(A), then we ought to have W≡𝒫(A), just because A is “smaller” than 𝒫(A) (in some sense)—W should just absorb A, if W is “big enough”. Also, if W is “big enough” then that should exclude the other arm of the choice, where W+A≡A. And if W≡𝒫(A), then 𝒫(A) and so also A can be well-ordered, as we have seen.

At this point Hartog’s theorem shows up at the door. This gives us a well-ordered set W with

W≤𝒫⁴(A) and W≰A

So we have

A≤W+A ≤𝒫⁴(A)+A ?≡? 𝒫⁴(A)

(where ?≡? means that the equivalence needs to be proven). W≰A excludes W+A≡A, good. Let’s postpone the issue of the ‘?’. Deal first with the problem that the bounds are not tight enough for GCH to apply. We fix that by looking at:

𝒫³(A)≤W+𝒫³(A)≤𝒫⁴(A)+𝒫³(A) ?≡? 𝒫⁴(A)

So if W+𝒫³(A)≡𝒫⁴(A), we ought to have W≡𝒫⁴(A) and hence a well-ordering of A. What about the other case, W+𝒫³(A)≡𝒫³(A)? Ah, then we have

𝒫²(A)≤W+𝒫²(A)≤W+𝒫³(A)≡𝒫³(A)

and so we can repeat the argument: either W+𝒫²(A)≡𝒫³(A), which ought to make 𝒫³(A) well-ordered and hence also A well-ordered; or W+𝒫²(A)≡𝒫²(A), in which case we repeat the argument yet again. Eventually we work our way down to

A≤W+A≤W+𝒫(A)≡𝒫(A)

and W+A≡A is excluded since W≰ A, and we are done.

All this relies on the intuition that if W+M≡𝒫(M), then we should have W≡𝒫(M): we used this with M=𝒫ⁿ(A) for n=0,…,3. Well, we can prove something a little weaker.

Lemma: If W+M≡𝒫(M)×𝒫(M), then W≥𝒫(M).

Proof: Suppose h:W+M→𝒫(M)×𝒫(M) is a bijection. Restrict h to M and compose with the projection to the second factor: π₂⚬(h↾M):M→𝒫(M). Cantor’s diagonal argument shows that this map cannot be onto. (The fact that π₂⚬(h↾M) might not be 1–1 doesn’t affect the argument.) So for some s₀∈𝒫(M), we know that h(x) never takes the form (−,s₀) for x∈M. In other words, the image of h↾W must include all of 𝒫(M)×{s₀}. Therefore 𝒫(M)×{s₀} can be mapped 1–1 to a subset of W. qed.

The missing pieces of the proof now all take the form of absorption equations. We know that 𝒫(M)×𝒫(M)≡𝒫(M+M)—as an equation for cardinals, 2^𝔪2^𝔪=2^2𝔪. If we had 2𝔪=𝔪, that would take care of that problem. The ?≡? above also takes the form 2^𝔪+𝔪 ?=? 2^𝔪, for 𝔪 the cardinality of 𝒫³(A).

The general absorption laws for addition depend on AC. But we do have these suggestive equations even without AC:

𝔞+ω+1 = 𝔞+ω, 2^𝔪+1 = 2·2^𝔪

and so if 𝔞+ω=𝔪 and 2^𝔪=𝔟, then 2𝔟=𝔟. So let’s say we set B=𝒫(A+ω). Then we have 2B≡𝒫(A+ω+1)≡B (where 2B, of course, is the disjoint union of B with itself). Also B≤B+1≤2B≡B, so B≡B+1 and so 𝒫(B)≡2𝒫(B). So if we replace A with B, then all gaps in the argument are filled and we conclude that B can be well-ordered. But obviously A can be imbedded in B, so A also can be well-ordered. QED.

Ernst Specker proved a “local” version of Sierpiński’s Theorem: if 𝔪 and 2^𝔪 both satisfy CH, then 2^𝔪=ℵ(𝔪).

Prev TOC Next