# Hereditarily finite set

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

In mathematics and set theory, hereditarily finite sets are defined as finite sets whose elements are all hereditarily finite sets.

## Formal definition

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

Base case: The empty set is a hereditarily finite set.
Recursion rule: If a1,...,ak are hereditarily finite, then so is {a1,...,ak}.

The set of all well-founded hereditarily finite sets is denoted Vω. If we denote by ℘(S) the power set of S, and by V0 the empty set, then Vω can also be constructed by setting V1 = ℘(V0), V2 = ℘(V1),..., Vk = ℘(Vk−1),... and so on. Thus, Vω can be expressed as follows:

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

## Discussion

The hereditarily finite sets are a subclass of the Von Neumann universe. They are a model of the axioms consisting of the axioms of set theory with the axiom of infinity replaced by its negation, thus proving that the axiom of infinity is not a consequence of the other axioms of set theory.

Notice that there are countably many hereditarily finite sets, since Vn is finite for any finite n (its cardinality is n−12, 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. Vω is also symbolized by ${\displaystyle H_{\aleph _{0}}}$, meaning hereditarily of cardinality less than ${\displaystyle \aleph _{0}}$.

## Ackermann's bijection

Ackermann (1937) gave the following natural bijection f from the natural numbers to the hereditarily finite sets, known as the Ackermann coding. It is defined recursively by

${\displaystyle f(2^{a}+2^{b}+\cdots )=\{f(a),f(b),\ldots \}}$ if a, b, ... are distinct.

We have f(m) ∈ f(n) if and only if the mth binary digit of n (counting from the right starting at 0) is 1.