Foundation: every nonempty set has a member that shares nothing with it¶

Level: 201 · for anyone who has read that ZF alone cannot say whether a set can be a member of itself, and wants to see the axiom that settles it

One line: Foundation (Cunningham and Jech: regularity) says every nonempty set has an ∈-minimal member, one that shares no member with it; from that, no set is a member of itself and no chain of memberships goes down forever, so every set is built from ∅ in stages and has a rank, which is the picture the whole chapter's universes V₁, V₂, V₃, V₄ were drawn from.

The axiom, read aloud¶

∀v₀ (¬v₀ ≃ ∅ ⇒ ∃v₁ (v₁ ∈ v₀ ∧ v₁ ∩ v₀ ≃ ∅))

For every set a: if a is not empty, then some member x of a has no member in common with a. Cunningham: every nonempty set A has an element that is disjoint from A. Jech: every nonempty set has an ∈-minimal element, which is the same thing said with order words: x is minimal in a when nothing in a is a member of x. Cori and Lascar bring the axiom in last, with the hierarchy V_α, and remark that without it ZF cannot answer the question "is there a set that is a member of itself?".

What it is for¶

No set is its own member. Suppose x ∈ x and look at the set {x}, which pairs gives. Its only member is x, and x shares the member x with {x}, so {x} has no member disjoint from it, against the axiom. Hence x ∉ x. The same move with {x, y} forbids x ∈ y ∈ x, and with {x, y, z} forbids a three-cycle; these are Cunningham's Exercises 1.5, numbers 3 to 5, and section 2 of the program states the argument and checks V₄ for cycles.

Every set has a rank. Follow ∈ downward from any set: a member, a member of that, and so on. Foundation says the descent stops, at ∅. So every set is built in stages, V₀ = ∅, V_{α+1} = 𝒫(V_α), unions at limits, and each set has a rank, the first stage that holds it. Section 4 counts the sixteen sets of V₄ by rank: 1, 1, 2 and 12. This is Cori and Lascar's final section, V = ∪ V_α, and the reason the chapter's small universes were cumulative stages and not arbitrary collections of sets.

Induction on ∈. A property that holds of a set whenever it holds of all its members holds of every set. That is induction on rank, and it is how theorems about all sets are proved.

What goes wrong without it¶

Section 3 builds three universes as membership tables. In the first a single point q has q as its only member: a Quine atom, q = {q}, which satisfies extensionality (one point, one set of members) and violates foundation at q. The second is the two-cycle a = {b}, b = {a} on its own, and it satisfies the axiom, which is the instructive surprise: a's member b has b ∩ a = {a} ∩ {b} = ∅. The violation appears only in the third universe, where the pair {a, b} is present, exactly the set the exercise tells you to consider. Foundation is a claim about the whole universe, and a cycle offends it only once the set that exhibits the cycle exists.

Such universes are consistent with the other axioms, which is what the book means by "ZF alone cannot answer". Peter Aczel's anti-foundation axiom (1988) replaces foundation with its opposite, and the resulting sets, which can contain themselves, model streams and processes in computer science. Ordinary mathematics never needs them, and never needs the axiom either: Kunen's Foundations of Mathematics says flatly that foundation "is never needed in the development of mathematics" and that most of elementary mathematics lives in Zermelo's theory without it. It is kept because it makes the universe a hierarchy and gives every set a rank, which makes the theory of sets itself simpler.

What the program prints¶

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

1. THE AXIOM ON V_4
   ∀v0 (¬v0 ≃ ∅ ⇒ ∃v1 (v1 ∈ v0 ∧ v1 ∩ v0 ≃ ∅))
   every nonempty set a has a member x with no member in common with a.
   checked for all 16 sets: True
   e.g. a = {∅, {∅}, {{∅}}}: the members sharing nothing with a: ['∅']
   The disjoint member is the ∈-minimal one: nothing in a is below it.

2. WHAT FOLLOWS: NO x ∈ x, NO x ∈ y ∈ x (CUNNINGHAM, EXERCISES 1.5)
   If x ∈ x, look at {x}: its only member x shares x with it. Foundation
   says some member of {x} is disjoint from {x}, so x ∉ x.
   If x ∈ y and y ∈ x, look at {x, y}: x shares y with it, y shares x.
   in V_4, sets with x ∈ x: 0;  pairs with x ∈ y ∈ x: 0

3. UNIVERSES THAT BREAK IT
   q = {q}, a set that is its own only member: foundation False, failing at q: its members are ['q'], each sharing a member with it
   a = {b}, b = {a}, and nothing else: foundation True, no point fails: a = {b} has the member b, and b ∩ a = {a} ∩ {b} = ∅
   a = {b}, b = {a}, and p = {a, b}: foundation False, failing at p: its members are ['a', 'b'], each sharing a member with it
   The two-cycle breaks the axiom only once the pair {a, b} is in the
   universe, which is why the exercise says 'consider {x, y}'.
   Such universes satisfy extensionality and can satisfy the rest; Aczel's
   anti-foundation axiom (1988) studies them, and computer science uses
   them for streams and processes that contain themselves.

4. WITH FOUNDATION, EVERY SET HAS A RANK
   rank(s) = 1 + max rank of its members, rank(∅) = 0: the stage where s appears
     rank 0:  1 sets   (appear in V_1)
     rank 1:  1 sets   (appear in V_2)
     rank 2:  2 sets   (appear in V_3)
     rank 3: 12 sets   (appear in V_4)
   Going down by ∈ must stop at ∅, which is foundation; so every set is
   built in stages, V = ∪ V_α, and a proof 'by induction on rank' covers
   every set there is. Cori and Lascar introduce the axiom for exactly
   that hierarchy, and show ZF cannot decide it either way.

Po polsku, w skrócie¶

Aksjomat regularności (ufundowania) mówi: każdy niepusty zbiór a ma element x, który nie ma z a żadnego wspólnego elementu, czyli element ∈-minimalny. Stąd żaden zbiór nie jest swoim elementem: gdyby x ∈ x, to zbiór {x} nie miałby elementu rozłącznego z sobą. Tak samo odpada x ∈ y ∈ x i każdy cykl; to zadania 3–5 z rozdziału 1.5 Cunninghama. Ważniejsze: schodząc w dół po ∈ zawsze dochodzi się do ∅, więc każdy zbiór powstaje w pewnym etapie hierarchii V₀ = ∅, V_{α+1} = 𝒫(V_α) i ma rangę; program liczy szesnaście zbiorów V₄ według rangi: 1, 1, 2, 12. Bez aksjomatu możliwe jest uniwersum z punktem q = {q}; para a = {b}, b = {a} sama w sobie aksjomatu nie łamie, łamie go dopiero zbiór {a, b}, dokładnie ten, o którym mówi zadanie. ZF bez tego aksjomatu nie rozstrzyga, czy zbiór może należeć do siebie; Cori i Lascar wprowadzają go na końcu, razem z hierarchią V_α.

Auf Deutsch: Stichwörter¶

Fundierung: jede nichtleere Menge hat ein Element, das mit ihr nichts gemeinsam hat; keine Menge enthält sich selbst, keine ∈-Kette fällt ewig.

Stichwörter: Fundierungsaxiom (Regularität), ∈-minimales Element, keine unendliche absteigende ∈-Kette, x ∉ x, kumulative Hierarchie, wohlfundiert.

Run it yourself¶

From the root of your clone of this repository:

python3 13_Axioms_of_Set_Theory/foundation/examples/foundation.py