Hacer un pedido - Preorder

En matemáticas , especialmente en teoría de órdenes , un preorden o cuasiordenador es una relación binaria que es reflexiva y transitiva . Los preordenes son más generales que las relaciones de equivalencia y los órdenes parciales (no estrictos) , los cuales 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.

El nombre preorden proviene de la idea de que los preordenes (que no son pedidos parciales) son pedidos "casi" (parciales), pero no del todo; no son necesariamente antisimétricas ni asimétricas . Debido a que un preorden es una relación binaria, el símbolo se puede usar como dispositivo de notación para la relación. Sin embargo, debido a que no son necesariamente antisimétricos, es posible que algunas de las intuiciones ordinarias asociadas al símbolo no se apliquen. Por otro lado, un preorden se puede utilizar, de forma sencilla, para definir un orden parcial y una relación de equivalencia. Sin embargo, hacerlo no siempre es útil o valioso, según el dominio del problema que se esté estudiando. ${\ Displaystyle \, \ leq \,}$${\ Displaystyle \, \ leq \,}$

En palabras, cuando se puede decir que b cubre a o que a precede a b , o que b se reduce a a . Ocasionalmente, se usa la notación ← o en lugar de${\ Displaystyle a \ leq b,}$ ${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle \, \ leq.}$

A cada preorden le corresponde un grafo dirigido , con elementos del conjunto correspondientes a vértices, y la relación de orden entre pares de elementos correspondiente a las aristas dirigidas entre vértices. Lo contrario no es cierto: la mayoría de los gráficos dirigidos no son reflexivos ni transitivos. En general, los gráficos correspondientes pueden contener ciclos . Un pedido anticipado 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.

Definicion formal

Considere una relación homogénea en algún conjunto dado de modo que, por definición, es un subconjunto de y la notación se usa en lugar de. Entonces se llama preorden o cuasorden si es reflexivo y transitivo ; es decir, si satisface: ${\ Displaystyle \, \ leq \,}$ ${\ Displaystyle P,}$${\ Displaystyle \, \ leq \,}$${\ Displaystyle P \ times P}$${\ Displaystyle a \ leq b}$${\ Displaystyle (a, b) \ in \, \ leq.}$${\ Displaystyle \, \ leq \,}$

1. Reflexividad : y${\ Displaystyle a \ leq a {\ text {para todos}} a \ in P,}$
2. Transitividad :${\ Displaystyle {\ text {if}} a \ leq b {\ text {y}} b \ leq c {\ text {luego}} a \ leq c {\ text {para todos}} a, b, c \ En p.}$

Un conjunto que está equipado con un pedido anticipado se denomina conjunto pedido anticipado (o proset ). Para enfatizar o contrastar los pedidos por adelantado estrictos , un pedido por adelantado también puede denominarse pedido por adelantado no estricto .

Si la reflexividad se reemplaza por irreflexividad (mientras se mantiene la transitividad), el resultado se denomina preorden estricto; explícitamente, un orden previo estricta en es una relación binaria homogénea en que satisface las siguientes condiciones: ${\ Displaystyle P}$${\ Displaystyle \, <\,}$${\ Displaystyle P}$

1. Irreflexividad o antirreflexividad : es decir, y${\ Displaystyle {\ textit {not}} \; a <a \; {\ text {para todos}} a \ in P;}$${\ Displaystyle \, a <a \; {\ text {es}} {\ textit {falso}} {\ text {para todos}} a \ en P,}$
2. Transitividad :${\ Displaystyle {\ text {if}} a <b {\ text {y}} b <c {\ text {luego}} a <c {\ text {para todos}} a, b, c \ en P. }$

Una relación binaria es un preorden estricto si y solo si es un orden parcial estricto . Por definición, un orden parcial estricto es un preorden estricto asimétrico , donde se llama asimétrico si para todos. A la inversa, todo preorden estricto es un orden parcial estricto porque toda relación transitiva irreflexiva es necesariamente asimétrica . Aunque son equivalentes, el término "orden parcial estricto" se prefiere típicamente sobre "preorden estricto" y se remite a los lectores al artículo sobre órdenes parciales estrictas para obtener detalles sobre tales relaciones. A diferencia de los pedidos por adelantado estrictos, hay muchos pedidos por adelantado (no estrictos) que no son pedidos parciales (no estrictos) . ${\ Displaystyle \, <\,}$${\ Displaystyle a <b {\ text {implica}} {\ textit {not}} \ b <a}$${\ Displaystyle a, b.}$

