Hacer un pedido

Relación binaria reflexiva y transitiva

Diagrama de Hasse del preorden x R y definido por x // 4≤ y // 4 en los números naturales . Las clases de equivalencia (conjuntos de elementos tales que x R y y y R x ) se muestran juntas como un solo nodo. La relación sobre clases de equivalencia es de orden parcial .

En matemáticas , especialmente en teoría del orden , un preorden o cuasiorden es una relación binaria que es reflexiva y transitiva . El nombre preorder pretende sugerir que los preorder son pedidos casi parciales , pero no del todo, ya que no son necesariamente antisimétricos .

Un ejemplo natural de preorden es la relación de división "x divide y" entre números enteros, polinomios o elementos de un anillo conmutativo . Por ejemplo, la relación divide es reflexiva ya que cada número entero se divide a sí mismo. Pero la relación divide no es antisimétrica, porque divide y divide . Es a este preorden al que "mayor" y "menor" se refieren en las frases " máximo común divisor " y " mínimo común múltiplo " (excepto que, para los números enteros, el máximo común divisor es también el mayor para el orden natural de los números enteros). ). ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle -1}$ ${\displaystyle 1}$

Los pedidos anticipados están estrechamente relacionados con relaciones de equivalencia y pedidos parciales (no estrictos). Ambos son casos especiales de preorden: un preorden antisimétrico es un orden parcial y un preorden simétrico es una relación de equivalencia. Además, un preorden en un conjunto puede definirse de manera equivalente como una relación de equivalencia en , junto con un orden parcial en el conjunto de clases de equivalencia. Al igual que los pedidos parciales y las relaciones de equivalencia, los pedidos anticipados (en un conjunto no vacío) nunca son asimétricos . ${\displaystyle X}$ ${\displaystyle X}$

Un preorden se puede visualizar como un gráfico dirigido , con elementos del conjunto correspondientes a los vértices, y la relación de orden entre pares de elementos correspondientes a las aristas dirigidas entre los vértices. Lo contrario no es cierto: la mayoría de los grafos dirigidos no son reflexivos ni transitivos. Un preorden que es antisimétrico ya no tiene ciclos; es un orden parcial, y corresponde a un grafo acíclico dirigido . Un preorden que es simétrico es una relación de equivalencia; se puede pensar que ha perdido los marcadores de dirección en los bordes del gráfico. En general, el gráfico dirigido correspondiente de un pedido anticipado puede tener muchos componentes desconectados.

Como relación binaria, un pedido anticipado puede denotarse o . En palabras, cuando se puede decir que b cubre a o que a precede a b , o que b se reduce a a . Ocasionalmente también se utiliza la notación ← o →. ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\leq \,}$ ${\displaystyle a\lesssim b,}$

Definición

Sea una relación binaria en un conjunto de modo que, por definición, sea un subconjunto de y la notación se use en lugar de. Entonces se llama preorden o cuasiorden si es reflexivo y transitivo ; es decir, si satisface: ${\displaystyle \,\lesssim \,}$ ${\displaystyle P,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle P\times P}$ ${\displaystyle a\lesssim b}$ ${\displaystyle (a,b)\in \,\lesssim .}$ ${\displaystyle \,\lesssim \,}$

1. Reflexividad : para todos y ${\displaystyle a\lesssim a}$ ${\displaystyle a\in P,}$
2. Transitividad : si para todos ${\displaystyle a\lesssim b{\text{ and }}b\lesssim c{\text{ then }}a\lesssim c}$ ${\displaystyle a,b,c\in P.}$

Un conjunto que está equipado con un pedido anticipado se llama conjunto reservado (o proset ). ^[1]

Pedidos anticipados como pedidos parciales en particiones.

Dado un pedido anticipado en uno, se puede definir una relación de equivalencia tal que ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ ${\displaystyle \,\sim \,}$ ${\displaystyle S}$

$${\displaystyle a\sim b\quad {\text{ if and only if }}\quad a\lesssim b\;{\text{ and }}\;b\lesssim a.}$$

${\displaystyle \,\sim \,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\lesssim \,}$

Usando esta relación, es posible construir un orden parcial en el conjunto cociente de la equivalencia, que es el conjunto de todas las clases de equivalencia de Si el preorden se denota por entonces es el conjunto de - clases de equivalencia del ciclo : si y sólo si o está en un ciclo con En cualquier caso, es posible definir si y sólo si Eso está bien definido, lo que significa que su condición definitoria no depende de qué representantes de y se eligen, se desprende de la definición de Es Se verifica fácilmente que esto produce un conjunto parcialmente ordenado. ${\displaystyle S/\sim ,}$ ${\displaystyle \,\sim .}$ ${\displaystyle R^{+=},}$ ${\displaystyle S/\sim }$ ${\displaystyle R}$ ${\displaystyle x\in [y]}$ ${\displaystyle x=y}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle S/\sim }$ ${\displaystyle [x]\leq [y]}$ ${\displaystyle x\lesssim y.}$ ${\displaystyle [x]}$ ${\displaystyle [y]}$ ${\displaystyle \,\sim .\,}$

