Relação de ordem

Em matemática e em lógica matemática, especialmente em teoria dos conjuntos e em teoria das relações, uma relação de ordem é uma relação binária que pretende captar o sentido intuitivo de relações como o maior e o menor, o anterior e o posterior, etc. Foram definidos muitos tipos de relações de ordem e diferentes obras usam os termos "ordem" e "relação de ordem" de maneiras diversas, pelo qual existe uma ambiguidade na literatura. Os tópicos "relações de ordens" estão fortemente vinculados ao conjunto parcialmente ordenado.

Definições básicas

Definição 1: Ordem parcial ampla ou não estrita

Dado um conjunto ${\displaystyle A}$ e uma relação binária ${\displaystyle R}$ sobre ${\displaystyle A:}$ ${\displaystyle R\subseteq A\times A,}$ dizemos que ${\displaystyle R}$ é uma relação de ordem (parcial) ampla (ou não estrita) sobre ${\displaystyle A}$ se satisfaz as seguintes condições:^[1]

1.a Reflexividade

${\displaystyle \forall \ x\in A\;\;R(x,x)}$ ${\displaystyle }$ (ou seja, todo elemento está relacionado consigo mesmo);

1.b Antissimetria

${\displaystyle \forall \ x,y\in A\;\left(R(x,y)\wedge R(y,x)\Rightarrow x=y\right);}$ e

1.c Transitividade

${\displaystyle \forall \ x,y,z\in A\;\left(R(x,y)\wedge R(y,z)\Rightarrow R(x,z)\right)}$

Quando uma relação ${\displaystyle R}$ satisfaz as condições acima, ${\displaystyle R(x,y)}$ é escrito como ${\displaystyle x\leq y.}$ A relação habitual de menor ou igual em conjuntos numéricos, ${\displaystyle \mathbb {N} }$, ${\displaystyle \mathbb {Z} }$, ${\displaystyle \mathbb {Q} }$, ${\displaystyle \mathbb {R} }$, cumpre com essas condições explicando essa notação.

Um exemplo típico é a relação de inclusão (ampla) entre conjuntos: ${\displaystyle A\subseteq B.}$ geralmente definida sobre o conjunto das partes de ${\displaystyle A:}$ ${\displaystyle {\mathcal {P}}\left(A\right).}$ Um outro exemplo é a relação "${\displaystyle x}$ divide ${\displaystyle y}$": seja ${\displaystyle \mathbb {N} ^{+}}$ o conjunto dos números naturais maiores que zero. Para ${\displaystyle x,y\in \mathbb {N} ^{+},}$ dizemos que ${\displaystyle x}$ divide ${\displaystyle y}$, em símbolos ${\displaystyle x|y}$ se e somente se existe um ${\displaystyle z\in \mathbb {N} ^{+},}$ tal que ${\displaystyle z.x=y.}$ Pode ser demonstrado que a relação "divide" assim definida satisfaz as condições da Definição 1.

Definição 2: Ordem parcial estrita

Dado um conjunto ${\displaystyle A}$ e uma relação binária ${\displaystyle R}$ sobre ${\displaystyle A:}$ ${\displaystyle R\subseteq A\times A,}$ dizemos que ${\displaystyle R}$ é uma relação de ordem (parcial) estrita sobre ${\displaystyle A}$ se satisfaz transitividade e:

2.a Irreflexividade

${\displaystyle \forall \ x\in A\;\;\neg R(x,x)}$ ${\displaystyle }$ (ou seja, nenhum elemento está relacionado consigo mesmo)

Se uma relação ${\displaystyle R}$ satisfaz transitividade e irreflexividade, pode ser demonstrado que ${\displaystyle R}$ também satisfaz:

2.b Assimetria

${\displaystyle \forall \ x,y\in A\;\left(R(x,y)\Rightarrow \neg R(y,x)\right).}$

Analogamente, pode ser demonstrado que se uma relação ${\displaystyle R}$ satisfaz transitividade e assimetria, então também satisfaz irreflexividade, fornecendo uma definição alternativa de ordem parcial estrita, preferida por alguns autores.

Quando uma relação ${\displaystyle R}$ é uma relação de ordem parcial estrita, ${\displaystyle R(x,y)}$ é escrito como ${\displaystyle x<y.}$

Um conjunto que possui uma relação de ordem é chamado de conjunto parcialmente ordenado.

