Ackermann coding

In 1937, Wilhelm Ackermann introduced an encoding of hereditarily finite sets as natural numbers.^[2][3][4] It is defined by a function ${\displaystyle f:V_{\omega }\to \omega }$ that maps each hereditarily finite set to a natural number, given by the following recursive definition:

${\displaystyle f(a)=\sum _{b\in a}2^{f(b)}}$

For example, the empty set ${\displaystyle \varnothing }$ contains no members, and is therefore mapped to an empty sum, that is, the number zero. On the other hand, a set with distinct members ${\displaystyle a,b,c,\dots }$ is mapped to ${\displaystyle 2^{f(a)}+2^{f(b)}+2^{f(c)}+\ldots }$.

The inverse of ${\displaystyle f}$, which maps natural numbers back to sets, is

${\displaystyle f^{-1}(i)=\{f^{-1}(j)\mid j\in \omega ,{\text{BIT}}(i,j)=1\}}$

where BIT denotes the BIT predicate.

The Ackermann coding can be used to construct a model of finitary set theory in the natural numbers. More precisely, ${\displaystyle (\mathbb {N} ,{\text{BIT}}^{\top })}$ (where ${\displaystyle {\text{BIT}}^{\top }}$ is the converse relation of BIT, swapping its two arguments) models Zermelo–Fraenkel set theory without the axiom of infinity. Here, each natural number models a set, and the BIT relation models the membership relation between sets.

Representation

This class of sets is naturally ranked by the number of bracket pairs necessary to represent the sets:

• ${\displaystyle \{\}}$ (i.e. ${\displaystyle \emptyset }$, the Neumann ordinal "0")
• ${\displaystyle \{\{\}\}}$ (i.e. ${\displaystyle \{\emptyset \}}$ or ${\displaystyle \{0\}}$, the Neumann ordinal "1")
• ${\displaystyle \{\{\{\}\}\}}$
• ${\displaystyle \{\{\{\{\}\}\}\}}$ and then also ${\displaystyle \{\{\},\{\{\}\}\}}$ (i.e. ${\displaystyle \{0,1\}}$, the Neumann ordinal "2"),
• ${\displaystyle \{\{\{\{\{\}\}\}\}\}}$, ${\displaystyle \{\{\{\},\{\{\}\}\}\}}$ as well as ${\displaystyle \{\{\},\{\{\{\}\}\}\}}$,
• ... sets represented with ${\displaystyle 6}$ bracket pairs, e.g. ${\displaystyle \{\{\{\{\{\{\}\}\}\}\}\}}$. There are six such sets
• ... sets represented with ${\displaystyle 7}$ bracket pairs, e.g. ${\displaystyle \{\{\{\{\{\{\{\}\}\}\}\}\}\}}$. There are twelve such sets
• ... sets represented with ${\displaystyle 8}$ bracket pairs, e.g. ${\displaystyle \{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}}$ or ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}}$ (i.e. ${\displaystyle \{0,1,2\}}$, the Neumann ordinal "3")
• ... etc.

In this way, the number of sets with ${\displaystyle n}$ bracket pairs is^[5] ${\displaystyle 1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,\dots }$

Theories of finite sets

The set ${\displaystyle \emptyset }$ also represents the first von Neumann ordinal number, denoted ${\displaystyle 0}$. And indeed all finite von Neumann ordinals are in ${\displaystyle H_{\aleph _{0}}}$ and thus the class of sets representing the natural numbers, i.e it includes each element in the standard model of natural numbers. Robinson arithmetic can already be interpreted in ${\displaystyle {\mathsf {ST}}}$, the very small sub-theory of ${\displaystyle {\mathsf {Z}}^{-}}$ with its axioms given by Extensionality, Empty Set and Adjunction.

Indeed, ${\displaystyle H_{\aleph _{0}}}$ has a constructive axiomatizations involving these axiom and e.g. Set induction and Replacement.

Their models then also fulfill the axioms consisting of the axioms of Zermelo–Fraenkel set theory ${\displaystyle {\mathsf {ZF}}}$ without the axiom of infinity. In this context, the negation of the axiom of infinity may be added, thus proving that the axiom of infinity is not a consequence of the other axioms of ${\displaystyle {\mathsf {ZF}}}$.

ZF

${\displaystyle ~V_{4}~}$ represented with circles in place of curly brackets    

The hereditarily finite sets are a subclass of the Von Neumann universe. Here, the class of all well-founded hereditarily finite sets is denoted V_ω. Note that this is also a set in this context.

If we denote by ℘(S) the power set of S, and by V₀ the empty set, then V_ω can be obtained by setting V₁ = ℘(V₀), V₂ = ℘(V₁),..., V_k = ℘(V_k−1),... and so on.

Thus, V_ω can be expressed as ${\displaystyle V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}}$ and all its elements are finite.

We see, again, that there are only countably many hereditarily finite sets: V_n is finite for any finite n, its cardinality is ⁿ⁻¹2 (see tetration), and the union of countably many finite sets is countable.

Equivalently, a set is hereditarily finite if and only if its transitive closure is finite.