Editing Hereditarily finite set (section)

==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.