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 ${\displaystyle R\subseteq X\times X}$ em um conjunto genérico ${\displaystyle X}$, nós dizemos que ${\displaystyle R}$ é negativamente transitiva se

${\displaystyle \forall \ x,y,z\in X\ \ \neg (xRz)\land \neg (zRy)\Rightarrow \neg (xRy),}$

onde por ${\displaystyle \neg (xRy)}$ nós queremos dizer ${\displaystyle (x,y)\not \in R.}$

Note que a transitividade negativa também pode ser reescrita como :${\displaystyle \forall \ x,y,z\in X\ \ (xRy)\Rightarrow (xRz)\lor (zRy)}$, simplesmente utilizando do fato de ${\displaystyle A\Rightarrow B}$ também pode ser escrita como ${\displaystyle \neg A\lor B}$

Definição (conexão)

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

Digamos que R é estritamente conexa ou completa se ${\displaystyle \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 ${\displaystyle \Rightarrow }$ R é assimétrica.

R é assimétrica, transitiva e conexa ${\displaystyle \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:

${\displaystyle \exists T\subseteq X\times X}$ de tal modo que ${\displaystyle R\subset T}$ e T é uma outra ordem parcial estrita em X.

Esse lema é facilmente provado quando se toma ${\displaystyle x\not =y\in X}$ de tal modo que ${\displaystyle \neg (xRy)\land \neg (yRx)}$ que existe uma vez que a relação não é conexa.

Abreviando:

${\displaystyle Rx=\{z\in X|zRx\}}$

${\displaystyle yR=\{z\in X|yRz\}}$

podemos definir outra relação:

${\displaystyle S=\{x\}\cup Rx\times \{y\}\cup yR\subseteq X\times X.}$

Finalmente, o conjunto ${\displaystyle 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 ${\displaystyle {\mathcal {P}}=\{P:R\subset P}$, P é uma ordem parcial estrita em X${\displaystyle \}}$.

Queremos mostrar a existência de um elemento maximal em ${\displaystyle {\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 ${\displaystyle {\mathcal {P}}}$ admite um limite superior em ${\displaystyle {\mathcal {P}}}$.

Seja ${\displaystyle {\mathcal {C}}}$ uma cadeia em ${\displaystyle {\mathcal {P}}}$.

Defina

${\displaystyle {\mathcal {M}}=\bigcup _{C\in {\mathcal {C}}}C.}$

Claramente ${\displaystyle {\mathcal {M}}}$ é um limite superior da cadeia, mas temos que mostrar que ${\displaystyle {\mathcal {M}}\in {\mathcal {P}}}$, dai que ${\displaystyle {\mathcal {M}}}$ é outra ordem parcial estrita que estende R.

Obviamente ela contem R, como todo ${\displaystyle C\in {\mathcal {C}}}$ contém R, e é irreflexiva, como ${\displaystyle (\bigcup _{C\in {\mathcal {C}}}C)\cap \Delta _{X}=\bigcup _{C\in {\mathcal {C}}}(C\cap \Delta _{X})=\emptyset }$, já que qualquer

${\displaystyle C\in {\mathcal {C}}}$ é irreflexivo,

${\displaystyle \Delta _{X}=\{(x,x)|x\in X\}.}$

Temos que mostrar que ${\displaystyle {\mathcal {M}}}$ é transitiva e usaremos aqui a propriedade de cadeia de ${\displaystyle {\mathcal {C}}}$.

Seja ${\displaystyle x,y,z\in X}$ tal que ${\displaystyle x{\mathcal {M}}y\land y{\mathcal {M}}z}$ sse ${\displaystyle (x,y),(y,z)\in {\mathcal {M}}}$.

Como ${\displaystyle {\mathcal {M}}}$ é definida como uma união de conjuntos, existe

${\displaystyle P_{1},P_{2}\in {\mathcal {C}}}$ tal que ${\displaystyle (x,y)\in P_{1},(y,z)\in P_{2}.}$.

Mas ${\displaystyle {\mathcal {C}}}$ é uma cadeia com respeito à inclusão, portanto ela assume que ${\displaystyle 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 ${\displaystyle (x,z)}$ também está neste conjunto, portanto em ${\displaystyle {\mathcal {M}}}$.

Aplicando o Lema de Zorn, deduzimos que ${\displaystyle {\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 ${\displaystyle {\mathcal {P}}}$, contradizendo que T é um maximal de ${\displaystyle {\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