Seja
uma relação binária num conjunto
. Defina uma relação binária
em
da seguinte maneira:
se existem
tais que
. Mostre que: a)
; b)
é transitiva; c)
é a interseção do conjunto de todas as relações binárias transitivas
em
que contêm
é o fecho transitivo de
.
Passo 1
O enunciado define uma relação binária
em um conjunto
e constrói uma nova relação
em
dizendo que
se existe uma cadeia finita
com
e
O objetivo é mostrar:
a) que ;
b) que é transitiva;
c) que é a interseção de todas as relações transitivas
em
que contêm
, ou seja, o fecho transitivo de
.
a) que
b) que
c) que
Passo 2
Para provar
, considere qualquer par
. Basta tomar uma cadeia de comprimento
:
Como
é exatamente
, concluímos que
. Logo
Passo 3
Para ver que
é transitiva, suponha
Pela definição existem cadeias
com
e
. Basta concatenar as duas cadeias (observando que
) para obter uma cadeia de
até
inteiramente em
. Assim
e
é transitiva.
Passo 4
Seja
qualquer relação transitiva em
que contenha
. Queremos mostrar
. Pegue
. Então existe uma cadeia
com
. Como
, cada par
está em
. E como
é transitiva, da cadeia toda segue que
. Logo
Isso mostra que
é contido em toda relação transitiva que contém
, ou seja,
o que caracteriza
como o fecho transitivo de
.
Resposta
a)
.
b) é transitiva.
c) , ou seja, o fecho transitivo de
.
b)
c)