Bom pedido - Well-order

Em matemática , uma boa ordem (ou boa ordem ou relação de boa ordem ) em um conjunto S é uma ordem total em S com a propriedade de que todo subconjunto não vazio de S tem um elemento mínimo nesta ordem. O conjunto de S em conjunto com o bem-fim relação é então denominado um conjunto bem ordenada . Em alguns artigos acadêmicos e livros didáticos estes termos são, em vez escrito como wellorder , wellordered e wellordering ou bem ordem , bem ordenada e bem encomendar .

Cada conjunto bem ordenado não vazio tem um elemento mínimo. Cada elemento s de um conjunto bem ordenado, exceto um possível elemento maior , tem um sucessor único (próximo elemento), ou seja, o menor elemento do subconjunto de todos os elementos maiores que s . Pode haver elementos além do elemento mínimo que não têm predecessor (ver § Números naturais abaixo para um exemplo). Um conjunto bem ordenada S contém para cada subconjunto t com um limite superior de menos limite superior ou seja, o elemento menos, do subconjunto de todos os limites superiores de T em S .

Se ≤ for uma ordenação de poço não estrita , então <é uma ordenação de poço estrita. Uma relação é um bem ordenado estrito se e somente se for uma ordem total estrita e bem fundada . A distinção entre ordens de poço estritas e não estritas é freqüentemente ignorada, uma vez que são facilmente interconvertíveis.

Cada conjunto bem ordenado é isomórfico de ordem única a um número ordinal único , chamado de tipo de ordem do conjunto bem ordenado. O teorema da boa ordenação , que é equivalente ao axioma da escolha , afirma que todo conjunto pode ser bem ordenado. Se um conjunto é bem ordenado (ou mesmo se simplesmente admite uma relação bem fundada ), a técnica de prova da indução transfinita pode ser usada para provar que uma determinada afirmação é verdadeira para todos os elementos do conjunto.

A observação de que os números naturais são bem ordenados pela relação menos que usual é comumente chamada de princípio de boa ordenação (para números naturais).

Números ordinais

Artigo principal: número ordinal

Cada conjunto bem ordenado é isomórfico de ordem única a um número ordinal único , chamado de tipo de ordem do conjunto bem ordenado. A posição de cada elemento dentro do conjunto ordenado também é fornecida por um número ordinal. No caso de um conjunto finito, a operação básica de contagem , para encontrar o número ordinal de um determinado objeto, ou para encontrar o objeto com um determinado número ordinal, corresponde a atribuir números ordinais um a um aos objetos. O tamanho (número de elementos, número cardinal ) de um conjunto finito é igual ao tipo de pedido. A contagem, no sentido cotidiano, geralmente começa com um, portanto, atribui a cada objeto o tamanho do segmento inicial com esse objeto como último elemento. Observe que esses números são um a mais do que os números ordinais formais de acordo com a ordem isomórfica, porque eles são iguais ao número de objetos anteriores (que corresponde à contagem a partir do zero). Assim, para n finito , a expressão " n -ésimo elemento" de um conjunto bem ordenado requer contexto para saber se isso conta de zero ou um. Em uma notação "β-ésimo elemento", em que β também pode ser um ordinal infinito, ele normalmente contará a partir de zero.

Para um conjunto infinito, o tipo de pedido determina a cardinalidade , mas não o contrário: conjuntos bem ordenados de uma determinada cardinalidade podem ter muitos tipos de pedidos diferentes, consulte a Seção #Números naturais para obter um exemplo simples. Para um conjunto infinito contável , o conjunto de tipos de pedidos possíveis é incontável.

Exemplos e contra-exemplos

Números naturais

A ordenação padrão ≤ dos números naturais é uma ordenação correta e tem a propriedade adicional de que todo número natural diferente de zero possui um predecessor único.

Outra boa ordenação dos números naturais é dada pela definição de que todos os números pares são menores do que todos os números ímpares, e a ordem usual se aplica dentro dos pares e das probabilidades:

0 2 4 6 8 ... 1 3 5 7 9 ...

Este é um conjunto bem ordenado do tipo de pedido ω + ω. Cada elemento tem um sucessor (não há elemento maior). Dois elementos não têm um predecessor: 0 e 1.

Inteiros

Ao contrário da ordenação padrão ≤ dos números naturais , a ordenação padrão ≤ dos inteiros não é uma boa ordenação, uma vez que, por exemplo, o conjunto de inteiros negativos não contém um elemento mínimo.

A seguinte relação R é um exemplo de boa ordenação dos inteiros: x R y se e somente se uma das seguintes condições for mantida:

  1. x = 0
  2. x é positivo ey é negativo
  3. x e y são ambos positivos, e x ≤ y
  4. x e y são ambos negativos e | x | ≤ | y |

Esta relação R pode ser visualizada da seguinte forma:

0 1 2 3 4 ... −1 −2 −3 ...

R é isomorfo ao número ordinal ω + ω.

Outra relação para ordenar bem os inteiros é a seguinte definição: x  ≤ z   y se e somente se (| x | <| y | ou (| x | = | y | e x  ≤  y )). Esta ordem de poço pode ser visualizada da seguinte forma:

0 −1 1 −2 2 −3 3 −4 4 ...

Tem o tipo de pedido ω.

Reais

