Inmathematics andset theory,hereditarily finite sets are defined asfinite 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 all the way down to theempty set.

Arecursive definition ofwell-founded hereditarily finite sets is as follows:

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

Recursion rule: If${\displaystyle a_1,\dots a_k}$ are hereditarily finite, then so is${\displaystyle \{a_1,\dots a_k\}}$.

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

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

• ${\displaystyle \{\}}$ (i.e.${\displaystyle \mathrm{\varnothing }}$, the Neumann ordinal "0")
• ${\displaystyle \{\{\}\}}$ (i.e.${\displaystyle \{\mathrm{\varnothing }\}}$ 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^[1]

The set${\displaystyle \{\{\},\{\{\{\}\}\}\}}$ is an example for such a hereditarily finite set and so is the empty set${\displaystyle \{\}}$, as noted. On the other hand, the sets${\displaystyle \{7,\mathbb{N},\pi \}}$ or${\displaystyle \{3,\{\mathbb{N}\}\}}$ are examples of finite sets that are nothereditarily finite. For example, the first cannot be hereditarily finite since it contains at least one infinite set as an element, when${\displaystyle \mathbb{N}=\{0,1,2,\dots \}}$.

The class of all hereditarily finite sets is denoted by${\displaystyle H_{{\mathrm{\aleph }}_0}}$, meaning that the cardinality of each member is smaller than${\displaystyle {\mathrm{\aleph }}_0}$. (Analogously, the class ofhereditarilycountable sets is denoted by${\displaystyle H_{{\mathrm{\aleph }}_1}}$.)It can also be denoted by${\displaystyle V_{\omega }}$, which denotes the${\displaystyle \omega }$th stage of thevon Neumann universe.^[2]

${\displaystyle H_{{\mathrm{\aleph }}_0}}$ is in bijective correspondence with${\displaystyle {\mathrm{\aleph }}_0}$.A theory which proves it to be a set also proves it to becountable.

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

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

For example, the empty set${\displaystyle \{\}}$ contains no members, and is therefore mapped to anempty sum, that is, the numberzero. 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)}+\dots }$.

The inverse is given by

${\displaystyle {\displaystyle f^{-1}:\omega \to H_{{\mathrm{\aleph }}_0}}}$

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

where BIT denotes theBIT 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}}^{\mathrm{\top }})}$ (where${\displaystyle {\text{BIT}}^{\mathrm{\top }}}$ is theconverse relation of${\displaystyle \text{BIT}}$, swapping its two arguments) modelsZermelo–Fraenkel set theory ZF without theaxiom of infinity. Here, each natural number models a set, and the${\displaystyle \text{BIT}}$ relation models the membership relation between sets.

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

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

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

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

Now note thatRobinson arithmetic can already be interpreted inST, the very small sub-theory ofZermelo set theory Z⁻ with itsaxioms given byExtensionality, Empty Set andAdjunction. All of${\displaystyle H_{{\mathrm{\aleph }}_0}}$ has aconstructive axiomatization involving these axioms and e.g.Set induction andReplacement.

Axiomatically characterizing the theory of hereditarily finite sets, the negation of theaxiom of infinity may be added. As the theory validates the other axioms of${\displaystyle \mathsf{Z}\mathsf{F}}$, this establishes that the axiom of infinity is not a consequence of these other${\displaystyle \mathsf{Z}\mathsf{F}}$ axioms.

The hereditarily finite sets are a subclass of theVon Neumann universe. Here, the class of all well-founded hereditarily finite sets is denoted${\displaystyle V_{\omega }}$. Note that this is also a set in this context.

If we denote by${\displaystyle \mathrm{\wp }(S)}$ thepower set of${\displaystyle S}$, and by${\displaystyle V_0}$ the empty set, then${\displaystyle V_{\omega }}$ can be obtained by setting${\displaystyle V_{i+1}=\mathrm{\wp }(V_i)}$ for each integer${\displaystyle i\ge 0}$. Thus,${\displaystyle V_{\omega }}$ can be expressed as

${\displaystyle {\displaystyle V_{\omega }=\bigcup _{k=0}^{\mathrm{\infty }}{V}_k}}$

and all its elements are finite.

This formulation shows, again, that there are onlycountably many hereditarily finite sets:${\displaystyle V_n}$ is finite for any finite${\displaystyle n}$, itscardinality is${\displaystyle 2\uparrow \uparrow (n-1)}$ inKnuth's up-arrow notation (a tower of${\displaystyle 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 itstransitive closure is finite.

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

• Set theory

• Articles with short description
• Short description matches Wikidata