Power set: the subsets of a set form a set¶

Level: 201 · for anyone reading ∀v₀∃v₁∀v₂(v₂ ∈ v₁ ⇔ ∀v₃(v₃ ∈ v₂ ⇒ v₃ ∈ v₀)) and finding no word "subset" in it

One line: The power set axiom hides ⊆ inside a ∀ … ⇒, promises 𝒫(a), the set of all subsets of a, and is the engine of size in the universe: each stage V_{n+1} is 𝒫(V_n), every finite universe lacks the power set of its top rank, and Cantor's theorem says 𝒫(a) is strictly bigger than a even when a is infinite, which is where the real numbers come from.

The axiom, read aloud¶

∀v₀ ∃v₁ ∀v₂ (v₂ ∈ v₁ ⇔ ∀v₃ (v₃ ∈ v₂ ⇒ v₃ ∈ v₀))

For every set a there is a set b such that z is a member of b exactly when every member of z is a member of a. The inner formula ∀v₃(v₃ ∈ v₂ ⇒ v₃ ∈ v₀) is the definition of z ⊆ a spelled out, since the language has no ⊆ of its own; so b's members are the subsets of a, and b is the power set 𝒫(a). Cunningham states it first in English, for every set A there is a set P that consists of all the sets that are subsets of A, then as ∀A ∃P ∀x (x ∈ P ↔ ∀y (y ∈ x → y ∈ A)); it is the same formula with letters for the variables and → for ⇒. Cori and Lascar call it the axiom of subsets.

What it is for¶

Counting subsets. Each member of a is in or out of a subset, independently, so a set of n members has 2ⁿ subsets: section 1 lists them for n up to 3. The subsets of {1, 2, 3} on page 4 of Cunningham are the eight sets ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, and 𝒫(A) ∋ X exactly when X ⊆ A.

Growing the universe. The stages of this chapter are power sets of each other: V₂ = 𝒫(V₁), V₃ = 𝒫(V₂), V₄ = 𝒫(V₃), checked in section 2, so their sizes go 1, 2, 4, 16, 65 536, 2⁶⁵ ⁵³⁶. The pair axiom adds one rank at a time; the power set axiom adds everything a rank holds at once.

The real numbers. A real number in [0, 1] is a sequence of bits, which is a subset of ℕ (the positions of the 1s), so ℝ lives in 𝒫(ω) and a function from ℝ to ℝ in 𝒫(𝒫(ω)). Without this axiom, Zermelo's theory could not prove that the set of real numbers exists.

Cantor's theorem. 𝒫(a) is always strictly bigger than a. For finite a that is 2ⁿ > n, section 5; for infinite a it is the diagonal argument, run in the reading guide's program: no map from a onto 𝒫(a) exists. So 𝒫(ω) is uncountable, and 𝒫(𝒫(ω)) is bigger again, and there is no largest set.

What goes wrong without it¶

