Relação de ordem: diferenças entre revisões

 

== Definições básicas ==

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

 

<math style="vertical-align:-7%;>\forall x\in A \;\; R(x,x) </math> <math> \;\;\;\;\;\; </math> (ou seja, todo elemento está relacionado consigo mesmo);

 

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

 

<math>\forall x, y, z \in A \; \left( R(x,y) \wedge R(y,z) \Rightarrow R(x, z) \right) </math>

 

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

 

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:

 

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

 

<math>\forall x, y \in A \; \left( R(x,y) \Rightarrow \neg R(y,x) \right) </math>.

 

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.

 

Dada uma ordem estrita ou uma ordem ampla, pode ser definida a outra ordem correspondente, segundo:<ref>[[#DaveyPriestley2002IntroductiontoLatticesAndOrder|DAVEY PRIESTLEY (2002)]], p. 2.</ref>

 

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

 

Uma ''relação de ordem linear ou total'' não têm elementos incomparáveis.

 

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:

 

<math>\forall x, y \in A \left( x \leq y \or y \le x \right) </math>

Também denominado "dicotomia".

 

No caso das ordens estritas:

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

 

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

 

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

 

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