- Seja
a relação que consiste em todos os pares
tal que
e
são seqüências de letras maiúsculas e minúsculas da língua inglesa com a propriedade que, para todo inteiro positivo
, o enésimo caractere em
e
é a mesma letra, ou minúscula ou maiúscula. Mostre que
é uma relação de equivalência.
Passo 1
O enunciado define uma relação
sobre o conjunto
de todas as sequências (infinitas) de letras inglesas maiúsculas e minúsculas. Para
e
, temos
O objetivo é mostrar que
é uma relação de equivalência, ou seja, que é reflexiva, simétrica e transitiva.
Passo 2
Mostramos que
é reflexiva, isto é,
De fato, para qualquer sequência
e qualquer
, temos
comparado a si mesmo, portanto são a mesma letra ignorando o caso. Logo
e
é reflexiva.
Passo 3
Mostramos que
é simétrica, ou seja,
Suponha
. Então
Mas isso é claramente uma relação simétrica: se
e
coincidem ignorando caso, então
e
também coincidem. Logo
e
é simétrica.
Passo 4
Mostramos que
é transitiva, isto é,
Suponha
e
. Então para todo
vale simultaneamente
-
e coincidem ignorando caso, -
e coincidem ignorando caso.
Como “coincidir ignorando caso” é transitivo sobre três letras, concluímos quee coincidem, . Logo e é transitiva.
Resposta
Concluímos que
é reflexiva, simétrica e transitiva, portanto é uma relação de equivalência em
.