19.2: Definición y propiedades

Observe que en cada uno de los ejemplos de la Sección 19.1, la noción de “es menor que” se define a través de una relación. Usaremos\(\mathord{\le}\) on\(\mathbb{N}\) como nuestro modelo para una relación en un conjunto que se pueda considerar como que expresa “es menor o igual en tamaño a”.

• Cada elemento del conjunto debe ser “menor o igual que” en sí mismo, por lo que la relación debe ser reflexiva.
• El tamaño relativo nunca debe ser bidireccional para distintos elementos del conjunto, por lo que la relación debe ser antisimétrica.
• Deberíamos ser capaces de inferir relaciones de tamaño a partir de cadenas de ellas, por lo que la relación debe ser transitiva.

Observe que estas son las mismas propiedades que para una relación de equivalencia, excepto que hemos volteado simétrico a antisimétrico. ¡Asegúrate de mantener esto recto!

Definición: Orden parcial

una relación reflexiva, antisimétrica y transitiva

Definición: Conjunto parcialmente ordenado

un conjunto equipado con un orden parcial particular

Definición:\(\mathord{\preceq}\)

símbolo para un orden parcial abstracto

Definición: estrictamente menos/más pequeños que

\(a \preceq b\)y\(a \neq b\)

Definición:\(a \prec b\)

\(a\)es estrictamente menor/más pequeño que\(b\)

Advertencia\(\PageIndex{1}\)

Anteriormente usamos el símbolo\(\mathord{\preceq}\) para significar exclusivamente “es un subgrafo de”, pero eso fue en anticipación de la introducción de este símbolo para significar ahora un orden parcial general.

Ejemplo\(\PageIndex{1}\): “Less than or equal to” versus “less than” on sets of numbers.

La noción habitual de\(\mathord{\leq}\) es un orden parcial sobre\(\mathbb{N}\) (o o\(\mathbb{Z}\)\(\mathbb{Q}\) o\(\mathbb{R}\)), pero no lo\(\mathord{\lt}\) es.

Ejemplo\(\PageIndex{2}\): Subset relation.

Por cada conjunto\(U\text{,}\) la relación\(\mathord{\subseteq}\) es un orden parcial\(\mathscr{P}(U)\text{,}\) pero no\(\mathord{\subsetneqq}\) lo es.

Ejemplo\(\PageIndex{3}\): Subgraph relation.

Por cada gráfica\(G\text{,}\) la relación subgráfica\(\mathord{\preceq}\) es un orden parcial en\(S(G)\text{,}\) el conjunto de subgráficos de\(G\text{.}\)

Ejemplo\(\PageIndex{4}\): Comparing cardinalities.

Supongamos que\(U\) es un conjunto universal, y consideramos la colección de subconjuntos finitos de\(U\text{.}\) Entonces tenemos una manera natural de comparar tamaños de estos subconjuntos: escribir\(A \mathrel{R} B\) para significar\(\vert A \vert \le \vert B \vert\text{.}\) Sin embargo, esta relación no es un orden parcial ya que no es antisimétrica. Esto se debe a que es posible tener ambos\(A \mathrel{R} B\) y\(B \mathrel{R} A\) con\(A \neq B\text{,}\) en el caso de que\(\vert A \vert = \vert B \vert\text{.}\) Cambiar la relación a media\(\vert A \vert \lneqq \vert B \vert\) no ayuda, desde entonces no sería reflexivo.

Ahora supongamos que el conjunto universal\(U\) es infinito y consideramos todos (de ahí posiblemente infinitos) subconjuntos de\(U\text{.}\) En este caso tenemos una idea más general de menor y mayor, donde\(A\) es menor que\(B\) si existe una inyección\(A \hookrightarrow B\) pero no biyección\(A \to B\text{.}\) Esta noción más general de comparación de tamaños vía cardinalidad sufre las mismas fallas que en el caso de conjunto finito, ya que no es reflexiva, y si tratamos de arreglar eso agregando “o el mismo tamaño que” entonces no será antisimétrico.

Sin embargo, tanto en casos finitos como (posiblemente) infinitos, podemos convertir la comparación de cardinalidad en un orden parcial usando “menor o igual a”, donde “menor” debe significar estrictamente menor en términos de cardinalidad, pero “igual” significa igualdad de conjuntos en lugar de igualdad de cardinalidad.

Ejemplo\(\PageIndex{5}\): English alphabetic order.

Dejar\(\Sigma = \{a, b, c, \ldots, y, z\}\text{,}\) y considerar el orden alfabético en el conjunto de palabras\(\Sigma ^{\ast}\text{;}\) e.g.

\ begin {align*}\ mathrm {gqtiu} &\ preceq\ mathrm {ppb}, &\ mathrm {aaay} &\ preceq\ mathrm {aaaz}, &\ mathrm {aaa} &\ preceq\ mathrm {aaaa}. \ end {align*} El orden
alfabético es un orden parcial en\(\Sigma ^{\ast}\text{.}\)

Ejemplo\(\PageIndex{6}\): Lexicographic order.

Podemos generalizar el ejemplo anterior: si\(\Sigma\) es un conjunto de alfabeto parcialmente ordenado equipado con orden parcial\(\mathord{\preceq}\text{,}\) entonces podemos definir inductivamente un orden\(\mathord{\preceq^\ast}\) parcial\(\Sigma ^{\ast}\) por:

