Feferman–Schütte ordinal

(Redirected from Feferman-Schutte ordinal) Large countable ordinal

In mathematics, the Feferman–Schütte ordinal (Γ₀) is a large countable ordinal. It is the proof-theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion. It is named after Solomon Feferman and Kurt Schütte, the former of whom suggested the name Γ₀.

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 functions: $\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 functions φ_α(β). 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 Γ₀.

Any recursive path ordering whose function symbols are well-founded with order type less than that of Γ₀ itself has order type less than Γ₀.

References

Gaisi Takeuti, Proof Theory (1975, p.413)
Kurt Schütte, Proof theory, Grundlehren der Mathematischen Wissenschaften, Band 225, Springer-Verlag, Berlin, Heidelberg, New York, 1977, xii + 302 pp.
Solomon Feferman, "Predicativity" (2002)
Nachum Dershowitz, Termination of Rewriting (pp.98--99), Journal of Symbolic Computation (1987). Accessed 3 October 2022.

Pohlers, Wolfram (1989), Proof theory, Lecture Notes in Mathematics, vol. 1407, Berlin: Springer-Verlag, doi:10.1007/978-3-540-46825-7, ISBN 3-540-51842-8, MR 1026933
Weaver, Nik (2005), Predicativity beyond Gamma_0, arXiv:math/0509244, Bibcode:2005math......9244W

v t e Large countable ordinals
First infinite ordinal ω Epsilon numbers ε₀ Feferman–Schütte ordinal Γ₀ Ackermann ordinal θ(Ω) small Veblen ordinal θ(Ω) large Veblen ordinal θ(Ω) Bachmann–Howard ordinal ψ(ε_Ω+1) Buchholz's ordinal ψ₀(Ω_ω) Takeuti–Feferman–Buchholz ordinal ψ(ε_{Ω_ω+1}) Proof-theoretic ordinals of the theories of iterated inductive definitions Computable ordinals < ω‍ ₁ Nonrecursive ordinal ≥ ω‍ ₁ First uncountable ordinal Ω

Large countable ordinals

First infinite ordinal ω
Epsilon numbers ε₀
Feferman–Schütte ordinal Γ₀
Ackermann ordinal θ(Ω)
small Veblen ordinal θ(Ω)
large Veblen ordinal θ(Ω)
Bachmann–Howard ordinal ψ(ε_Ω+1)
Buchholz's ordinal ψ₀(Ω_ω)
Takeuti–Feferman–Buchholz ordinal ψ(ε_{Ω_ω+1})
Proof-theoretic ordinals of the theories of iterated inductive definitions
Computable ordinals < ω‍
₁
Nonrecursive ordinal ≥ ω‍
₁
First uncountable ordinal Ω

This set theory-related article is a stub. You can help Misplaced Pages by expanding it.

This article about a number is a stub. You can help Misplaced Pages by expanding it.

Categories: