2.5: Órdenes

Template:MathJaxZach

Muchas de nuestras comparaciones implican describir algunos objetos como “menores que”, “iguales a” o “mayores que” otros objetos, en cierto sentido. Éstas implican relaciones de orden. Pero hay diferentes tipos de relaciones de orden. Por ejemplo, algunos requieren que dos objetos cualesquiera sean comparables, otros no, algunos incluyen identidad (like\(\le\)) y otros la excluyen (like\(<\)). Nos ayudará tener una taxonomía aquí.

Definición\(\PageIndex{1}\): Preorder

Una relación que es tanto reflexiva como transitiva se llama preorden.

Definición\(\PageIndex{2}\): Partial order

Un preorden que también es antisimétrico se llama orden parcial.

Definición\(\PageIndex{3}\): Linear order

Un orden parcial que también está conectado se denomina orden total o orden lineal.

Cada orden lineal es también un orden parcial, y cada orden parcial también es un preorden, pero los conversos no se mantienen.

Ejemplo\(\PageIndex{1}\)

Cada orden lineal es también un orden parcial, y cada orden parcial también es un preorden, pero los conversos no se mantienen. La relación universal on\(A\) es un preorden, ya que es reflexiva y transitiva. Pero, si\(A\) tiene más de un elemento, la relación universal no es antisimétrica, y por lo tanto no es un orden parcial.

Ejemplo\(\PageIndex{2}\)

Considera la relación no más larga\(\preccurlyeq\) sobre\(\Bin^*\):\(x \preccurlyeq y\) iff\(\len{x} \le \len{y}\). Se trata de un preorden (reflexivo y transitivo), e incluso conectado, pero no un orden parcial, ya que no es antisimétrico. Por ejemplo,\(01 \preccurlyeq 10\) y\(10 \preccurlyeq 01\), pero\(01 \neq 10\).

Ejemplo\(\PageIndex{3}\)

Un orden parcial importante es la relación\(\subseteq\) en un conjunto de conjuntos. Esto no es en general un orden lineal, ya que si\(a \neq b\) y consideramos\(\Pow{\{a, b\}} = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}\), vemos que\(\{a\} \nsubseteq \{b\}\) y\(\{a\} \neq \{b\}\) y\(\{b\} \nsubseteq \{a\}\).

Ejemplo\(\PageIndex{4}\)

La relación de divisibilidad sin resto nos da un orden parcial que no es un orden lineal. Para enteros\(n\),\(m\), escribimos\(n\mid m\) para significar\(n\) (uniformemente) divide\(m\), es decir, iff hay algún entero\(k\) así que eso\(m=kn\). On\(\Nat\), este es un orden parcial, pero no un orden lineal: por ejemplo,\(2\nmid3\) y también\(3\nmid2\). Considerada como una relación sobre\(\Int\), la divisibilidad es sólo un preorden ya que no es antisimétrica:\(1\mid-1\) y\(-1\mid1\) sino\(1\neq-1\).

Definición\(\PageIndex{4}\): Strict order

Un orden estricto es una relación irreflexiva, asimétrica y transitiva.

Definición\(\PageIndex{5}\): Strict linear order

Un orden estricto que también está conectado se llama orden lineal estricto.

Ejemplo\(\PageIndex{5}\)

\(\le\)es el orden lineal correspondiente al orden lineal estricto\(<\). \(\subseteq\)es el orden parcial correspondiente al orden estricto\(\subsetneq\).

Definición\(\PageIndex{6}\): Total order

Un orden estricto que también está conectado se llama orden total. A esto también se le llama a veces un orden lineal estricto.

Cualquier orden\(R\) estricto encendido se\(A\) puede convertir en un orden parcial agregando la diagonal\(\Id{A}\), es decir, agregando todos los pares\(\tuple{x, x}\). (Esto se llama el cierre reflexivo de\(R\).) Por el contrario, a partir de una orden parcial, se puede obtener una orden estricta quitando\(\Id{A}\). Estos dos resultados siguientes hacen que esto sea preciso.

Proposición\(\PageIndex{1}\)

Si\(R\) es una orden estricta en\(A\), entonces\(R^+ = R \cup \Id{A}\) es una orden parcial. Además, si\(R\) es total, entonces\(R^+\) es un orden lineal.

Comprobante. Supongamos que\(R\) es un orden estricto,\(R\) es decir,\(R \subseteq A^2\) y es irreflexivo, asimétrico y transitorio. Vamos\(R^+ = R \cup \Id{A}\). Tenemos que demostrar que\(R^+\) es reflexivo, antisimétrico y transitivo.

\(R^+\)es claramente reflexivo, ya que\(\tuple{x, x} \in \Id{A} \subseteq R^+\) para todos\(x \in A\).

Mostrar\(R^+\) es antisimétrico, supongamos para reductio eso\(R^+xy\) y\(R^+yx\) pero\(x \neq y\). Ya que\(\tuple{x,y} \in R \cup \Id{X}\), pero\(\tuple{x, y} \notin \Id{X}\), debemos tener\(\tuple{x, y} \in R\), es decir,\(Rxy\). De igual manera,\(Ryx\). Pero esto contradice la suposición que\(R\) es asimétrica.

Para establecer la transitividad, supongamos que\(R^+xy\) y\(R^+yz\). Si ambos\(\tuple{x, y} \in R\) y\(\tuple{y,z} \in R\), entonces\(\tuple{x, z} \in R\) ya\(R\) es transitivo. De lo contrario, ya sea\(\tuple{x, y} \in \Id{X}\), es decir\(x = y\),, o\(\tuple{y, z} \in \Id{X}\), es decir,\(y = z\). En el primer caso, tenemos eso\(R^+yz\) por suposición,\(x = y\), de ahí\(R^+xz\). De igual manera en el segundo caso. En cualquier caso\(R^+xz\), así, también\(R^+\) es transitivo.

En cuanto a la cláusula “además”, supongamos que\(R\) es un orden total, es decir, que\(R\) está conectado. Entonces para todos\(x \neq y\), ya sea\(Rxy\) o\(Ryx\), es decir, cualquiera\(\tuple{x, y} \in R\) o\(\tuple{y, x} \in R\). Ya que\(R \subseteq R^+\), esto sigue siendo cierto de\(R^+\), por lo que\(R^+\) está conectado también. ◻

Proposición\(\PageIndex{2}\)

Si\(R\) es una orden parcial encendida\(X\), entonces\(R^- = R \setminus \Id{X}\) es una orden estricta. Además, si\(R\) es lineal, entonces\(R^-\) es total.

Comprobante. Esto se deja como ejercicio. ◻

Problema\(\PageIndex{1}\)

Dar un comprobante de Proposición\(\PageIndex{2}\).

Ejemplo\(\PageIndex{6}\)

\(\le\)es el orden lineal correspondiente al orden total\(<\). \(\subseteq\)es el orden parcial correspondiente al orden estricto\(\subsetneq\).

El siguiente resultado simple que establece que las órdenes totales satisfacen una propiedad similar a la de la extensión:

Proposición\(\PageIndex{3}\)

Si ordena\(<\) totalmente\(A\), entonces:\[(\forall a, b \in A)((\forall x \in A)(x < a \leftrightarrow x < b) \rightarrow a = b)\nonumber\]

Comprobante. Supongamos\((\forall x \in A)(x < a \leftrightarrow x < b)\). Si\(a < b\), entonces\(a < a\), contradiciendo el hecho de que\(<\) es irreflexivo; entonces\(a \nless b\). Exactamente similar,\(b \nless a\). Entonces\(a = b\), como\(<\) está conectado. ◻