Relação de ordem

Uma relação de ordem é uma relação binária em um conjunto que é reflexiva, antissimétrica e transitiva.

Motivação

A ordem é um conceito comum, com o qual trabalhamos também no dia a dia. Podemos ordenar muitas coisas de algum modo — palavras por ordem alfabética, alunos de uma escola por altura, mercadorias por preço. Tudo isso é descrito pela relação de ordem, que costumamos representar com o símbolo ≤. Os símbolos relacionados são: <, >, ≥. O significado deles é evidente.

O que esperaríamos de uma relação assim? Já pelo símbolo fica claro que na relação de ordem haverá elementos iguais — portanto, o que queremos é definir as propriedades da relação menor ou igual. Uma relação assim deveria ser reflexiva. Deve valer a ≤ a.

E o que mais? Certamente não valerá a simetria — se temos a ordem por preço, então, se o carro é mais barato que o pão, certamente o pão não será ao mesmo tempo mais barato que o carro. O que esperaríamos em geral, se acontecesse a ≤ b e, ao mesmo tempo, b ≤ a? Isso faria sentido alguma vez? Sim, se valesse a = b. O único caso em que a ordem dos elementos colocados na relação não importa é quando esses elementos são iguais — a ordem é, portanto, antissimétrica.

Por fim, se sabemos que o carro é mais caro que o pão e o avião é ainda mais caro que o carro, esperamos que o avião seja certamente mais caro que o pão. Isso é descrito pela transitividade.

Ordem parcial

O que acabamos de definir é, na verdade, apenas uma ordem parcial, não é uma ordem total. Por que não é total? Vamos tentar definir uma ordem em conjuntos. De que modo poderíamos comparar dois conjuntos?

Dizemos que o conjunto A é menor ou igual ao conjunto B se A ⊆ B, isto é, se A é subconjunto de B. Isso faz sentido, porque, se temos A = {1, 2} e B = {1, 2, 3}, poderíamos dizer que A é menor — B contém os mesmos elementos que A e, além disso, contém também o número três. Assim, por exemplo, valerá:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

O problema surge quando queremos comparar estes conjuntos: A = {a, b} e B = {a, c}. Qual deles é menor ou maior? O problema é que, embora os dois conjuntos contenham o elemento a, o segundo elemento é sempre diferente. Nenhum dos conjuntos é subconjunto do outro, então não vale A ≤ B nem B ≤ A. Esses conjuntos não são comparáveis pela nossa ordem.

Por isso, definimos um conjunto totalmente ordenado ou também cadeia quando quaisquer dois elementos do conjunto são comparáveis. Conjuntos assim são, por exemplo, os conjuntos numéricos com a ordem usual. Para quaisquer dois números reais a, b, você consegue decidir se a ≤ b ou b ≤ a.

Exemplos do dia a dia

Um exemplo em que compensa não comparar poderia ser a ordem por beleza: a relação < significaria “ser mais feio”. Talvez fosse melhor defini-la ao contrário, > como “ser mais bonito”, para sermos mais corretos :-). Provavelmente faz sentido comparar entre si duas personagens femininas dos contos de fadas, por exemplo “Madrasta” < “Branca de Neve”, no sentido de que a Branca de Neve é mais bonita que a Madrasta. Ou dois personagens masculinos: “Lobo Mau” < “Príncipe Encantado”, no sentido de que o Príncipe é mais bonito que o Lobo.

O problema é que dificilmente conseguimos comparar a beleza de um homem e a de uma mulher. Quem é mais bonito: a Branca de Neve ou o Príncipe Encantado? Quem é mais feio: a Madrasta ou o Lobo Mau? Melhor nem investigar…

Se, no último exemplo, nos limitarmos, por exemplo, apenas às personagens femininas, podemos dizer que temos um conjunto totalmente ordenado, porque conseguimos comparar a beleza de todas elas.

Elemento minimal e maximal, menor e maior elemento

Se temos um conjunto ordenado M, dizemos que o elemento min ∈ M é minimal se não existe x ∈ M tal que x < min. Ou seja, não conseguimos encontrar um elemento que seja menor que o elemento min.

Dizemos que o elemento max ∈ M é maximal se não existe x ∈ M tal que x > max. Ou seja, não conseguimos encontrar um elemento que seja maior.

Esses dois conceitos são diferentes dos conceitos de menor e maior elemento.

Dizemos que o elemento a ∈ M é o menor elemento se, para todo x ∈ M, vale a ≤ x. Ou seja, o menor elemento a é menor ou igual a todos os outros elementos do conjunto M.

