FANDOM


Baptist Church

This church is not to be confused with logician Alonzo Church. It is probably very clean.

An ordinal is considered recursive iff it is the order type of a computable well-ordering of a subset of the natural numbers. The Church-Kleene ordinal \(\omega_1^\text{CK}\), then, is the first ordinal that is not recursive.

An ordinal is always recursive iff it is less than another recursive ordinal, so the Church-Kleene ordinal is also the supremum of all recursive ordinals. It is a limit ordinal, since the successor of a recursive ordinal is also recursive. Since every computable well-ordering can be identified by a distinct Turing machine, of which there are countably many, \(\omega_1^\text{CK}\) is also countable.

Ordinal notation Edit

A system called Kleene's \(\mathcal{O}\) gives us an ordinal notation over all recursive ordinals. Before constructing Kleene's \(\mathcal{O}\), first we need an enumeration \(f_0, f_1, f_2, \ldots\) of all the partial recursive functions. One way to do this is to order all the Turing machines lexicographically.

Let \(K\) be the set of all notations, let \(<_\mathcal{O}\) be an operator indicating a well-ordering of \(K\), and let \(\mathcal{O}\) be a function mapping notations to ordinals. These three are defined inductively as follows:

  • \(0 \in K\) and \(\mathcal{O}(0) = 0\).
  • If \(n \in K\) and \(\mathcal{O}(n) = \alpha\), then \(2^n \in K\), \(\mathcal{O}(2^n) = \alpha + 1\), and \(n <_\mathcal{O} 2^n\).
  • If for all natural numbers \(n\), we have \(f_i(n) \in K\) and \(f_i(n) <_\mathcal{O} f_i(n + 1)\), then \(3 \cdot 5^i \in K\), \(\mathcal{O}(3 \cdot 5^i) = \lim_{k \rightarrow \omega} \mathcal{O}(f_i(k))\), and for all \(k\) \(f_i(k) <_\mathcal{O} 3 \cdot 5^i\).
  • \(a <_\mathcal{O} b\) and \(b <_\mathcal{O} c\) implies \(a <_\mathcal{O} c\).

Kleene's \(\mathcal{O}\) is, inescapably, not a computable notation.

See also Edit

Ordinals, ordinal analysis and set theory

Basics: cardinal numbers · normal function · ordinal notation · ordinal numbers
Theories: Presburger arithmetic · Peano arithmetic · second-order arithmetic · ZFC
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\Gamma_0\) · \(\vartheta(\Omega^3)\) · \(\vartheta(\Omega^\omega)\) · \(\vartheta(\Omega^\Omega)\) · \(\vartheta(\varepsilon_{\Omega + 1})\) · \(\psi(\Omega_\omega)\) · \(\psi(\varepsilon_{\Omega_\omega + 1})\) · \(\psi(\psi_I(0))\)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^\text{CK}\) · \(\lambda,\zeta,\Sigma,\gamma\) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal · more...

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.