A ordenação padrão ≤ de qualquer intervalo real não é uma ordenação boa, pois, por exemplo, o intervalo aberto (0, 1) ⊆ [0,1] não contém um elemento mínimo. A partir dos axiomas ZFC da teoria dos conjuntos (incluindo o axioma da escolha ), pode-se mostrar que existe uma boa ordem dos reais. Também Wacław Sierpiński provou que ZF + GCH (a hipótese do contínuo generalizado ) implica o axioma da escolha e, portanto, uma boa ordem dos reais. No entanto, é possível mostrar que os axiomas ZFC + GCH por si só não são suficientes para provar a existência de uma ordem definível (por uma fórmula) dos reais. No entanto, é consistente com ZFC que existe uma ordenação definível dos reais - por exemplo, é consistente com ZFC que V = L , e segue de ZFC + V = L que uma fórmula particular ordena bem os reais, ou mesmo qualquer definir.

Um incontável subconjunto de números reais com a ordem padrão ≤ não pode ser uma boa ordem: Suponha que X seja um subconjunto de R bem ordenado por ≤. Para cada x em X , seja s ( x ) o sucessor de x na ordem ≤ em X (a menos que x seja o último elemento de X ). Seja A = {( x , s ( x )) | x ∈ X } cujos elementos são intervalos não vazios e disjuntos. Cada tal intervalo contém pelo menos um número racional, para que haja uma função injetivo de uma a Q . Há uma injeção de X para A (exceto possivelmente para um último elemento de X que poderia ser mapeado para zero posteriormente). E é sabido que há uma injeção de Q nos números naturais (que poderiam ser escolhidos para evitar que se batesse em zero). Assim, há uma injeção de X nos números naturais, o que significa que X é contável. Por outro lado, um subconjunto infinito contável de reais pode ou não ser uma ordem de poço com o padrão "≤". Por exemplo,

  • Os números naturais são uma boa ordem sob a ordem padrão ≤.
  • O conjunto {1 / n: n = 1,2,3, ...} não tem o menor elemento e, portanto, não é uma boa ordem sob a ordem padrão ≤.

Exemplos de ordens de poço:

  • O conjunto de números {- 2 - n | 0 ≤ n <ω} tem tipo de pedido ω.
  • O conjunto de números {- 2 - n - 2 - m - n | 0 ≤ m , n <ω} tem tipo de pedido ω 2 . O conjunto anterior é o conjunto de pontos limite dentro do conjunto. Dentro do conjunto de números reais, seja com a topologia ordinária ou com a topologia de ordem, 0 também é um ponto limite do conjunto. É também um ponto limite do conjunto de pontos limite.
  • O conjunto de números {- 2 - n | 0 ≤ n <ω} ∪ {1} tem tipo de pedido ω + 1. Com a topologia de pedido deste conjunto, 1 é um ponto limite do conjunto. Com a topologia comum (ou equivalentemente, a topologia de ordem) dos números reais não é.

Formulações equivalentes

Se um conjunto estiver totalmente ordenado , os seguintes são equivalentes entre si:

  1. O conjunto está bem ordenado. Ou seja, todo subconjunto não vazio tem um elemento mínimo.
  2. A indução transfinita funciona para todo o conjunto solicitado.
  3. Cada sequência estritamente decrescente de elementos do conjunto deve terminar após apenas um número finito de etapas (assumindo o axioma da escolha dependente ).
  4. Cada subordinação é isomórfica a um segmento inicial.

Topologia do pedido

Cada conjunto bem ordenado pode ser transformado em um espaço topológico dotando-o da topologia de ordem .

Com relação a esta topologia, pode haver dois tipos de elementos:

  • pontos isolados - estes são o mínimo e os elementos com um predecessor.
  • pontos limite - este tipo não ocorre em conjuntos finitos, podendo ou não ocorrer em conjuntos infinitos; os conjuntos infinitos sem ponto limite são os conjuntos de tipo ordem ω, por exemplo N .

Para subconjuntos, podemos distinguir:

  • Subconjuntos com um máximo (ou seja, subconjuntos que são limitados por eles mesmos); pode ser um ponto isolado ou um ponto limite de todo o conjunto; no último caso, pode ou não ser também um ponto limite do subconjunto.
  • Subconjuntos que são ilimitados por si próprios, mas limitados em todo o conjunto; eles não têm máximo, mas um supremo fora do subconjunto; se o subconjunto não for vazio, esse supremo é um ponto limite do subconjunto e, portanto, também de todo o conjunto; se o subconjunto estiver vazio, este supremo é o mínimo de todo o conjunto.
  • Subconjuntos que são ilimitados em todo o conjunto.

Um subconjunto é cofinal em todo o conjunto se, e somente se, for ilimitado em todo o conjunto ou tiver um máximo que também é máximo em todo o conjunto.

Um conjunto bem ordenado como espaço topológico é um espaço de primeira contagem se e somente se tiver tipo de pedido menor ou igual a ω 1 ( ômega-um ), ou seja, se e somente se o conjunto for contável ou tiver o menor tipo de pedido incontável .

Veja também

Referências

  1. ^ Feferman, S. (1964). “Algumas aplicações das noções de forçantes e conjuntos genéricos” . Fundamenta Mathematicae . 56 (3): 325–345. doi : 10.4064 / fm-56-3-325-345 .