Número ordinal
En Matemáticas, un número ordinal denota a posición dun elemento pertencente a unha sucesión ordenada. Por exemplo, na sucesión a b c d, o elemento a é o primeiro, b o segundo, c o terceiro etc.
Os números ordinais poden xeneralizarse para as sucesións infindas, concepto introducido por Georg Cantor en 1897. É esta xeneralización a que se explicará neste artigo.
Xeneralización editar
Os números naturais pódense empregar con dous fins distintos: describi-lo tamaño dun conxunto e describi-la posición dun elemento nunha sucesión. Aínda que no mundo finito estes dous conceptos coinciden, cando se trata con conxuntos infindos hai que os distinguir entre si. O aspecto do tamaño dun conxunto descríbese mediante números cardinais, que tamén foron descubertos por Cantor, mentres que o aspecto da posición xeneralízase mediante os números ordinais, os que analizaremos aquí.
Na teoría de conxuntos, os números naturais adoitan construírse como conxuntos tales que cada número natural é o conxunto de tódolos números naturais máis pequenos:
Visto así, cada número natural é un conxunto ben ordenado: por exemplo, o conxunto do 4 ten os elementos 0, 1, 2 e 3, que por suposto ordénanse 0 < 1 < 2 < 3. Un número natural é menor ca outro se e só se é un elemento do outro.
Baixo esta convención, pódese demostrar que todo conxunto finito ben ordenado é ordenadamente isomorfo a exactamente un número natural. Este isomorfismo motiva a xeneralizar esta construción cara ós conxuntos non finitos e os seus correspondentes números que serían máis grandes ca calquera número natural.
Definición moderna de ordinal editar
Deséxase construír números ordinais como conxuntos ben ordenados especiais de forma que todo conxunto ben ordenado é ordenadamente isomorfo a exactamente un número ordinal. A seguinte definición mellora o enfoque de Cantor e foi proposta inicialmente por John von Neumann:
- Un conxunto S é un ordinal se e só se S está totalmente ordenado con respecto á inclusión de conxuntos (é dicir, a relación subconxunto) e todo elemento de S é tamén un subconxunto de S.
Baseándose no axioma de regularidade, que pode enunciarse como: «Todo conxunto non baleiro "S" contén un elemento "a" disxunto de "S".»
Nótese que os naturais, na representación proposta máis arriba son os chamados ordinais finitos. Por exemplo, é un elemento de 4 = {0, 1, 2, 3}, e 2 é igual a {0, 1} polo que tamén é un subconxunto de 4.
Pódese demostrar, aplicando indución transfinita que todo conxunto ben ordenado é ordenadamente isomorfo a exactamente un destes ordinais.
Máis aínda, os elementos de cada ordinal son en si mesmos ordinais. Cando se teñen dous ordinais S e T, S é un elemento de T se e só se S é un subconxunto propio de T, e máis aínda, cando S e T son distintos e S non é un elemento de T, cúmprese que T é un elemento de S. De maneira que todo conxunto de ordinais está totalmente ordenado e máis aínda, Todo conxunto de ordinais é ben ordenado. Este último resultado é a xeneralización da mesma propiedade sobre os naturais, o que permite enunciar e utilizar indución transfinita para demostrar propiedades sobre ordinais.
Outra consecuencia é que todo ordinal S é un conxunto que contén como elementos precisamente os ordinais máis pequenos que S. Esta afirmación determina completamente a estrutura de conxunto de cada ordinal en termos doutros ordinais. Ela é utilizada para demostrar moitas dos propiedades destes números. Un exemplo do mesmo é unha importante caracterización da relación de orde entre ordinais: todo conxunto de ordinais ten un supremo, que é o ordinal obtido como a unión de tódolos ordinais do conxunto.
Outro exemplo é o feito de que a colección de tódolos ordinais non é un conxunto. Posto que todo ordinal contén unicamente ordinais, se cumpre que todo elemento da colección de tódolos ordinais tamén é o seu subconxunto. Así, se esa colección fose un conxunto, tería que ser un ordinal tamén, por definición; entón sería un elemento do mesmo, o cal contradí o axioma de regularidade. (Véxase tamén o Paradoxo de Burali-Forti).
Aplicacións editar
Os ordinais utilízanse comunmente para realizar demostracións de terminación de algoritmos. O sistema de axuda á demostración ACL2 permite utilizar números ordinais como cota de terminación de algoritmos e é capaz de realizar probas por indución transfinita.