Feferman–Schütte Ordinal
   HOME

TheInfoList



OR:

In mathematics, the Feferman–Schütte ordinal (Γ0) is a
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 relev ...
. It is the proof-theoretic ordinal of several mathematical theories, such as
arithmetical transfinite recursion In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. A precur ...
. It is named after
Solomon Feferman Solomon Feferman (December 13, 1928July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. In addition to his prolific technical work in proof theory, computability theory, and set theory, he was known for h ...
and Kurt Schütte, the former of whom suggested the name Γ0. There is no standard notation for ordinals beyond the Feferman–Schütte ordinal. There are several ways of representing the Feferman–Schütte ordinal, some of which use
ordinal collapsing function In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (Ordinal notation, notations for) certain Recursive ordinal, recursive large countable ordinals, whose principle is to give n ...
s: \psi(\Omega^\Omega), \theta(\Omega), \varphi_\Omega(0), or \varphi(1,0,0).


Definition

The Feferman–Schütte ordinal can be defined as the smallest ordinal that cannot be obtained by starting with 0 and using the operations of ordinal addition and the
Veblen function In mathematics, the Veblen functions are a hierarchy of normal functions ( continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If ''φ''0 is any normal function, then for any non-zero ordinal '' ...
s ''φ''''α''(''β''). That is, it is the smallest ''α'' such that ''φ''''α''(0) = ''α''.


Properties

This ordinal is sometimes said to be the first impredicative ordinal, though this is controversial, partly because there is no generally accepted precise definition of " predicative". Sometimes an ordinal is said to be predicative if it is less than Γ0. Any recursive path ordering whose function symbols are well-founded with order type less than that of Γ0 itself has order type less than Γ0.
Nachum Dershowitz Nachum Dershowitz () is an Israeli computer scientist, known e.g. for the Dershowitz–Manna ordering and the Path_ordering_(term_rewriting), multiset path ordering used to prove Rewriting#Termination, termination of term rewrite systems. Educat ...

Termination of Rewriting
(pp.98--99),
Journal of Symbolic Computation The ''Journal of Symbolic Computation'' is a Peer review, peer-reviewed monthly scientific journal covering all aspects of symbolic computation published by Academic Press and then by Elsevier. It is targeted to both mathematicians and computer sc ...
(1987). Accessed 3 October 2022.


References

* * Proof theory Ordinal numbers {{number-stub