Definiciones relacionadas

Si un pedido anticipado también es antisimétrico , es decir, e implica que es un pedido parcial . ${\ Displaystyle a \ leq b}$${\ Displaystyle b \ leq a}$${\ Displaystyle a = b,}$

Por otro lado, si es simétrico , es decir, si implica, entonces es una relación de equivalencia . ${\ Displaystyle a \ leq b}$${\ Displaystyle b \ leq a,}$

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

La noción de un conjunto preordenado se puede formular en un marco categórico como una categoría delgada ; es decir, como una categoría con como máximo un morfismo de un objeto a otro. Aquí los objetos corresponden a los elementos de y hay un morfismo para los objetos que están relacionados, cero en caso contrario. Alternativamente, un conjunto preordenado puede entenderse como una categoría enriquecida, enriquecida sobre la categoría${\ Displaystyle P}$${\ Displaystyle P,}$${\ Displaystyle 2 = (0 \ a 1).}$

Una clase reservada es una clase equipada con una reserva. Cada conjunto es una clase y, por lo tanto, cada conjunto preordenado es una clase preordenada.

Ejemplos de

La asequibilidad relación en cualquier gráfico dirigido (posiblemente ciclos que contienen) da lugar a un orden previo, en donde en el orden previo si y sólo si existe un camino desde x a y en el gráfico dirigido. Por el contrario, cada orden previo es la relación de alcanzabilidad de un grafo dirigido (por ejemplo, el gráfico que tiene un borde de x a y para cada par ( x , y ) con Sin embargo, muchos gráficos diferentes pueden tener el mismo orden previo alcanzabilidad como 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 (pedidos anticipados que satisfacen una propiedad antisimetría adicional). ${\ Displaystyle x \ leq y}$${\ Displaystyle x \ leq y.}$

Todo espacio topológico finito da lugar a un preorden en sus puntos al definir si y solo si x pertenece a cada vecindad de y . Cada preorden finito puede formarse como preorden de especialización de un espacio topológico de esta manera. Es decir, existe una correspondencia uno a uno entre topologías finitas y preordenes finitos. Sin embargo, la relación entre espacios topológicos infinitos y sus preordenes de especialización no es uno a uno. ${\ Displaystyle x \ leq 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 ser reemplazados por conjuntos parcialmente ordenados sin perder características importantes.

Más ejemplos:

• La relación definida por if donde f es una función en algún preorden.${\ Displaystyle x \ leq y}$${\ Displaystyle f (x) \ leq f (y),}$
• La relación se define por si existe alguna inyección de x a y . La inyección puede reemplazarse por sobreyección o cualquier tipo de función de conservación de la estructura, como el homomorfismo de anillo o la permutación .${\ Displaystyle x \ leq y}$
• La relación de incrustación para pedidos totales contables .
• La relación grafo-menor en la teoría de grafos .
• 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 . En este sentido, las categorías "generalizan" los preordenes al permitir más de una relación entre objetos: cada morfismo es una relación de preorden distinta (nombrada).

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

• Las reducciones de Many-one y Turing son pedidos anticipados en clases de complejidad.
• Las relaciones de subtipificación suelen ser pedidos por adelantado.
• 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 inclusión en el conjunto de términos , definido por si un subtermo de t es una instancia de sustitución de s .${\ Displaystyle s \ leq t}$

Ejemplo de un pedido anticipado total :

• Preferencia , según modelos comunes.

Usos

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

• A cada preorden se le puede dar una topología, la topología Alexandrov ; y de hecho, cada preorden en un set está en correspondencia uno a uno con una topología de Alexandrov en ese set.
• 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 .
• Pre-ordenes se utilizan en forzando en la teoría de conjuntos para probar la consistencia y la independencia de los resultados.

Construcciones

Cada relación binaria en un conjunto puede extenderse a un preorden en tomando el cierre transitivo y el cierre reflexivo . El cierre transitivo indica una conexión de ruta en si y solo si hay una - ruta 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 , donde denota la relación inversa de y denota la relación de complemento 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}$

Pedidos anticipados y pedidos parciales en particiones

Dado un preorden en uno puede definir una relación de equivalencia en tal que ${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle S}$ ${\ Displaystyle \, \ sim \,}$${\ Displaystyle S}$

La relación resultante es reflexiva ya que un preorden es reflexivo, transitivo al aplicar la transitividad del preorden dos veces y simétrico por definición. ${\ Displaystyle \, \ sim \,}$

Usando esta relación, es posible construir un orden parcial en el conjunto cociente de la equivalencia, el conjunto de todas las clases de equivalencia de Si el preorden es 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 Por la construcción de esta definición es independiente de los representantes elegidos y la relación correspondiente está efectivamente bien definida. 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] {\ text {si y solo si}} x \ lesssim y.}$${\ Displaystyle \, \ sim,}$

