In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and
set theorySet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
,
hereditarily finite sets are defined
recursivelyRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
as
finite sets consisting of 0 or more hereditarily finite sets.
Formal definition
A recursive definition of a hereditarily finite set goes as follows:
- Base case: The empty set is a hereditarily finite set.
- Recursion rule: If a_{1},...,a_{k} are hereditarily finite, then so is {a_{1},...,a_{k}}.
The set of all hereditarily finite sets is denoted
V_{ω}. If we denote
P(
S) for the
power set of
S,
V_{ω} can also be constructed by first taking the empty set written
V_{0}, then
V_{1} =
P(
V_{0}),
V_{2} =
P(
V_{1}),...,
V_{k} =
P(
V_{k−1}),... Then
Discussion
The hereditarily finite sets are a subclass of the
Von Neumann universeIn set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted V, is the class of hereditary well-founded sets...
. They are a
modelIn mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of the axioms consisting of the axioms of set theory with the
axiom of infinityIn axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory...
replaced by its negation, thus proving that the axiom of infinity is not a consequence of the other axioms of set theory.
Notice that there are countably many hereditarily finite sets, since
V_{n} is finite for any finite
n (its
cardinality is
^{n−1}2, see
tetrationIn mathematics, tetration is an iterated exponential and is the next hyper operator after exponentiation. The word tetration was coined by English mathematician Reuben Louis Goodstein from tetra- and iteration. Tetration is used for the notation of very large numbers...
), and the union of countably many finite sets is countable.
Equivalently, a set is hereditarily finite if and only if its
transitive closureIn set theory, a set A is transitive, if* whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently,* whenever x ∈ A, and x is not an urelement, then x is a subset of A....
is finite. V
_{ω} is also symbolized by
, meaning hereditarily of cardinality less than
.