Por el contrario, a partir de cualquier orden parcial sobre una partición de un conjunto es posible construir un preorden sobre sí mismo. Existe una correspondencia uno a uno entre pedidos anticipados y pares (partición, pedido parcial). ${\displaystyle S,}$ ${\displaystyle S}$

Ejemplo : Sea una teoría formal , que es un conjunto de oraciones con ciertas propiedades (cuyos detalles se pueden encontrar en el artículo sobre el tema ). Por ejemplo, podría ser una teoría de primer orden (como la teoría de conjuntos de Zermelo-Fraenkel ) o una teoría de orden cero más simple . Una de las muchas propiedades de es que está cerrado bajo consecuencias lógicas, de modo que, por ejemplo, si una oración implica lógicamente alguna oración que se escribirá como y también como entonces necesariamente (por modus ponens ). La relación es un preorden porque siempre se cumple y cuando y ambos se cumplen, entonces también se cumple. Además, para cualquiera si y solo si ; es decir, dos oraciones son equivalentes respecto de si y sólo si son lógicamente equivalentes . Esta relación de equivalencia particular se denota comúnmente con su propio símbolo especial y, por lo tanto, este símbolo puede usarse en lugar de. La clase de equivalencia de una oración denotada por consiste en todas las oraciones que son lógicamente equivalentes a (es decir, todas aquellas que ). El orden parcial inducido por el cual también se denotará con el mismo símbolo se caracteriza por si y sólo si donde la condición del lado derecho es independiente de la elección de los representantes y de las clases de equivalencia. Todo lo que se ha dicho hasta ahora también se puede decir de su relación inversa. El conjunto preordenado es un conjunto dirigido porque if y if denota la oración formada por la conjunción lógica entonces y dónde . En consecuencia , el conjunto parcialmente ordenado también es un conjunto dirigido. Consulte Álgebra de Lindenbaum-Tarski para ver un ejemplo relacionado. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle A\in S}$ ${\displaystyle B,}$ ${\displaystyle A\Rightarrow B}$ ${\displaystyle B\Leftarrow A,}$ ${\displaystyle B\in S}$ ${\displaystyle \,\Leftarrow \,}$ ${\displaystyle S}$ ${\displaystyle A\Leftarrow A}$ ${\displaystyle A\Leftarrow B}$ ${\displaystyle B\Leftarrow C}$ ${\displaystyle A\Leftarrow C.}$ ${\displaystyle A,B\in S,}$ ${\displaystyle A\sim B}$ ${\displaystyle A\Leftarrow B{\text{ and }}B\Leftarrow A}$ ${\displaystyle \,\Leftarrow \,}$ ${\displaystyle A\sim B}$ ${\displaystyle A\iff B,}$ ${\displaystyle \,\iff \,}$ ${\displaystyle \,\sim .}$ ${\displaystyle A,}$ ${\displaystyle [A],}$ ${\displaystyle B\in S}$ ${\displaystyle A}$ ${\displaystyle B\in S}$ ${\displaystyle A\iff B}$ ${\displaystyle S/\sim }$ ${\displaystyle \,\Leftarrow ,\,}$ ${\displaystyle \,\Leftarrow ,\,}$ ${\displaystyle [A]\Leftarrow [B]}$ ${\displaystyle A\Leftarrow B,}$ ${\displaystyle A\in [A]}$ ${\displaystyle B\in [B]}$ ${\displaystyle \,\Leftarrow \,}$ ${\displaystyle \,\Rightarrow .\,}$ ${\displaystyle (S,\Leftarrow )}$ ${\displaystyle A,B\in S}$ ${\displaystyle C:=A\wedge B}$ ${\displaystyle \,\wedge ,\,}$ ${\displaystyle A\Leftarrow C}$ ${\displaystyle B\Leftarrow C}$ ${\displaystyle C\in S.}$ ${\displaystyle \left(S/\sim ,\Leftarrow \right)}$

Relación con órdenes parciales estrictas

