Mostre que a relação
no conjunto de todas as seqüências de bits tal que
se e somente se
e
contiverem o mesmo número de 1s é uma relação de equivalência.
Passo 1
Temos o conjunto
de todas as sequências finitas de bits (0 e 1) e a relação
onde
é o número de ocorrências de
em
. Para provar que
é uma relação de equivalência, precisamos verificar que ela é reflexiva, simétrica e transitiva.
Passo 2
(reflexividade)
Para qualquer sequência vale
Para qualquer sequência
logo
. Assim,
é reflexiva.
Passo 3
(simetria)
Se , então por definição
. Mas igualdade é simétrica, então
, o que implica
. Logo,
é simétrica.
Se
Passo 4
(transitividade)
Suponha e
. Então
Suponha
Pela transitividade da igualdade temos
, ou seja,
. Assim,
é transitiva.
Resposta
A relação
é de equivalência, pois satisfaz reflexividade, simetria e transitividade.