Em contextos não matemáticos é mais comum utilizar as ordens em sentido estrito. Por exemplo, dizemos que João é mais alto que Pedro no sentido que a altura de João é estritamente maior que a de Pedro. Também pode ser verificado que a relação "${\displaystyle x}$ é antepassado de ${\displaystyle y}$" também é uma ordem estrita.

Definição 3: Correspondência entre ordens estritas e amplas

Dada uma ordem estrita ou uma ordem ampla, pode ser definida a outra ordem correspondente, segundo:^[2]

3.a Correspondência

${\displaystyle x\leqslant y\Leftrightarrow \left(x<y\lor x=y\right)}$

${\displaystyle x<y\Leftrightarrow \left(x\leqslant y\land x\neq y\right)}$

Relações de ordem linear ou total

Dada um relação ${\displaystyle R,}$ dizemos que ${\displaystyle x,y\in A,\;\;x\neq y}$ são incomparáveis, ${\displaystyle x\parallel y}$ se e somente se ${\displaystyle \neg R(x,y)}$ nem ${\displaystyle \neg R(y,x).}$ Uma relação de ordem linear ou total não têm elementos incomparáveis.

Definição 4: Totalidade ou linearidade

Sendo ${\displaystyle R}$ uma relação sobre ${\displaystyle A,}$ no caso de uma ordem ampla, a totalidade (linearidade) está dada por:

4.a Totalidade ou linearidade (para ordens amplas)

${\displaystyle \forall \ x,y\in A\left(x\leqslant y\lor y\leqslant x\right)}$ Também denominado "dicotomia".

No caso das ordens estritas:

4.b Totalidade ou linearidade (para ordens estritas)

${\displaystyle \forall \ x,y\in A\left(x\neq y\Rightarrow x<y\lor y<x\right)}$

Também denominado "tricotomia", pois pode ser escrito equivalentemente:

${\displaystyle \forall \ x,y\in A\left(x=y\lor x<y\lor y<x\right)}$

As ordens dos conjuntos numéricos, ${\displaystyle \mathbb {N} }$, ${\displaystyle \mathbb {Z} }$, ${\displaystyle \mathbb {Q} }$, ${\displaystyle \mathbb {R} }$ são lineares. Dado um conjunto ${\displaystyle A}$ com dois ou mais elementos, ${\displaystyle {\wp }\left(A\right),}$ o conjunto das partes de ${\displaystyle A,}$ não está linearmente ordenado por inclusão ${\displaystyle \left(\subseteq \right)}$.

Relações de ordem densa

A ideia intuitiva de densidade de uma ordem corresponde a conceber que entre dois elementos comparáveis existe uma quantidade infinita de elementos.

Definição 5: Densidade

Uma relação de ordem estrita, parcial ou total, é denominada densa se entre dois elementos sempre existe um outro:

5 Densidade (para ordens estritas)

${\displaystyle \forall \ x,y\in A\ \left(x<y\Rightarrow \exists \ z\in S\left(x<z<y\right)\right)}$

Inversa de uma ordem

Se uma relação ${\displaystyle R}$ é uma ordem estrita, então a relação inversa de ${\displaystyle R:}$

${\displaystyle R^{-1}=\left\{\left\langle y,x\right\rangle \mid \left\langle x,y\right\rangle \in R\right\}}$

também é uma relação de ordem estrita. A inversa de "${\displaystyle <}$" é geralmente escrita "${\displaystyle >}$". De maneira análoga, para uma relação de ordem ampla "${\displaystyle \leqslant }$" pode ser definida a sua inversa "${\displaystyle \geqslant }$", que também é uma relação de ordem ampla.

Apesar dessa propriedade ser denominada às vezes de "dualidade", não é uma dualidade em sentido estrito, como a que possuem as álgebras de Boole.

Elementos distinguidos numa ordem

Alguns elementos de um conjunto ordenado podem ser caraterizados usando a relação de ordem. Apesar das definições abaixo serem expressadas somente para ordens amplas, "${\displaystyle \leq }$", ou estritas, "${\displaystyle <}$", definições correspondentes podem ser estabelecidas usando Definição 3.

Mínimo e máximo

Dada uma relação de ordem ampla ${\displaystyle \leqslant }$ sobre um conjunto ${\displaystyle A,}$ um elemento ${\displaystyle a\in A}$ é denominado mínimo ou primeiro elemento se e somente se:

${\displaystyle \forall \ b\in A\left(a\leqslant b\right)}$

