Axiom of infinity
From Wikipedia, the free encyclopedia
In 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.
[edit] Formal statement
In the formal language of the Zermelo-Fraenkel axioms, the axiom reads:
or in words: There is a set N, such that the empty set is in N and such that whenever x is a member of N, the set formed by taking the union of x with its singleton {x} is also a member of N. Such a set is sometimes called an inductive set.
[edit] Interpretation and consequences
To understand this axiom, first we define the successor of x as x ∪ {x}. Note that the axiom of pairing allows us to form the singleton {x}, and also to form the pair. Successors are used to define the usual set theory encoding of the natural numbers. In this encoding, zero is the empty set (0 = {}), and 1 is the successor of 0:
1 = 0 ∪ {0} = {} ∪ {0} = {0}.
Likewise, 2 is the successor of 1:
2 = 1 ∪ {1} = {0} ∪ {1} = {0,1},
and so on. A consequence of this definition is that every natural number is equal to the set of all preceding natural numbers.
We want to form the set of all natural numbers. However, the other axioms are apparently insufficient to prove the existence of the set of all natural numbers. So its existence must be taken as an axiom — the axiom of infinity. This axiom asserts that there is a set S that contains zero, and then for each element of S, the successor of that element is also in S. This is related to mathematical induction.
This set S is a superset of the natural numbers. So to show that the natural numbers themselves constitute a set, we apply the axiom schema of specification to remove unwanted elements, leaving the set N of all natural numbers. This set is unique by the axiom of extensionality. The result of applying the axiom of separation is:
In words, the set of all natural numbers exists; where a natural number is either zero or a successor and each of its elements is either zero or a successor of another of its elements.
Thus the essence of the axiom is:
There is a set containing all the natural numbers.
The axiom of infinity is also one of the von Neumann-Bernays-Gödel axioms.
The cardinality of the set of natural numbers, Aleph null, has many of the properties of a large cardinal. Thus the axiom of infinity is sometimes regarded as the first large cardinal axiom.
[edit] References
- Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
- Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
- Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.