Difference between revisions of "Church-Kleene"

From Cantor's Attic
Jump to: navigation, search
(Created page with "{{DISPLAYTITLE: The Church-Kleene ordinal $\omega_1^{ck}$}} The ''Church-Kleene'' ordinal $\omega_1^{ck}$ is the supremum of the computable ordinals, where an ordinal $\alpha$ i...")
 
Line 1: Line 1:
{{DISPLAYTITLE: The Church-Kleene ordinal $\omega_1^{ck}$}}
+
{{DISPLAYTITLE: The Church-Kleene ordinal, $\omega_1^{ck}$}}
  
 
The ''Church-Kleene'' ordinal $\omega_1^{ck}$ is the supremum of the computable ordinals, where an ordinal $\alpha$ is ''computable'' if there is a computable relation $\triangle$ on $\mathbb{N}$ of order type $\alpha$, that is, such that $\langle\alpha,\lt\rangle\cong\langle\mathbb{N},\triangle\rangle$.  
 
The ''Church-Kleene'' ordinal $\omega_1^{ck}$ is the supremum of the computable ordinals, where an ordinal $\alpha$ is ''computable'' if there is a computable relation $\triangle$ on $\mathbb{N}$ of order type $\alpha$, that is, such that $\langle\alpha,\lt\rangle\cong\langle\mathbb{N},\triangle\rangle$.  

Revision as of 08:25, 30 December 2011


The Church-Kleene ordinal $\omega_1^{ck}$ is the supremum of the computable ordinals, where an ordinal $\alpha$ is computable if there is a computable relation $\triangle$ on $\mathbb{N}$ of order type $\alpha$, that is, such that $\langle\alpha,\lt\rangle\cong\langle\mathbb{N},\triangle\rangle$.

This ordinal is closed under all of the elementary ordinal arithmetic operations, such as successor, addition, multiplication and exponentiation.

The Church-Kleene ordinal is the least admissible ordinal.

Relativized Church-Kleene ordinal

The Church-Kleene idea easily relativizes to oracles, where for any real $x$, we define $\omega_1^x$ to be the supremum of the $x$-computable ordinals. This is also the least admissible ordinal relative to $x$, and every countable admissible ordinal is $\omega_1^x$ for some $x$.


    This article is a stub. Please help us to improve Cantor's Attic by adding information.