hereditarily finite set

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

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

: Recursion rule: If $a\_1,\backslash dots\; a\_k$ are hereditarily finite, then so is $\backslash \{a\_1,\backslash dots\; a\_k\backslash \}$.

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

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

• $\backslash \{\backslash \}$ (i.e. $\backslash emptyset$, the Neumann ordinal "0")
• $\backslash \{\backslash \{\backslash \}\backslash \}$ (i.e. $\backslash \{\backslash emptyset\backslash \}$ or $\backslash \{0\backslash \}$, the Neumann ordinal "1")
• $\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}$
• $\backslash \{\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}$ and then also $\backslash \{\backslash \{\backslash \},\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}$ (i.e. $\backslash \{0,1\backslash \}$, the Neumann ordinal "2"),
• $\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}$, $\backslash \{\backslash \{\backslash \{\backslash \},\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}$ as well as $\backslash \{\backslash \{\backslash \},\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}$,
• ... sets represented with $6$ bracket pairs, e.g. $\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}$. There are six such sets
• ... sets represented with $7$ bracket pairs, e.g. $\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}$. There are twelve such sets
• ... sets represented with $8$ bracket pairs, e.g. $\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}\backslash \}$ or $\backslash \{\backslash \{\backslash \},\; \backslash \{\backslash \{\backslash \}\backslash \},\; \backslash \{\backslash \{\backslash \},\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}$ (i.e. $\backslash \{0,1,2\backslash \}$, the Neumann ordinal "3")
• ... etc.

In this way, the number of sets with $n$ bracket pairs is{{Cite OEIS|A004111}}

{{bi|left=1.6|1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, ...}}

The set $\backslash \{\backslash \{\backslash \},\backslash \{\backslash \{\backslash \{\backslash \}\backslash \}\backslash \}\backslash \}$ is an example for such a hereditarily finite set and so is the empty set $\backslash \{\backslash \}$, as noted.

On the other hand, the sets $\backslash \{7,\; \{\backslash mathbb\; N\},\; \backslash pi\backslash \}$ or $\backslash \{3,\; \backslash \{\{\backslash mathbb\; N\}\backslash \}\backslash \}$ 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 $\{\backslash mathbb\; N\}\; =\; \backslash \{0,1,2,\backslash dots\backslash \}$.

The class of all hereditarily finite sets is denoted by $H\_\{\backslash aleph\_0\}$, meaning that the cardinality of each member is smaller than $\backslash aleph\_0$. (Analogously, the class of hereditarily countable sets is denoted by $H\_\{\backslash aleph\_1\}$.)

$H\_\{\backslash aleph\_0\}$ is in bijective correspondence with $\backslash aleph\_0$.

It can also be denoted by $V\_\backslash omega$, which denotes the $\backslash omega$th stage of the von Neumann universe.{{cite web |url=https://ncatlab.org/nlab/show/hereditarily+finite+set |title=hereditarily finite set |author-link=nLab |date=January 2023 |website=nLab |access-date=January 28, 2023 |quote=The set of all (well-founded) hereditarily finite sets (which is infinite, and not hereditarily finite itself) is written $V\_\backslash omega$ to show its place in the von Neumann hierarchy of pure sets.}}

So here it is a countable set.

In 1937, Wilhelm Ackermann introduced an encoding of hereditarily finite sets as natural numbers.{{cite journal|

last=Ackermann|first=Wilhelm| title=Die Widerspruchsfreiheit der allgemeinen Mengenlehre|

journal=Mathematische Annalen|

year=1937|volume=114|pages=305–315|

url=http://www.digizeitschriften.de/dms/img/?PPN=PPN235181684_0114&DMDID=dmdlog23|

access-date=2012-01-09|doi=10.1007/bf01594179

|s2cid=120576556}}{{cite journal|

last=Kirby|first=Laurence|

title=Finitary Set Theory|

journal=Notre Dame Journal of Formal Logic|

year=2009|volume=50|issue=3|pages=227–244|doi=10.1215/00294527-2009-009

|doi-access=free}}{{cite book | last1 = Omodeo | first1 = Eugenio G. | last2 = Policriti | first2 = Alberto | last3 = Tomescu | first3 = Alexandru I. | contribution = 3.3: The Ackermann encoding of hereditarily finite sets | doi = 10.1007/978-3-319-54981-1 | isbn = 978-3-319-54980-4 | mr = 3558535 | pages = 70–71 | publisher = Springer | title = On Sets and Graphs: Perspectives on Logic and Combinatorics | year = 2017}}

It is defined by a function $f\backslash colon\; H\_\{\backslash aleph\_0\}\; \backslash to\; \backslash omega$ that maps each hereditarily finite set to a natural number, given by the following recursive definition:

{{bi|left=1.6|$\backslash displaystyle\; f(a)\; =\; \backslash sum\_\{b\; \backslash in\; a\}\; 2^\{f(b)\}$}}

For example, the empty set $\backslash \{\backslash \}$ contains no members, and is therefore mapped to an empty sum, that is, the number zero. On the other hand, a set with distinct members $a,\; b,\; c,\; \backslash dots$ is mapped to $2^\{f(a)\}\; +\; 2^\{f(b)\}\; +\; 2^\{f(c)\}\; +\; \backslash ldots$.

The inverse is given by

{{bi|left=1.6|$\backslash displaystyle\; f^\{-1\}\backslash colon\backslash omega\backslash to\; H\_\{\backslash aleph\_0\}$}}

{{bi|left=1.6|$\backslash displaystyle\; f^\{-1\}(i)\; =\; \backslash \{f^\{-1\}(j)\; \backslash mid\; \backslash text\{BIT\}(i,\; j)\; =\; 1\backslash \}$}}

where BIT denotes the BIT predicate.

The Ackermann coding can be used to construct a model of finitary set theory in the natural numbers. More precisely, $(\backslash mathbb\{N\},\; \backslash text\{BIT\}^\backslash top)$ (where $\backslash text\{BIT\}^\backslash top$ is the converse relation of $\backslash text\{BIT\}$, swapping its two arguments) models Zermelo–Fraenkel set theory ZF without the axiom of infinity. Here, each natural number models a set, and the $\backslash text\{BIT\}$ relation models the membership relation between sets.

The class $H\_\{\backslash aleph\_0\}$ 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 is the identity):

The root vertex corresponds to the top level bracket $\backslash \{\backslash dots\backslash \}$ and each edge leads to an element (another such set) 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 (e.g. $\backslash \{t,t,s\backslash \}=\backslash \{t,s\backslash \}$, trivializing the permutation of the two subgraphs of shape $t$).

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 and edges correspond to set membership is the Rado graph or random graph.

In the common axiomatic set theory approaches, the empty set $\backslash \{\backslash \}$ also represents the first von Neumann ordinal number, denoted $0$. All finite von Neumann ordinals are indeed hereditarily finite and, thus, so is the class of sets representing the natural numbers. In other words, $H\_\{\backslash aleph\_0\}$ includes each element in the standard model of natural numbers and so a set theory expressing $H\_\{\backslash aleph\_0\}$ 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. All of $H\_\{\backslash aleph\_0\}$ 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 may be added. As the theory validates the other axioms of $\backslash mathsf\{ZF\}$, this establishes that the axiom of infinity is not a consequence of these other $\backslash mathsf\{ZF\}$ axioms.

File:Nested_set_V4.svg    File:Loupe light.svg ]]

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\_\{\backslash omega\}$. Note that this is also a set in this context.

If we denote by $\backslash wp(S)$ the power set of $S$, and by $V\_0$ the empty set, then $V\_\{\backslash omega\}$ can be obtained by setting $V\_\{i+1\}=\backslash wp(V\_i)$ for each integer $i\backslash ge\; 0$. Thus, $V\_\{\backslash omega\}$ can be expressed as

{{bi|left=1.6|$\backslash displaystyle\; V\_\backslash omega\; =\; \backslash bigcup\_\{k=0\}^\backslash infty\; V\_k$}}

and all its elements are finite.

This formulation shows, again, that there are only countably many hereditarily finite sets: $V\_n$ is finite for any finite $n$, its cardinality is $2\backslash uparrow\backslash uparrow\; (n-1)$ in Knuth's up-arrow notation (a tower of $n-1$ 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.

• Constructive set theory
• Finite set
• Hereditary set
• Hereditarily countable set
• Hereditary property
• Rooted trees

{{Reflist}}

{{Set theory}}

Category:Set theory