a) Prove que: se
e definimos
tal que
, então essa relação é de equivalência. Mais ainda, o conjunto das classes de equivalência
. Dizemos que
é induzida pela partição
.
Passo 1
Beleza, aqui a ideia é trabalhar com partições e relações de equivalência. O enunciado diz que temos um conjunto
e uma partição
dele, ou seja:
1°) Cada duas partes em são disjuntas.
2°) A união de todas as partes dá .
1°) Cada duas partes em
2°) A união de todas as partes dá
A gente define uma relação em
assim:
Precisamos provar duas coisas:
a) é de equivalência (ou seja, reflexiva, simétrica e transitiva).
b) As classes de equivalência de coincidem exatamente com os blocos de
; em símbolos,
.
a)
b) As classes de equivalência de
Para isso, vamos usar a definição de relação de equivalência e de classe de equivalência.
Passo 2
Mostrar que
é reflexiva.
Definição: uma relação é reflexiva se para todo ,
.
Como é uma partição que cobre
, para cada
existe pelo menos um bloco
tal que
. Mas aí
e
estão no mesmo
, logo
.
Conclusão: é reflexiva.
Definição: uma relação é reflexiva se para todo
Como
Conclusão:
Passo 3
Mostrar que
é simétrica.
Definição: simétrica quer dizer: se , então
.
Suponha . Então existe um bloco
com
. Mas isso não distingue ordem: se
, também
. Logo
.
Conclusão: é simétrica.
Definição: simétrica quer dizer: se
Suponha
Conclusão:
Passo 4
Mostrar que
é transitiva.
Definição: transitiva significa: se e
, então
.
Definição: transitiva significa: se
-
implica que existe com . -
implica que existe com .
Como em uma partição blocos são ou iguais ou disjuntos, e
pertence a ambos
e
, a única saída é
. Então
e
estão juntos nesse mesmo bloco, ou seja,
.
Conclusão: é transitiva.
Conclusão:
Até aqui, como é reflexiva, simétrica e transitiva,
é de equivalência.
Passo 5
Mostrar que as classes de equivalência são os blocos de
.
Lembrando que, para relação de equivalência
, a classe de equivalência de um
é
(a) Primeiro, dado
, ele está em algum bloco
.
- Se
, então está no mesmo bloco que , logo . - Reciprocamente, todo
tem .
Conclusão:. Isso mostra que cada classe é exatamente um bloco de .
(b) Por outro lado, cada bloco
é
para qualquer
.
Portanto o conjunto de todas as classes de equivalência
é igual a
.
Resposta
A relação
é reflexiva, simétrica e transitiva, logo é de equivalência. Além disso, cada classe de equivalência coincide com um bloco da partição
, de modo que
.