Si la reflexividad se reemplaza por la irreflexividad (manteniendo la transitividad), entonces obtenemos la definición de un orden parcial estricto en . Por este motivo, el término pedido anticipado estricto se utiliza a veces para un pedido parcial estricto. Es decir, ésta es una relación binaria que satisface: ${\displaystyle P}$ ${\displaystyle \,<\,}$ ${\displaystyle P}$

1. Irreflexividad o antirreflexividad: no para todo lo que es, es falso para todos y ${\displaystyle a<a}$ ${\displaystyle a\in P;}$ ${\displaystyle \,a<a}$ ${\displaystyle a\in P,}$
2. Transitividad : si para todos ${\displaystyle a<b{\text{ and }}b<c{\text{ then }}a<c}$ ${\displaystyle a,b,c\in P.}$

Orden parcial estricto inducido por un pedido anticipado

Cualquier pedido anticipado da lugar a un orden parcial estricto definido por si y sólo si y no . Utilizando la relación de equivalencia introducida anteriormente, si y sólo si se cumple lo siguiente ${\displaystyle \,\lesssim \,}$ ${\displaystyle a<b}$ ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a}$ ${\displaystyle \,\sim \,}$ ${\displaystyle a<b}$ ${\displaystyle a\lesssim b{\text{ and not }}a\sim b;}$

$${\displaystyle a\lesssim b\quad {\text{ if and only if }}\quad a<b\;{\text{ or }}\;a\sim b.}$$

orden parcial estrictotodoSiantisimétrico ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle a\sim b}$ ${\displaystyle a=b}$ ${\displaystyle \,<\,}$

$${\displaystyle a<b\quad {\text{ if and only if }}\quad a\lesssim b\;{\text{ and }}\;a\neq b\quad \quad ({\text{assuming }}\lesssim {\text{ is antisymmetric}}).}$$

nono ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle a<b}$ ${\displaystyle a\lesssim b{\text{ and }}a\neq b}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,<\,}$ ${\displaystyle \lesssim }$ ${\displaystyle \leq }$ ${\displaystyle a\leq b}$ ${\displaystyle a<b{\text{ or }}a=b.}$

Pedidos anticipados inducidos por un pedido parcial estricto

Utilizando la construcción anterior, múltiples pedidos anticipados no estrictos pueden producir el mismo pedido anticipado estricto, por lo que sin más información sobre cómo se construyó (como el conocimiento de la relación de equivalencia, por ejemplo), podría no ser posible reconstruir el pedido anticipado no estricto original a partir de Posible. Los pedidos anticipados (no estrictos) que inducen el pedido anticipado estricto dado incluyen lo siguiente: ${\displaystyle \,<,\,}$ ${\displaystyle \,<\,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle \,<.\,}$ ${\displaystyle \,<\,}$

• Definir como (es decir, tomar el cierre reflexivo de la relación). Esto da el orden parcial asociado con el orden parcial estricto " " mediante cierre reflexivo; en este caso la equivalencia es igualdad por lo que los símbolos y no son necesarios. ${\displaystyle a\leq b}$ ${\displaystyle a<b{\text{ or }}a=b}$ ${\displaystyle <}$ ${\displaystyle \,=,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\sim \,}$
• Definir como " " (es decir, tomar el complemento inverso de la relación), lo que corresponde a definir como "ninguno "; estas relaciones y en general no son transitivas; sin embargo, si lo son entonces es una equivalencia; en ese caso " " es un orden estrictamente débil . El pedido anticipado resultante está conectado (anteriormente llamado total); es decir, una preventa total . ${\displaystyle a\lesssim b}$ ${\displaystyle {\text{ not }}b<a}$ ${\displaystyle a\sim b}$ ${\displaystyle a<b{\text{ nor }}b<a}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle \,\sim \,}$ ${\displaystyle <}$

Si entonces Lo contrario se cumple (es decir, ) si y sólo si siempre que entonces o ${\displaystyle a\leq b}$ ${\displaystyle a\lesssim b.}$ ${\displaystyle \,\lesssim \;\;=\;\;\leq \,}$ ${\displaystyle a\neq b}$ ${\displaystyle a<b}$ ${\displaystyle b<a.}$

Ejemplos

Teoría de grafos

• La relación de accesibilidad en cualquier gráfico dirigido (que posiblemente contenga ciclos) da lugar a un pedido anticipado, donde en el pedido anticipado si y solo si hay una ruta de xay en el gráfico dirigido . Por el contrario, cada pedido anticipado es la relación de accesibilidad de un gráfico dirigido (por ejemplo, el gráfico que tiene un borde de xay para cada par ( x , y ) con ). Sin embargo, muchos gráficos diferentes pueden tener el mismo preorden de accesibilidad entre sí. De la misma manera, la accesibilidad de gráficos acíclicos dirigidos , gráficos dirigidos sin ciclos, da lugar a conjuntos parcialmente ordenados (preórdenes que satisfacen una propiedad antisimétrica adicional). ${\displaystyle x\lesssim y}$ ${\displaystyle x\lesssim y}$
• La relación gráfico-menor también es un preorden.

