Número ordinal
![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/20px-Disambig_grey.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Omega-exp-omega-labeled.svg/220px-Omega-exp-omega-labeled.svg.png)
Na teoria dos conjuntos, um número ordinal, ou só ordinal, é um tipo de ordem de um conjunto bem-ordenado. Eles são usualmente identificados com conjuntos hereditariamente transitivos. Ordinais são uma extensão dos números naturais diferentes dos inteiros e dos cardinais. Como outros tipos de números, ordinais podem ser somados, multiplicados e exponenciados.
Os ordinais foram apresentados por Georg Cantor em 1883 para acomodar sequências infinitas e para classificar conjuntos com certos tipos de estruturas de ordem neles. Ele os derivou por acidente, enquanto trabalhava num problema que envolvia séries trigonométricas.
Os ordinais finitos (e cardinais finitos) são os números naturais: , já que quaisquer duas ordens de um conjunto finito são isomórficas de ordem. O menor ordinal infinito é o , que é identificado com o número cardinal . Entretanto, no caso transfinito, além de , ordinais elaboram uma distinção mais refinada do que os cardinais na contagem de suas informações de ordem. Enquanto há somente um cardinal infinito contável, que é o , há incontáveis ordinais infinitos contáveis, que são:
Aqui, adição e multiplicação não são comutativas: em particular, é , ao contrário de , assim como é , enquanto não é. O conjunto de todos os ordinais contáveis constitui o primeiro ordinal incontável , que é identificado como cardinal (próximo cardinal após o). Cardinais bem-ordenados são identificados com seus ordinais iniciais, ou seja, o menor ordinal daquela cardinalidade. A cardinalidade de um ordinal é a associação de ordinais com cardinais.
Em geral, cada ordinal é o tipo de ordem do conjunto de ordinais estritamente menores que o ordinal, o próprio
Ordinais estendem os números naturais
[editar | editar código-fonte]Um número natural (que, neste contexto, inclui o número 0) pode ser usado para dois propósitos: para descrever o tamanho de um conjunto ou para descrever a posição de um elemento numa sequência. Quando restritos a conjuntos finitos, estes conceitos coincidem; há somente uma forma de inserir um conjunto finito numa sequência linear, a menos de isomorfismo. Ao lidar com conjuntos infinitos, deve-se distinguir entre a noção de tamanho, que leva a números cardinais, e a noção de posição, que é generalizado pelos números ordinais descritos aqui. Isto se deve, enquanto todo conjunto tem somente um tamanho (sua cardinalidade), há várias boa-ordenações não isomórficas de qualquer conjunto infinito, como explicado abaixo.
Enquanto a noção de número cardinal é associada com um conjunto sem estrutura particular sobre ele, os ordinais são intimamente ligados com o tipo especial de conjuntos que são chamados de bem-ordenados (tão intimamente ligados, de fato, que alguns matemáticos não fazem qualquer distinção entre os dois conceitos). Um conjunto bem-ordenado é um conjunto totalmente ordenado (dado quaisquer dois elementos, define-se qual é o menor e o maior de forma coerente) tal que não haja sequência decrescente infinita (entretanto, pode haver sequências crescentes infinitas); isso quer dizer, todo subconjunto não vazio do conjunto tem um elemento mínimo. Ordinais podem ser usados para rotular os elementos de qualquer conjunto bem-ordenado (o menor elemento sendo rotulado como 0, o sucessor dele é 1, o próximo é 2, “etc”) e para medir a “extensão” de todo o conjunto pelo menos ordinal que não é rótulo de um elemento pertencente ao conjunto. Esta “extensão” é chamado o tipo de ordem do conjunto.
Qualquer ordinal é definido pelo conjunto de ordinais que o precedem: de fato, a definição mais comum de ordinais identifica cada ordinal como o conjunto de ordinais que o precedem. Por exemplo, o ordinal 42 é o tipo de ordem de ordinais menores que ele, ou seja, os ordinais de 0 (o menor dos ordinais) a 41 (o predecessor imediato de 42), e é identificado como o conjunto {0, 1, 2...41}. Da mesma forma, qualquer conjunto (S) de ordinais que é fechado ‘pra baixo’ – quer dizer que qualquer ordinal
Até então nós mencionamos somente ordinais finitos, que são os números naturais. Mas há infinitos também: o menor infinito é
Talvez uma intuição mais clara dos ordinais pode ser formada ao examinar os primeiros: como mencionado acima, eles começam com os números naturais, 0, 1, 2, 3, 4, 5... depois de todos os números naturais, vem o primeiro ordinal infinito, o
Definições
[editar | editar código-fonte]Conjuntos bem ordenados
[editar | editar código-fonte]Num conjunto bem-ordenado, todo subconjunto não vazio tem um menor elemento. Dado o axioma da escolha dependente, isto é equivalente a dizer que o conjunto é totalmente ordenado e não há sequência infinita decrescente, algo talvez melhor de ser visualizado. Na prática, a importância da boa ordenação é justificada pela possibilidade de aplicações na indução transfinita, que diz, essencialmente, que qualquer propriedade que passar de um predecessor de um elemento para o próprio elemento deve ser verdade para todos os outros elementos (do dado conjunto bem-ordenado). Se os estados da computação (programa computacional ou jogo) podem ser bem ordenados de tal forma que cada passo é seguido por um passo “mais baixo”, então você pode ter certeza que a computação terminará.
Agora, nós não queremos distinguir entre dois conjuntos bem ordenados eles somente diferem nos “rótulos dos seus elementos”, ou mais formalmente: se nós podemos parear os elementos do primeiro conjunto com os elementos do segundo, de tal forma que um elemento é menor do que outro no primeiro conjunto, então o par do primeiro elemento é menor do que o parceiro do segundo elemento no segundo conjunto, e vice-versa. Tal correspondência um-pra-um é chamada de isomorfismo de ordem e dois conjuntos bem-ordenados são isomórficos-de-ordem, ou similar (obviamente isto é uma relação de equivalência). Desde que exista um isomorfismo de ordem entre dois conjuntos bem-ordenados, o isomorfismo de ordem é único: isto torna bastante justificável considerar os dois conjuntos como essencialmente idênticos achar um representante “canônico” do tipo de isomorfismo (classe). Isto é exatamente o que os ordinais fornecem, assim como também fornecem a rotulagem canônica dos elementos de qualquer conjunto bem ordenado.
Então nós queremos essencialmente definir um ordinal como uma classe de isomorfismos dos conjuntos bem ordenados: isto é, como uma classe de equivalência para a relação de equivalência de “é isomórfico de ordem”. Há uma dificuldade técnica envolvida, entretanto, no fato de que a classe de equivalência é muito grande para ser um conjunto na formalização usual de Zermelo-Fraenkel (ZF) da teoria dos conjuntos. Mas isto não é uma dificuldade séria. Nós diremos que o ordinal é o tipo de ordem de qualquer conjunto na classe.
Definição de um ordinal como uma classe de equivalência
[editar | editar código-fonte]A definição original de um número ordinal, encontrado no exemplo no Principia Mathematica, define o tipo de ordem de uma boa-ordenação como o conjunto de todas as boas ordenações similares (isomórficas de ordem) àquela boa ordenação: em outras palavras, um número ordinal é genuinamente uma classe de equivalência de conjuntos bem ordenados. Esta definição deve ser abandonada no ZF e sistemas relacionadas da teoria axiomática dos conjuntos porque estas classes de equivalência são muito grandes para formar um conjunto. Entretanto, esta definição pode ainda ser usada na teoria dos tipos e nas “Novas Fundações” da teoria dos conjuntos de Quine e sistemas relacionados (que sustentam uma solução alternativa um tanto surpreendente ao paradoxo de Burali-Forti do maior ordinal).
Definição de Von Neumann dos ordinais
[editar | editar código-fonte]Ao invés de definir um ordinal como uma classe de equivalência dos conjuntos bem-ordenados, nós o definiremos como um conjunto bem-ordenado particular que representa (canonicamente) a classe. Assim, um número ordinal será um conjunto bem-ordenado; e todo conjunto bem-ordenado será isomórfico de ordem a exatamente um número ordinal.
A definição padrão, sugerida por John Von Neumann, é: cada ordinal é o conjunto bem-ordenado de todos os ordinais menores. Em símbolos,
- Um conjunto S é um ordinal se e somente se S é estritamente bem-ordenado com respeito a ordem de “pertence” do conjunto e todo elemento de S é também um subconjunto de S.
Note que os números naturais são ordinais por esta definição. Por exemplo, 2 é um elemento de 4 = {0, 1, 2, 3}, e 2 é igual a {0, 1}, assim como é um subconjunto de {0, 1, 2, 3}.
Pode ser mostrado por indução transfinita que todo conjunto bem-ordenado é isomórfico de ordem a exatamente um destes ordinais, ou seja, há uma ordem que preserva uma função bijetora entre eles.
Assim, os elementos de todo ordinal são ordinais também. Sempre que você tem dois ordinais, S e T, S é um elemento de T se e somente se é um subconjunto próprio de T. Em outras palavras, ou S é um elemento de T ou T é um elemento de S, ou eles são iguais. Então todo conjunto de ordinais é totalmente ordenado. Ainda mais, todo conjunto de ordinais é bem ordenado. Isto generaliza o fato de que todo conjunto de números naturais é bem ordenado.
Consequentemente, todo ordinal S é um conjunto que contém como elementos precisamente os ordinais menores que S. Por exemplo, todo conjunto de ordinais tem um supremo, o ordinal obtido por unir todos os ordinais do conjunto. Esta união existe independente do tamanho do conjunto, pelo axioma da união.
A classe de todos os ordinais não é um conjunto. Se fosse um conjunto, poderíamos mostrar que seria um ordinal e assim um membro dele mesmo, que contradiria sua ordem estrita de “pertence”. Isto é o paradoxo de Burali-Forti. A classe de todos os ordinais é de várias formas chamado “Ord”, “ON”, ou “∞”.
Um ordinal é finito se e somente se a a ordem oposta é também bem ordenada, que é o caso se e somente se cada um de seus subconjuntos tem um máximo.
Outras definições
[editar | editar código-fonte]Há outras formulações modernas da definição de ordinal. Por exemplo, assumindo o axioma de regularidade, é equivalente dizer para um conjunto x:
- x é um ordinal,
- x é um conjunto transitivo e os membros do conjunto são tricotômicos em x,
- x é um conjunto transitivo totalmente ordenado pela inclusão,
- x é um conjunto transitivo de conjuntos.
Estas definições não podem ser usadas nas teorias dos conjuntos “não bem-fundados”. Nas teorias dos conjuntos com “urelementos”, temos que assim ter certeza que a definição não permite que os urelementos apareçam nos ordinais.
Sequência transfinita
[editar | editar código-fonte]Se
Indução transfinita
[editar | editar código-fonte]O que é indução transfinita?
[editar | editar código-fonte]Indução transfinita vale em qualquer conjunto bem-ordenado, mas é também tão importante para os ordinais que é bom relembrarmos aqui:
- Qualquer propriedade que passa de um conjunto de ordinais menores do que um dado
α para o próprioα , é verdade para todos os ordinais.
Isto é, se P(
Recursão transfinita
[editar | editar código-fonte]Indução transfinita pode ser usada não somente para fornecer coisas, mas também para defini-las. Tal definição é normalmente chamada de recursão transfinita – a prova que o resultado é bem definido usa indução transfinita. Seja F uma função (classe) para ser definida sobre os ordinais. A ideia agora é que, na definição F(
Eis um exemplo da definição por recursão transfinita sobre os ordinais (mais será dado depois):
- defina a função F tal que F(
α ) seja o menor ordinal que não esteja na classe {F(β ) |β <α }, isto é, a classe consistindo de todos os F(β ) paraβ <α . Esta definição assume que F(β ) é conhecido no próprio processo de definição de F; este ciclo aparentemente vicioso é exatamente o que a definição por recursão transfinita permite. De fato, F(0) faz sentido já que não há ordinalβ < 0, e a classe {F(β ) |β < 0} é vazia. Então F(0) é igual a 0 (o menor ordinal de todos). Agora que F(0) é conhecido, a definição aplicada a F(1) faz sentido (é o menor ordinal que não está na classe de um só elemento {F(0)} = {0}), e assim sucessivamente (este sucessivamente é exatamente a indução transfinita). Acontece que este exemplo não é muito empolgante, já que provavelmente F(α ) =α para todos os ordinaisα , que pode ser mostrado, precisamente, por indução transfinita.
Ordinais sucessor e limite
[editar | editar código-fonte]Qualquer ordinal que não seja o zero tem um elemento mínimo, que é o zero. Pode ou por não ter um elemento máximo. Por exemplo, 42 tem máximo 41 e
Um ordinal que não seja zero que não é sucessor é chamado de ordinal limite. Uma justificativa para este termo é que o ordinal limite é de fato o limite num sentido topológico de todos os ordinais menores (sob a topologia de ordem).
Quando ‹
Outra forma de definir um ordinal limite é dizer que
- Há um ordinal menor que
α e sempre que µ for menor queα , então existe um ordinalβ tal que µ <β <α . Então, na seguinte sequência:
- 0, 1, 2...
ω ,ω +1
- 0, 1, 2...
ω é um ordinal limite porque para qualquer ordinal menor (neste exemplo, um número natural), nós podemos achar outro ordinal (número natural) maior que ele, mas ainda assim menor queω .
Assim, todo ordinal, ou é zero, ou é sucessor (de um predecessor bem-definido) ou é limite. Esta distinção é importante, porque várias definições por indução transfinita se baseiam nela. Muitas vezes, quando se define uma função F por indução transfinita sobre todos os ordinais, define-se F(0) e F(
Indexação de classes de ordinais
[editar | editar código-fonte]Nós mencionamos que qualquer conjunto bem ordenado é similar (isomórfico de ordem) a um único número ordinal
Nós podemos aplicar isto, por exemplo, na classe dos ordinais limite: o µ-ésimo ordinal, que ou é limite ou zero, é
Conjuntos não limitados fechados e classes
[editar | editar código-fonte]Uma classe C de ordinais é dita não limitada, ou cofinal, quando dado um ordinal
De importância particular, são aquelas classes de ordinais que são fechadas e não limitadas, algumas vezes chamadas de clubes. Por exemplo, a classe de todos os ordinais limites é fechada e não limitada: isto se traduz no fato de que há sempre um ordinal limite maior que o ordinal em questão, e que um limite de ordinais limites é um ordinal limite (um fato um tanto feliz, se a terminologia tivesse que fazer certo sentido!). A classe de ordinais aditivamente indecomponíveis, ou a classe de ordinais
Uma classe é estacionária se tem uma interseção não vazia com toda classe fechada e não limitada. Todas as superclasses de classes fechadas e não limitadas são estacionárias, e classes estacionárias são não limitadas, mas há classes estacionárias que não são fechadas e classes estacionárias que não possui subclasse fechada e não limitada (tal como a classe de todos os ordinais limites que cofinalidade contável). Já que a interseção de duas classes fechadas e não limitadas é fechada e não limitada, a interseção de uma classe estacionária e uma classe fechada não estacionária é estacionária. Mas a interseção de duas classes estacionárias pode ser vazia, por exemplo, a classe de ordinais com cofinalidade
Ao invés de formular estas definições para classes (próprias) de ordinais, podemos formulá-las para conjuntos de ordinais abaixo de um dado ordinal
Aritmética de ordinais
[editar | editar código-fonte]Há três operações básicas sobre os ordinais: adição, multiplicação e exponenciação. Cada uma pode ser definida de duas formas essencialmente diferentes: ou pela construção de um conjunto explicitamente bem ordenado que representa a operação ou por usar recursão transfinita. A forma normal de Cantor provê uma maneira padronizada de escrever os ordinais. As operações aritméticas chamadas “naturais” retém comutatividade às custas da continuidade.
Ordinais e cardinais
[editar | editar código-fonte]Ordinal inicial de um cardinal
[editar | editar código-fonte]Cada ordinal está associado a um cardinal, sua cardinalidade, obtido simplesmente ao esquecer a ordem. Qualquer conjunto bem ordenado que contém aquele ordinal como seu tipo de ordem tem a mesma cardinalidade. O menor ordinal que contém um dado cardinal como sua cardinalidade é chamado o ordinal inicial daquele cardinal. Todo ordinal finito (número natural) é inicial, mas a maioria dos ordinais infinitos não é inicial. O axioma da escolha é equivalente ao enunciado que todo conjunto pode ser bem ordenado, ou seja, todo cardinal tem um ordinal inicial. Neste caso, é comum identificar o número cardinal com seu ordinal inicial, e nós dizemos que este ordinal inicial é um cardinal.
Cantor usava a cardinalidade para particionar ordinais em classes. Ele se referia aos números naturais como a primeira classe de número, os ordinais com cardinalidade (os contáveis ordinais infinitos) como a segunda classe de números e de forma geral, os ordinais com cardinalidade como a n-ésima classe de número.
O
Cofinalidade
[editar | editar código-fonte]A confinalidade de um ordinal
Assim, para um ordinal limite, existe um µ-indexado estritamente crescente com limite
A cofinalidade de 0 é 0. E a cofinalidade de qualquer ordinal sucessor é 1. A cofinalidade de qualquer ordinal limite é no mínimo ) .
Um ordinal que é igual a sua cofinalidade é chamado regular e é sempre um ordinal inicial. Qualquer limite de ordinais regulares é um limite de ordinais iniciais e assim é também inicial, mesmo se não for regular, o qual usualmente não é. Se o axioma da escolha vale, então é regular para cada
A cofinalidade de qualquer ordinal
Alguns ordinais contáveis “enormes”
[editar | editar código-fonte]Nós já mencionamos (veja forma normal de Cantor) o ordinal
Ordinais consideravelmente enormes podem ser definidos abaixo de , que mede a “força da prova-teórica” de certos sistemas formais (por exemplo,
Topologia e ordinais
[editar | editar código-fonte]Qualquer ordinal pode ser transformado em um espaço topológico de forma natural ao dotá-lo com uma topologia de ordem. Veja a sessão de topologia e ordinais do artigo “Topologia de Ordem”.
Conjuntos Fechados para baixo e Ordinais
[editar | editar código-fonte]Um conjunto é fechado para baixo se qualquer coisa menor do que um elemento do conjunto também está no conjunto. Se um conjunto de ordinais é fechado para baixo, então aquele conjunto é um ordinal – o menor ordinal que não está no conjunto.
Exemplo:
- O conjunto dos ordinais menores que 3 é 3 = {0, 1, 2}, o menor ordinal que não é menor do que 3.
Classificação ordinal
[editar | editar código-fonte]A classificação de um elemento em um ordinal depende sempre do número de elementos que estão à sua frente. De modo que em concursos públicos ou demais disputas, quando há empate entre dois competidores numa posição X, a classificação seguinte é considerada vazia. Por exemplo, num empate entre dois competidores na primeira colocação, o próximo competidor melhor colocado é considerado terceiro, ficando vago o segundo lugar.[1] Nem sempre, no entanto, esta regra é seguida, existindo algumas organizações que consideram que aquele que ficou com dois competidores à sua frente pode ser o segundo, caso os outros dois estejam empatados.
Ver também
[editar | editar código-fonte]Referências
- ↑
“ Os três grandes mestres participantes do 73º Campeonato Brasileiro Individual Absoluto chegam à última rodada empatados na liderança da prova, com 7 pontos e meio conquistados nas dez rodadas disputadas até aqui.(...) James, com 5, é o sexto, meio à frente de Fier - que tem hoje sua última noite como o campeão reinante. A oitava posição é dividida por Limp, Diamant e Diego Rafael Di Berardino (que hoje venceu Jefferson dos Santos Oliveira), todos com 3½. Pelikian, com 3 está em 11º e o representante local, Oliveira em 12º com 2. ”
- Cantor, G., (1897), Beitrage zur Begrundung der transfiniten Mengenlehre. II (tr.: Contributions to the Founding of the Theory of Transfinite Numbers II), Mathematische Annalen 49, 207-246 English translation.
- Conway, J. H. and Guy, R. K. "Cantor's Ordinal Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 266–267 and 274, 1996.
- Dauben, Joseph Warren, (1990), Georg Cantor: his mathematics and philosophy of the infinite. Chapter 5: The Mathematics of Cantor's Grundlagen. ISBN 0-691-02447-2
- Hamilton, A. G. (1982), Numbers, Sets, and Axioms : the Apparatus of Mathematics, ISBN 0-521-24509-5, New York: Cambridge University Press See Ch. 6, "Ordinal and cardinal numbers"
- Kanamori, A., Set Theory from Cantor to Cohen, to appear in: Andrew Irvine and John H. Woods (editors), The Handbook of the Philosophy of Science, volume 4, Mathematics, Cambridge University Press.
- Levy, A. (1979), Basic Set Theory, Berlin, New York: Springer-Verlag Reprinted 2002, Dover. ISBN 0-486-42079-5
- Jech, Thomas (2003), Set Theory, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag
- Sierpiński, W. (1965). Cardinal and Ordinal Numbers (2nd ed.). Warszawa: Państwowe Wydawnictwo Naukowe. Also defines ordinal operations in terms of the Cantor Normal Form.
- Suppes, P. (1960), Axiomatic Set Theory, D.Van Nostrand Company Inc., ISBN 0-486-61630-4
Ligações externas
[editar | editar código-fonte]- Weisstein, Eric W. «Ordinal Number». MathWorld (em inglês)
- Ordinals at ProvenMath
- Beitraege zur Begruendung der transfiniten Mengenlehre Cantor's original paper published in Mathematische Annalen 49(2), 1897
- Ordinal calculator GPL'd free software for computing with ordinals and ordinal notations