De maneira simétrica, ${\displaystyle a\in A}$ é denominado máximo ou último elemento se e somente se:

${\displaystyle \forall \ b\in A\left(a\geqslant b\right)}$

O conjunto ${\displaystyle \mathbb {N} }$ tem mínimo, mas não tem máximo. Os conjuntos ${\displaystyle \mathbb {Z} }$, ${\displaystyle \mathbb {Q} }$ e ${\displaystyle \mathbb {R} }$ não têm nem máximo, nem mínimo. O intervalo

${\displaystyle \left[0,1\right]=\left\{x\in \mathbb {R}$ :\;\;0\leqslant x\leqslant 1\right\}}

tem mínimo 0 e máximo 1. Dado um conjunto ${\displaystyle A}$ e considerando a ordem inclusão, ${\displaystyle \subseteq }$, o conjunto ${\displaystyle \wp \left(A\right)}$ , das partes de ${\displaystyle A,}$ tem mínimo ${\displaystyle \varnothing }$ é máximo ${\displaystyle A.}$ Se um conjunto tem mínimo, então tem um único mínimo. O mesmo vale para o máximo.

Minimal e maximal

Dada uma relação de ordem estrita ${\displaystyle <}$ sobre um conjunto ${\displaystyle A,}$ um elemento ${\displaystyle a\in A}$ é denominado minimal quando não existe outro elemento que seja menor que ele:

${\displaystyle \nexists \ x\in A,\;\;x<a}$

Analogamente, um elemento de um conjunto parcialmente ordenado é maximal quando não existe outro elemento que seja maior que ele:

${\displaystyle \nexists \ x\in A,\;\;x>a}$

Cotas inferior (minorante) e superior (majorante)

Um elemento ${\displaystyle a\in A}$ é uma cota inferior ou minorante de um subconjunto ${\displaystyle B\subseteq A}$ se e somente se:

${\displaystyle \forall \ b\in B\left(a\leqslant b\right)}$

Um elemento ${\displaystyle a\in A}$ é uma cota superior ou majorante de um subconjunto ${\displaystyle B\subseteq A}$ se e somente se:

${\displaystyle \forall \ b\in B\left(a\geqslant b\right)}$

Às vezes os elementos acima são denominados de limite inferior e limite superior, mas este conceito não deve ser confundido com o de limite de uma sequência.

Se consideramos o intervalo ${\displaystyle \left[0,1\right]\subseteq \mathbb {R} ,}$ então qualquer ${\displaystyle x\leqslant 0,x\in \mathbb {R} }$ é cota inferior do intervalo e qualquer ${\displaystyle x\geqslant 1,x\in \mathbb {R} }$ é cota superior.

Boa ordem

Uma relação de ordem estrita ${\displaystyle R}$ sobre um conjunto ${\displaystyle A}$ é denominada uma boa ordem se e somente se todo subconjunto não vazio de ${\displaystyle A}$ tem primeiro elemento segundo ${\displaystyle R.}$ Em símbolos, uma relação "${\displaystyle <}$" sobre ${\displaystyle A}$ é uma boa ordem se e somente se:

• ${\displaystyle <}$ é irreflexiva, transitiva e

• ${\displaystyle \forall \ B\subseteq A\left(B\neq \varnothing \Rightarrow \left(\exists \ a\in B\;\;\forall \ b\in B\left(a\neq b\Rightarrow a<b\right)\right)\right)}$

Um conjunto com uma relação de boa ordem é denominado bem ordenado. Por exemplo, ${\displaystyle \mathbb {N} }$ é bem ordenado pela relação natural desse conjunto (ver Princípio da boa-ordenação), mas ${\displaystyle \mathbb {Z} ,}$ ${\displaystyle \mathbb {Q} }$ e ${\displaystyle \mathbb {R} }$ não são, segundo as suas ordens naturais. O conceito de boa ordem é importante para definir matematicamente os números ordinais em teoria dos conjuntos.

Uma boa ordem é sempre uma ordem linear, pois se para ${\displaystyle a,b\in A,a\neq b}$ consideramos o conjunto ${\displaystyle \{a,b\},}$ ele tem primeiro elemento, de modo que ou ${\displaystyle a<b,}$ ou ${\displaystyle b<a.}$

Referências

1. BIRKHOFF (1948), p. 1.
2. DAVEY PRIESTLEY (2002), p. 2.