Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 38 ยท Projects and Practice

Project: The Hereditarily Finite Universe

Build every hereditarily finite set up to rank 4, count them, number them with the Ackermann coding, and check von Neumann ordinals, step by step.

In this final project you will build a small but genuine universe of sets inside Python. The universe is the hereditarily finite sets: sets that are finite, whose elements are finite, whose elements' elements are finite, and so on down. It is a model of every ZFC axiom except Infinity, and it is where the arithmetic of finite numbers lives inside set theory.

You will use almost everything from this chapter: power sets, von Neumann ordinals, the ZFC axioms, and counting.

Plan

  1. Build the stages Vโ‚€, Vโ‚, Vโ‚‚, ... by taking power sets.
  2. Count the sets in each stage and the rank of a set.
  3. Give every hereditarily finite set a natural number code (the Ackermann coding), showing the universe is countable.
  4. Detect which sets are von Neumann ordinals.
  5. Check that the universe satisfies pairing, union and power set.

Step 1: the stages

Define Vโ‚€ = โˆ… and V_{n+1} = P(Vโ‚™). Each stage contains all earlier ones.

Python Step 1 and 2: build the stages and count them

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sizes 0, 1, 2, 4, 16 come from |V_{n+1}| = 2^|Vโ‚™|. The next stage has 2ยนโถ = 65536 sets, and the next has 2^65536. The growth is a tower of exponentials. The union of all stages is the set of hereditarily finite sets, usually written V_ฯ‰.

Step 3: numbering every set

Wilhelm Ackermann found a neat way to number them: the set {a, b, c} gets code 2^code(a) + 2^code(b) + 2^code(c). Starting from โˆ… โ†ฆ 0, each code is a binary number saying which elements are present.

Text
code(โˆ…)        = 0
code({โˆ…})      = 2^0 = 1
code({{โˆ…}})    = 2^1 = 2
code({โˆ…,{โˆ…}})  = 2^0 + 2^1 = 3

This is a bijection between hereditarily finite sets and the natural numbers: the first uses finite subsets of โ„• (as in the practice lesson) recursively.

Python Step 3: the Ackermann coding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Since every hereditarily finite set has a unique natural number as its code, the universe V_ฯ‰ is countable. A classic fact is that V_ฯ‰ satisfies all the axioms of ZFC except Infinity.

Step 4: find the ordinals

A set is a (finite) von Neumann ordinal if it is transitive and every element is also transitive and the members are totally ordered by โˆˆ (ordinals lesson). Let us find all of them in Vโ‚„.

Python Step 4: which sets are ordinals?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should find the ordinals 0, 1, 2, 3: the ordinal n has rank n, so it first appears in V_(n+1), and 4 has to wait for Vโ‚…. Their codes are 0, 1, 3, 11; the next ordinal, 4, would have code 2059, which shows how fast codes grow.

Step 5: closure under the axioms

V_ฯ‰ contains โˆ…, and is closed under:

  • Pairing: if a and b are in V_ฯ‰, then {a, b} is hereditarily finite.
  • Union: the union of a hereditarily finite set is hereditarily finite.
  • Power set: every subset of a hereditarily finite set is hereditarily finite, and there are finitely many.
  • Separation: a subset of a hereditarily finite set is itself in V_ฯ‰.

It is not closed under Infinity: there is no hereditarily finite set containing all the natural numbers.

Python Step 5: closure checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Extensions

  • Write a function that checks extensionality: two Python frozensets are equal exactly when they have the same elements. (Python already does it.)
  • Compute the rank of the code 2059 and draw its membership tree with matplotlib.
  • Count how many sets have rank exactly n in V_ฯ‰: 1, 1, 2, 12, 65520.... Why do the counts equal |V_{n+1}| - |V_n|?
  • Write the Kuratowski pair (a, b) and the Cartesian product of two hereditarily finite sets, and verify the product rule from the counting lesson.

You have just modelled a universe of mathematics with only braces. In the full ZFC universe, adding Infinity makes the picture bigger: one more stage, V_{ฯ‰+1}, already has the cardinality ๐”  of the continuum.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many sets are in Vโ‚„, if Vโ‚€ = โˆ… and V_(n+1) = P(Vโ‚™)?

    The sizes are 0, 1, 2, 4, 16, ... and |V_(n+1)| = 2^|Vโ‚™|. So |Vโ‚„| = 2^4 = 16.
  2. 2. What is the Ackermann code of the set {โˆ…, {โˆ…}}?

    code(โˆ…) = 0 and code({โˆ…}) = 2^0 = 1. The set {โˆ…, {โˆ…}} has code 2^0 + 2^1 = 3.
  3. 3. Why is the hereditarily finite universe countable?

    The Ackermann coding is a bijection between the hereditarily finite sets and โ„•.
  4. 4. Which ZFC axiom fails in the hereditarily finite universe?

    Every set in this universe is finite, so none contains all the natural numbers.

Summary

  • The stages V_(n+1) = P(Vโ‚™) have sizes 0, 1, 2, 4, 16, 65536, ...; their union is the hereditarily finite universe.
  • The Ackermann coding code(s) = ฮฃ 2^code(x) numbers every such set, so the universe is countable.
  • The von Neumann ordinals in it are exactly 0, 1, 2, ... that fit in the stage you build (0, 1, 2, 3 in Vโ‚„).
  • The universe satisfies all ZFC axioms except Infinity.
  • You have now met the main ideas of set theory: sets, functions, orders, cardinality, ordinals and the axioms. Return to the track overview to revisit any lesson.