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:

1. Base case: The empty set is a hereditarily finite set.

2. Recursion rule.

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

Representation

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

• , the Neumann ordinal "0")

• , the Neumann ordinal "1")

• , the Neumann ordinal "2"),

• ,

• . There are six such sets

• . There are twelve such sets

• , the Neumann ordinal "3")

• ... etc.

bracket pairs is

Discussion

are examples of finite sets that are not hereditarily.

. (Analogously, the class of hereditarily countable setsth stage of the von Neumann universe.

. A theory that proves it to be a set also proves it to be countable.

Models

Ackermann coding

In 1937, Wilhelm Ackermann introduced an encoding of hereditarily finite sets as natural numbers. that maps each hereditarily finite set to a natural number, given by the following recursive definition: contains no members, and is therefore mapped to an empty sum, that is, the number zero.

The inverse is given by where BIT denotes the BIT predicate.

is the converse relation, swapping its two arguments) models Zermelo–Fraenkel set theory ZF without the axiom of infinity relation models the membership relation between sets.

Graph models

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 and each edge). 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 modelss 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.

Axiomatizations

Theories of finite sets

also represents the first von Neumann ordinal number includes each element in the standard model of natural numbers must necessarily contain them as well.

Now note that Robinson arithmetic can already be interpreted in ST, the very small sub-theory of Zermelo set theory Z with its axioms given by Extensionality, Empty Set and Adjunction has a constructive axiomatization involving these axioms and e.g. Set induction and Replacement.

Axiomatically characterizing the theory of hereditarily finite sets, the negation of the axiom of infinity axioms.

ZF

The hereditarily finite sets are a subclass of the Von Neumann universe. Note that this is also a set in this context.

the power set can be expressed as and all its elements are finite.

This formulation shows, again, that there are only countably, its cardinality in Knuth's up-arrow notation powers of two), 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.

See also

• Constructive set theory

• Finite set

• Hereditary set

• Hereditarily countable set

• Hereditary property

• Rooted trees

References