Grandes ordinais contáveis

Ver artigo principal: Número ordinal

Na disciplina de teoria dos conjuntos, há muitas maneiras de descrever ordinais específicos eque são contáveis. As menores descrições podem ser claramente e de forma não-redundante expressas em termos de suas formas normais Cantor. Além disso, muitos ordinais relevantes para a teoria da prova ainda tem notações ordinais computáveis. No entanto, não é possível decidir eficazmente se uma determinada notação ordinal é notação ou não (por razões de certa forma análogas, à insolubilidade do problema da parada); existem várias maneiras de saber se uma notação ordinal é definível.

Desde que existam muitas notações contáveis, todos os ordinal com notações são completamente explorados sob o primeiro o ordinal não contável w1; seu supremo é chamado Church-Kleene w1 ou w1ck (não confunda com o primeiro ordinal não-contável, w1), descrito abaixo. Números ordinais abaixo de w1ck são ordinais recursivos (veja abaixo). Ordinais contáveis maiores do que este pode ainda ser definida, mas não têm notações.

Devido ao foco nos ordinais contáveis, a aritmética ordinal é usada por toda parte, exceto onde o contrário é indicado. Os ordinais descritos aqui não são tão grandes como os cardinais longos, mas eles são grandes entre aqueles que têm notações construtivas (descrições). Ordinais cada vez maiores pode ser definida, mas tornam-se mais e mais difícil de descrever.

Generalizações em ordinais recursivos editar

 Ver artigo principal: Ordinal recursivo

Notações ordinais editar

 Ver artigo principal: Notação ordinal

Ordinais recursivos (ou ordinais computáveis) são alguns ordinais contáveis: falando vagamente, são aqueles representados por uma função computável. Existem várias definições equivalentes para isso: a mais simples diz que um ordinal computável é da ordem de algumas ordenações recursivas de números naturais, então, essencialmente, um ordinal é recursivo quando podemos apresentar o conjunto de ordinais menores, de tal forma que um computador (máquina de Turing, por exemplo) pode manipulá-los (e, essencialmente, compará-los).

Uma definição diferente usa o sistema de notações ordinais de Kleene. Resumidamente, uma notação ordinal é o zero (descrevendo o ordinal 0), ou o sucessor de uma notação ordinal (descrevendo o sucessor do ordinal descrito pela notação), ou uma máquina de Turing (função computável), que produz uma seqüência crescente notações de ordinais (que descrevem o ordinal que é o limite da sequência), e notações ordinais são (parcialmente) ordenadas de modo a tornar o sucessor de o superior que o e para fazer o limite de o superior a qualquer um dos termos da sequência (esta ordem é computável, no entanto, o conjunto de notações ordinais O é em si altamente não-recursivo, devido à impossibilidade de decidir se uma determinada máquina de Turing, de fato, produzir uma sequência de notações), um ordinal recursivo é, então, um ordinal descrito por alguma por alguns ordinal notação ordinal.

Qualquer ordinal menor do que um ordinal recursivo em si é recursivo, de modo que o conjunto de todos os ordinais recursivos resulta em um ordinal(contável), o ordinal Church-Kleene.

É tentador esquecer notações ordinais, e só falar dos ordinais recursivos: algumas declarações são feitas sobre ordinais recursivos que, de fato, concedem notações para esses números ordinais. Isto conduz a dificuldades, no entanto, como até mesmo o menor ordinal infinito ω, tem muitas notações, algumas das quais não podem ser provadas como sendo equivalente à notação óbvia (o limite do programa mais simples que enumera todos os números naturais).

Relacionamentos de sistemas aritméticos editar

Existe uma relação entre ordinais computáveis e alguns sistemas formais (contendo aritmética, isto é, pelo menos, um fragmento de razoável aritmética de Peano).

Alguns ordinais computáveis são tão grandes que, que enquanto eles podem ser dados por uma determinada notação ordinal o, um dado sistema formal pode não ser suficientemente poderoso para mostrar que o é, de fato, uma notação ordinal: o sistema não mostra indução transfinita para ordinais tão grandes.

Por exemplo, os axiomas habituais de primeira ordem de Peano não provam indução transfinita de (ou além) ε0: enquanto o ordinal ε0 pode ser facilmente descrito aritmeticamente (é contável), os axiomas de Peano não são fortes o suficiente para mostrar que ele é de fato um ordinal, na verdade, indução transfinita em ε0 prova a consistência dos axiomas de Peano (um teorema por Gentzen), por isso, segundo teorema da incompletude de Gödel, axiomas de Peano não pode formalizar esse raciocínio. (Esta é a base do teorema de Kirby-Paris em seqüências Goodstein.) Dizemos que ε0 mede a força-prova teórica de axiomas de Peano.

Mas podemos fazer isso por outros sistemas, além axiomas de Peano. Por exemplo, a força-prova teórica da teoria dos conjuntos Kripke-Platek é o ordinal Bachmann-Howard (ver abaixo), e, de fato, a simples inclusão de axiomas de Peano os axiomas que o estado do bem-ordenação de todos os ordinais está abaixo da Bachmann-Howard ordinal é suficiente para obter todas as conseqüências matemáticas da teoria dos conjuntos Kripke-Platek.

Ordinais recursivos específicos editar

Definições afirmativas e hierarquia de Veblen editar

