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 | editar a fonte]Os números naturais pódense empregar con dous fins distintos: describir o tamaño dun conxunto e describir a 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 | editar a fonte]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 | editar a fonte]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.