Hereditarily finite set

In mathematics, specifically set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets. In other words, the set itself is finite and all of its elements are finite sets, recursively down to the empty set.

Formal definition

A recursive definition of well-founded hereditarily finite sets is as follows:

Base case: the empty set is a hereditarily finite set.

Recursion rule: if $a_{1},\dots a_{k}$ are hereditarily finite sets, then so is $\{a_{1},\dots a_{k}\}$.

Only sets that can be built by a finite number of applications of these two rules are hereditarily finite.

Representation

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

• One bracket pair: $\{\}=\varnothing$ (the ordinal "0").
• Two bracket pairs: $\{\{\}\}=\{\varnothing \}=\{0\}$ (the ordinal "1").
• Three bracket pairs: $\{\{\{\}\}\}$.
• Four bracket pairs: $\{\{\{\{\}\}\}\}$ and also $\{\{\},\{\{\}\}\}=\{0,\{0\}\}=\{0,1\}$ (the ordinal "2").
• Five bracket pairs: $\{\{\{\{\{\}\}\}\}\}$, also $\{\{\{\},\{\{\}\}\}\}$ as well as $\{\{\},\{\{\{\}\}\}\}$.
• Six bracket pairs, such as $\{\{\{\{\{\{\}\}\}\}\}\}$. There are six such sets.
• Seven bracket pairs, such as $\{\{\{\{\{\{\{\}\}\}\}\}\}\}$. There are twelve such sets.
• Eight bracket pairs, such as $\{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}$ or $\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}=\{0,1,\{0,1\}\}=\{0,1,2\}$ (the ordinal "3").

The number of sets with $n$ bracket pairs is

$1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,\dots$

(sequence A004111 in the OEIS).

Discussion

Not every finite set is hereditarily finite. For example, $\{7,{\mathbb {N} }\}$ is not hereditarily finite since it contains an infinite set as an element, the set of natural numbers $\mathbb {N} =\{0,1,2,\dots \}$.

The class of all hereditarily finite sets is denoted by $H_{\aleph _{0}}$, meaning that the cardinality of each member is smaller than $\aleph _{0}$. (Analogously, the class of hereditarily countable sets is denoted by $H_{\aleph _{1}}$.) It can also be denoted by $V_{\omega }$, which denotes the $\omega$th stage of the von Neumann universe.

$H_{\aleph _{0}}$ is in bijective correspondence with $\aleph _{0}$. Any theory that can prove $H_{\aleph _{0}}$ to be a set can also prove it to be countable.

Models

Ackermann coding

In 1937, Wilhelm Ackermann introduced an encoding of hereditarily finite sets as natural numbers. It is defined by a function $f:H_{\aleph _{0}}\to \mathbb {N}$ that maps each hereditarily finite set to a natural number, given by the following recursive definition:

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

For example, the empty set $\{\}$ 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 $a,b,c,\dots$ is mapped to $2^{f(a)}+2^{f(b)}+2^{f(c)}+\ldots$

The inverse $f^{-1}:\mathbb {N} \to H_{\aleph _{0}}$ of this function is given by

$f^{-1}(i)=\{f^{-1}(j)\mid {\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, $(\mathbb {N} ,{\text{BIT}}^{\top })$ (where ${\text{BIT}}^{\top }$ is the converse relation of ${\text{BIT}}$, swapping its two arguments) models Zermelo–Fraenkel set theory without the axiom of infinity. Here, each natural number models a set, and the ${\text{BIT}}$ relation models the membership relation between sets.

Graph models

The class $H_{\aleph _{0}}$ can be seen to be in exact correspondence with a class of rooted trees, namely those without non-trivial symmetries (i.e. whose only automorphism is the identity). The root vertex corresponds to the top level bracket $\{\dots \}$ and each edge leads to an element (another such set) that can act as a root vertex in its own right. No automorphism of this graph exists, corresponding to the fact that equal branches are identified (e.g. $\{t,t,s\}=\{t,s\}$, trivializing the permutation of the two subgraphs of shape $t$). This graph model enables an implementation of ZF without infinity as data types and thus an interpretation of set theory in expressive type theories.

Graph models exist for ZF and also set theories different from Zermelo set theory, such as non-well founded theories. Such models have more intricate edge structure.

In graph theory, the graph whose vertices correspond to hereditarily finite sets and edges correspond to set membership is the Rado graph or random graph.

Axiomatizations

Theories of finite sets

In common axiomatic set theory approaches, the empty set $\{\}$ also represents the first von Neumann ordinal number, denoted $0$. All finite von Neumann ordinals are indeed hereditarily finite and, thus, so is every set in the class of sets representing the natural numbers. In other words, $H_{\aleph _{0}}$ includes each element in the standard model of natural numbers and so a set theory expressing $H_{\aleph _{0}}$ must necessarily contain them as well.

Robinson arithmetic can be interpreted in ST, the very small sub-theory of Zermelo set theory with only the axioms of extensionality, empty set and adjunction. All of $H_{\aleph _{0}}$ has a constructive axiomatization involving these axioms and, for example, the axioms of set induction and replacement.

Axiomatically characterizing the theory of hereditarily finite sets, the negation of the axiom of infinity may be added. As the theory validates the other axioms of ZF, this establishes that the axiom of infinity is not a consequence of these other ZF axioms.

ZF

$~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_{\omega }$. Note that this is also a set in this context.

If we denote by ${\mathcal {P}}(S)$ the power set of $S$, and by $V_{0}$ the empty set, then $V_{\omega }$ can be obtained by setting $V_{i+1}={\mathcal {P}}(V_{i})$ for each $i\geq 0$. Thus, $V_{\omega }$ can be expressed as

$V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}$

and all its elements are finite.

This formulation shows, again, that there are only countably many hereditarily finite sets: $V_{n}$ is finite for any finite $n$, its cardinality is $2\uparrow \uparrow (n-1)$ in Knuth's up-arrow notation (a tower of $n-1$ powers of two), 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.

See also

• Constructive set theory
• Finite set
• Hereditary set
• Hereditarily countable set
• Hereditary property
• Rooted trees

References

• Ackermann, Wilhelm (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre". Mathematische Annalen. 114: 305–315. doi:10.1007/bf01594179.

• Kirby, Laurence (2009). "Finitary set theory". Notre Dame Journal of Formal Logic. 50 (3): 227–244. doi:10.1215/00294527-2009-009. Zbl 1190.03043.

• Omodeo, Eugenio G.; Policriti, Alberto; Tomescu, Alexandru I. (2017). On Sets and Graphs: Perspectives on Logic and Combinatorics. Cham: Springer. ISBN 978-3-319-54980-4. MR 3558535.