Sejam A e B dois conjuntos totalmente ordenados pela relação <=. Sejam a=(x, y) e b=(x^prime, y^prime) elementos de A times B, em que está definida a relação R dada por:
a R b se, e somente se, x <= x^prime ou (x=x^prime e y <= y^prime)
Prove que R é uma relação de ordem total em A times B.

Passo 1

O enunciado define em Atimes B a relação lexicográfica
(x,y),R,(x',y')se e somente se x<= x';lor;(x=x';land;y<= y')
Queremos mostrar que R é ordem total, ou seja, que é reflexiva, antissimétrica, transitiva e connexa (total).

Passo 2

Prova de reflexividade.
Seja a=(x,y)in Atimes B. Como em todo conjunto ordenado vale x<= x e também y<= y, temos
x<= xLongrightarrow a,R,a
Logo, R é reflexiva.

Passo 3

Prova de antissimetria.
Suponha a=(x,y) e b=(x',y') tais que a,R,b e b,R,a.
  1. De a,R,b segue x<= x' ou (x=x' e y<= y').
  2. De b,R,a segue x'<= x ou (x'=x e y'<= y).
    Se x < x', então não pode valer x'<= x, restando x'=x e daí x=x'. Análogo se x' < x. Logo necessariamente x = x'.
    Com x=x', das condições originais seguem y<= y' e y'<= y, ou seja y=y'. Assim (x,y)=(x',y'), isto é a=b. Portanto R é antissimétrica.

Passo 4

Prova de transitividade.
Sejam a=(x,y), b=(x',y') e c=(x'',y'') com a,R,b e b,R,c.
  • Se x<= x' e x'<= x'', então x<= x'', logo a,R,c.
  • Se x<= x' e x'=x'' com y'<= y'', então x<= x'', logo a,R,c.
  • Se x=x' com y<= y' e x'<= x'', então x<= x'', logo a,R,c.
  • Se x=x'=x'' e y<= y' com y'<= y'', então y<= y'' e x=x'', logo a,R,c.
    Em todos os casos a,R,c, provando a transitividade.

Passo 5

Prova de connexidade (totalidade).
Para quaisquer a=(x,y) e b=(x',y'), como A é totalmente ordenado temos x<= x' ou x'<= x.
  • Se x< x', então a,R,b.
  • Se x'=x, como B é totalmente ordenado temos y<= y' ou y'<= y, daí ou a,R,b ou b,R,a.
  • Se x'>x, então b,R,a.
    Assim para todo par (a,b) vale a,R,b ou b,R,a.

Resposta

A relação R é reflexiva, antissimétrica, transitiva e total, logo é uma ordem total em Atimes B.

Exercícios relacionados