Teorema da extensão de Szpilrajn
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Julho de 2016) |
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)[editar | editar código-fonte]
Dada uma relação binária em um conjunto genérico , nós dizemos que é negativamente transitiva se
- onde por nós queremos dizer
Note que a transitividade negativa também pode ser reescrita como :, simplesmente utilizando do fato de também pode ser escrita como
Definição (conexão)[editar | editar código-fonte]
Dada uma relação binária em um conjunto genérico , dizemos que R é (fracamente) conexa se : então ou ou .
- Digamos que R é estritamente conexa ou completa se .
Propriedades[editar | editar código-fonte]
Estas propriedades sobre as relações binárias podem ser facilmente verificadas pela definição:
- R é irreflexiva e transitiva R é assimétrica.
- R é assimétrica, transitiva e conexa 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)[editar | editar código-fonte]
- 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[editar | editar código-fonte]
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:
- de tal modo que e T é uma outra ordem parcial estrita em X.
Esse lema é facilmente provado quando se toma de tal modo que que existe uma vez que a relação não é conexa.
- Abreviando:
podemos definir outra relação:
Finalmente, o conjunto que é trivialmente uma extensão de R e outra ordem parcial estrita em X.
Teorema (Teorema da Extensão de Szpilrajn)[editar | editar código-fonte]
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[editar | editar código-fonte]
- Seja , 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
Claramente é um limite superior da cadeia, mas temos que mostrar que , dai que é outra ordem parcial estrita que estende R.
Obviamente ela contem R, como todo contém R, e é irreflexiva, como , já que qualquer
- é irreflexivo,
Temos que mostrar que é transitiva e usaremos aqui a propriedade de cadeia de .
Seja tal que sse .
Como é definida como uma união de conjuntos, existe
- tal que .
Mas é uma cadeia com respeito à inclusão, portanto ela assume que 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 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[editar | editar código-fonte]
- Szpilrajn, E. (1930), «Sur l'extension de l'ordre partiel», Fundamenta Mathematicae, ISSN 0016-2736, 16: 386–389