|
Em [[matemática]] e em [[lógica matemática|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 e etc. Foram [[definição|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]] <math style="vertical-align:0%;"> A </math> e uma [[relação binária]] <math style="vertical-align:0%;"> R </math> sobre <math style="vertical-align:0%;"> A :</math>: <math style="vertical-align:-17%;"> R \subseteq A \times A ,</math>, dizemos que <math style="vertical-align:0%;"> R </math> é uma ''relação de ordem (parcial) ampla (ou não estrita) sobre <math style="vertical-align:0%;"> A </math>'' se satisfaz as seguintes condições<ref>[[#Birkhoff1948LatticeTheory|BIRKHOFF (1948), p. 1.]]</ref>:
==== 1.a Reflexividade: ====
<math style="vertical-align:-7%;>\forall x\in A \;\; R(x,x) </math> <math> \;\;\;\;\;\; </math> (ou seja, todo elemento está relacionado consigo mesmo);
==== 1.b Antissimetria'': ====
<math>\forall x, y \in A \; \left( R(x,y) \wedge R(y,x) \Rightarrow x = y \right) ;</math>; e
==== 1.c Transitividade: ====
<math>\forall x, y, z \in A \; \left( R(x,y) \wedge R(y,z) \Rightarrow R(x, z) \right) </math>
Quando uma relação <math style="vertical-align:0%;"> R </math> satisfaz as condições acima, <math style="vertical-align:-30%;"> R(x,y) </math> é escrito como <math style="vertical-align:-22%;"> x \le y .</math>. A relação habitual de menor ou igual em conjuntos numéricos, [[número natural|<math style="vertical-align:0%;">\mathbb{N}</math>]], [[número inteiro|<math style="vertical-align:0%;">\mathbb{Z}</math>]], [[número racional|<math style="vertical-align:-17%;">\mathbb{Q}</math>]], [[número real|<math style="vertical-align:0%;">\mathbb{R}</math>]], cumpre com essas condições explicando essa notação.
Um exemplo típico é a relação de inclusão (ampla) entre conjuntos: <math style="vertical-align:-14%;"> A \subseteq B .</math>. geralmente definida sobre o conjunto das partes de <math style="vertical-align:0%;"> A :</math>: <math style="vertical-align:-25%;"> \mathcal{P}\left(A\right) .</math>. Um outro exemplo é a relação <big>"</big><math style="vertical-align:0%;">x</math> divide <math style="vertical-align:-25%;">y</math><big>"</big>: seja <math style="vertical-align:0%;">\mathbb{N}^{+} </math> o conjunto dos números naturais maiores que zero. Para <math style="vertical-align:-20%;">x, y \in \mathbb{N}^{+} ,</math>, dizemos que ''<math style="vertical-align:0%;">x</math> divide <math style="vertical-align:-20%;">y</math>'', em símbolos <math style="vertical-align:-27%;">x | y</math> se e somente se existe um <math style="vertical-align:-9%;"> z \in \mathbb{N}^{+} ,</math>, tal que <math style="vertical-align:-23%;">z . x = y.</math>. Pode ser demonstrado que a relação "divide" assim definida satisfaz as condições da [[#Definição 1: Ordem parcial ampla ou não estrita|Definição 1.]]
=== Definição 2: Ordem parcial estrita ===
Dado um [[conjunto]] <math style="vertical-align:0%;"> A </math> e uma [[relação binária]] <math style="vertical-align:0%;"> R </math> sobre <math style="vertical-align:0%;"> A :</math>: <math style="vertical-align:-17%;"> R \subseteq A \times A ,</math>, dizemos que <math style="vertical-align:0%;"> R </math> é uma ''relação de ordem (parcial) estrita sobre <math style="vertical-align:0%;"> A </math>'' se satisfaz [[#1.c Transitividade:|transitividade]] e:
==== 2.a Irreflexividade: ====
<math style="vertical-align:-26%;">\forall x\in A \;\; \neg R(x,x) </math> <math> \;\;\;\;\;\; </math> (ou seja, nenhum elemento está relacionado consigo mesmo)
Se uma relação <math style="vertical-align:0%;"> R </math> satisfaz [[#1.c Transitividade:|transitividade]] e [[#2.a Antirreflexividade:|irreflexividade]], pode ser demonstrado que <math style="vertical-align:0%;"> R </math> também satisfaz:
==== 2.b Assimetria: ====
<math>\forall x, y \in A \; \left( R(x,y) \Rightarrow \neg R(y,x) \right) .</math>.
Analogamente, pode ser demonstrado que se uma relação <math style="vertical-align:0%;"> R </math> satisfaz [[#1.c Transitividade:|transitividade]] e [[#2.b Assimetria:|assimetria]], então também satisfaz [[#2.a Irreflexividade:|irreflexividade]], fornecendo uma definição alternativa de ordem parcial estrita, preferida por alguns autores.
Quando uma relação <math style="vertical-align:0%;"> R </math> é uma relação de ordem parcial estrita, <math style="vertical-align:-24%;"> R(x,y) </math> é escrito como <math style="vertical-align:-20%;"> x < y .</math>.
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 <big>"</big><math style="vertical-align:0%;"> x </math> é antepassado de <math style="vertical-align:-20%;"> y </math><big>"</big> também é uma ordem estrita.
=== Definição 3: Correspondência entre ordens estritas e amplas ===
== Relações de ordem linear ou total ==
Dada um relação <math style="vertical-align:0%;"> R ,</math>, dizemos que <math style="vertical-align:-26%;"> x, y \in A, \;\; x \neq y </math> são ''incomparáveis'', <math style="vertical-align:-30%;"> x \parallel y </math> se e somente se <math style="vertical-align:-30%;"> \neg R(x,y) </math> nem <math style="vertical-align:-30%;"> \neg R(y, x) .</math>.
Uma ''relação de ordem linear ou total'' não têm elementos incomparáveis.
=== Definição 4: Totalidade ou linearidade ===
Sendo <math style="vertical-align:0%;"> R </math> uma relação sobre <math style="vertical-align:0%;"> A ,</math>, no caso de uma ordem ampla, a totalidade (linearidade) está dada por:
==== 4.a Totalidade ou linearidade (para ordens amplas): ====
<math>\forall x, y \in A \left( x = y \or x < y \or y < x \right) </math>
As ordens dos conjuntos numéricos, [[número natural|<math style="vertical-align:0%;">\mathbb{N}</math>]], [[número inteiro|<math style="vertical-align:0%;">\mathbb{Z}</math>]], [[número racional|<math style="vertical-align:-14%;">\mathbb{Q}</math>]], [[número real|<math style="vertical-align:0%;">\mathbb{R}</math>]] são lineares. Dado um conjunto <math style="vertical-align:0%;"> A </math> com dois ou mais elementos, <math style="vertical-align:-30%;"> \mathcal{P}\left( A \right) ,</math>, o [[conjunto das partes]] de <math style="vertical-align:0%;"> A ,</math>, não está linearmente ordenado por [[inclusão]] <math style="vertical-align:-20%;"> \left( \subseteq \right) </math><big>.</big>
== Relações de ordem densa ==
==== 5 Densidade (para ordens estritas) ====
<math>\forall x, y \in A\ \left(x < y \Rightarrow \exists z \in S\left( x < z < y \right) \right)\,</math>
== Inversa de uma ordem ==
Se uma relação <math style="vertical-align:0%;"> R </math> é uma ordem estrita, então a [[Relação (matemática)#Relação inversa|relação inversa]] de <math style="vertical-align:0%;"> R :</math>:
<math style="vertical-align:0%;"> R^{-1} = \left\{ \left\langle y, x \right\rangle : \;\; \left\langle x, y \right\rangle \in R \right\} </math>
também é uma relação de ordem estrita. A inversa de <big>"</big><math style="vertical-align:0%;"> < </math><big>"</big> é geralmente escrita <big>"</big><math style="vertical-align:0%;"> > </math><big>"</big>. De maneira análoga, para uma relação de ordem ampla <big>"</big><math style="vertical-align:-15%;"> \le </math><big>"</big> pode ser definida a sua inversa <big>"</big><math style="vertical-align:-15%;"> \ge </math><big>"</big>, 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 [[álgebra de Boole|á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<big>, "</big><math style="vertical-align:-15%;"> \le </math><big>",</big> ou estritas<big>, "</big><math style="vertical-align:0%;"> < </math><big>",</big> definições correspondentes podem ser estabelecidas usando [[#Definição 3: Correspondência entre ordens estritas e amplas|Definição 3]].
=== Mínimo e máximo ===
Dada uma relação de ordem ampla <math style="vertical-align:-15%;"> \le </math> sobre um conjunto <math style="vertical-align:0%;"> A ,</math>, um elemento <math style="vertical-align:-9%;"> a \in A </math> é denominado ''mínimo'' ou ''primeiro elemento'' se e somente se:
<math style="vertical-align:0%;"> \forall b \in A \left( a \le b \right) </math>
De maneira simétrica, <math style="vertical-align:-9%;"> a \in A </math> é denominado ''máximo'' ou ''último elemento'' se e somente se:
<math style="vertical-align:0%;"> \forall b \in A \left( a \ge b \right) </math>
O conjunto [[número natural|<math style="vertical-align:0%;">\mathbb{N}</math>]] tem mínimo, mas não tem máximo. Os conjuntos [[número inteiro|<math style="vertical-align:0%;">\mathbb{Z}</math>]], [[número racional|<math style="vertical-align:-17%;">\mathbb{Q}</math>]] e [[número real|<math style="vertical-align:0%;">\mathbb{R}</math>]] não têm nem máximo, nem mínimo. O intervalo
<math style="vertical-align:0%;"> \left[ 0, 1 \right] = \left\{ x \in \mathbb{R} : \;\; 0 \le x \le 1 \right\} </math>
tem mínimo 0 e máximo 1. Dado um conjunto <math style="vertical-align:0%;"> A </math> e considerando a ordem [[inclusão]]<big>,</big> <math style="vertical-align:-10%;"> \subseteq </math><big>,</big> o conjunto <math style="vertical-align:-30%;"> \mathcal{P}\left( A \right) </math>
, [[conjunto das partes|das partes]] de <math style="vertical-align:0%;"> A ,</math>, tem mínimo <math style="vertical-align:0%;"> \varnothing </math> é máximo <math style="vertical-align:0%;"> A .</math>.
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 <math style="vertical-align:-15%;"> < </math> sobre um conjunto <math style="vertical-align:0%;"> A ,</math>, um elemento <math style="vertical-align:-9%;"> a \in A </math> é denominado ''minimal'' quando não existe outro elemento que seja menor que ele:
<math style="vertical-align:0%;"> \neg \exists x \in A, \;\; x < a </math>
Analogamente, um elemento de um conjunto parcialmente ordenado é ''maximal'' quando não existe outro elemento que seja maior que ele:
<math style="vertical-align:0%;"> \neg \exists x \in A, \;\; x > a </math>
=== Cotas inferior (minorante) e superior (majorante) ===
Um elemento <math style="vertical-align:-9%;"> a \in A </math> é uma ''cota inferior'' ou ''[[majorante (matemática)#Definição|minorante]]'' de um subconjunto <math style="vertical-align:-25%;"> B \subseteq A </math> se e somente se:
<math style="vertical-align:0%;"> \forall b \in B \left( a \le b \right) </math>
Um elemento <math style="vertical-align:-9%;"> a \in A </math> é uma ''cota superior'' ou ''[[majorante (matemática)|majorante]]'' de um subconjunto <math style="vertical-align:-25%;"> B \subseteq A </math> se e somente se:
<math style="vertical-align:0%;"> \forall b \in B \left( a \ge b \right) </math>
À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 <math style="vertical-align:-25%;"> \left[ 0, 1 \right] \subseteq \mathbb{R} ,</math>, então qualquer <math style="vertical-align:-20%;"> x \le 0, x \in \mathbb{R} </math> é cota inferior do intervalo e qualquer <math style="vertical-align:-20%;"> x \ge 1, x \in \mathbb{R} </math> é cota superior.
== Boa ordem ==
Uma relação de ordem estrita <math style="vertical-align:0%;"> R </math> sobre um conjunto <math style="vertical-align:0%;"> A </math> é denominada uma ''boa ordem'' se e somente se todo subconjunto não vazio de <math style="vertical-align:0%;"> A </math> tem primeiro elemento segundo <math style="vertical-align:0%;"> R .</math>. Em símbolos, uma relação <big>"</big><math style="vertical-align:0%;"> < </math><big>"</big> sobre <math style="vertical-align:0%;"> A </math> é uma ''boa ordem'' se e somente se:
* <math style="vertical-align:0%;"> < </math> é [[#2.a Irreflexividade:|irreflexiva]], [[#1.c Transitividade:|transitiva]] e
* <math style="vertical-align:-30%;"> \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) </math>
Um conjunto com uma relação de boa ordem é denominado ''bem ordenado''. Por exemplo, <math style="vertical-align:0%;">\mathbb{N}</math> é bem ordenado pela relação natural desse conjunto (ver [[Princípio da boa-ordenação]]), mas <math style="vertical-align:0%;">\mathbb{Z},</math>, <math style="vertical-align:-16%;">\mathbb{Q}</math> e <math style="vertical-align:0%;">\mathbb{R}</math> não são, segundo as suas ordens naturais. O conceito de boa ordem é importante para definir matematicamente os [[número ordinal|números ordinais]] em teoria dos conjuntos.
Uma boa ordem é sempre uma ordem linear, pois se para <math style="vertical-align:-30%;"> a, b \in A, a \ne b </math> consideramos o conjunto <math style="vertical-align:-30%;"> \{ a, b \} ,</math>, ele tem primeiro elemento, de modo que ou <math style="vertical-align:0%;"> a < b ,</math>, ou <math style="vertical-align:0%;"> b < a .</math>.
<!--
== Ordem em sequências ==
}}
== {{VejaVer também}} ==
* [[Relação (matemática)]]
* [[Topologia da ordem]]: uma relação de ordem parcial gera uma [[espaço topológico|topologia]], que tem como [[base (topologia)|base]] os conjuntos do tipo {x | x < b}, {x | x > a} e {x | a < x < b}.
| 