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 e y R x ) se muestran juntas como un único nodo. La relación en las clases de equivalencia es un orden parcial .

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

Un ejemplo natural de un preorden es la relación divisoria "x divide a y" entre números enteros, polinomios o elementos de un anillo conmutativo . Por ejemplo, la relación divisoria es reflexiva, ya que cada número entero se divide a sí mismo. Pero la relación divisoria no es antisimétrica, porque divide y divide . Es a este preorden al que se refieren "mayor" y "menor" 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 preórdenes están estrechamente relacionados con las relaciones de equivalencia y los órdenes parciales (no estrictos). Ambos son casos especiales de un 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 la clase de equivalencia. Al igual que los órdenes parciales y las relaciones de equivalencia, los preórdenes (en un conjunto no vacío) nunca son asimétricos . ${\displaystyle X}$ ${\displaystyle X}$

Un preorden puede visualizarse como un grafo dirigido , con elementos del conjunto correspondientes a vértices, y la relación de orden entre pares de elementos correspondientes a las aristas dirigidas entre vértices. Lo inverso no es cierto: la mayoría de los grafos dirigidos no son ni 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 las aristas del grafo. En general, el grafo dirigido correspondiente de un preorden puede tener muchos componentes desconectados.

Como relación binaria, un preorden puede denotarse como 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 tal que por definición, es algún subconjunto de y se utiliza la notación 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 preorden se llama conjunto preordenado (o proconjunto ). ^[1]

Pedidos anticipados como pedidos parciales en particiones

Dado un preorden en uno, se puede definir una relación de equivalencia en tal que La relación resultante es reflexiva ya que el preorden es reflexivo; transitiva al aplicar la transitividad de dos veces; y simétrica por definición. ${\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 sobre 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 de ciclo : si y solo si o está en un -ciclo con . En cualquier caso, en es posible definir si y solo si Que esto está bien definido, es decir, que su condición definitoria no depende de qué representantes de y se elijan, se sigue de la definición de 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 .\,}$

A la inversa, a partir de cualquier orden parcial de una partición de un conjunto es posible construir un preorden sobre sí mismo. Existe una correspondencia biunívoca entre preórdenes y pares (partición, orden 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á cerrada 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 en porque siempre se cumple y siempre que y ambos se cumplen entonces también lo hace Además, para cualquier si y solo si ; es decir, dos oraciones son equivalentes con respecto a si y solo 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 tales que ). El orden parcial inducido por el cual también se denotará por el mismo símbolo se caracteriza por si y solo si donde la condición del lado derecho es independiente de la elección de 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 si y si denota la oración formada por la conjunción lógica entonces y donde El conjunto parcialmente ordenado es, en consecuencia, también un conjunto dirigido. Véase el álgebra de Lindenbaum-Tarski para 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 se reemplaza la reflexividad por la irreflexividad (manteniendo la transitividad), obtenemos la definición de un orden parcial estricto en . Por este motivo, a veces se utiliza el término preorden estricto para un orden parcial estricto. Es decir, se trata de una relación binaria en que satisface: ${\displaystyle P}$ ${\displaystyle \,<\,}$ ${\displaystyle P}$

1. Irreflexividad o antirreflexividad: no para todo lo que es, es falso para todo 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 estricta inducida por un preorden

