Ordinal number

Ordinals are mathematical objects that generalize the concept of position (index ) of an element in a (possibly terminating ) sequence on well-orderings over arbitrary (even infinite) quantities. Are positions in the sequences considered as natural numbers ( linguistically expressed by the ordinals "first, second, third, ..." ( element ) ) which form the finite ordinals. What is decisive in this generalization that, as with consequences a smallest position ( the ordinal number zero) exists and each element ( with the exception of any existing last element ) has a unique successor. As (total ) arrangements that satisfy these conditions, can still have very different structures, one introduces an additional condition a, that there should be a minimum index to every non-empty subset of indices, and so find the well-orderings.

Ordinals allow the generalization of limited consequences on methods of proof of complete induction on arbitrarily large amounts or even real classes, provided they can probably arrange, by the method of transfinite induction.

The description of the size of a lot, naive spoken to the number of its elements, in contrast, leads to the concept of cardinal number ( "One, two, three, ...").

Georg Cantor had the idea of ​​how the two concepts - number as size and number as the index - can be generalized within the set theory to infinite sets; because while they coincide for finite sets, one has to distinguish them for infinite sets. Cardinal numbers are defined as special ordinals. The set of ordinals, which you usually denoted by or forms in modern set theory - as well as the entirety of the cardinal numbers - not a lot, but a real class.

For many of these considerations (such as transfinite induction and the definition of cardinal numbers as ordinals ) is the axiom of choice or the equivalent thereto well-ordering theorem needed.

Ordinals are of particular importance for the set theory, in other areas of mathematics, other generalized indexing are used, such as nets and filters, which are of particular importance to the topology and operate over other orders as well-orderings, in particular generalize this as opposed to ordinal the important consequences for the concept of convergence.

History of discovery

The modern mathematical concept of ordinal numbers has been largely developed by the mathematician Georg Cantor. The basic idea he found in studies on the uniqueness of the representation of real functions by trigonometric series. However, the Ordinalzahltheorie for these studies ultimately proved not to be fruitful.

From preliminary work of Eduard Heine was known that the constant in the interval functions have a unique representation as a trigonometric series. Cantor showed (1870 ) that this is true for any function that converges whose trigonometric series everywhere. The question of the existence of other functional classes that have this property, but this does not answer. Even the set of Heine is right for functions that are almost everywhere continuous, ie those with a finite set of points of discontinuity. The question of uniqueness is equivalent to the question whether the disappearance of the trigonometric series

Draws on the amount the disappearance of the coefficients and by itself. Quantities with this property are called sets of the form U ( from the French unicite - uniqueness) and all other quantities - quantities of the type M ( multiplicité - ambiguity ). Finite quantities are quantities Thus, by integrating twice the type U., one obtains the Riemann function:

If is linear, then all and equal. If one were to prove so for a lot of that from the linearity of the following, then so would be referred at the membership of the type U. Cantor used this idea in his article "On the extension of a theorem from the theory of trigonometric series " from 1871 and shows:

If is infinite, then it has at least one accumulation point. Cantor calls the set of accumulation points of a set quantity derived and designated by them, derived from he calls, etc. ( see main article: derivation of a quantity). If after finitely many steps a finite set is reached, Cantor calls the set a lot of ter - art Cantor notes that can also prove the linearity in the interval when finally contains many points of the set, where the correctness this statement on the choice of natural number is not dependent. Quantities with a blank multiple derivation are thus always of type U.

In this article, the Cantor's considerations are not yet beyond finite iteration processes; However, he already has thought patterns that will later characterize the entire set theory. It assigns to illustrate the real numbers by geometric points to a secondary role by defining the real numbers as Cauchy sequences of elements of the set A of rational numbers. The amount of these episodes he labeled B, where it defines the standard for A Computation. Cauchy sequences of elements of the set B form a further amount C. This process can theoretically continue indefinitely. Cantor understood from now on under point an element of any sets A, B, C, ... The construction of such subordinate hierarchies, in which the transition from one stage to the next is through border crossings is later became a frequently used means of introducing new quantitative theoretical concepts. We will see that such a hierarchy can be seen even at the ordinal numbers.

After this paper on trigonometric series, the interest Cantor has weakened to the problem of simultaneously necessary and sufficient condition for the uniqueness of the development of functions in trigonometric series. The question is later very intensively by Paul Du Bois- Reymond, Charles- Jean de la Vallée Poussin, William Henry Young, Arnaud Denjoy, Nina Bari, Raich man and Dmitri Jewgenjewitsch Menshov been studied, but without coming to a satisfactory result. Cantor himself has devoted himself to the task of classifying the point sets then, when the process of deriving ends. Amounts at which that happens after finitely many steps, called Cantor sets of the first kind. A lot is just then a lot of the first genus, if the average

Yet. A natural idea is to make precisely this amount to the first derivative of transfinite order for quantities of the second kind. Cantor is denoted by. This is followed by the derivatives

Cantor writes in his article about infinite linear Punktmannichfaltigkeiten 1880:

In this five -page article not even as good as the whole path has been drawn, how to develop from the natural numbers a complete trans- finite system of ordinal numbers. The concept of ordinal number then he defined in his two articles contributions to the creation of transfinite set theory from 1895/97 as a well-ordered order type quantities.

The natural numbers as ordered sets

The ordinals are in modern mathematics, a concept of set theory. In order to define it as a generalization of the natural numbers, it is obvious to embed the natural numbers in a set-theoretic hierarchy. This one explains the empty set for the zero of the natural number sequence. The empty set is therefore in the Peano axioms of natural numbers specifically marked and not explicitly defined number without predecessors. Following a suggestion by John von Neumann is defined then any other number as the set of numbers that are already defined:

The quantities, etc. are well-ordered by the relation element (). For example, the number 4 has the elements 0, 1, 2, 3, which are ordered as 0 < 1 < 2 <3. It therefore also writes. Is a natural number that is smaller than a number which when an item is from. For the entire set of natural numbers to sets. The amount represents a model of Peano axiom system out its existence is secured in the Zermelo - Fraenkel set theory with the axiom of infinity.

Motivation and definition

The theory of ordinals is an abstraction theory, in which the "true nature" of the amount of the elements will be omitted and only those properties are investigated, which can be derived from their arrangement. We define this: A bijection from the totally ordered set on the totally ordered set is called Ordnungsisomorphismus ( or similar figure), if and are equivalent for all. It is said that the quantities and are is order (or similar) and writes when there is a Ordnungsisomorphismus between and. The total of all amounts each other ordnungsisomorphen represents an equivalence class, the order type is called.

One can show that every finite well-ordered set is order to ( exactly ) is a natural number. In addition, for a well-ordered set, the following three statements are equivalent:

• It is finite.
• The reverse order is a well-ordering.
• Each non-empty subset has a greatest element.

This provides the basis for the generalization of the natural numbers to ordinal numbers that are chosen as a special well-ordered sets such that every well-ordered set is order to exactly one ordinal. Thus, each ordinal is so special representative of a particular order type. The following definition improves Cantor's approach and was first given by John von Neumann:

Definition I. ( sets the foundation axiom advance): A set is ordinal if every element of even a subset of, and with respect to the set inclusion is totally ordered.

Such an amount is automatically well-ordered because of the foundation axiom, which states: Every nonempty set has an element that is to be disjoint. The natural numbers are according to this definition ordinals. For example, a member of a subset and at the same time. is also an ordinal number, the smallest transfinite ordinal number (greater than every natural number ). The Neumann definition is opposite to the first definition has the advantage that it determines from the perspective of basic research properly defined within the axiomatic set theory set-theoretical object. Every well-ordered set is order is to exactly one ordinal number you usually denoted by or.

Remarks and other definitions

The use of equivalence classes of all amounts by Ordnungsisomorphismus applies from the perspective of modern mathematics therefore problematic, because these " incredibly large objects " represent defined genetically and do not substantially von Neumann ordinals in contrast to the. Their existence is assumed in the naive set theory without explicit justification and can not be justified within ZFC without the use of ordinal numbers.

In each set theory is called ordinal such objects that fulfill the Ordinalzahlaxiom. This states: Every well-ordered set (or possibly other well-ordered structure) can be assigned an ordinal that any assigned to two different quantities ordinal if and are equal if the two sets are to each other is order. In all teaching axiomatic set one tries to avoid the introduction of new basic objects to find suitable prescribed by the theory objects that meet the Ordinalzahlaxiom. A possibility for this is particular amount hierarchy (such as the von Neumann numbers) construct.

What difficulties may be the abandonment connected in such hierarchies, can be illustrated by the example of the general linear orders for which one does not know any suitable amount hierarchy ( 2004). Positing the existence of order types can be avoided in this case only by resorting to rank or step functions. After special items that would be suitable for the introduction of ordinals, have already been named, the Ordinalzahlaxiom (if at all possible ) is eliminated ( downgraded to a theorem ). Within ZFC you need for the Adolf Abraham Halevi Fraenkel 1922 the Zermelo's axiom system specially added substitution axiom.