Por el contrario, a partir de un pedido parcial en una partición de un conjunto, se puede construir un pedido anticipado. Existe una correspondencia biunívoca entre los pedidos anticipados y los pares (partición, orden parcial). ${\ Displaystyle S}$${\ Displaystyle S.}$

Ejemplo : Sea una teoría formal , que es un conjunto de oraciones con determinadas 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 será escrita como y como entonces necesariamente La relación es un preorden en porque siempre se cumple y siempre y cuando ambos se mantienen. 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 sobre inducido por el cual también será denotado 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 conjunción lógica entonces y donde El conjunto parcialmente ordenado es, en consecuencia, también un conjunto dirigido. Consulte el á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 \ en S.}$${\ Displaystyle \, \ Leftarrow \,}$${\ Displaystyle S}$${\ Displaystyle A \ Leftarrow A}$${\ Displaystyle A \ Leftarrow B}$${\ Displaystyle B \ Leftarrow C}$${\ Displaystyle A \ Leftarrow C.}$${\ Displaystyle A, B \ en S,}$ ${\ Displaystyle A \ sim B}$${\ Displaystyle A \ Leftarrow B {\ text {y}} 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 \ en [A]}$${\ Displaystyle B \ en [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 \ en S.}$${\ Displaystyle \ left (S / \ sim, \ Leftarrow \ right)}$

Pedidos por adelantado y pedidos por adelantado estrictos

Pedido anticipado estricto inducido por un pedido anticipado

Dado un preorden, se puede definir una nueva relación declarando que si y solo si o de manera equivalente, utilizando la relación de equivalencia introducida anteriormente, de modo que la relación satisfaga ${\ Displaystyle \, \ lesssim,}$${\ Displaystyle \, <\,}$${\ Displaystyle a <b}$${\ displaystyle (a \ lesssim b {\ text {y no}} b \ lesssim a),}$${\ Displaystyle (a \ lesssim b {\ text {y no}} a \ sim b)}$

La relación es un orden parcial estricto y todo orden parcial estricto puede ser el resultado de tal construcción. Si el preorden es antisimétrico y, por lo tanto, un orden parcial, entonces la equivalencia es igualdad (es decir, ) y, por lo tanto, la relación de esta definición se puede reformular como: ${\ Displaystyle \, <\,}$${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle a \ sim b {\ text {si y solo si}} a = b}$${\ Displaystyle \, <\,}$

$${\ Displaystyle a <b \ quad {\ text {si y solo si}} \ quad (a \ leq b {\ text {y}} a \ neq b) \ quad \ quad ({\ text {if}} \ lesssim {\ text {es antisimétrico}}).}$$

Pero lo más importante, esto es , no la definición general de la relación (es decir, se no se define como: si y sólo si ) ya que si el orden previo no es antisimétrica entonces la relación resultante no sería transitiva (pienso en lo equivalente no iguales elementos relacionar). Esta es la razón por la que se usa el símbolo " " en lugar del "menor o igual que" símbolo " ", lo que puede causar confusión para un pedido por adelantado que no es antisimétrico, ya que puede sugerir de manera engañosa que implica${\ Displaystyle \, <\,}$${\ Displaystyle \, <\,}$${\ Displaystyle a <b}$${\ Displaystyle (a \ lesssim b {\ text {y}} a \ neq b)}$${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle \, <\,}$${\ Displaystyle \ lesssim}$${\ Displaystyle \ leq}$${\ Displaystyle a \ leq b}$${\ Displaystyle a <b {\ text {o}} a = b.}$

Pedidos anticipados inducidos por un pedido anticipado estricto

Con esta construcción, múltiples preordenes " " pueden resultar en la misma relación estricta preorden, por lo que sin más información, como la relación de equivalencia " " no se puede reconstruir a partir de " ". Los posibles pedidos por adelantado incluyen lo siguiente: ${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle \, <, \,}$${\ Displaystyle \, \ lesssim \,}$${\ 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 no necesitamos las notaciones y${\ Displaystyle a \ leq b}$${\ Displaystyle a <b {\ text {o}} a = b}$${\ Displaystyle <}$${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle \, \ sim.}$
• Definir como " " (es decir, tomar el complemento inverso de la relación), que corresponde a definir como "ninguno "; estas relaciones y , en general, no son transitivas; sin embargo, si lo son, es una equivalencia; en ese caso, " " es un

orden estrictamente débil . El pedido anticipado resultante está conectado (anteriormente llamado total), es decir, un pedido anticipado total .${\ Displaystyle a \ lesssim b}$${\ Displaystyle {\ text {not}} b <a}$${\ Displaystyle a \ sim b}$${\ Displaystyle a <b {\ text {ni}} b <a}$${\ Displaystyle \, \ lesssim \,}$${\ Displaystyle \, \ sim \,}$${\ Displaystyle \, \ sim \,}$${\ Displaystyle <}$

Número de pedidos anticipados

Número de relaciones binarias de n elementos de diferentes tipos

Elementos	Ninguna	Transitivo	Reflexivo	Hacer un pedido	Orden parcial	Reserva total	Orden total	Relación de equivalencia
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	dieciséis	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3.994	4.096	355	219	75	24	15
norte	2 n 2		2 n 2 - n			${\ textstyle \ sum _ {k = 0} ^ {n} k!}$S ( n , k )	n !	${\ textstyle \ sum _ {k = 0} ^ {n}}$S ( n , k )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

• por ${\ Displaystyle n = 3:}$
  • 1 partición de 3, dando 1 preorden
  • 3 particiones de 2 + 1 , dando preordenes${\ Displaystyle 3 \ times 3 = 9}$
  • 1 partición de 1 + 1 + 1 , dando 19 preordenes
  Es decir, juntos, 29 pedidos por adelantado.
• por ${\ Displaystyle n = 4:}$
  • 1 partición de 4, dando 1 preorden
  • 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 , dando 219 pedidos por adelantado
  Es decir, juntos, 355 pedidos por adelantado.

Intervalo

Para el

intervalo es el conjunto de puntos x que satisfacen y también escrito contiene por lo menos los puntos de una 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)}$

Usando la correspondiente relación estricta " ", también se puede definir el intervalo como el conjunto de puntos

x satisfactorios y también escrito 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

• Pedido parcial: pedido anticipado que es antisimétrico
• Relación de equivalencia : preorden simétrico
• Pedido anticipado total: pedido anticipado total
• Orden total : preorden antisimétrico y total
• Conjunto dirigido
• Categoría de conjuntos preordenados
• Ordenamiento previo
• Bien casi ordenado

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 , MR  1127325.
2. ^ Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . Cambridge, Massachusetts / Londres, Inglaterra: The MIT Press. págs. 182ff. ISBN 0-262-16209-1.
3. ^ Kunen, Kenneth (1980), Teoría de conjuntos, Introducción a las pruebas de independencia , Estudios de lógica y fundamentos de las matemáticas, 102 , Amsterdam, Países Bajos: Elsevier.
4. ^ En este contexto, "" no significa "diferencia de conjuntos".${\ Displaystyle \ backslash}$

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