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