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 $A$ e uma relação binária $R$ sobre $A:$ $R\subseteq A\times A,$ dizemos que $R$ é uma relação de ordem (parcial) ampla (ou não estrita) sobre $A$ se satisfaz as seguintes condições:

1.a Reflexividade

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

1.b Antissimetria

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

1.c Transitividade

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

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

Um exemplo típico é a relação de inclusão (ampla) entre conjuntos: $A\subseteq B.$ geralmente definida sobre o conjunto das partes de $A:$ ${\mathcal {P}}\left(A\right).$ Um outro exemplo é a relação "$x$ divide $y$": seja $\mathbb {N} ^{+}$ o conjunto dos números naturais maiores que zero. Para $x,y\in \mathbb {N} ^{+},$ dizemos que $x$ divide $y$, em símbolos $x|y$ se e somente se existe um $z\in \mathbb {N} ^{+},$ tal que $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 $A$ e uma relação binária $R$ sobre $A:$ $R\subseteq A\times A,$ dizemos que $R$ é uma relação de ordem (parcial) estrita sobre $A$ se satisfaz transitividade e:

2.a Irreflexividade

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

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

2.b Assimetria

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

Analogamente, pode ser demonstrado que se uma relação $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 $R$ é uma relação de ordem parcial estrita, $R(x,y)$ é escrito como $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 "$x$ é antepassado de $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:

3.a Correspondência

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

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

Relações de ordem linear ou total

Dada um relação $R,$ dizemos que $x,y\in A,\;\;x\neq y$ são incomparáveis, $x\parallel y$ se e somente se $\neg R(x,y)$ nem $\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 $R$ uma relação sobre $A,$ no caso de uma ordem ampla, a totalidade (linearidade) está dada por:

4.a Totalidade ou linearidade (para ordens amplas)

$\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)

$\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:

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

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

$\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 $R$ é uma ordem estrita, então a relação inversa de $R:$

$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 "$<$" é geralmente escrita "$>$". De maneira análoga, para uma relação de ordem ampla "$\leqslant$" pode ser definida a sua inversa "$\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, "$\leq$", ou estritas, "$<$", definições correspondentes podem ser estabelecidas usando Definição 3.

Mínimo e máximo

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

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

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

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

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

$\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 $A$ e considerando a ordem inclusão, $\subseteq$, o conjunto $\wp \left(A\right)$ , das partes de $A,$ tem mínimo $\varnothing$ é máximo $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 $<$ sobre um conjunto $A,$ um elemento $a\in A$ é denominado minimal quando não existe outro elemento que seja menor que ele:

$\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:

$\nexists \ x\in A,\;\;x>a$

Cotas inferior (minorante) e superior (majorante)

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

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

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

$\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 $\left[0,1\right]\subseteq \mathbb {R} ,$ então qualquer $x\leqslant 0,x\in \mathbb {R}$ é cota inferior do intervalo e qualquer $x\geqslant 1,x\in \mathbb {R}$ é cota superior.

Boa ordem

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

• $<$ é irreflexiva, transitiva e

• $\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, $\mathbb {N}$ é bem ordenado pela relação natural desse conjunto (ver Princípio da boa-ordenação), mas $\mathbb {Z} ,$ $\mathbb {Q}$ e $\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 $a,b\in A,a\neq b$ consideramos o conjunto $\{a,b\},$ ele tem primeiro elemento, de modo que ou $a<b,$ ou $b<a.$

Bibliografia

• BIRKHOFF, Garrett (1948). Lattice Theory (em inglês). New York: American Mathematical Society 

• DAVEY, B.A.; PRIESTLEY, H.A (2002). Introduction to Lattices and Order (em inglês) 2nd. ed. Cambridge: Cambridge University Press. ISBN 978-0-521-78451-1 

• FRAÏSSÉ, Roland (2000). Theory of Relations (em inglês) 1rst. (revised) ed. Amsterdam: Elsevier. ISBN 0-444-50542-3 

• ROMAN, Steven (2008). Lattices and Ordered Sets (em inglês). New York: Springer. ISBN 978-0-387-78900-2 

• ROSENSTEIN, Joseph G (1982). Linear Orderings (em inglês) 2nd. ed. New York: Academic Press. ISBN 0-12-597680-1 

Ver também

• Relação (matemática)
• Topologia da ordem: uma relação de ordem parcial gera uma topologia, que tem como base os conjuntos do tipo {x | x < b}, {x | x > a} e {x | a < x < b}.
• Corpo ordenado: quando o conjunto ordenado tem uma estrutura algébrica de corpo, e a ordem e as operações algébricas são compatíveis.