Relação de ordem

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 maior, menor, anterior, posterior, etc. Foram definidos muitos tipos de relações de ordem e diferentes obras usam os termos "ordem" e "relação de ordem" de maneira diversa, pelo qual existe uma ambiguidade na literatura. O tópico "relação de ordem" está fortemente vinculado a conjunto parcialmente ordenado.

Definições básicas[editar | editar código-fonte]

Definição 1: Ordem parcial ampla ou não estrita[editar | editar código-fonte]

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] :

1.a Reflexividade:[editar | editar código-fonte]

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

1.b Antissimetria:[editar | editar código-fonte]

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

1.c Transitividade:[editar | editar código-fonte]

\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 \le 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[editar | editar código-fonte]

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 Antirreflexividade:[editar | editar código-fonte]

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

Se uma relação  R satisfaz transitividade e antirreflexividade, pode se demonstrado que  R também satisfaz:

2.b Assimetria:[editar | editar código-fonte]

\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[editar | editar código-fonte]

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

3.a Correspondência:[editar | editar código-fonte]

 x \leq y \Leftrightarrow \left( x < y \or x = y \right)

 x < y \Leftrightarrow \left( x \le y \and x \neq y \right)

Relações de ordem linear ou total[editar | editar código-fonte]

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[editar | editar código-fonte]

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):[editar | editar código-fonte]

\forall x, y \in A \left( x \leq y  \or y \le x \right) Também denominado "dicotomia".

No caso das ordens estritas:

4.b Totalidade ou linearidade (para ordens estritas):[editar | editar código-fonte]

\forall x, y \in  A \left( x \neq y \Rightarrow x < y \or y < x \right)

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

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

As ordens dos conjuntos numéricos, \mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R} são lineares. Dado um conjunto o conjunto  A com dois ou mais elementos,  \mathcal{P}\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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

5 Densidade (para ordens estritas)[editar | editar código-fonte]

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

Inversa de uma ordem[editar | editar código-fonte]

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 : \;\; \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 " \le " pode ser definida a sua inversa " \ge ", que também é uma relação de ordem ampla.

A pesar 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[editar | editar código-fonte]

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, " \le ", ou estritas, " < ", definições correspondentes podem ser estabelecidas usando Definição 3.

Mínimo e máximo[editar | editar código-fonte]

Dada uma relação de ordem ampla  \le 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 \le 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 \ge 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 \le x \le 1 \right\}

tem mínimo 0 e máximo 1. Dado um conjunto  A e considerando a ordem inclusão,  \subseteq , o conjunto  \mathcal{P}\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[editar | editar código-fonte]

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:

 \neg \exists 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:

 \neg \exists x \in A, \;\; x > a

Cotas inferior (minorante) e superior (majorante)[editar | editar código-fonte]

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 \le 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 \ge 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 \le 0, x \in \mathbb{R} é cota inferior do intervalo e qualquer  x \ge 1, x \in \mathbb{R} é cota superior.

Boa ordem[editar | editar código-fonte]

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:

  •  \forall B \subseteq A \left( B \ne \varnothing \Rightarrow \left( \exists a \in B \;\;\forall b \in B \left( a \ne 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 \ne b consideramos o conjunto  \{ a, b \} , ele tem primeiro elemento, de modo que ou  a < b , ou  b < a .

Referências

Bibliografia[editar | editar código-fonte]

  • BIRKHOFF, Garrett. Lattice Theory (em inglês). New York: American Mathematical Society, 1948.
  • DAVEY, B.A.; PRIESTLEY, H.A. Introduction to Lattices and Order (em inglês). 2nd. ed. Cambridge: Cambridge University Press, 2002. ISBN 978-0-521-78451-1
  • FRAÏSSÉ, Roland. Theory of Relations (em inglês). 1rst. (revised) ed. Amsterdam: Elsevier, 2000. ISBN 0-444-50542-3
  • ROSENSTEIN, Joseph G. Linear Orderings (em inglês). 2nd. ed. New York: Academic Press, 1982. ISBN 0-12-597680-1

Ver também[editar | editar código-fonte]