Relação bem-ordenadaNa 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 ordinaisTodo 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
Formulações equivalentesSe um conjunto é totalmente ordenado, então as seguintes sentenças são equivalentes entre si:
Referências
|