hereditarily finite set



A hereditarily finite set is a finite set of hereditarily finite sets; this circular definition is usually interpreted recursively, although you can also interpret it corecursively to get ill-founded hereditarily finite sets. The set of all (well-founded) hereditarily finite sets (which is infinite, and not hereditarily finite itself) is written V ωV_\omega to show its place in the von Neumann hierarchy of pure sets.

As a property of a set, being hereditarily finite is equivalent (up to isomorphism of sets) to simply being finite. So the ‘hereditary’ part is meaningful only in material set theory, not structurally, unless you see it as a property of a pure set represented structurally as a membership tree.


There are countably many hereditarily finite sets, up to equality (in material set theory), and in fact they can be neatly enumerated as follows: Given a natural number n0n \geq 0, write nn in base 22; the iith hereditarily finite set is a member of the nnth one if the iith digit of nn is 11. (This definition is well-founded, because the highest non-zero digit of nn must have position at most log 2n\log_2 n, which is less than nn.)

So the hereditarily finite sets are as follows:

numberin base 22set
00(empty)={}\empty = \{\}
1111={}\star = \{\empty\}
2210102 Z={}2_Z = \{\star\}
3311112 vN={,}2_{vN} = \{\empty, \star\}
441001003 Z={2 Z}3_Z = \{2_Z\}
55101101{,2 Z}\{\empty, 2_Z\}
66110110{,2 Z}\{\star, 2_Z\}
77111111{,,2 Z}\{\empty, \star, 2_Z\}
8810001000{2 vN}\{2_{vN}\}
9910011001{,2 vN}\{\empty, 2_{vN}\}
101010101010{,2 vN}\{\star, 2_{vN}\}
1111101110113 vN={,,2 vN}3_{vN} = \{\empty, \star, 2_{vN}\}
121211001100{2 Z,2 vN}\{2_Z, 2_{vN}\}
131311011101{,2 Z,2 vN}\{\empty, 2_Z, 2_{vN}\}
141411101110{,2 Z,2 vN}\{\star, 2_Z, 2_{vN}\}
151511111111{,,2 Z,2 vN}\{\empty, \star, 2_Z, 2_{vN}\}

In this table, we've indicated the representations of 22 and 33 in the most common models of natural numbers as pure sets, those of Zermelo (where n+1={n}n + 1 = \{n\}) and of von Neumann (where n+1=n{n}n + 1 = n \cup \{n\}); these both begin with 0=0 = \empty and 1=1 = \star but diverge thereafter. (Von Neumann's representation is favoured now, as it allows each natural number to have itself as its cardinal number, a situation that generalises to infinite limit ordinal numbers.) However, the existence of this enumeration shows that another representation of natural numbers as pure sets is to use all hereditarily finite sets.

The set V ωV_\omega of hereditarily finite sets is a Grothendieck universe (unless you phrase the definition specifically to rule this out). Thus the axiom of infinity (which guarantees the existence of some model of the set N\mathbf{N} of natural numbers) can be seen as following from a very simple universe axiom: that some Grothendieck universe exists. Conversely, if any natural numbers object N\mathbf{N} exists in the category of sets, then you can form the universe V ωV_\omega (using the axiom of replacement) by performing the above enumeration.

In constructive mathematics, one gets different notions of hereditarily finite set depending on exactly how one defines finite set. The enumeration above works if you use the strictest sense, but you need to close under taking subsets (or use subfinite sets to start with) to get a Grothendieck universe in material set theory.

Revised on June 20, 2013 03:05:07 by Toby Bartels (