# Hereditarily finite set

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

## Contents

## Formal definition[edit]

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*a*_{1},...,*a*_{k}are hereditarily finite, then so is {*a*_{1},...,*a*_{k}}.

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

## Discussion[edit]

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 *V _{n}* is finite for any finite

*n*(its cardinality is

^{n−1}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. V_{ω} is also symbolized by , meaning hereditarily of cardinality less than .

## Ackermann's bijection[edit]

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

- if
*a*,*b*, ... are distinct.

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

## Rado graph[edit]

The graph whose vertices are the hereditarily finite sets, with an edge joining two vertices whenever one is contained in the other, is the Rado graph or random graph.

## See also[edit]

## References[edit]

- Ackermann, Wilhelm (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre",
*Mathematische Annalen*,**114**(1): 305–315, doi:10.1007/BF01594179