Seja R uma relação binária num conjunto X. Defina uma relação binária R^prime em X da seguinte maneira: a R^prime b se existem c1, c2, ldots, cn in X tais que c1=a, c1 R c2, c2 R c3, ldots, cn-1 R cn, cn=b. Mostre que: a) R subset R^prime; b) R^prime é transitiva; c) R^prime é a interseção do conjunto de todas as relações binárias transitivas S em X que contêm R R^prime é o fecho transitivo de R.

Passo 1

O enunciado define uma relação binária R em um conjunto X e constrói uma nova relação R' em X dizendo que
a,R',b
se existe uma cadeia finita
c1,c2,dots,cnin X
com
c1=a, cn=b,
e
ci,R,ci+1 para i=1,2,dots,n-1
O objetivo é mostrar:
a) que Rsubseteq R';
b) que R' é transitiva;
c) que R' é a interseção de todas as relações transitivas S em X que contêm R, ou seja, o fecho transitivo de R.

Passo 2

Para provar Rsubseteq R', considere qualquer par (a,b)in R. Basta tomar uma cadeia de comprimento n=2:
c1=a, c2=b
Como c1,R,c2 é exatamente a,R,b, concluímos que a,R',b. Logo
Rsubseteq R'

Passo 3

Para ver que R' é transitiva, suponha
a,R',b e b,R',d
Pela definição existem cadeias
a=c1,c2,dots,ck=b e b=d1,d2,dots,dm=d
com ci,R,ci+1 e dj,R,dj+1. Basta concatenar as duas cadeias (observando que ck=d1=b) para obter uma cadeia de a até d inteiramente em R. Assim a,R',d e R' é transitiva.

Passo 4

Seja S qualquer relação transitiva em X que contenha R. Queremos mostrar R'subseteq S. Pegue (a,b)in R'. Então existe uma cadeia
a=c1,c2,dots,cn=b
com ci,R,ci+1. Como Rsubseteq S, cada par (ci,ci+1) está em S. E como S é transitiva, da cadeia toda segue que (a,b)in S. Logo
R'subseteq S
Isso mostra que R' é contido em toda relação transitiva que contém R, ou seja,
R' ;=; capsubstackSsupseteq RS transitiva S, §
o que caracteriza R' como o fecho transitivo de R.

Resposta

a) Rsubseteq R'.
b) R' é transitiva.
c) R'=capsubstackSsupseteq RS transitivaS§, ou seja, o fecho transitivo de R.

Exercícios relacionados