Hereditarily finite set

Short description: Finite sets whose elements are all hereditarily finite sets

In mathematics and 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 all the way 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₁,...,a_k are hereditarily finite, then so is {a₁,...,a_k}.

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

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

Discussion

The class of hereditarily finite sets is denoted by [math]\displaystyle{ H_{\aleph_0} }[/math], meaning that the cardinality of each member is smaller than [math]\displaystyle{ \aleph_0 }[/math]. (Analogously, the class of hereditarily countable sets is denoted by [math]\displaystyle{ H_{\aleph_1} }[/math].)

It can also be denoted by [math]\displaystyle{ V_\omega }[/math], which denotes the [math]\displaystyle{ \omega }[/math]th stage of the von Neumann universe.

The class [math]\displaystyle{ H_{\aleph_0} }[/math] is countable.

Ackermann coding

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

[math]\displaystyle{ f(a) = \sum_{b \in a} 2^{f(b)} }[/math]

For example, the empty set [math]\displaystyle{ \varnothing }[/math] 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 [math]\displaystyle{ a, b, c, \dots }[/math] is mapped to [math]\displaystyle{ 2^{f(a)} + 2^{f(b)} + 2^{f(c)} + \ldots }[/math].

The inverse of [math]\displaystyle{ f }[/math], which maps natural numbers back to sets, is

[math]\displaystyle{ f^{-1}(i) = \{f^{-1}(j) \mid j \in \omega, \text{BIT}(i, j) = 1\} }[/math]

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, [math]\displaystyle{ (\mathbb{N}, \text{BIT}^\top) }[/math] (where [math]\displaystyle{ \text{BIT}^\top }[/math] 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:

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

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

Axiomatizations

Theories of finite sets

The set [math]\displaystyle{ \emptyset }[/math] also represents the first von Neumann ordinal number, denoted [math]\displaystyle{ 0 }[/math]. And indeed all finite von Neumann ordinals are in [math]\displaystyle{ H_{\aleph_0} }[/math] 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 [math]\displaystyle{ {\mathsf {ST}} }[/math], the very small sub-theory of [math]\displaystyle{ {\mathsf {Z}}^- }[/math] with its axioms given by Extensionality, Empty Set and Adjunction.

Indeed, [math]\displaystyle{ H_{\aleph_0} }[/math] 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 [math]\displaystyle{ {\mathsf {ZF}} }[/math] 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 [math]\displaystyle{ {\mathsf {ZF}} }[/math].

ZF

[math]\displaystyle{ ~V_4~ }[/math] represented with circles in place of curly brackets    15px

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 [math]\displaystyle{ V_\omega = \bigcup_{k=0}^\infty V_k }[/math] 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.

Graph models

The class [math]\displaystyle{ H_{\aleph_0} }[/math] can be seen to be in exact correspondence with a class of rooted trees, namely those without non-trivial symmetries (i.e. the only automorphism is the identity): The root vertex corresponds to the top level bracket [math]\displaystyle{ \{\dots\} }[/math] 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 exist, corresponding to the fact that equal branches are identified (e.g. [math]\displaystyle{ \{t,t,s\}=\{t,s\} }[/math], trivializing the permutation of the two subgraphs of shape [math]\displaystyle{ t }[/math]). 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.

See also

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