Teorema de extensão de Szpilrajn

Teorema da extensão de Szpilrajn Na teoria da ordem, o teorema de extensão de Szpilrajn (também chamado de princípio de extensão de ordem), provado por Edward Szpilrajn em 1930,[1] afirma que toda ordem parcial estrita está contida em uma ordem total. Intuitivamente, o teorema diz que qualquer método de comparação de elementos que deixa alguns pares incomparáveis ​​pode ser estendido de tal forma que cada par se torna comparável. O teorema é um dos muitos exemplos do uso do axioma de escolha na forma do lema de Zorn para encontrar um conjunto maximal com certas propriedades.

Conteúdo 1 Definições e declaração 2 Prova 3 Outros teoremas de extensão 4 Veja também 5 References Definitions and statement A binary relation {estilo de exibição R} em um conjunto {estilo de exibição X} é formalmente definido como um conjunto de pares ordenados {estilo de exibição (x,y)} de elementos de {estilo de exibição X,} e {estilo de exibição (x,y)em R} é muitas vezes abreviado como {estilo de exibição xRy.} Uma relação é reflexiva se {estilo de exibição xRx} vale para cada elemento {estilo de exibição xin X;} é transitivo se {estilo de exibição xRy{texto{ e }}y Rz} implicar {estilo de exibição xRz} para todos {estilo de exibição x,y,Zin X;} é antisimétrica se {estilo de exibição xRy{texto{ e }}yRx} implicar {estilo de exibição x=y} para todos {estilo de exibição x,yin X;} e é uma relação de conexão se {estilo de exibição xRy{texto{ ou }}yRx} vale para todos {estilo de exibição x,Yin X.} Um pedido parcial é, por definição, um reflexivo, relação transitiva e antisimétrica. Um pedido total é um pedido parcial que está conectado.

Uma relação {estilo de exibição R} está contido em outra relação {estilo de exibição S} quando todos os pares ordenados em {estilo de exibição R} também aparecem em {estilo de exibição S;} isso é, {estilo de exibição xRy} implica {estilo de exibição xSy} para todos {estilo de exibição x,Yin X.} O teorema da extensão afirma que toda relação {estilo de exibição R} isso é reflexivo, transitivo e antisimétrico (isso é, um pedido parcial) está contido em outra relação {estilo de exibição S} que é reflexivo, transitivo, antisimétrico e conexo (isso é, um pedido total).

Proof The theorem is proved in two steps. Primeiro, se um pedido parcial não se compara {estilo de exibição x} e {estilo de exibição y,} pode ser estendido adicionando primeiro o par {estilo de exibição (x,y)} e, em seguida, realizando o fechamento transitivo, e em segundo lugar, já que esta operação gera uma ordenação que contém estritamente a original e pode ser aplicada a todos os pares de elementos incomparáveis, existe uma relação na qual todos os pares de elementos se tornaram comparáveis.

O primeiro passo é provado como um lema preliminar, em que uma ordem parcial em que um par de elementos {estilo de exibição x} e {estilo de exibição y} são incomparáveis ​​é alterado para torná-los comparáveis. Isso é feito adicionando primeiro o par {estilo de exibição xRy} para a relação, que pode resultar em uma relação não transitiva, e, em seguida, restaurando a transitividade adicionando todos os pares {qRp estilo de exibição} de tal modo que {estilo de exibição qRx{texto{ e }}yRp.} Isso é feito em um único par de elementos incomparáveis {estilo de exibição x} e {estilo de exibição y,} e produz uma relação ainda reflexiva, antisimétrico e transitivo e que contém estritamente o original.

A seguir mostra-se que a poset de ordens parciais contendo {estilo de exibição R,} ordenado por inclusão, tem um elemento máximo. A existência de tal elemento máximo é provada aplicando o lema de Zorn a este poset. Uma cadeia neste poset é um conjunto de relações contendo {estilo de exibição R} tal que, dadas quaisquer duas dessas relações, um está contido no outro.

Para aplicar o lema de Zorn, deve ser mostrado que toda cadeia tem um limite superior no poset. Deixar {estilo de exibição {matemática {C}}} seja tal cadeia, e resta mostrar que a união de seus elementos, {copo grande estilo de exibição {matemática {C}},} é um limite superior para {estilo de exibição {matemática {C}}} que está na pose: {estilo de exibição {matemática {C}}} contém a relação original {estilo de exibição R} uma vez que cada elemento de {estilo de exibição {matemática {C}}} é uma ordem parcial contendo {estilo de exibição R.} Próximo, é mostrado que {copo grande estilo de exibição {matemática {C}}} é uma relação transitiva. Suponha que {estilo de exibição (x,y)} e {estilo de exibição (y,z)} estão dentro {copo grande estilo de exibição {matemática {C}},} para que existam {estilo de exibição S,Lata {matemática {C}}} de tal modo que {estilo de exibição (x,y)em S{texto{ e }}(y,z)em T.} Desde {estilo de exibição {matemática {C}}} é uma cadeia, qualquer {estilo de exibição Ssubseteq T{texto{ ou }}Tsuseteq S.} Suponha {estilo de exibição Ssubseteq T;} o argumento para quando {estilo de exibição Tsubseteq S} É similar. Então {estilo de exibição (x,y)em T.} Como todas as relações produzidas pelo nosso processo são transitivas, {estilo de exibição (x,z)} é em {estilo de exibição T} e, portanto, também em {copo grande estilo de exibição {matemática {C}}.} De forma similar, pode ser mostrado que {copo grande estilo de exibição {matemática {C}}} é antisimétrico.

Portanto, pelo lema de Zorn o conjunto de ordens parciais contendo {estilo de exibição R} tem um elemento máximo {estilo de exibição Q,} e resta apenas mostrar que {estilo de exibição Q} é total. De fato, se {estilo de exibição Q} tinha um par de elementos incomparáveis, então é possível aplicar o processo do primeiro passo a ele, levando a outra ordem parcial estrita que contém {estilo de exibição R} e contém estritamente {estilo de exibição Q,} contradizendo isso {estilo de exibição Q} é máximo. {estilo de exibição Q} é, portanto, uma ordem total contendo {estilo de exibição R,} completando a prova.

Other extension theorems Arrow stated that every preorder (Relação reflexiva e transitiva) pode ser estendido para uma pré-encomenda total (relação transitiva e conexa), e esta afirmação foi mais tarde provada por Hansson.

Suzumura provou que uma relação binária pode ser estendida para uma pré-ordem total se e somente se for consistente com Suzumura, o que significa que não há ciclo de elementos tal que {estilo de exibição xRy} para cada par de elementos consecutivos {estilo de exibição (x,y),} e há algum par de elementos consecutivos {estilo de exibição (x,y)} no ciclo para o qual {estilo de exibição yRx} não segura.

See also Linear extension – Mathematical ordering of a partial order References ^ Szpilrajn, Eduardo (1930), "Sobre a extensão da ordem parcial" (PDF), Fundamentos da Matemática (em francês), 16: 386-389, doi:10.4064/fm-16-1-386-389. Categorias: Axioma da escolhaTeoremas nos fundamentos da matemáticaTeoria da ordem