Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Hereditarily finite set
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.