Relação bem-ordenada

Na matemática, uma relação bem-ordenada (ou boa-ordenação) em um conjunto S é uma ordenação total em S com a propriedade de que todo subconjunto não-vazio de S possui um elemento mínimo na ordenação. O conjunto S juntamente com a relação bem-ordenada é chamado de conjunto bem-ordenado.

Todo elemento s, exceto um possível elemento máximo, tem um único sucessor (próximo elemento) a saber, o elemento mínimo do subconjunto de todos os elementos maiores que s. Todo subconjunto que possui um limitante superior possui um supremo. Podem existir elementos (além do elemento mínimo) que não possuem predecessores.

Se ≤ é uma (não-estrita) boa-ordenação, então < é uma boa-ordenação estrita. Uma relação é uma boa-ordenação estrita se e somente se ela for uma ordenação total estrita bem-fundada. A diferença entre boas-ordenações estritas e não-estritas é frequentemente ignorada, uma vez que elas são facilmente interconversíveis.

Se um conjunto é bem-ordenado (ou até se ele meramente admite uma relação bem-fundada), a técnica de prova de indução transfinita pode ser usada para provar que uma dada sentença é verdadeira para todos os elementos do conjunto.

A observação de que os números naturais são bem-ordenados através relação menor que, é comumente chamada de princípio da boa-ordenação (para números naturais).

O teorema da boa-ordenação, que é equivalente ao axioma da escolha, afirma que todo conjunto pode ser bem-ordenado. O teorema da boa-ordenação também é equivalente ao lema de Kuratowski-Zorn.

Números ordinais

Todo conjunto bem-ordenado é isomorfo a um único número ordinal, chamado tipo de ordem do conjunto bem-ordenado. A posição de cada elemento do conjunto ordenado também é dada por um número ordinal. No caso de um conjunto finito, a operação básica de contagem, para achar o número ordinal de um objeto em particular, ou para achar o objeto de um número ordinal em particular, correspondem a atribuir números ordinais um a um para os objetos. O tamanho (número de elementos, número cardinal) de um conjunto finito é igual ao seu tipo de ordem. A contagem no dia-a-dia começa tipicamente do um, então ela atribui para cada objeto o tamanho do segmento inicial que possui aquele objeto como último elemento. Note que esses números são um a mais que os números ordinais formais de acordo com a ordem isomórfica, porque esses são iguais ao número de objetos anteriores (que corresponde a contar do zero). Portanto, para um n finito, a expressão "n-ésimo elemento" de um conjunto bem-ordenado requer o contexto para saber se a conta começa do zero ou um. Numa notação "β-ésimo elemento", em que β pode ser um ordinal infinito, a conta geralmente começa do zero.

Para um conjunto infinito o tipo de ordem determina a cardinalidade, mas a recíproca não é verdadeira: conjuntos bem-ordenados de uma determinada cardinalidade podem ter diferentes tipos de ordem. Para um conjunto infinito contável, o conjunto de possíveis tipos de ordem é incontável.

Exemplos e contra-exemplos

• Em qualquer conjunto finito, toda relação de ordem total é bem ordenada
• A relação a < b nos números naturais é uma relação bem ordenada
• A relação a R b definida por a R b se, e somente se, a > b é bem ordenada no conjuntos dos números inteiros negativos
• A relação a < b em qualquer conjunto que contenha os números inteiros não é bem ordenada
• É possível construir uma relação bem ordenada nos números inteiros. Basta definir uma bijeção $f:\mathbb {Z} \to \mathbb {N} \,$, e definir a R b = (f(a) < f(b))
• A relação a R b definida nos números naturais por a R 0 para todo a ≠ 0 e a R b sss a < b, a ≠ 0 e b ≠ 0 é uma relação bem ordenada

Formulações equivalentes

Se um conjunto é totalmente ordenado, então as seguintes sentenças são equivalentes entre si:

1. O conjunto é bem-ordenado. Isto é, todo subconjunto não-vazio tem um elemento mínimo.
2. Indução transfinita funciona para todo o conjunto ordenado.
3. Toda sequência estritamente decrescente de elementos do conjunto deve terminar após um número finito de passos (assumindo o princípio da escolha dependente).
4. Toda subordenação é isomórfica a um segmento inicial.

Referências

• Folland, Gerald B. (1999). Real Analysis: Modern Techniques and Their Applications. Col: Pure and applied mathematics 2nd ed. [S.l.]: John Wiley & Sons. pp. 4–6, 9. ISBN 978-0-471-31716-6 
• «Well Order» (em inglês)