Ciencias de la Computación

En informática, se pueden encontrar ejemplos de los siguientes pedidos anticipados.

• El orden asintótico provoca un preorden sobre funciones . La relación de equivalencia correspondiente se llama equivalencia asintótica . ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$
• El tiempo polinomial , muchos uno (mapeo) y las reducciones de Turing son pedidos anticipados de clases de complejidad.
• Las relaciones de subtipos suelen ser pedidos anticipados. ^[2]
• Los pedidos anticipados de simulación son pedidos anticipados (de ahí el nombre).
• Relaciones de reducción en sistemas de reescritura abstracta .
• El preorden de abarcación en el conjunto de términos , definido por si un subtérmino de t es una instancia de sustitución de s . ${\displaystyle s\lesssim t}$
• Theta-subsunción , ^[3] que es cuando los literales de una fórmula disyuntiva de primer orden están contenidos por otra, previa aplicación de una sustitución a la primera.

Teoría de categorías

• Una categoría con como máximo un morfismo de cualquier objeto x a cualquier otro objeto y es un preorden. Estas categorías se denominan delgadas . Aquí los objetos corresponden a los elementos de y hay un morfismo para los objetos que están relacionados, cero en caso contrario. En este sentido, las categorías "generalizan" los pedidos anticipados al permitir más de una relación entre objetos: cada morfismo es una relación de pedido previo distinta (nombrada). ${\displaystyle P,}$
• Alternativamente, un conjunto reservado puede entenderse como una categoría enriquecida , enriquecida sobre la categoría. ${\displaystyle 2=(0\to 1).}$

Otro

Más ejemplos:

• Todo espacio topológico finito da lugar a un preorden en sus puntos al definir si y sólo si x pertenece a cada vecindad de y . De este modo, todo preorden finito puede formarse como preorden de especialización de un espacio topológico. Es decir, existe una correspondencia uno a uno entre topologías finitas y pedidos anticipados finitos. Sin embargo, la relación entre infinitos espacios topológicos y sus preórdenes de especialización no es uno a uno. ${\displaystyle x\lesssim y}$

• Una red es un preorden dirigido , es decir, cada par de elementos tiene un límite superior . La definición de convergencia a través de redes es importante en topología , donde los pedidos anticipados no pueden reemplazarse por conjuntos parcialmente ordenados sin perder características importantes.

• La relación definida por if donde f es una función en algún preorden. ${\displaystyle x\lesssim y}$ ${\displaystyle f(x)\lesssim f(y),}$
• La relación definida por si existe alguna inyección de x a y . La inyección puede reemplazarse por sobreyección o cualquier tipo de función que preserve la estructura, como el homomorfismo de anillo o la permutación . ${\displaystyle x\lesssim y}$
• La relación de incrustación para pedidos totales contables .

Ejemplo de un pedido anticipado total :

• Preferencia , según modelos comunes.

Construcciones

Cada relación binaria en un conjunto se puede extender a un preorden tomando el cierre transitivo y el cierre reflexivo . El cierre transitivo indica conexión de camino en si y sólo si hay un camino desde hasta ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R^{+=}.}$ ${\displaystyle R:xR^{+}y}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle y.}$

Preorden residual izquierdo inducido por una relación binaria

Dada una relación binaria, la composición complementada forma un preorden llamado residual izquierdo , ^[4] donde denota la relación inversa de y denota la relación complementaria de mientras que denota la composición de la relación . ${\displaystyle R,}$ ${\displaystyle R\backslash R={\overline {R^{\textsf {T}}\circ {\overline {R}}}}}$ ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle R,}$ ${\displaystyle {\overline {R}}}$ ${\displaystyle R,}$ ${\displaystyle \circ }$

Definiciones relacionadas

Si un preorden también es antisimétrico , es decir, e implica entonces es un orden parcial . ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a}$ ${\displaystyle a=b,}$

En cambio, si es simétrica , es decir, si implica entonces es una relación de equivalencia . ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a,}$

Un pedido anticipado es total si o para todos ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a}$ ${\displaystyle a,b\in P.}$

Una clase reservada es una clase equipada con un pedido anticipado. Cada conjunto es una clase y, por lo tanto, cada conjunto reservado es una clase reservada.

Usos