Dizemos que o elemento b ∈ M é o maior elemento se, para todo x ∈ M, vale b ≥ x. O maior elemento b é maior ou igual a todos os outros elementos do conjunto M.

Qual é a diferença entre o maior elemento e um elemento maximal? Pode haver vários elementos maximais, porque o conjunto não precisa estar totalmente ordenado. Se voltarmos ao exemplo da comparação de personagens com base na aparência, podemos dizer que a Branca de Neve é a personagem feminina mais bonita e o Príncipe Encantado é o personagem masculino mais bonito. Mas já não conseguimos comparar essas duas figuras entre si; não sabemos se é mais bonita a Branca de Neve ou o Príncipe Encantado.

Os dois elementos são, portanto, maximais. Não conseguimos encontrar uma personagem que seja mais bonita que o Príncipe Encantado — ele é mais bonito que todos os outros personagens masculinos, e com as personagens femininas não podemos compará-lo. Do mesmo modo para a Branca de Neve — ela é mais bonita que todas as personagens femininas, e com os personagens masculinos não podemos compará-la.

Mas nenhum dos dois é o maior, neste sentido, o mais bonito. Porque, para o Príncipe Encantado ser o mais bonito/maior, ele teria de ser mais bonito que todas as figuras, inclusive todas as personagens femininas. Mas já dissemos que não podemos compará-lo com elas, por isso ele não pode ser o mais bonito de todos; é apenas, na terminologia da teoria da ordem, maximal.

É fácil perceber que, se um conjunto tem um maior elemento, então esse elemento é também maximal. Se o elemento a é maior que todos os outros elementos do conjunto (definição de maior elemento), certamente não encontraremos um elemento que seja ainda maior (definição de elemento maximal).

Um exemplo de conjunto que tem maior e menor elemento é o intervalo fechado [0, 1]. Se escolhermos o mesmo intervalo, mas aberto, ele não teria nem maior nem menor elemento: ]0, 1[.

Se quiséssemos infinitos elementos minimais, poderíamos definir a ordem R assim. Primeiro definimos conjuntos auxiliares M_x. Os conjuntos terão esta forma: para todo x do intervalo ]0, 1[, definimos o conjunto M_x = {y | y = x + n}, em que n é um número inteiro não negativo. Com isso obtemos, por exemplo, estes conjuntos:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Em cada conjunto M_x definimos a ordem usual, que chamamos de R_x. No final, basta unir essas ordens: R = ∪ R_x. Nessa ordem, só podemos comparar dentro das cadeias originais. Assim, podemos descobrir se 0,5 ≤ 2,5, mas já não podemos descobrir se 0,5 ≤ 2,7, porque esses números não estavam no mesmo conjunto M_x e, por isso, a relação entre eles não está definida.

Nessa relação de ordem vale, então, que todo elemento do intervalo ]0, 1[ é um elemento minimal.

Diagramas de Hasse

Os conjuntos ordenados podem ser desenhados com um diagrama de Hasse. Trata-se de um grafo em que os vértices representam os elementos do conjunto e a aresta entre os vértices (a, b) nos diz que a < b e, ao mesmo tempo, não existe c tal que a < c < b. Ou seja, entre os elementos a e b já não há nenhum outro elemento. Além disso, deve valer que, no grafo, o vértice a está mais abaixo que o vértice b. Exemplo de diagrama de Hasse:

Esse diagrama de Hasse representa o conjunto ordenado {A, B, C, D, E, F}. Nele, vale: A < B, B < E e, é claro, também vale A < E, mas entre esses vértices não há aresta, porque existe o vértice B, para o qual vale A < B < E. Os elementos E e D não são comparáveis, porque nenhum deles está acima ou abaixo do outro.

Embora os diagramas de Hasse costumem ser desenhados assim, bem alinhados, isso não é obrigatório. O diagrama de Hasse anterior também pode ter esta aparência:

Outro exemplo pode ser o conjunto: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. São os divisores naturais do número 60. A ordem por divisibilidade pode ser representada assim:

Ordem por divisibilidade significa que (a, b) ∈ R se e somente se a divide b. Pelo diagrama, podemos notar que cada número tem acima de si os números que ele divide. Por exemplo, acima do número 6 estão os números 12, 30 e 60. Acima do número 4 estão os números 12, 20 e 60. E assim por diante. Já o número 3 não tem acima de si o número 10, porque não o divide — atenção, o número 10 está visualmente acima do número 3, mas nenhuma linha leva até ele “de baixo para cima”. Se, a partir do número 3, nos movermos apenas para cima, podemos ir aos números 15 e 6 e, deles, ao número 30. Para chegar ao número 10, teríamos de descer, o que não podemos.