Editing Hereditarily finite set

{{Short description|Finite sets whose elements are all hereditarily finite sets}}
In [[mathematics]] and [[set theory]], '''hereditarily finite sets''' are defined as [[finite set]]s 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-foundedness|well-founded]] hereditarily finite sets is as follows:
: ''Base case'': The empty set is a hereditarily finite set.
: ''Recursion rule'': If <math>a_1,\dots a_k</math> are hereditarily finite, then so is <math>\{a_1,\dots a_k\}</math>.
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:

* <math>\{\}</math> (i.e. <math>\emptyset</math>, the Neumann ordinal "0")
* <math>\{\{\}\}</math> (i.e. <math>\{\emptyset\}</math> or <math>\{0\}</math>, the Neumann ordinal "1")
* <math>\{\{\{\}\}\}</math>
* <math>\{\{\{\{\}\}\}\}</math> and then also <math>\{\{\},\{\{\}\}\}</math> (i.e. <math>\{0,1\}</math>, the Neumann ordinal "2"),
* <math>\{\{\{\{\{\}\}\}\}\}</math>, <math>\{\{\{\},\{\{\}\}\}\}</math> as well as <math>\{\{\},\{\{\{\}\}\}\}</math>,
* ... sets represented with <math>6</math> bracket pairs, e.g. <math>\{\{\{\{\{\{\}\}\}\}\}\}</math>. There are six such sets
* ... sets represented with <math>7</math> bracket pairs, e.g. <math>\{\{\{\{\{\{\{\}\}\}\}\}\}\}</math>. There are twelve such sets
* ... sets represented with <math>8</math> bracket pairs, e.g. <math>\{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}</math> or <math>\{\{\}, \{\{\}\}, \{\{\},\{\{\}\}\}\}</math> (i.e. <math>\{0,1,2\}</math>, the Neumann ordinal "3")
* ... etc.
In this way, the number of sets with <math>n</math> bracket pairs is<ref>{{Cite OEIS|A004111}}</ref>
{{bi|left=1.6|1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, ...}}

==Discussion==
The set <math>\{\{\},\{\{\{\}\}\}\}</math> is an example for such a hereditarily finite set and so is the empty set <math>\{\}</math>, as noted. 
On the other hand, the sets <math>\{7, {\mathbb N}, \pi\}</math> or <math>\{3, \{{\mathbb N}\}\}</math> 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 <math>{\mathbb N} = \{0,1,2,\dots\}</math>.

The class of all hereditarily finite sets is denoted by <math>H_{\aleph_0}</math>, meaning that the cardinality of each member is smaller than <math>\aleph_0</math>. (Analogously, the class of [[hereditarily countable set|hereditarily ''countable'' set]]s is denoted by <math>H_{\aleph_1}</math>.)
<math>H_{\aleph_0}</math> is in bijective correspondence with <math>\aleph_0</math>.
It can also be denoted by <math>V_\omega</math>, which denotes the <math>\omega</math>th stage of the [[von Neumann universe]].<ref>{{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 <math>V_\omega</math> to show its place in the von Neumann hierarchy of pure sets.}}</ref>
So here it is a [[Countable set|countable]] set.

==Models==
===Ackermann coding===
In 1937, [[Wilhelm Ackermann]] introduced an encoding of hereditarily finite sets as natural numbers.<ref name=ackermann>{{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}}</ref><ref>{{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}}</ref><ref>{{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}}</ref>
It is defined by a function <math>f\colon H_{\aleph_0} \to \omega</math> that maps each hereditarily finite set to a natural number, given by the following recursive definition:
{{bi|left=1.6|<math>\displaystyle f(a) = \sum_{b \in a} 2^{f(b)}</math>}}
For example, the empty set <math>\{\}</math> 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 <math>a, b, c, \dots</math> is mapped to <math>2^{f(a)} + 2^{f(b)} + 2^{f(c)} + \ldots</math>.