Cualquier preorden da lugar a un orden parcial estricto definido por si y solo si y no . Usando la relación de equivalencia introducida anteriormente, si y solo si y por lo tanto se cumple lo siguiente La relación es un orden parcial estricto y cada orden parcial estricto se puede construir de esta manera. Si el preorden es antisimétrico (y por lo tanto un orden parcial) entonces la equivalencia es igualdad (es decir, si y solo si ) y por lo tanto en este caso, la definición de se puede reformular como: Pero lo que es más importante, esta nueva condición no se usa como (ni es equivalente a) la definición general de la relación (es decir, no se define como: si y solo si ) porque si el preorden no es antisimétrico entonces la relación resultante no sería transitiva (considere cómo se relacionan los elementos no iguales equivalentes). Esta es la razón para usar el símbolo " " en lugar del símbolo "menor o igual a" " ", que podría causar confusión para un preorden que no es antisimétrico ya que podría sugerir engañosamente que implica ${\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.}$$ ${\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}}).}$$ ${\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

Usando la construcción anterior, múltiples preórdenes no estrictos pueden producir el mismo preorden estricto , por lo que sin más información sobre cómo se construyó (tal conocimiento de la relación de equivalencia , por ejemplo), podría no ser posible reconstruir el preorden no estricto original a partir de Los posibles preórdenes (no estrictos) que inducen el preorden estricto dado incluyen los siguientes: ${\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 " " a través del 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 son en general no transitivas; sin embargo, si lo son entonces es una equivalencia; en ese caso " " es un orden débil estricto . El preorden resultante es conexo (antes llamado total); es decir, un preorden 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 El recíproco 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 alcanzabilidad en cualquier grafo dirigido (que posiblemente contenga ciclos) da lugar a un preorden, donde en el preorden si y solo si hay un camino de x a y en el grafo dirigido. A la inversa, cada preorden es la relación de alcanzabilidad de un grafo dirigido (por ejemplo, el grafo que tiene una arista de x a y para cada par ( x , y ) con ). Sin embargo, muchos grafos diferentes pueden tener el mismo preorden de alcanzabilidad entre sí. De la misma manera, la alcanzabilidad de grafos acíclicos dirigidos , grafos dirigidos sin ciclos, da lugar a conjuntos parcialmente ordenados (preórdenes que satisfacen una propiedad de antisimetría adicional). ${\displaystyle x\lesssim y}$ ${\displaystyle x\lesssim y}$
• La relación grafo-menor también es un preorden.

Ciencias de la Computación

En informática se pueden encontrar ejemplos de los siguientes preórdenes.

• El orden asintótico produce un preordenamiento de las funciones . La relación de equivalencia correspondiente se denomina equivalencia asintótica . ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$
• Las reducciones de tiempo polinomial , de muchos-uno (mapeo) y de Turing son preórdenes en clases de complejidad.
• Las relaciones de subtipificación suelen ser preórdenes. ^[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 abarcamiento 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}$
• Subsunción theta , ^[3] que es cuando los literales en una fórmula disyuntiva de primer orden están contenidos por otro, después de aplicar una sustitución al anterior.

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. Tales categorías se denominan thin . 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 preórdenes al permitir más de una relación entre objetos: cada morfismo es una relación de preorden distinta (con nombre). ${\displaystyle P,}$
• Alternativamente, un conjunto preordenado 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 definirse si y solo si x pertenece a cada entorno de y . Todo preorden finito puede formarse como el preorden de especialización de un espacio topológico de esta manera. Es decir, existe una correspondencia biunívoca entre topologías finitas y preórdenes finitos. Sin embargo, la relación entre espacios topológicos infinitos y sus preórdenes de especialización no es biunívoca. ${\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 preórdenes no pueden reemplazarse por conjuntos parcialmente ordenados sin perder características importantes.

• La relación definida por si donde f es una función en algún preorden. ${\displaystyle x\lesssim y}$ ${\displaystyle f(x)\lesssim f(y),}$
• Relación definida por si existe alguna inyección de x a y . La inyección puede reemplazarse por una 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 ordenamientos totales contables .

Ejemplo de un pedido anticipado total :

• Preferencia , según modelos comunes.

Construcciones

Toda relación binaria en un conjunto se puede extender a un preorden en tomando el cierre transitivo y el cierre reflexivo . El cierre transitivo indica conexión de caminos en si y solo si hay un camino de a ${\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 residuo 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, y implica entonces que es un orden parcial . ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a}$ ${\displaystyle a=b,}$

Por otro lado, 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 preordenada es una clase equipada con un preorden. Cada conjunto es una clase y, por lo tanto, cada conjunto preordenado es una clase preordenada.

Usos

Los pedidos anticipados juegan un papel fundamental en varias situaciones:

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

Número de pedidos anticipados

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

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

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

Intervalo

Para el intervalo es el conjunto de puntos x que satisfacen y también se escribe Contiene al menos los puntos a y b . Se puede optar por extender 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)}$

Utilizando la relación estricta correspondiente " ", también se puede definir el intervalo como el conjunto de puntos x que satisfacen y también se escribe 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 se puede definir de manera similar . ${\displaystyle [a,b)}$ ${\displaystyle (a,b]}$

Véase también

• Orden parcial – preorden que es antisimétrico
• Relación de equivalencia : preorden que es simétrico
• Pedido anticipado total : pedido anticipado total
• Orden total : preorden que es antisimétrico y total
• Conjunto dirigido
• Categoría de sets preordenados
• Pedido previo al pozo
• Bien-cuasi-ordenamiento

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, Benjamin C. (2002). Tipos y lenguajes de programación . Cambridge, Massachusetts/Londres, Inglaterra: The MIT Press. pp. 182ff. ISBN 0-262-16209-1.
3. Robinson, JA (1965). "Una lógica orientada a máquinas 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 "diferencia de conjunto". ${\displaystyle \backslash }$
5. Kunen, Kenneth (1980), Teoría de conjuntos, una 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 matemáticas y sus aplicaciones, vol. 132, Cambridge University Press, 2011, ISBN 978-0-521-76268-7 
• Schröder, Bernd SW (2002), Conjuntos ordenados: una introducción , Boston: Birkhäuser, ISBN 0-8176-4128-9