Em N x N considere a relação unlhd dada por
(x, y) unlhd (a, b) <=> (x < a) ou (x = a e y <= b)
Essa relação é chamada de ordem lexicográfica em N x N.
(a) Prove que unlhd é uma ordem total em N x N.
(b) Ordene os seguintes elementos de acordo com a ordem lexicográfica:
(1,2), (2,1), (3,1), (1,1), (2,2), (3,3), (1,4), (3,5), (2,4), (4,4), (4,1)

Passo 1

Vamos resolver esse exercício que fala sobre a ordem lexicográfica em pares de números naturais. Primeiro, vamos provar que essa relação é uma ordem total. Depois, vamos usar essa ordem para organizar uma lista de pares. Para isso, precisamos entender os conceitos de ordem total e as propriedades que ela deve ter.

Passo 2

Uma ordem total precisa satisfazer quatro propriedades principais:
  1. Reflexividade: Todo elemento está relacionado consigo mesmo.
  2. Antissimetria: Se um elemento está relacionado com outro e vice-versa, então os dois elementos são iguais.
  3. Transitividade: Se um elemento está relacionado com o segundo e o segundo com o terceiro, então o primeiro está relacionado com o terceiro.
  4. Totalidade: Qualquer dois elementos podem ser comparados.
Vamos verificar se a relação unlhd que define a ordem lexicográfica satisfaz essas propriedades.

Passo 3

Reflexividade: Precisamos ver se todo par (x, y) está relacionado consigo mesmo, ou seja, se .
Na definição:
Como e sempre são verdadeiros, a condição é satisfeita. Logo, a relação é reflexiva.

Passo 4

Antissimetria: Vamos ver se, se e , então .
Pela definição:
  1. ou .
  2. ou .
Se e , isso é impossível. Então, a única possibilidade é que e , e ao mesmo tempo e . Assim, . Portanto, , mostrando que a relação é antissimétrica.

Passo 5

Transitividade: Precisamos mostrar que se e , então .
Vamos considerar os casos:
  1. Se e , então , então .
  2. Se e , então , então .
  3. Se e , e , então , então .
  4. Se e , e e , então e , então .
Em todos os casos, a condição de transitividade é satisfeita.

Passo 6

Totalidade: Precisamos garantir que qualquer dois pares (x, y) e (a, b) podem ser comparados, ou seja, ou ou .
Para qualquer dois pares:
  • Se , então .
  • Se , então .
  • Se , então ou ou , então um dos dois será verdadeiro.
Assim, a relação é total.

Passo 7

Com todas as propriedades verificadas (reflexividade, antissimetria, transitividade e totalidade), podemos concluir que a relação unlhd é uma ordem total em N x N.

Passo 8

Agora, vamos para a parte (b), onde precisamos ordenar uma lista de pares usando a ordem lexicográfica definida.
Os pares são:

Passo 9

Para ordenar, seguimos esses passos:
  1. Primeiro elemento: Ordenamos os pares pelo primeiro número.
  2. Segundo elemento: Se o primeiro número for igual, ordenamos pelo segundo número.
Vamos aplicar isso:
  • Primeiro elementos 1:
    • 1,1
    • 1,2
    • 1,4
  • Primeiro elementos 2:
    • (2,1)
    • (2, 2)
    • 2,4
  • Primeiro elementos 3:
    • 3,1
    • 3,3
    • (3,5)
  • Primeiro elementos 4:
    • (4,1)

Passo 10

Assim, a lista ordenada fica:

Resposta

(a) A relação unlhd é uma ordem total em N x N.
(b) A ordenação dos elementos conforme a ordem lexicográfica fica:

Exercícios relacionados