Teorema da extensão de Szpilrajn

Predefinição:Sem notas 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

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

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

Note que a transitividade negativa também pode ser reescrita como :$\mathrm{\forall }x,y,z\in X(xRy)\Rightarrow (xRz)\vee (zRy)$, simplesmente utilizando do fato de $A\Rightarrow B$ também pode ser escrita como $\mathrm{\neg }A\vee 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 :$\mathrm{\forall }x,y\in X:x=y$ então ou $xRy$ ou $yRx$.

Digamos que R é estritamente conexa ou completa se $\mathrm{\forall }x,y\in X,xRy\vee 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:

$\mathrm{\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=y\in X$ de tal modo que $\mathrm{\neg }(xRy)\wedge \mathrm{\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 $𝒫=\{P:R\subset P$, P é uma ordem parcial estrita em X$\}$.

Queremos mostrar a existência de um elemento maximal em $𝒫$ 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 $𝒫$ admite um limite superior em $𝒫$.

Seja $𝒞$ uma cadeia em $𝒫$.

Defina

$ℳ=\bigcup _{C\in 𝒞}C.$

Claramente $ℳ$ é um limite superior da cadeia, mas temos que mostrar que $ℳ\in 𝒫$, dai que $ℳ$ é outra ordem parcial estrita que estende R.

Obviamente ela contem R, como todo $C\in 𝒞$ contém R, e é irreflexiva, como $(\bigcup _{C\in 𝒞}C)\cap {\mathrm{\Delta }}_X=\bigcup _{C\in 𝒞}(C\cap {\mathrm{\Delta }}_X)=\mathrm{\varnothing }$, já que qualquer

$C\in 𝒞$ é irreflexivo,

${\mathrm{\Delta }}_X=\{(x,x)|x\in X\}.$

Temos que mostrar que $ℳ$ é transitiva e usaremos aqui a propriedade de cadeia de $𝒞$.

Seja $x,y,z\in X$ tal que $xℳy\wedge yℳz$ sse $(x,y),(y,z)\in ℳ$.

Como $ℳ$ é definida como uma união de conjuntos, existe

$P_1,P_2\in 𝒞$ tal que $(x,y)\in P_1,(y,z)\in P_2.$.

Mas $𝒞$ é 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 $ℳ$.

Aplicando o Lema de Zorn, deduzimos que $𝒫$ 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 $𝒫$, contradizendo que T é um maximal de $𝒫$.

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

• Predefinição:Citation