Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Hereditarily finite set
Summary
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.
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 a1,...,ak are hereditarily finite, then so is {a1,...,ak}.
and only sets that can be built by a finite number of applications of these two rules are hereditarily finite.
The set is an example for such a hereditarily finite set and so is the empty set .
On the other hand, the sets or 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 .
The class of hereditarily finite sets is denoted by , meaning that the cardinality of each member is smaller than . (Analogously, the class of hereditarily countable sets is denoted by .)
It can also be denoted by , which denotes the th stage of the von Neumann universe.
The class is countable.
In 1937, Wilhelm Ackermann introduced an encoding of hereditarily finite sets as natural numbers.
It is defined by a function that maps each hereditarily finite set to a natural number, given by the following recursive definition:
For example, the empty set 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 is mapped to .
The inverse of , which maps natural numbers back to sets, is
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, (where is the converse relation of BIT, swapping its two arguments) models Zermelo–Fraenkel set theory without the axiom of infinity. Here, each natural number models a set, and the BIT relation models the membership relation between sets.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.