Mostre que a relação
, que consiste em todos os pares
tal que
e
são seqüências de bits que coincidem nos seus primeiro e terceiro bits, é uma relação de equivalência no conjunto de todas as seqüências de bits de comprimento maior que ou igual a 3.
Passo 1
O enunciado define a relação
sobre o conjunto
por
por
Queremos mostrar que
é uma relação de equivalência, ou seja, verificar reflexividade, simetria e transitividade.
Passo 2
(Reflexividade)
Tomemos uma sequência arbitrária . Claro que
Tomemos uma sequência arbitrária
logo
. Assim,
é reflexiva.
Passo 3
(Simetria)
Suponha . Então
Suponha
Mas essas igualdades implicam também
portanto
. Assim,
é simétrica.
Passo 4
(Transitividade)
Suponha e
. Então
Suponha
Pela transitividade da igualdade em
segue
isto é,
. Logo,
é transitiva.
Resposta
Como
é reflexiva, simétrica e transitiva, concluímos que
é uma relação de equivalência em
.