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:
: 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
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, \