19.4: Total de Órdenes

Definición: Elementos comparables

elementos\(a,b\) en un conjunto parcialmente ordenado de tal manera\(a \preceq b\) que\(b \preceq a\)

Definición: Elementos Incomparables

elementos que no son comparables

Ejemplo\(\PageIndex{1}\): Comparable and incomparable subsets.

Let\(U\) representar algún conjunto universal que contiene al menos dos elementos, y considerar\(\mathscr{P}(U)\) parcialmente ordenado por\(\mathord{\subseteq}\text{.}\)

• Tanto el conjunto\(\emptyset\) vacío como el conjunto universal\(U\) son comparables a cada elemento de\(\mathscr{P}(U)\text{.}\)
• Porque\(x,y\in U\) con\(x\ne y\text{,}\) entonces\(\{x\},\{y\}\) son incomparables.
• De hecho, por cada subconjunto no vacío y apropiado\(A \subsetneqq U\) existe un subconjunto\(B \subseteq U\) que es incomparable de\(A\text{:}\) tomar\(B = A^C\text{.}\)

No obstante, no dejes que los dos segundos puntos anteriores te lleven por mal camino: no es necesario que los subconjuntos sean disjuntos para ser incomparables. Siempre y cuando cada uno de un par de subconjuntos contenga un elemento que el otro no, entonces los dos serán incomparables por\(\mathord{\subseteq}\text{.}\)

Definición: Total Order

un orden parcial en un conjunto tal que cada par de elementos es comparable

Definición: Conjunto totalmente ordenado

un conjunto equipado con un pedido total

Ejemplo\(\PageIndex{2}\): Subset order is not total.

Para el\(U\text{,}\) pedido\(\mathord{\subseteq}\) de conjunto universal no\(\mathscr{P}(U)\) es total excepto cuando\(\vert U \vert \le 1\text{.}\)

Ejemplo\(\PageIndex{3}\): Usual order of numbers is total.

Nuestro pedido habitual para números,\(\mathord{\leq}\text{,}\) es un pedido total\(\mathbb{N}\text{,}\)\(\mathbb{Z}\text{,}\) encendido\(\mathbb{Q}\text{,}\) o encendido\(\mathbb{R}\text{.}\)

Ejemplo\(\PageIndex{4}\): Total order on alphabet induces total order on words.

Si\(\mathord{\preceq}\) es un orden total en un alfabeto\(\Sigma\text{,}\) entonces el orden lexicográfico\(\preceq^\ast\) descrito en el Ejemplo 19.2.6 es un orden total en el conjunto de palabras\(\Sigma^{\ast}\text{.}\)

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

Si\(B\) está totalmente ordenado y usamos una inyección\(f: A \hookrightarrow B\) para “tirar hacia atrás” el pedido en\(B\) un pedido encendido\(A\) (ver Ejemplo 19.2.10), entonces el pedido recién creado en también\(A\) será total.

Ejemplo\(\PageIndex{6}\): Countable can be totally ordered.

Si\(A\) es un conjunto contablemente infinito, entonces existe una biyección\(f: \mathbb{N} \rightarrow A\text{.}\) Podemos usar la inversa\(f^{-1}: A \rightarrow \mathbb{N}\) para “tirar hacia atrás” el orden total habitual\(\mathord{\le}\) en\(\mathbb{N}\) un orden total encendido\(A\) (ver Ejemplo\(\PageIndex{5}\)).

Otro punto de vista sobre esto es que nuestra bijección\(f\) crea una secuencia infinita

\ begin {ecuación*} a_0, a_1, a_2,\ ldots\ text {,}\ end {ecuación*}
donde cada elemento de\(A\) aparece exactamente una vez. Esta secuencia se puede convertir en una especificación del orden total activado\(A\) simplemente convirtiendo las comas en\(\mathord{\le}\) símbolos:

\ begin {ecuación*} a_0\ le a_1\ le a_2\ le\ cdots\ texto {.} \ end {ecuación*}

Comentario\(\PageIndex{1}\)

El patrón de Ejemplo\(\PageIndex{6}\) se vuelve aún más simple cuando lo aplicamos a un conjunto finito: un orden total en un conjunto finito no es diferente de un orden de los elementos del conjunto en una lista, como

\ begin {equation*} a_0, a_1, a_2,\ ldots, a_n\ end {ecuación*} simplemente se
puede convertir en

\ begin {ecuación*} a_0\ le a_1\ le a_2\ le\ cdots\ le a_n\ text {,}\ end {ecuación*}
y viceversa.

Pregunta\(\PageIndex{1}\)

Si\(A\) es un conjunto finito, totalmente ordenado, ¿cómo se ve el diagrama de Hasse correspondiente?

La respuesta a esta pregunta está contenida en la observación\(\PageIndex{1}\).

Hecho\(\PageIndex{1}\)

Un orden parcial en un conjunto finito es total si y solo si su diagrama Hasse forma una sola línea vertical.

Ejemplo\(\PageIndex{7}\): A totally ordered finite set.

La figura\(\PageIndex{1}\) exhibe el diagrama de Hasse para el orden total\(\mathord{\mid}\) en el set\(\{2,4,8,16,32\}\text{,}\) aunque hemos dibujado el diagrama en una inclinación desde la vertical para que sea más fácil ver todo el diagrama de un vistazo.

Figura\(\PageIndex{1}\): Diagrama de Hasse de un conjunto totalmente ordenado.