Hereditarily finite set

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.

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

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.

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

Their models then also fulfill the axioms consisting of the axioms of Zermelo–Fraenkel set theory 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 set theory.

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 V0 the empty set, then Vω can be obtained by setting V1 = ℘(V0), V2 = ℘(V1),..., Vk = ℘(Vk−1),... and so on.

We see, again, that there are only countably many hereditarily finite sets: 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.

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.