Loading [MathJax]/jax/element/mml/optable/MathOperators.js
Saltar al contenido principal
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
LibreTexts Español

2.5: Órdenes

( \newcommand{\kernel}{\mathrm{null}\,}\)

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) y otros la excluyen (like<). Nos ayudará tener una taxonomía aquí.

Definición2.5.1: Preorder

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

Definición2.5.2: Partial order

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

Definición2.5.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.

Ejemplo2.5.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 onA es un preorden, ya que es reflexiva y transitiva. Pero, siA tiene más de un elemento, la relación universal no es antisimétrica, y por lo tanto no es un orden parcial.

Ejemplo2.5.2

Considera la relación no más larga 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 y10 \preccurlyeq 01, pero01 \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 sia \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 enterosn,m, escribimosn\mid m para significarn (uniformemente) dividem, es decir, iff hay algún enterok así que esom=kn. On\Nat, este es un orden parcial, pero no un orden lineal: por ejemplo,2\nmid3 y también3\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 sino1\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}

\lees el orden lineal correspondiente al orden lineal estricto<. \subseteqes 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 ordenR estricto encendido seA 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 deR.) 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}

SiR es una orden estricta enA, entoncesR^+ = R \cup \Id{A} es una orden parcial. Además, siR es total, entoncesR^+ es un orden lineal.

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

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

MostrarR^+ es antisimétrico, supongamos para reductio esoR^+xy yR^+yx perox \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 queR es asimétrica.

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

En cuanto a la cláusula “además”, supongamos queR es un orden total, es decir, queR está conectado. Entonces para todosx \neq y, ya seaRxy oRyx, es decir, cualquiera\tuple{x, y} \in R o\tuple{y, x} \in R. Ya queR \subseteq R^+, esto sigue siendo cierto deR^+, por lo queR^+ está conectado también. ◻

Proposición\PageIndex{2}

SiR es una orden parcial encendidaX, entoncesR^- = R \setminus \Id{X} es una orden estricta. Además, siR es lineal, entoncesR^- es total.

Comprobante. Esto se deja como ejercicio. ◻

Problema\PageIndex{1}

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

Ejemplo\PageIndex{6}

\lees el orden lineal correspondiente al orden total<. \subseteqes 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< totalmenteA, 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). Sia < b, entoncesa < a, contradiciendo el hecho de que< es irreflexivo; entoncesa \nless b. Exactamente similar,b \nless a. Entoncesa = b, como< está conectado. ◻


This page titled 2.5: Órdenes is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .

Support Center

How can we help?