Difference between revisions of "Church-Kleene"

From Cantor's Attic
Jump to: navigation, search
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 $\lhd$ on $\mathbb{N}$ of order type $\alpha$, that is, such that $\langle\alpha,\lt\rangle\cong\langle\mathbb{N},\lhd\rangle$.  
  
 
This ordinal is closed under all of the elementary ordinal arithmetic operations, such as successor, addition, multiplication and exponentiation.  
 
This ordinal is closed under all of the elementary ordinal arithmetic operations, such as successor, addition, multiplication and exponentiation.  

Revision as of 11:07, 9 January 2012


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 $\lhd$ on $\mathbb{N}$ of order type $\alpha$, that is, such that $\langle\alpha,\lt\rangle\cong\langle\mathbb{N},\lhd\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.