Sejam
uma função e
uma relação de equivalência sobre
determinada por
. Mostre que
se, e somente se,
implica que
, para todos
.
Passo 1
Beleza, vamos lá! O enunciado nos pede para mostrar que, para uma função
e uma relação de equivalência
definida por
, a condição
é verdadeira se e somente se, sempre que
está na classe de equivalência de
(escrito
), então
também está na classe de
. Para resolver isso, vamos precisar entender o que são relações de equivalência, composição de funções e condições de idempotência.
Passo 2
Primeiro, vamos relembrar o que é uma relação de equivalência. É uma relação que é reflexiva, simétrica e transitiva. Quando temos uma relação de equivalência
sobre um conjunto
, ela divide
em classes de equivalência, onde todos os elementos de uma classe estão relacionados entre si.
Passo 3
A composição de funções
significa aplicar a função
duas vezes. Ou seja,
. A condição
quer dizer que aplicar
duas vezes é a mesma coisa que aplicar uma vez, o que chamamos de função idempotente.
Passo 4
Vamos começar mostrando que se
, então se
, então
. Suponha que
. Como
, pela definição de classe de equivalência,
está relacionado a
, então
deve também estar relacionado a
. Isso porque aplicar
novamente não muda a relação devido à idempotência.
Passo 5
Agora, vamos mostrar o contrário: se sempre que
, então
, isso implica que
. Ou seja, se ao aplicar
um elemento da classe de
ainda pertence à classe de
, então aplicar
duas vezes não muda nada, já que a segunda aplicação de
mantém o elemento na mesma classe. Portanto,
.
Resposta
Assim, mostramos que
se, e somente se, sempre que
, então
para todo
.