# Teorema da extensão de Szpilrajn

Na matemática, O Teorema da Extensão de Szpilrajn, assim denominado em homenagem a Edward Szpilrajn (1930) (mais tarde chamado Edward Marczewski), é um dos muitos exemplos do uso do axioma da escolha (na forma do Lema de Zorn) para encontrar um conjunto maximal com certas propriedades.
O teorema afirma que, dada uma relação binária R que é irreflexiva e transitiva sempre é possível encontrar uma extensão da relação (ou seja, uma relação T que inclui estritamente R), que é assimétrica, negativamente transitiva e conexa.
Antes de tudo, precisamos de algumas definições de modo que fique claro qual é a terminologia que usaremos quando estivermos falando sobre as relações com propriedades particulares.

## Definição (transitividade negativa)

Dada uma relação binária $R\subseteq X\times X$ em um conjunto genérico $X$, nós dizemos que $R$ é negativamente transitiva se
    $\forall \ x,y,z\in X\ \ \neg (xRz)\land \neg (zRy)\Rightarrow \neg (xRy),$
    onde por $\neg (xRy)$ nós queremos dizer $(x,y)\not \in R.$
Note que a transitividade negativa também pode ser reescrita como :$\forall \ x,y,z\in X\ \ (xRy)\Rightarrow (xRz)\lor (zRy)$, simplesmente utilizando do fato de $A\Rightarrow B$ também pode ser escrita como $\neg A\lor B$

## Definição (conexão)

Dada uma relação binária $R\subseteq X\times X$ em um conjunto genérico $X$, dizemos que R é (fracamente) conexa se :$\forall x,y\in X:x\not =y$ então ou $xRy$ ou $yRx$.
    Digamos que R é estritamente conexa ou completa se $\forall x,y\in X,xRy\lor yRx$.

## Propriedades

Estas propriedades sobre as relações binárias podem ser facilmente verificadas pela definição:
    R é irreflexiva e transitiva $\Rightarrow$ R é assimétrica.
    R é assimétrica, transitiva e conexa $\Rightarrow$ R é negativamente transitiva.
Para enunciar precisamente o teorema, precisamos ainda de um par de definições e um lema simples útil.

## Definição (orem estrita)

    Uma relação binária R é dita ser uma ordem estrita parcial se for irreflexiva e transitiva, e que é uma ordem estrita, se for assimétrica, negativamente transitiva e completa.

## Lema

Seja R uma ordem parcial estrita em X. Então existe uma outra relação binária T em X que ainda é uma ordem parcial estrita e estende R, portanto:
    $\exists T\subseteq X\times X$ de tal modo que $R\subset T$ e T é uma outra ordem parcial estrita em X.
Esse lema é facilmente provado quando se toma $x\not =y\in X$ de tal modo que $\neg (xRy)\land \neg (yRx)$ que existe uma vez que a relação não é conexa.
    Abreviando:
    $Rx=\{z\in X|zRx\}$
    $yR=\{z\in X|yRz\}$
podemos definir outra relação:
    $S=\{x\}\cup Rx\times \{y\}\cup yR\subseteq X\times X.$
Finalmente, o conjunto $T=R\cup S$ que é trivialmente uma extensão de R e outra ordem parcial estrita em X.

## Teorema (Teorema da Extensão de Szpilrajn)

Seja R uma ordem estrita parcial no conjunto de X. Então existe uma relação T que estende R e é uma ordem estrita em X.

## Prova

    Seja ${\mathcal {P}}=\{P:R\subset P$, P é uma ordem parcial estrita em X$\$.
Queremos mostrar a existência de um elemento maximal em ${\mathcal {P}}$ com respeito ao conjunto inclusão.
Para fazer isso, iremos utilizar o Lema de Zorn. Primeiramente queremos verificar a hipotese do Lema, daí que qualquer cadeia (com respeito à inclusão) de ${\mathcal {P}}$ admite um limite superior em ${\mathcal {P}}$.
Seja ${\mathcal {C}}$ uma cadeia em ${\mathcal {P}}$.
Defina
    ${\mathcal {M}}=\bigcup _{C\in {\mathcal {C}}}C.$
Claramente ${\mathcal {M}}$ é um limite superior da cadeia, mas temos que mostrar que ${\mathcal {M}}\in {\mathcal {P}}$, dai que ${\mathcal {M}}$ é outra ordem parcial estrita que estende R.
Obviamente ela contem R, como todo $C\in {\mathcal {C}}$ contém R, e é irreflexiva, como $(\bigcup _{C\in {\mathcal {C}}}C)\cap \Delta _{X}=\bigcup _{C\in {\mathcal {C}}}(C\cap \Delta _{X})=\emptyset$, já que qualquer
    $C\in {\mathcal {C}}$ é irreflexivo,
    $\Delta _{X}=\{(x,x)|x\in X\}.$
Temos que mostrar que ${\mathcal {M}}$ é transitiva e usaremos aqui a propriedade de cadeia de ${\mathcal {C}}$.
Seja $x,y,z\in X$ tal que $x{\mathcal {M}}y\land y{\mathcal {M}}z$ sse $(x,y),(y,z)\in {\mathcal {M}}$.
Como ${\mathcal {M}}$ é definida como uma união de conjuntos, existe
    $P_{1},P_{2}\in {\mathcal {C}}$ tal que $(x,y)\in P_{1},(y,z)\in P_{2}.$.
Mas ${\mathcal {C}}$ é uma cadeia com respeito à inclusão, portanto ela assume que $P_{1}\subseteq P_{2}$ ou vice versa, de modo que os dois casais de elementos de X ambos pertencem ao mesmo conjunto da união, e esse conjunto é uma relação transitiva; então $(x,z)$ também está neste conjunto, portanto em ${\mathcal {M}}$.
Aplicando o Lema de Zorn, deduzimos que ${\mathcal {P}}$ admite um limite superior com respeito ao conjunto de inclusões; vamos chamar T esse limite.
T tem que ser uma relação completa, já que s
Tem que haver uma relação completa, já que se não fosse, poderíamos construir (exatamente como no Lema anterior) outra relação binária que se estende estritamente (inclui estritamente) T e é uma ordem parcial estrita, de modo ainda mais um elemento de ${\mathcal {P}}$, contradizendo que T é um maximal de ${\mathcal {P}}$.
Então T é uma relação binária irreflexiva, transitiva e completa em X. Mas como observamos acima, irreflexividade e transitividade dão assimetria que, com transitividade e completividade, dão a negatividade transitiva.
Portanto T é uma ordem estrita em X que estende a ordem parcial R.

## Referencias

* Szpilrajn, E. (1930), «Sur l'extension de l'ordre partiel», Fundamenta Mathematicae, ISSN 0016-2736, 16: 386–389