# Difference between revisions of "Feferman-Schütte"

Line 34: | Line 34: | ||

*if \(\alpha<\beta\) then \(\varphi_\alpha(0)<\varphi_\beta(0)\) | *if \(\alpha<\beta\) then \(\varphi_\alpha(0)<\varphi_\beta(0)\) | ||

*if \(\alpha>\gamma\) then \(\varphi_\alpha(\beta)=\varphi_\gamma(\varphi_\alpha(\beta))\) | *if \(\alpha>\gamma\) then \(\varphi_\alpha(\beta)=\varphi_\gamma(\varphi_\alpha(\beta))\) | ||

− | * | + | *\(\varphi_\alpha(\beta)\) is an additive principal number. |

An ordinal \(\alpha\) is an additive principal number if \(\alpha>0\) and \(\alpha>\delta+\eta\) for all \(\delta, \eta<\alpha\). Let \(P\) denote the set of all additive principal numbers. | An ordinal \(\alpha\) is an additive principal number if \(\alpha>0\) and \(\alpha>\delta+\eta\) for all \(\delta, \eta<\alpha\). Let \(P\) denote the set of all additive principal numbers. |

## Latest revision as of 01:49, 22 May 2018

The Feferman-Schütte ordinal, denoted $\Gamma_0$ ("gamma naught"), is the first ordinal fixed point of the Veblen function. It figures prominently in the ordinal-analysis of the proof-theoretic strength of several mathematical theories.

This page needs additional information.

## Veblen hierarchy

Every increasing continuous ordinal function $f$ has an unbounded set of fixed points;

Proof |
---|

When $f$ is increasing, $f(\alpha)\geq \alpha$ for all $\alpha$; when also continuous,
$$ f ( \cup_n f^n (\alpha + 1)) = \cup_n f^n (\alpha + 1) $$ is a fixed point greater than $\alpha$ |

Since the set of fixed points is an unbounded, well-ordered set, there is an ordinal function $\varphi^{[f]}$ listing these fixedpoints; it is in turn increasing and continuous. The **Veblen Hierarchy** is the sequence of functions $\varphi_\alpha$ defined by

- $\varphi_0 x = \omega^x$
- $\varphi_{\alpha + 1} = \varphi^{[\varphi_\alpha]}$
- for $ 0 \lt \beta = \cup \beta $, $\varphi_\beta(x)$ enumerates the fixedpoints common to all $\varphi_\alpha$ for $\alpha \lt \beta$

(For $\alpha \lt \beta$, the fixed point sets of $\varphi_\alpha$ are all closed sets, and so their intersection is closed; it is unbounded because $\cup_\alpha \varphi_\alpha(t+1)$ is a common fixed point greater than $t$)

In particular the function \(\varphi_1\) enumerates epsilon numbers i.e. \(\varphi_1(\alpha)=\varepsilon_\alpha\)

The Veblen functions have the following properties:

- if \(\beta<\gamma\) then \(\varphi_\alpha(\beta)<\varphi_\alpha(\gamma)\)
- if \(\alpha<\beta\) then \(\varphi_\alpha(0)<\varphi_\beta(0)\)
- if \(\alpha>\gamma\) then \(\varphi_\alpha(\beta)=\varphi_\gamma(\varphi_\alpha(\beta))\)
- \(\varphi_\alpha(\beta)\) is an additive principal number.

An ordinal \(\alpha\) is an additive principal number if \(\alpha>0\) and \(\alpha>\delta+\eta\) for all \(\delta, \eta<\alpha\). Let \(P\) denote the set of all additive principal numbers.

We define the normal form for ordinals \(\alpha\) such that \(0<\alpha<\Gamma_0=\min\{\beta|\varphi(\beta,0)=\beta\}\)

- \(\alpha=_{NF}\varphi_\beta(\gamma)\) if and only if \(\alpha=\varphi_\beta(\gamma)\) and \(\beta,\gamma<\alpha\)
- \(\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n\) if and only if \(\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n\) and \(\alpha>\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_n\) and \(\alpha_1,\alpha_2,...,\alpha_n\in P\)

Let \(T\) denote the set of all ordinals which can be generated from the ordinal number 0 using the Veblen functions and the operation of addition

- \(0 \in T\)
- if \(\alpha=_{NF}\varphi_\beta(\gamma)\) and \(\beta,\gamma \in T\) then \(\alpha\in T\)
- if \(\alpha=_{NF}\alpha_1+\alpha_2+\cdots+\alpha_n\) and \(\alpha_1,\alpha_2,...,\alpha_n\in T\) then \(\alpha\in T\)

For each limit ordinal number \(\alpha\in T\) we assign a fundamental sequence i.e. a strictly increasing sequence \((\alpha[n])_{n<\omega}\) such that the limit of the sequence is the ordinal number \(\alpha\)

- if \(\alpha=\alpha_1+\alpha_2+\cdots+\alpha_k\) then \(\alpha[n]=\alpha_1+\alpha_2+\cdots+(\alpha_k[n])\)
- if \(\alpha=\varphi_0(\beta+1)\) then \(\alpha[n]=\varphi_0(\beta)\times n\)
- if \(\alpha=\varphi_{\beta+1}(0)\) then \(\alpha[0]=0\) and \(\alpha[n+1]=\varphi_\beta(\alpha[n])\)
- if \(\alpha=\varphi_{\beta+1}(\gamma+1)\) then \(\alpha[0]=\varphi_{\beta+1}(\gamma)+1\) and \(\alpha[n+1]=\varphi_\beta(\alpha[n])\)
- if \(\alpha=\varphi_{\beta}(\gamma)\) and \(\gamma\) is a limit ordinal then \(\alpha[n]=\varphi_{\beta}(\gamma[n])\)
- if \(\alpha=\varphi_{\beta}(0)\) and \(\beta\) is a limit ordinal then \(\alpha[n]=\varphi_{\beta[n]}(0)\)
- if \(\alpha=\varphi_{\beta}(\gamma+1)\) and \(\beta\) is a limit ordinal then \(\alpha[n]=\varphi_{\beta[n]}(\varphi_{\beta}(\gamma)+1)\)

The Feferman-Schütte ordinal, \(\Gamma_0\) is the least ordinal not in \(T\).

## Gamma function

The Gamma function is a function enumerating ordinal numbers \(\alpha\) such that \(\varphi(\alpha,0)=\alpha\)

- if \(\alpha=\Gamma_0\) then \(\alpha[0]=0\) and \(\alpha[n+1]=\varphi(\alpha[n],0)\)
- if \(\alpha=\Gamma_{\beta+1}\) then \(\alpha[0]=\Gamma_{\beta}+1\) and \(\alpha[n+1]=\varphi(\alpha[n],0)\)
- if \(\alpha=\Gamma_{\beta}\) and \(\beta\) is a limit ordinal then \(\alpha[n]=\Gamma_{\beta[n]}\)

## References

Oswald Veblen. Continuous Increasing Functions of Finite and Transfinite Ordinals. Transactions of the American Mathematical Society (1908) Vol. 9, pp.280–292