Concept
Ordinal notation
Related concepts (7)
Hyperarithmetical theory
In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an important tool in effective descriptive set theory. The central focus of hyperarithmetic theory is the sets of natural numbers known as hyperarithmetic sets. There are three equivalent ways of defining this class of sets; the study of the relationships between these different definitions is one motivation for the study of hyperarithmetical theory.
Ordinal analysis
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory. The field of ordinal analysis was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that the proof-theoretic ordinal of Peano arithmetic is ε0.
Computable ordinal
In mathematics, specifically computability and set theory, an ordinal is said to be computable or recursive if there is a computable well-ordering of a computable subset of the natural numbers having the order type . It is easy to check that is computable. The successor of a computable ordinal is computable, and the set of all computable ordinals is closed downwards. The supremum of all computable ordinals is called the Church–Kleene ordinal, the first nonrecursive ordinal, and denoted by .
First uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by or sometimes by , is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum (least upper bound) of all countable ordinals. When considered as a set, the elements of are the countable ordinals (including finite ordinals), of which there are uncountably many. Like any ordinal number (in von Neumann's approach), is a well-ordered set, with set membership serving as the order relation. is a limit ordinal, i.
Large countable ordinal
In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations (see ordinal analysis). However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not (for reasons somewhat analogous to the unsolvability of the halting problem); various more-concrete ways of defining ordinals that definitely have notations are available.
Epsilon number
In mathematics, the epsilon numbers are a collection of transfinite numbers whose defining property is that they are fixed points of an exponential map. Consequently, they are not reachable from 0 via a finite series of applications of the chosen exponential map and of "weaker" operations like addition and multiplication. The original epsilon numbers were introduced by Georg Cantor in the context of ordinal arithmetic; they are the ordinal numbers ε that satisfy the equation in which ω is the smallest infinite ordinal.
Ordinal arithmetic
In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.