Mostre que a relação R no conjunto de todas as seqüências de bits tal que s R t se e somente se s e t contiverem o mesmo número de 1s é uma relação de equivalência.

Passo 1

Temos o conjunto S de todas as sequências finitas de bits (0 e 1) e a relação
s\,R\,t \iff \#_1(s)=\#_1(t),
onde \#_1(x) é o número de ocorrências de 1 em x. Para provar que R é uma relação de equivalência, precisamos verificar que ela é reflexiva, simétrica e transitiva.

Passo 2

(reflexividade)
Para qualquer sequência s\in S vale
\#_1(s)=\#_1(s),
logo s\,R\,s. Assim, R é reflexiva.

Passo 3

(simetria)
Se s\,R\,t, então por definição \#_1(s)=\#_1(t). Mas igualdade é simétrica, então \#_1(t)=\#_1(s), o que implica t\,R\,s. Logo, R é simétrica.

Passo 4

(transitividade)
Suponha s\,R\,t e t\,R\,u. Então
\#_1(s)=\#_1(t) \quad\text{e}\quad \#_1(t)=\#_1(u).
Pela transitividade da igualdade temos \#_1(s)=\#_1(u), ou seja, s\,R\,u. Assim, R é transitiva.

Resposta

A relação R é de equivalência, pois satisfaz reflexividade, simetria e transitividade.

Exercícios de Livros Relacionados