What is the set-theoretic strength of the Ordinalzahlaxioms, indicates the fact that the Infinity, the replacement and for some even the axiom of choice must be used for the proof of the existence of "many " von Neumann ordinals. The von Neumann definition of ordinals is nowadays the most widely used. But even in the axiomatic set teachings definitions of ordinals can be found, based on the formation of equivalence classes. These equivalence classes are, however, in order to avoid contradictions, formed only with certain restrictions. For example, the set of countable ordinals is built by Hartogs so: It is defined as a set of equivalence classes in the subset of well-ordered elements of when. Here are two subsets equivalent if they can be mapped to each other is order. is well-ordered set. This hierarchy can be continued by placing and forms the amounts for. The definition of Hartogs used not authorized selection and is sufficient for many applications of ordinal numbers in analysis and in the topology. Equivalence classes of ordnungsisomorphen quantities are formed in the amount of lessons with step- theoretical structure ( Bertrand Russell, Willard Van Orman Quine, Dana Scott, Klaua and others). In the AM of Klaua eg all quantities of elements Allmengen. The ordinal number of the well-ordered set is then the equivalence class of all to ordnungsisomorphen elements of the smallest Allmenge containing about ordnungsisomorphe quantities. In the Scott - Potter set theory, which is an example of a set theory without substitution axiom, the von Neumann ordinals Pseudoordinalzahlen be called. , The ordinals in this set theory will be defined for each well-ordered collection and refers to the ordinal numbers of well-ordered sets as small ordinals. is the collection of small ordinals and - the smallest large ordinal. A collection of all ordinals is not available in the Scott - Potter set theory. It has already been mentioned that the well-ordering property of the ordinals can be derived in ZF from the foundation axiom. However, it is common in the set-theoretic literature to formulate definitions as independent as possible from the axioms.

The following seven alternative definitions of ordinals are specified, all of which are in ZF without the foundation axiom to each other and in ZF with the foundation axiom also to the above- formulated definitions are equivalent. Before two concepts: A set is transitive if. In words: In a transitive amount contained in the elements with each element of the set of all elements. From this definition follows: A set is transitive exactly when. A set is well-founded if there is a such that and are disjoint.

Definition II by Ernst Zermelo (1915, published 1941):

Definition III by Ernst Zermelo (1915, published 1930), first published Ordinalzahldefinition of John von Neumann (1923 ):

Definition IV of Kurt Gödel (1937, published 1941):

Definition of V by Raphael M. Robinson ( 1937):

Definition VI by Paul Bernays (1941 ):

Definition VII:

Definition VIII:

The last definition is also the same, how to determine the ordinal number of a well-ordered set. The fact that the functions are well defined, it follows from the theorem on transfinite recursion and that their images - called Epsilonbilder - quantities are from the substitution axiom.

Limes and successor numbers

The elements of a ( von Neumann ) ordinal are ordinals themselves. If you have two ordinals and, then is an element of if and only if a proper subset of, and it is true that either is an element of, or an element of, or =. This is defined by the membership relation between elements of an ordinal a irreflexive total order relation. It is even more true: every set of ordinals is well-ordered. This generalizes the well-ordering principle that every set of natural numbers is well-ordered, and allows free use of transfinite induction and the proof method of " infinite descent " on ordinals.

Each ordinal number is just the ordinal numbers as elements that are smaller than. The set-theoretic structure of an ordinal is therefore completely described by smaller ordinals. Each average or association of ordinals is a set of ordinals. Because any set of ordinals is well-ordered, every transitive set of ordinals itself an ordinal (see Definition VII ). It follows that any average or association of ordinals is an ordinal. The union of all elements of a set of ordinals is called supremum of and is denoted by. It is not difficult to show that, for every one and that it exists for every with. For the purposes of this definition, the supremum of the empty set is the empty set, ie the ordinal.

Well-ordered quantities is order to none of their top lines. Therefore exists between two ordinal only a similar picture, if they are equal. The class of all ordinals is not a set (see also: the Burali - Forti paradox ). If it namely a lot, then it would be a well-ordered and transitive set - that is an ordinal number, applies. Ordinal data that contain themselves as an element, but do not exist, they would be required is order to their initial distances ( namely ). From the theorem that a real class, it follows that for every set of ordinals, ordinals exist that are larger than any element of. Under the ordinal numbers that are greater than any element of a set of ordinals, there is always a smallest. They are called upper limit, the quantity and is denoted by.

