Seja R uma relação binária em X e triang<==(a, a) mid a in X a relação diagonal em X. Mostre que R é uma relação de ordem se, e somente se: R^2=R e R cap R^-1=triang<=. Aqui, R^2=R circ R.

Passo 1

O enunciado pede para mostrarmos que, para uma relação binária R em X, as condições
R^2=R e Rcap R^-1=triang<=
são equivalentes a dizer que R é uma relação de ordem (isto é, reflexiva, antissimétrica e transitiva). Vamos usar as definições de composição de relações, inversa, interseção e diagonal, além das propriedades de ordem.

Passo 2

( Rightarrow) Suponha que R seja relação de ordem em X.
(a) Provar Rcap R^-1=triang<=.
Se (x,y)in Rcap R^-1, então (x,y)in R e (y,x)in R. Como R é antissimétrica, isso implica x=y, logo (x,y)intriang<=. Assim Rcap R^-1subseteqtriang<=.
Por outro lado, se (x,x)intriang<=, a reflexividade garante (x,x)in R e também (x,x)in R^-1, de modo que (x,x)in Rcap R^-1. Logo triang<=subseteq Rcap R^-1. Concluímos
Rcap R^-1=triang<=
(b) Provar R^2=R.
— Se (x,z)in R^2=Rcirc R, existe y com (x,y)in R e (y,z)in R. Pela transitividade de R, segue (x,z)in R. Logo R^2subseteq R.
— Se (x,z)in R, como R é reflexiva, temos (z,z)in R, então (x,z)in Rcirc R = R^2. Logo Rsubseteq R^2.
Portanto
R^2=R

Passo 3

Leftarrow Suponha agora que R^2=R e Rcap R^-1=triang<=. Vamos verificar as três propriedades de ordem.
(a) Reflexividade: triang<=subseteq Rcap R^-1subseteq R implica que todo (x,x)intriang<= está em R.
(b) Antissimetria: se (x,y)in R e (y,x)in R, então (x,y)in Rcap R^-1=triang<=, o que força x=y.
(c) Transitividade: se (x,y)in R e (y,z)in R, então (x,z)in Rcirc R=R^2=R.
Assim R é reflexiva, antissimétrica e transitiva, i.e.\ é uma relação de ordem.

Resposta

Mostramos as duas implicações, portanto
R é ordem Long<=ftrightarrow R^2=R e Rcap R^-1=triang<= é

Exercícios relacionados