O de Kleene

Na teoria dos conjuntos e teoria da computação, ${\mathcal {O}}$ de Kleene é um sub conjunto canônico dos números naturais quando considerado como notação ordinal. Ele contém notações ordinais para cada ordinal recursivo, isto é, um ordinal sob os ordinais Church-Kleene $\omega _{1}^{CK}$. Desde $\omega _{1}^{CK}$ é o primeiro ordinal não representado num sistema de ordinais computáveis, os elementos de ${\mathcal {O}}$ podem ser considerados como notações ordinais canônicas.

Kleene (1938) descreve um sistema de notação para todos os ordinais recursivos (exceto os ordinais Church-Kleene). Ele usa um sub-conjunto de números naturais em vez de cadeias de símbolos finitas. Infelizmente, não existe um modo efetivo para dizer que um número natural representa um ordinal, ou então que dois números representam o mesmo ordinal. Contudo, podemos achar notações que representem uma soma, uma multiplicação e exponenciação de ordinais de quaisquer duas notações em O de Kleene ${\mathcal {O}}$; e dada qualquer notação de um ordinal, existe um conjunto enumerável recursivo de notações os quais contém um elemento para cada ordinal menor e é efetivamente ordenado.

${\mathcal {O}}$ de Kleene

A ideia básica do sistema de notações ordinais de Kleene é construir ordinais de uma maneira eficiente. Para membros $p$ de ${\mathcal {O}}$, o ordinal para o qual $p$ é um notação é $|p|$. The definição comum procede por uma transdução infinita e a ordenação $<_{\mathcal {O}}$ (uma ordennação parcial de ${\mathcal {O}}$ de Kleene) é definida simutâneamente.

• O número natural 0 pertence à ${\mathcal {O}}$ de Kleene e $|0|=0$.
• Se $i$ pertence à ${\mathcal {O}}$ de Kleene e $|i|=\alpha$, então pertence à $2^{i}$ de Kleene e ${\mathcal {O}}$ e $|2^{i}|=\alpha +1$ and $i<_{\mathcal {O}}2^{i}$.
• Suponha $\{e\}$ é a $e$-sima função parcial recursiva. Se $e$ é total, com o alcance contido em ${\mathcal {O}}$, e para cada número natural $n$, nós temos $\{e\}(n)<_{\mathcal {O}}\{e\}(n+1)$ então $3\cdot 5^{e}$ pertence à ${\mathcal {O}}$ de Kleene, $\{e\}(n)<_{\mathcal {O}}3\cdot 5^{e}$ para cada $n$ e $|3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|$, i.e. $3\cdot 5^{e}$ é uma notação para o limite dos ordinais $\gamma _{k}$ onde $|\{e\}(k)|=\gamma _{k}$ para cada número natural $k$.
• $p<_{\mathcal {O}}q$ e $q<_{\mathcal {O}}r$ implica $p<_{\mathcal {O}}r$ (isso garante que $<_{\mathcal {O}}$ é transitiva.)

Esta definição tem a vantagem que pode-se enumerar recursivamente os predecessors de um dado ordinal (mas não através de ordenação $<_{\mathcal {O}}$) e que as notações são próximas, i. e, se existe uma notação para $\gamma$ e $\alpha <\gamma$ então existe uma notação para $\alpha$.

Propriedades básicas de $<_{\mathcal {O}}$

• Se $|i|=\alpha$ e $|j|=\beta$ e $i<_{\mathcal {O}}j\,,$ , então $\alpha <\beta$; mas o oposto pode não ser verdade;
• $<_{\mathcal {O}}$ induz a uma estrtura de árvore em ${\mathcal {O}}$, então ${\mathcal {O}}$ é bem-formado;
• ${\mathcal {O}}$ apenas se ramifica nos ordinais limitantes; e em cada notação de um ordinal limitante, ${\mathcal {O}}$ é ramificado infinitamente;
• O primeiro ordinal que n~so recebe uma representação é o ordinal Church-Kleene e é denotado por $\omega _{1}^{CK}$. Uma vez que existem muitas funções recursivas contáveis, o ordinal $\omega _{1}^{CK}$ é evidentemente contável.
• Os ordinais com a notação em ${\mathcal {O}}$ de Kleene são exatamente ordinais recursivos. (O fato que todo ordinal recursivo tem um notação que decorre do fecho do sistema de notação ordinal sob sucessor e limites efetivos.)
• $<_{\mathcal {O}}$ não é contável recursivamente, mas existe uma relação de enumeração recursiva que concorda com $<_{\mathcal {O}}$ precisamente em membros de .
• Para cada notação , o conjunto de notações sob é recursivamente enumerável. Contudo, ${\mathcal {O}}$ de Kleene, quando tomado como um todo, é $\Pi _{1}^{1}$.
• De fato, ${\mathcal {O}}$ é $\Pi _{1}^{1}$-completo e todo $\Sigma _{1}^{1}$ sub-conjunto de ${\mathcal {O}}$ é limitado em ${\mathcal {O}}$.
• ${\mathcal {O}}$ é o sistema de notações ordinais universais no sentido de que qualquer conjunto específico de notações ordinais pode ser mapeada diretamente nele. Mais precisamente, existe uma função $f$ tal que se $e$ é um índice para uma ordenação, então $f(e)$ é um membro de ${\mathcal {O}}$ e $<_{e}$ é isomorficamente ordenada para um segmento inicial do conjunto $\{p\mid p<_{\mathcal {O}}f(e)\}$.
• Existe uma função recursiva $+_{\mathcal {O}}$, a qual, para membros de ${\mathcal {O}}$, imita uma adição ordinal e tem a propriedade $\max\{p,q\}\leq p+_{\mathcal {O}}q$.(Jockusch)