The least ordinal greater than the ordinal is called successor. The successor of the ordinal is often referred to. This term thus has a meaning outside of transfinite arithmetic ( without being in contradiction to this ). If a greatest element, then this is called a predecessor of and is denoted by. Not every ordinal number has a precursor (such as ). This is called an ordinal a predecessor ( such as ), successor number or numbers of the first kind An ordinal if and only of the first kind, though. The ordinal numbers of the first kind and is called isolated. A positive ordinal without predecessor is called a limit ordinal (or limit number ). A positive ordinal if and only limit ordinal, though. As an ordinal of the second kind is called the Limes figures and the. Each ordinal is therefore a number of either the first or second kind, and either limit ordinal or isolated, which coincide for positive numbers the terms limit number and number of the second kind as well as isolated number and number of the first kind. The number is the only isolated number of the second kind

Infinite sequences of ordinals always contain infinite non-decreasing subsequence.

As a recursive data type

In the meta-mathematics and especially in the proof theory, the ordinals are often defined recursively or axiomatic, as the natural numbers can be defined by the Peano axioms. The purpose of these definitions is, however, in contrast to the Ordinalzahldefinitionen of set theory not to determine a proper class of ordinals, but to find the longest possible initial stretching, which can be defined and analyzed with allowable from the perspective of a metamathematical program funds (see main article: Constructive ordinal number). While there is talk within the metamathematics of writing characters used in set theory and recursion theory, introduced by Stephen Cole Kleene term Ordinalzahlnotation. For the meta-mathematics are mainly from the following well-ordering as well as some arithmetic properties of the ordinals of importance. When one considers the existence of successor and limit numbers as basic properties, then can be within the theory of recursive data types ( inductively defined classes ) formulate the following definition for the class of ordinals. and be the constructors of the recursive data type ordinal - the Fundierer and - a partial order relation on the properties:

• For each chain:
• For each chain:

It is by structural induction to show that a well-ordered class. In the terminology of the theory of the recursive data types are the von Neumann ordinal is an implementation of the recursive data type ordinal number, i.e., a model of the above set of axioms.

Arithmetic operations

The arithmetic operations on ordinals are introduced as a generalization of the well-known from elementary arithmetic arithmetic. Under the sum of two ordinals and refers to the ordinal number of a well-ordered set, which consists of the elements of the two sets, when all the elements of standing in the well-ordering from the elements of. This corresponds exactly to the idea that is familiar to us from the finite numbers that the concatenation of two finite sequences of length and a finite sequence of length arises. You have to differentiate among the transfinite ordinals between isolated and Limes numbers, care is taken in the implementation of the arithmetic operations that these continuous extensions of finite arithmetic operations. The continuity of the arithmetic operations in the ordinals can be seen most clearly in the so-called functional introduction of transfinite arithmetic. The functional introduction of ordinal arithmetic is established by means of transfinite recursion. Not all known from the finite arithmetic properties of the arithmetic operations are transferable to infinity. Thus, the addition is not commutative in general. Using the Cantor polynomial, which is a kind of trans- finite value system, alternative arithmetic operations can be introduced: the so- called natural operations between ordinals, so that none of the known from the finite arithmetic rules must be missing.

Topological properties

Any ordinal can be done to a topological space due to their total order by the order topology. In this topology, the sequence (0, 1, 2, ... ) to ω, and the sequence

Converges to ε0. Ordinals without predecessors can always be represented as the limit of a network of smaller ordinals, such as the network of all smaller ordinals with their natural order. The cardinality of the smallest such a network is called cofinality. This may be uncountable, ie, generally those ordinals are not the limit of a sequence of smaller ordinals, such as the smallest uncountable ordinal ω1.

The topological spaces ω1 and ω1 1 are often mentioned in textbooks as an example of a non- countable topology. For example, applies in space ω1 1, the element ω1 is in the completion of the subset of ω1, but no sequence converges to ω1 against the element ω1. The space ω1 satisfies the first but not the second axiom of countability and ω1 1 neither.

The space ω1 has exactly one ( Hausdorff ) compactification, namely ω1 1. This means that the maximum possible, the Stone - Čech compactification coincides here with the smallest possible, the single-point or Alexandroff compactification.