Seja
uma relação binária em
e
a relação diagonal em
. Mostre que
é uma relação de ordem se, e somente se:
e
. Aqui,
.
Passo 1
O enunciado pede para mostrarmos que, para uma relação binária
em
, as condições
são equivalentes a dizer que
é 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
(
) Suponha que
seja relação de ordem em
.
(a) Provar .
Se , então
e
. Como
é antissimétrica, isso implica
, logo
. Assim
.
Por outro lado, se , a reflexividade garante
e também
, de modo que
. Logo
. Concluímos
(a) Provar
Se
Por outro lado, se
(b) Provar
.
— Se , existe
com
e
. Pela transitividade de
, segue
. Logo
.
— Se , como
é reflexiva, temos
, então
. Logo
.
Portanto
— Se
— Se
Portanto
Passo 3
(a) Reflexividade:
(b) Antissimetria: se
(c) Transitividade: se
Assim
é reflexiva, antissimétrica e transitiva, i.e.\ é uma relação de ordem.
Resposta
Mostramos as duas implicações, portanto