Teorema de extensão de Szpilrajn

Em matemática , o teorema de extensão de Szpilrajn , demonstrado por Edward Szpilrajn , afirma que qualquer ordem parcial está contida em uma ordem total . Intuitivamente, o teorema diz que uma comparação entre elementos que deixa alguns pares incomparáveis ​​pode ser estendida de tal forma que cada elemento seja inferior ou superior a outro. Este é um dos muitos exemplos de uso do axioma de escolha (na forma do lema de Zorn ) para encontrar um conjunto máximo com certas propriedades.

Definições e declaração

• Uma relação binária R em um conjunto S é formalmente definida como um conjunto de pares ordenados ( x , y ) de elementos de S . A condição ( x , y ) ∈ R é geralmente abreviada como xRy .
• Uma relação de ordem (ou ordem parcial) em S é uma relação binária reflexiva ( xRx para todo x ∈ S ), antissimétrica ( xRy e yRx implica x = y ) e transitiva ( xRy e yRz implica xRz ).
• Se for mais total ( xRy ou yRx é verdadeiro para cada par ( x , y ) de elementos de S ), dizemos que é uma ordem total.
• Uma relação R está contida em outra relação T quando cada par no primeiro está também no segundo, isto é , quando xRy implica xTy .

Os estados de extensão teorema que qualquer relação de ordem (parcial) R está contido em uma relação de ordem total t .

Demonstração

Seja E todas as ordens parciais (não vazias) em S que contêm a sequência R dada .

Ordenando E por inclusão, obtemos um conjunto indutivo . Na verdade, qualquer cadeia de E , ou seja , qualquer parte C de E totalmente ordenado pela relação de inclusão, admitiu em E um limite superior  : a reunião dos elementos C .

De acordo com o lema de Zorn, E , portanto, tem pelo menos um elemento minimal Q .

Esta ordem Q em S é total, porque de outro modo, não existiria em S dois elementos Q -incomparable x e y , e pode-se, em seguida, formar um elemento t de E contendo estritamente Q (o que contraria a maximalidade de Q ): bastaria tomar para T o fechamento transitivo de Q ∪ {( x , y )}. ( T seria bastante antissimétrico, uma vez que Q ∪ {( x , y )} seria sem ciclo.)

Outros teoremas de extensão

• Kenneth Arrow afirmou que qualquer pré-encomenda (relação reflexiva e transitiva) pode ser estendida em uma pré-encomenda total; esta afirmação foi posteriormente comprovada por Hansson.
• Kotaro Suzumura  (in) provou que uma relação binária R pode ser estendida para formar uma ordem fraca se e somente se for Suzumura- isto é, d consistente . se não houver ciclo de elementos em que xRy para cada par ( x , y ) de elementos consecutivos e em que, para pelo menos um desses pares, yRx não seja verdadeiro.

Notas e referências

(pt) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado "  Teorema da extensão de Szpilrajn  " ( veja a lista de autores ) .

1. E. Szpilrajn, “  Sobre a Extensão da Ordem Parcial  ”, Fundo. Matemática. , vol.  16,1930, p.  386-389 ( ler online ).