• \(\emptyset \preceq^\ast w\)para cada\(w \in \Sigma ^{\ast}\text{,}\) donde\(\emptyset\) está la palabra vacía;
• por\(a,b \in \Sigma\text{,}\) considerar estas letras como palabras de longitud\(1\) en\(\Sigma ^{\ast}\) tomar\(a \preceq^\ast b\) para significar\(a \preceq b\) en\(\Sigma\text{;}\)
• para las letras\(a_1, a_2 \in \Sigma\) y las palabras\(w_1, w_2 \in \Sigma ^{\ast}\text{,}\) llevan\(a_1 w_1 \preceq^\ast a_2 w_2\) a significar que ya sea
  1. \(a_1 \ne a_2\)y\(a_1 \preceq a_2\text{,}\) o
  2. \(a_1 = a_2\)y\(w_1 \preceq^\ast w_2\text{.}\)

Esto se llama orden lexicográfico o diccionario en\(\Sigma ^{\ast}\text{.}\)

Ejemplo\(\PageIndex{7}\): Ordering Cartesian products.

Podemos emplear una táctica similar para los productos cartesianos. Si\(\mathord{\preceq_A}, \mathord{\preceq_B}\) son órdenes parciales en conjuntos\(A,B\text{,}\) respectivamente, podemos definir un orden parcial\(\mathord{\preceq}\) en\(A \times B\)\((a_1, b_1) \preceq (a_2, b_2)\) permitiendo significar que cualquiera

\(a_1 \ne a_2\)y\(a_1 \preceq_A a_2\text{,}\) o

\(a_1 = a_2\)y\(b_1 \preceq_B b_2\text{.}\)

Esto también se llama orden lexicográfico.

Ejemplo\(\PageIndex{8}\): Larger/greater than is a partial order.

Podemos voltear “menor/menor que o igual a” alrededor de “grandes/mayor que o igual a”. Por ejemplo, para los elementos\(m,n \in \mathbb{N}\text{,}\)\(m \preceq n\) escribir significa\(m \ge n\text{.}\) Entonces\(\mathord{\preceq}\) es un orden parcial en\(\mathbb{N}\text{.}\)

Esta es una instancia de un patrón más general. Dado un orden parcial\(\mathord{\preceq}\) en un conjunto,\(A\text{,}\) la relación inversa\(\mathord{\vert \preceq \vert}\text{,}\)\(a_1 \mathrel{\vert \preceq \vert} a_2\) donde\(a_2 \preceq a_1\text{,}\) media es también un orden parcial en\(A\text{,}\) llamado orden dual.

Ejemplo\(\PageIndex{9}\): Transferring \(\le\) on \(\mathbb{N}\) to a power set.

Vamos\(A = \{a,b,c,d\}\text{,}\) y vamos a “codificar” cada elemento de\(\mathscr{P}(A)\) por el siguiente algoritmo.

Dado elemento de entrada\(X \in \mathscr{P}(A)\) (es decir, dada entrada\(X\) que es un subconjunto de\(A\)):

1. Inicializar valor codificado\(r = 0\text{.}\)
2. Si\(X\) contiene\(a\text{,}\) agregar\(1\) a\(r\text{.}\)
3. Si\(X\) contiene\(b\text{,}\) agregar\(2\) a\(r\text{.}\)
4. Si\(X\) contiene\(c\text{,}\) agregar\(4\) a\(r\text{.}\)
5. Si\(X\) contiene\(d\text{,}\) agregar\(8\) a\(r\text{.}\)
6. Establecer\(\text{encode}(X)\) para ser el valor final de\(r\text{.}\)

Por ejemplo,

\ begin {alinear*}\ texto {codificar} (\ {b\}) & = 2, &\ texto {codificar} (\ emptyset) & = 0,\\\ texto {codificar} (\ {a, c\}) & = 1 + 4 = 5, &\ texto {codificar} (A) & = 1 + 2 + 4 + 8 = 15. \ end {align*}
Este proceso de codificación es uno a uno; es decir, no hay dos subconjuntos de\(A\) salida del mismo valor codificado.

Ahora defina\(\mathord{\preceq}\)\(\mathscr{P}(A)\) tomando\(X \preceq Y\) como significado\(\text{encode}(X) \le \text{encode}(Y)\text{.}\) Por ejemplo,

\ begin {align*}\ {a, b, c\} &\ preceq\ {d\}, &\ {a, d\} &\ preceq\ {b, d\},\ end {align*}
y ambos

\ begin {align*}\ emptyset &\ preceq X, & X &\ preceq A\ end {align*}
son verdaderos para cada subconjunto\(X \subseteq A\text{.}\)

Los hechos que\(\mathord{\le}\) es un orden parcial\(\mathbb{N}\) y que este proceso de codificación es uno a uno se combinarán para hacer\(\mathord{\preceq}\) un orden parcial.

Ejemplo\(\PageIndex{10}\): Pulling a partial order back through an injection.

Generalizando Ejemplo\(\PageIndex{9}\), supongamos que\(f: A \hookrightarrow B\) es una inyección donde\(B\) está parcialmente ordenada por\(\mathord{\preceq_B}\text{.}\) Entonces podemos “tirar hacia atrás” el orden parcial encendido\(B\) para crear un orden parcial encendido de la\(A\) siguiente manera: definir\(a_1 \preceq_A a_2\) para significar que\(f(a_1) \preceq_B f(a_2)\) es cierto. Obsérvese que el supuesto de que\(f\) es inyectivo es esencial para garantizar que\(\mathord{\preceq_A}\) será antisimétrico.