Seja
a relação no conjunto de todas as pessoas que já visitaram uma página particular na Web tal que
se e somente se a pessoa
e a pessoa
seguiram o mesmo conjunto de links, começando nessa página da Web (indo de página da Web para página da Web até que parassem de usar a Web). Mostre que
é uma relação de equivalência.
Passo 1
O enunciado define uma relação
num conjunto
de pessoas que já visitaram uma certa página na Web. Para quaisquer duas pessoas
, dizemos
O que precisamos mostrar é que
é uma relação de equivalência, ou seja, que ela satisfaz as três propriedades:
- Reflexividade:
. - Simetria:
. - Transitividade:
.
Passo 2
(Reflexividade)
Pegue qualquer pessoa . Ela segue um certo conjunto de links — e, logicamente, esse conjunto coincide consigo própria. Logo,
e
seguem o mesmo conjunto de links, o que nos dá
Pegue qualquer pessoa
Passo 3
(Simetria)
Suponha que . Por definição, isso significa que o conjunto de links seguidos por
é igual ao conjunto de links seguidos por
. Mas igualdade de conjuntos é uma relação simétrica, isto é, se
então
. Portanto,
também segue o mesmo conjunto que
, logo
Suponha que
Passo 4
(Transitividade)
Suponha que e
. Então o conjunto de links de
é igual ao de
, e o de
é igual ao de
. Pela transitividade da igualdade de conjuntos, o conjunto de
coincide com o de
. Logo
Suponha que
Resposta
Como
é reflexiva, simétrica e transitiva, concluímos que
é relação de equivalência.