Section 3 counts: of the sixteen sets in V₄, the four of rank at most 2 have their power set in V₄ and the twelve of rank 3 do not, because 𝒫 of a rank-3 set has rank 4. The axiom asks for a set one rank up, as pairs does, and every finite stage fails it. Nor is it a consequence of the other axioms: a universe can satisfy all of them and still be countable (Skolem's observation of 1922), in which case the "power set of ω" it contains is not the real one. What the axiom asserts is the existence of all subsets, including the ones no formula describes, and that is a much stronger claim than it looks.

What the program prints¶

Verified output of power_set.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE AXIOM, AND 2^n
   ∀v0 ∃v1 ∀v2 (v2 ∈ v1 ⇔ ∀v3 (v3 ∈ v2 ⇒ v3 ∈ v0))
   for every a there is a b whose members are exactly the sets z with
   'every member of z is a member of a', the subsets of a. b is 𝒫(a).
   a = ∅                  |a| = 0   𝒫(a) = {∅}                                |𝒫(a)| = 1 = 2^0
   a = {∅}                |a| = 1   𝒫(a) = {∅, {∅}}                           |𝒫(a)| = 2 = 2^1
   a = {∅, {∅}}           |a| = 2   𝒫(a) = {∅, {∅}, {{∅}}, {∅, {∅}}}          |𝒫(a)| = 4 = 2^2
   a = {∅, {∅}, {∅, {∅}}} |a| = 3   𝒫(a) = (8 sets)                           |𝒫(a)| = 8 = 2^3
   Each member is in or out, independently: 2 choices, n times.

2. THE STAGES ARE POWER SETS OF EACH OTHER: V_{n+1} = 𝒫(V_n)
   𝒫(V_1) == V_2: True   (1 sets -> 2 sets)
   𝒫(V_2) == V_3: True   (2 sets -> 4 sets)
   𝒫(V_3) == V_4: True   (4 sets -> 16 sets)
   So V_5 has 2^16 = 65,536 sets and V_6 has 2^65536, more than the
   atoms in the universe; the axiom is the engine of that growth.

3. WHERE V_4 RUNS OUT
   of the 16 sets in V_4, 4 have their power set in V_4 and
   12 do not; every one of those has rank [3],
   e.g. a = {{{∅}}}: rank(𝒫(a)) = 4, and V_4 stops at 3.
   Like pairs, the axiom asks for a set one rank up, and every V_n fails it.

4. THE INNER FORMULA IS ⊆, AND PYTHON HAS IT
   ∀v3 (v3 ∈ z ⇒ v3 ∈ a) agrees with Python's z <= a for every z, a in V_3: True

5. CANTOR: THE POWER SET IS ALWAYS STRICTLY BIGGER
   |𝒫(a)| > |a| for every a in V_4: True  (2^n > n)
   For infinite a counting fails and the diagonal argument takes over:
   no map a -> 𝒫(a) is onto (the reading guide's program runs it). So
   𝒫(ω) is uncountable, and that is where the real numbers live.

Section 4 is the one line that connects the formula to code: the inner ∀v₃(v₃ ∈ v₂ ⇒ v₃ ∈ v₀) agrees with Python's z <= a on every pair of sets tried, which is how the chapter's model checker evaluates this axiom.

Po polsku, w skrócie¶

Aksjomat zbioru potęgowego mówi: dla każdego zbioru a istnieje zbiór 𝒫(a), którego elementami są dokładnie podzbiory a. W formule nie ma znaku ⊆; zastępuje go ∀v₃(v₃ ∈ v₂ ⇒ v₃ ∈ v₀), czyli „każdy element z jest elementem a", a Python pisze to z <= a. Zbiór n-elementowy ma 2ⁿ podzbiorów, bo każdy element jest w podzbiorze albo nie. To silnik wzrostu uniwersum: V₂ = 𝒫(V₁), V₃ = 𝒫(V₂), V₄ = 𝒫(V₃), a rozmiary rosną 1, 2, 4, 16, 65 536. W V₄ brakuje zbiorów potęgowych wszystkich zbiorów rangi 3, więc aksjomat nie zachodzi w żadnym skończonym V_n. Twierdzenie Cantora mówi, że 𝒫(a) jest zawsze ściśle większy od a, także dla a nieskończonego; dlatego 𝒫(ω) jest nieprzeliczalny, a tam mieszkają liczby rzeczywiste.

Auf Deutsch: Stichwörter¶

Potenzmengenaxiom: die Teilmengen einer Menge bilden eine Menge, 2ⁿ viele; Cantors Satz |𝒫(A)| > |A|.

Stichwörter: Potenzmenge, Teilmenge, 2ⁿ, Satz von Cantor, Diagonalargument, charakteristische Funktion.

Run it yourself¶

From the root of your clone of this repository:

python3 13_Axioms_of_Set_Theory/power_set/examples/power_set.py