Propriedades de caminhos em ${\mathcal {O}}$

Um caminho em ${\mathcal {O}}$ é um sub-conjunto ${\mathcal {P}}$ de ${\mathcal {O}}$ o qual é totalmente ordenado por <_\mathcal{O} </math> e é fechado sob a operação predecessor, i.e., se $p$ é um membro de um caminho ${\mathcal {P}}$ e $q<_{\mathcal {O}}p$ então $q$ também é um membro de ${\mathcal {P}}$. Um caminho ${\mathcal {P}}$ é máximo, se não existe elemento de ${\mathcal {O}}$,acima (no sentido de $<_{\mathcal {O}}$) de todos os membros de ${\mathcal {P}}$, do contrário ${\mathcal {P}}$ não é máximo.

• Um caminho ${\mathcal {P}}$ não é máximo se e somente se ${\mathcal {P}}$ é recursivamente enumerável (r.e.). Segue-se pela observação acima que cada elemento $p$ de ${\mathcal {O}}$ determina uma não-máximo de ${\mathcal {P}}$, e todo caminho não-máximo é então determinado.
• Existem $2^{\aleph _{0}}$ caminhos máximos através de ${\mathcal {O}}$, uma vez que eles são máximos, eles não são recursivamente enumeráveis.
• De fato, existem $2^{\aleph _{0}}$ caminhos máximos em ${\mathcal {O}}$ com comprimento $\omega ^{2}$.(Crossley, Schütte)
• Para todo ordinal diferente $\lambda <\omega _{1}^{CK}$, existem $2^{\aleph _{0}}$ caminhos máximos em ${\mathcal {O}}$ de comprimento $\omega ^{2}\cdot \lambda$.(Aczel)
• Além disso, se ${\mathcal {P}}$ é um caminho cujo comprimento não é múltiplo de $\omega ^{2}$, então ${\mathcal {P}}$ não é máximo. (Aczel)
• Para cada grau $d$ recursivamente enumerável, existe um membro $e_{d}$ de ${\mathcal {O}}$ tal que o caminho ${\mathcal {P}}=\lbrace p\mid p<_{\mathcal {O}}e_{d}\rbrace$ tem mais de um grau $d$. De fato, para cada ordinal recursivo $\alpha \geq \omega ^{2}$, a notação $e_{d}$ existe $|e_{d}|=\alpha$.(Jockusch)
• Existem $\aleph _{0}$ caminhos através de ${\mathcal {O}}$ os quais são $\Pi _{1}^{1}$.Dado o avanço das teorias recursivamente enumeráveis baseadas na iteração Reflexão Uniforme (Uniform Reflection), cada caminho desse é imcompleto com respeito ao conjunto verdade $\Pi _{1}^{0}$ sentenças.(Feferman & Spector)
• Existem $\Pi _{1}^{1}$ cominhos por ${\mathcal {O}}$ onde cada segmento inicial do qual não é meramente r.e., mas recursivo. (Jockusch)
• Vários outros caminhos em ${\mathcal {O}}$ tem sido descobertos, cada um tipos específicos de propriedades de redutibilidade.

Referências

• Church, Alonzo (1938), «The constructive second number class», Bull. Amer. Math. Soc., 44 (4): 224–232, doi:10.1090/S0002-9904-1938-06720-1 
• Kleene, S. C. (1938), «On Notation for Ordinal Numbers», Association for Symbolic Logic, The Journal of Symbolic Logic, 3 (4): 150–155, JSTOR 2267778, doi:10.2307/2267778 
• Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, ISBN 978-0-262-68052-3, First MIT press paperback edition 
• Feferman, Solomon; Spector, Clifford (1962), «Incompleteness along paths in progressions of theories», Journal of Symbolic Logic, 27 (4): 383–390, doi:10.2307/2964544