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.

Formal definition

A recursive definition of well-founded hereditarily finite sets is as follows:
The set is an example for such a hereditarily finite set and so is the empty set.
On the other hand, the sets or 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.

Discussion

A symbol for the class is, standing for the cardinality of each of its member being smaller than. Whether is a set and statements about cardinality depend on the theory in context.

Ackermann's bijection

The class is countable. gave the following natural bijection f from the natural numbers to the, known as the Ackermann coding. It is defined recursively by
E.g.
We have f ∈ f if and only if the mth binary digit of n is 1.

Representation

This class of sets is naturally ranked by the number of bracket pairs necessary to represent the sets:
In this way, the number of sets with bracket pairs is

Axiomatizations

Theories of finite sets

The set also represents the first von Neumann ordinal number, denoted.
And indeed all finite von Neumann ordinals are in 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 ST, the very small sub-theory of with axioms given by Extensionality, Empty Set and Adjunction.
Indeed, 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 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.

ZF

The hereditarily finite sets are a subclass of the Von Neumann universe. Here, all well-founded hereditarily finite sets is denoted Vω. Note that this is a set in this context.
If we denote by ℘ the power set of S, and by V0 the empty set, then Vω can be obtained by setting
V1 = ℘, V2 = ℘,..., Vk = ℘,... and so on.
Thus, Vω can be expressed as.
We see, again, that there's only countably many hereditarily finite sets: Vn is finite for any finite n. Its cardinality is n−12, see tetration.
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 can be seen to be in exact correspondence with a class of rooted trees, namely those without non-trivial symmetries :
The root vertex corresponds to the top level bracket and each edge leads to an element 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.
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 is the Rado graph or random graph.