Relación de orden

En matemática y en lógica matemática, especialmente en teoría de conjuntos y teoría de relaciones, una relación de orden es una relación binaria que pretende formalizar la idea intuitiva de ordenación de los elementos de un conjunto.

Definición

Sea $A$ un conjunto dado no vacío y $R$ una relación binaria definida en $A$, entonces se dice que $R$ es una relación de orden si cumple las siguientes propiedades:

1. Reflexividad: Todo elemento de $A$ está relacionado consigo mismo. Es decir, $\forall x\in A, \; xRx$.
2. Antisimetría: Si dos elementos de $A$ se relacionan entre sí, entonces ellos son iguales. Es decir, $\forall x,y\in A, \; xRy, \; yRx \; \Rightarrow \; x=y$
3. Transitividad: Si un elemento de $A$ está relacionado con otro, y ese otro a su vez se relaciona con un tercero, entonces el primero estará relacionado también con este último. Es decir, $\forall x,y,z\in A, \; xRy , yRz \Rightarrow xRz$

Una relación de orden $R$ sobre un conjunto $A$ puede denotarse con el par ordenado $(A,\le)$.

Relación de orden total

Sea $A$ un conjunto dado, $\le$ es una relación de orden total si y solo si todos los elementos de $A$ se relacionan entre sí, es decir,

$\forall x,y\in A, (x\le y) \vee (y\le x)$.

• Ejemplo $(\mathbb{N},\le)$ es totalmente ordenado. En efecto, es:
  • Reflexivo: $\forall n\in\mathbb{N},$ entonces $n\le n$ (porque por definición, $n=n\,$)
  • Antisimétrico: $\forall n_1, n_2\in\mathbb{N},$ si $\; \; n_1\le n_2\; \;$ y $\; \; n_2\le n_1,\; \;$ entonces $n_1\le n_2\le n_1$ $\Rightarrow n_1=n_2$
  • Transitivo: $\forall n_1,n_2,n_3\in\mathbb{N},$ si $\; \; n_1\le n_2\; \;$ y $\; \; n_2\le n_3,\; \;$ entonces $n_1\le n_2\le n_3 \Rightarrow n_1\le n_3$
  • Orden total, pues

Sean m y n dos números naturales, entonces m ≤ n ó n ≤ m .

Contraejenplo, (ℤ₊, | ) no es totalmente ordenado con la relación a|b , " a divide b"; pues

5 no divide a 12, ya que no existe h entero positivo tal que 12 = 5h. En todo caso , para cualquier h ∈ ℤ₊, 12 ≠ 5h.

Relación de orden parcial

Sea $A$ un conjunto dado, $\le$ es una relación de orden parcial si y solo si al menos un par de elementos de $A$ se relacionan entre sí, es decir,

$\exists x,y\in A,$ tal que $(x\le y) \vee (y\le x)$.

• Ejemplo. Sea el conjunto $X=\{1, 2, 3\}$ y el conjunto potencia de $X$, definido por:

$\mathcal{P}(X)=\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}$

Entonces $(\mathcal{P}(X), \subseteq)$ es parcialmente ordenado, pues sean

$A=\{1\}, B=\{1,2\}, C=\{3\}\in\mathcal{P}(X),$

$A\subseteq B,$ pero $(A\nsubseteq C) \wedge (C\nsubseteq A).$

Nótese que las relaciones de orden total son un caso particular de las relaciones de orden parcial.

Relación de orden densa

Véase también: Conjunto denso.

Una relación de orden parcial ≤ sobre un conjunto X se dice densa (o densa-en -sí-misma) si, para todo x e y en X tales que x < y (x ≤ y y x ≠ y), existe otro z en X tal que x < z < y.

• Ejemplo 1: Los números racionales con la ordenación habitual son un conjunto densamente ordenado, al igual que los números reales. Si q₁ < q₂ entonces tenemos que q₃ := (q₁+q₂)/2 satisface que: q₁ < q₃ < q₂.
• Ejemplo 2: Los números enteros por otro lado con la ordenación habitual no son un conjunto densamente ordenado ya que entre un número entero y su siguiente no existe un número intermedio.

Véase también

• Teoría del orden

Esquema de temas relacionados

Teoría del orden Bien ordenado Orden total Parcialmente ordenado Preordenado Relación reflexiva Relación transitiva Relación antisimétrica Relación total Relación bien fundada

Bibliografía

• Birkhoff, Garrett (1948) (en inglés). Lattice Theory. New York: American Mathematical Society. 

• Davey, B.A.; Priestley, H.A (2002) (en inglés). Introduction to Lattices and Order. Cambridge: Cambridge University Press. ISBN 978-0-521-78451-1. 

• Fraïssé, Roland (2000) (en inglés). Theory of Relations. Amsterdam: Elsevier. ISBN 0-444-50542-3. 

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

• Rosenstein, Joseph G (1982) (en inglés). Linear Orderings (2nd. edición). New York: Academic Press. ISBN 0-12-597680-1.