Nós já mencionamos (veja Forma normal de Cantor) o ordinal ε0, que é o menor satisfazendo da equação  , então ele é o limite da sequência 0, 1,  ,  ,  , etc. O próximo ordinal que satisfaz a equação é chamado ε1: é o limite da sequência

 

Generalizando, o  -ésimo ordinal de modo que   é chamado  . Nós podemos definir   o menor ordinal de modo que  , mas como o alfabeto grego não tem transfinitamente muitas letras é melhor usar notações mais robustas: defina os ordinais   por uma descrição transfinita como segue: seja   e seja   é o  -ésimo ponto de   (i.e., o  -ésimo ordinal tal que  ; então por exemplo,  ), e quando   é o ordinal limite, defina   como o  -ésimo ponto comum de   para todo  . Esta família de funções é conhecida como hierarquia Veblen. (Existem várias definições desnecessárias, como deixando, que um ordinal limite  ,   seja o limite de   para :isso apenas desloca o índice por 1, que não faz diferença.)   is called the   função Veblen (para a base  ).

Ordinais não-afirmativos editar

Para ir muito além do ordinal Feferman-Schütte, é necessário introduzir novos métodos. Infelizmente, ainda não há nenhuma maneira padrão de fazer isso: cada autor no assunto parece ter inventado o seu próprio sistema de notação, e é muito difícil de traduzir entre os diferentes sistemas. O primeiro sistema foi introduzido pela Bachmann em 1950 (de uma forma ad hoc) e extensões diferentes e variações do que foi descrito por Buchholz, Takeuti (diagramas ordinais), Feferman (θ sistemas), Aczel, Bridge, Schütte, e Pohlers . No entanto, a maioria dos sistemas usam a mesma ideia básica, de construção de novos ordinais contáveis usando a existência de certos ordinais incontáveis. Aqui é um exemplo de uma tal definição, descrito em maior detalhe no artigo em função colapso ordinal:

• ψ (α) é definido como sendo o menor ordinal que não pode ser construído a partir de 0, 1, ω e Ω, e aplicar repetidamente adição, multiplicação e exponenciação e ψ para ordinais, previamente elaborados (excepto que ψ só pode ser aplicado a argumentos menores que α, para garantir que seja bem definido).

Aqui Ω = ω1 é o primeiro ordinal incontável. É posto em causa, caso contrário, a função ψ fica "presa" no menor ordinal σ tal que εσ = σ: em particular ψ (α) = σ para qualquer ordinal α satisfazendo σ ≤ α ≤ Ω. No entanto, o fato de que nós incluímos Ω nos permite passar por este ponto: ψ (Ω +1) é maior do que σ. A propriedade essencial da Ω utilizada é que ele é maior do que qualquer ordinal produzido por ψ. Esta definição é assertiva, porque ela usa o ordinal incontável Ω, o que, em certo sentido, já usa todos os ordinais contáveis que estamos tentando construir na sua construção. Do mesmo modo, o operador de menor ponto fixo utilizado na hierarquia Veblen não é predicativa [1].

Para construir ordinais ainda maiores, podemos estender a definição de ψ, lançando mais maneiras de construir ordinais incontáveis. Existem várias maneiras de fazer isso, descritos de certa maneira no artigo na função de colapso ordinal.

O ordinal Bachmann-Howard (às vezes chamado apenas de ordinal Howard, ψ (εΩ +1) com a notação acima) é um passo importante, porque descreve a força-prova teórica da teoria dos conjuntos Kripke-Platek. Na verdade, a principal importância desses grandes ordinais, e a razão para descrevê-las, é a sua relação com certos sistemas formais, como explicado acima. No entanto, esses poderosos sistemas formais como aritmética de segunda ordem completa, deixa de lado a teoria dos conjuntos de Zermelo-Fraenkel, que parecem fora de alcance no momento.

Além dos ordinais recursivos editar

O ordinal Church–Kleene editar

O conjunto de ordinais recursivos é um ordinal que é o menor ordinal que não pode ser descrita de uma forma recursiva. (Não é o tipo de ordem de qualquer boa ordenação recursiva de inteiros.). Este ordinal é um ordinal contável chamado de ordinal Church-Kleene,  . Assim,   é o menor não ordinal recursiva, e não há nenhuma esperança de descrever precisamente qualquer ordinal a partir deste ponto - só podemos defini-los. Mas ainda é muito menor do que o primeiro ordinal incontável,  . No entanto, como seu símbolo sugere, ele se comporta em muitos aspectos, um pouco como  .

Referências editar

Mais livros descrevendo grandes ordinais contáveis estão em teoria da prova, infelizmente podem não estar impressos.

Sobre ordinais recursivos editar

Além dos ordinais recursivos editar

  • Barwise, Jon (1976). Admissible Sets and Structures: an Approach to Definability Theory. Col: Perspectives in Mathematical Logic. [S.l.]: Springer-Verlag. ISBN 3-540-07451-1 
  • Hinman, Peter G. (1978). Recursion-theoretic hierarchies. Col: Perspectives in Mathematical Logic. [S.l.]: Springer-Verlag 

Ordinais recursivos e não-recursivos editar

  • Michael Rathjen, "The realm of ordinal analysis." in S. Cooper and J. Truss (eds.): Sets and Proofs. (Cambridge University Press, 1999) 219–279. At Postscript file.

Referências

Predefinição:Countable ordinals