The inverse is given by
{{bi|left=1.6|<math>\displaystyle f^{-1}\colon\omega\to H_{\aleph_0}</math>}}
{{bi|left=1.6|<math>\displaystyle f^{-1}(i) = \{f^{-1}(j) \mid \text{BIT}(i, j) = 1\}</math>}}
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, <math>(\mathbb{N}, \text{BIT}^\top)</math> (where <math>\text{BIT}^\top</math> is the [[converse relation]] of <math>\text{BIT}</math>, swapping its two arguments) models [[Zermelo–Fraenkel set theory]] ZF without the [[axiom of infinity]]. Here, each natural number models a set, and the <math>\text{BIT}</math> relation models the membership relation between sets.

===Graph models===
The class <math>H_{\aleph_0}</math> can be seen to be in exact correspondence with a class of [[Tree (graph theory)#Rooted tree|rooted trees]], namely those without non-trivial symmetries (i.e. the only [[Graph automorphism|automorphism]] is the identity): 
The root vertex corresponds to the top level bracket <math>\{\dots\}</math> and each [[Vertex (graph theory)|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. <math>\{t,t,s\}=\{t,s\}</math>, trivializing the permutation of the two subgraphs of shape <math>t</math>).
This graph model enables an implementation of ZF without infinity as data types and thus an interpretation of set theory in expressive [[type theory|type theories]].

Graph [[model theory|model]]s exist for ZF and also set theories different from Zermelo set theory, such as [[Aczel's anti-foundation axiom|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===
In the common axiomatic set theory approaches, the empty set <math>\{\}</math> also represents the first von Neumann [[ordinal number]], denoted <math>0</math>. All finite von Neumann ordinals are indeed hereditarily finite and, thus, so is the class of sets representing the natural numbers. In other words, <math>H_{\aleph_0}</math> includes each element in the [[Set-theoretic definition of natural numbers|standard model of natural numbers]] and so a set theory expressing <math>H_{\aleph_0}</math> must necessarily contain them as well.

Now note that [[Robinson arithmetic]] can already be interpreted in [[General set theory|ST]], the very small sub-theory of [[Zermelo set theory]] Z<sup>&minus;</sup> with its [[axioms]] given by [[Axiom of Extensionality|Extensionality]], Empty Set and [[General set theory|Adjunction]]. All of <math>H_{\aleph_0}</math> has a [[Constructive set theory|constructive axiomatization]] involving these axioms and e.g. [[Epsilon induction|Set induction]] and [[Axiom of replacement|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 <math>\mathsf{ZF}</math>, this establishes that the axiom of infinity is not a consequence of these other <math>\mathsf{ZF}</math> axioms.

===ZF===
[[File:Nested_set_V4.svg|thumb|400px|<math>~V_4~</math> represented with circles in place of [[Bracket (mathematics)#Sets and groups|curly brackets]]&nbsp;&nbsp;&nbsp;&nbsp;[[File:Loupe light.svg|15px|link=http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Nested_set_V4.svg/1600px-Nested_set_V4.svg.png]] ]]

The hereditarily finite sets are a subclass of the [[Von Neumann universe]]. Here, the class of all well-founded hereditarily finite sets is denoted <math>V_{\omega}</math>. Note that this is also a set in this context.

If we denote by <math>\wp(S)</math> the [[power set]] of <math>S</math>, and by <math>V_0</math> the empty set, then <math>V_{\omega}</math> can be obtained by setting <math>V_{i+1}=\wp(V_i)</math> for each integer <math>i\ge 0</math>. Thus, <math>V_{\omega}</math> can be expressed as
{{bi|left=1.6|<math>\displaystyle V_\omega = \bigcup_{k=0}^\infty V_k</math>}}
and all its elements are finite.

This formulation shows, again, that there are only [[countably]] many hereditarily finite sets: <math>V_n</math> is finite for any finite <math>n</math>, its [[cardinality]] is <math>2\uparrow\uparrow (n-1)</math> in [[Knuth's up-arrow notation]] (a tower of <math>n-1</math> 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 set|transitive closure]] is finite.

==See also==
* [[Constructive set theory]]
* [[Finite set]]
* [[Hereditary set]]
* [[Hereditarily countable set]]
* [[Hereditary property]]
* [[Tree (graph theory)#Rooted tree|Rooted trees]]

==References==
{{Reflist}}

{{Set theory}}

[[Category:Set theory]]