Los pedidos por adelantado juegan un papel fundamental en varias situaciones:

• A cada pedido anticipado se le puede dar una topología, la topología de Alexandrov ; y, de hecho, cada pedido anticipado en un conjunto está en correspondencia uno a uno con una topología de Alexandrov en ese conjunto.
• Los pedidos anticipados se pueden utilizar para definir álgebras interiores .
• Los pedidos anticipados proporcionan la semántica de Kripke para ciertos tipos de lógica modal .
• Los pedidos anticipados se utilizan para forzar la teoría de conjuntos para demostrar resultados de coherencia e independencia . ^[5]

Número de pedidos anticipados

Tenga en cuenta que S ( n , k ) se refiere a los números de Stirling del segundo tipo .

Como se explicó anteriormente, existe una correspondencia 1 a 1 entre pedidos anticipados y pares (partición, pedido parcial). Por tanto, el número de pedidos anticipados es la suma del número de pedidos parciales en cada partición. Por ejemplo:

• para ${\displaystyle n=3:}$
  • 1 partición de 3, dando 1 pedido anticipado
  • 3 particiones de 2+1 , dando pedidos anticipados ${\displaystyle 3\times 3=9}$
  • 1 partición de 1 + 1 + 1 , dando 19 pedidos anticipados
  Es decir, en conjunto, 29 pedidos anticipados.
• para ${\displaystyle n=4:}$
  • 1 partición de 4, dando 1 pedido anticipado
  • 7 particiones con dos clases (4 de 3 + 1 y 3 de 2 + 2 ), dando pedidos anticipados ${\displaystyle 7\times 3=21}$
  • 6 particiones de 2+1+1 , dando pedidos anticipados ${\displaystyle 6\times 19=114}$
  • 1 partición de 1 + 1 + 1 + 1 , dando 219 pedidos anticipados
  Es decir, en conjunto, 355 pedidos anticipados.

Intervalo

Porque el intervalo es el conjunto de puntos x satisfactorios y también escritos. Contiene al menos los puntos a y b . Se puede optar por ampliar la definición a todos los pares. Los intervalos adicionales están todos vacíos. ${\displaystyle a\lesssim b,}$ ${\displaystyle [a,b]}$ ${\displaystyle a\lesssim x}$ ${\displaystyle x\lesssim b,}$ ${\displaystyle a\lesssim x\lesssim b.}$ ${\displaystyle (a,b)}$

Usando la relación estricta correspondiente " ", también se puede definir el intervalo como el conjunto de puntos x que satisfacen y también se escriben. Un intervalo abierto puede estar vacío incluso si ${\displaystyle <}$ ${\displaystyle (a,b)}$ ${\displaystyle a<x}$ ${\displaystyle x<b,}$ ${\displaystyle a<x<b.}$ ${\displaystyle a<b.}$

También y se puede definir de manera similar. ${\displaystyle [a,b)}$ ${\displaystyle (a,b]}$

Ver también

• Orden parcial : preorden que es antisimétrica
• Relación de equivalencia – preorden que es simétrica
• Reserva total : reserva total
• Orden total – preorden que es antisimétrica y total
• Conjunto dirigido
• Categoría de conjuntos reservados
• Preordenar
• Bien casi-ordenando

Notas

1. Para "proset", véase, por ejemplo, Eklund, Patrik; Gähler, Werner (1990), "Espacios de Cauchy generalizados", Mathematische Nachrichten , 147 : 219–233, doi :10.1002/mana.19901470123, SEÑOR  1127325.
2. Pierce, Benjamín C. (2002). Tipos y Lenguajes de Programación . Cambridge, Massachusetts/Londres, Inglaterra: The MIT Press. págs. 182 y siguientes. ISBN 0-262-16209-1.
3. Robinson, JA (1965). "Una lógica orientada a máquina basada en el principio de resolución". ACM . 12 (1): 23–41. doi : 10.1145/321250.321253 . S2CID  14389185.
4. En este contexto, " " no significa "establecer diferencia". ${\displaystyle \backslash }$
5. Kunen, Kenneth (1980), Teoría de conjuntos, Introducción a las pruebas de independencia , Estudios de lógica y fundamentos de las matemáticas, vol. 102, Ámsterdam, Países Bajos: Elsevier.

Referencias

• Schmidt, Gunther, "Matemáticas relacionales", Enciclopedia de las matemáticas y sus aplicaciones, vol. 132, Cambridge University Press, 2011, ISBN 978-0-521-76268-7 
• Schröder, Bernd SW (2002), Conjuntos ordenados: introducción , Boston: Birkhäuser, ISBN 0-8176-4128-9