Hacer un pedido

En matemáticas , en particular en la teoría del orden , un preorden o cuasiorden es una relación binaria reflexiva y transitiva . El término preorden sugiere que los preórdenes son casi órdenes 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 a y" entre enteros . Esta relación es reflexiva, ya que todo entero se divide a sí mismo. También es transitiva. Pero no es antisimétrica, porque, por ejemplo,${\displaystyle 1}$divide${\displaystyle -1}$y${\displaystyle -1}$divide${\displaystyle 1}$, pero${\displaystyle -1}$no es igual a${\displaystyle 1}$Es a este preorden al que se refiere "menor" en la frase " mínimo común múltiplo " (en contraste, usando el orden natural en los enteros, por ejemplo${\displaystyle 4}$y${\displaystyle 6}$tienen múltiplos comunes${\displaystyle 24}$,${\displaystyle 12}$,${\displaystyle 0}$,${\displaystyle -12}$,${\displaystyle -24}$, ..., pero al menos uno).

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${\displaystyle X}$puede definirse equivalentemente como una relación de equivalencia en${\displaystyle X}$, junto con un orden parcial en el conjunto de la clase de equivalencia , cf. imagen. Al igual que los órdenes parciales y las relaciones de equivalencia, los preórdenes (en un conjunto no vacío) nunca son asimétricos .

Un preorden puede visualizarse como un grafo dirigido , donde los elementos del conjunto corresponden a los vértices y la relación de orden entre pares de elementos corresponde a las aristas dirigidas entre vértices. Lo contrario no es cierto: la mayoría de los grafos dirigidos no son ni reflexivos ni transitivos. Un preorden antisimétrico ya no tiene ciclos; es un orden parcial y corresponde a un grafo dirigido acíclico . Un preorden simétrico es una relación de equivalencia; puede considerarse como si hubiera perdido los marcadores de dirección en las aristas del grafo. En general, el grafo dirigido correspondiente a un preorden puede tener muchos componentes desconectados.

Un pedido anticipado suele estar indicado${\displaystyle \,\lesssim \,}$o${\displaystyle \,\leq \,}$.

Una relación binaria${\displaystyle \,\lesssim \,}$en un plató${\displaystyle X}$Se denomina preorden o cuasiorden si es reflexivo y transitivo ; es decir, si satisface:

1. Reflexividad :${\displaystyle a\lesssim a}$a pesar de${\displaystyle a\in X,}$y
2. Transitividad : si${\displaystyle a\lesssim b{\text{ y }}b\lesssim c{\text{ entonces }}a\lesssim c}$a pesar de${\displaystyle a,b,c\in X.}$

Un conjunto que está equipado con un preorden se llama conjunto preordenado (o proset ). ^{[ 1 ]}

Dado un pedido anticipado${\displaystyle \,\lesssim \,}$en${\displaystyle X}$se puede definir una relación de equivalencia${\displaystyle \,\sim \,}$en${\displaystyle X}$por $${\displaystyle a\sim b\quad {\text{ si }}\quad a\lesssim b\;{\text{ y }}\;b\lesssim a.}$$ La relación resultante${\displaystyle \,\sim \,}$es reflexivo ya que el pedido anticipado${\displaystyle \,\lesssim \,}$es reflexivo; transitivo aplicando la transitividad de${\displaystyle \,\lesssim \,}$dos veces; y simétrico por definición.

Utilizando esta relación, es posible construir un orden parcial en el conjunto cociente.${\displaystyle X/\sim }$de la equivalencia, definiendo${\displaystyle [x]\leq [y]}$si${\displaystyle x\lesssim y.}$ Que esto esté bien definido , lo que significa que no depende de la elección particular de representantes.${\displaystyle x}$y${\displaystyle y}$, se deduce de la definición de${\displaystyle \,\sim \,}$.

Por el contrario, a partir de cualquier orden parcial en una partición de un conjunto${\displaystyle X,}$es posible construir un pedido anticipado en${\displaystyle X}$en sí mismo. Existe una correspondencia uno a uno entre preórdenes y pares (partición, orden parcial).

Ejemplo : Dejemos${\displaystyle X}$sea ​​el conjunto de todas las oraciones (válidas o inválidas) en algún subcampo de las matemáticas, como la geometría . Definir${\displaystyle p\Leftarrow q}$si${\displaystyle p}$es una consecuencia lógica de${\displaystyle q}$. Entonces${\displaystyle \Leftarrow }$es un pedido anticipado en${\displaystyle X}$: cada oración${\displaystyle p}$puede probarse a partir de sí mismo (reflexividad), y si${\displaystyle p}$se puede probar a partir de${\displaystyle q}$, y${\displaystyle q}$de${\displaystyle r}$, entonces${\displaystyle p}$También se puede probar a partir de${\displaystyle r}$(transitividad). La relación de equivalencia correspondiente se suele denotar${\displaystyle p\Leftrightarrow q}$y definido como${\displaystyle p\Leftarrow q}$y${\displaystyle q\Leftarrow p}$; en este caso${\displaystyle p}$y${\displaystyle q}$se denominan " lógicamente equivalentes ". La clase de equivalencia de una oración${\displaystyle p}$es el conjunto de todas las oraciones${\displaystyle q\in X}$que son lógicamente equivalentes a${\displaystyle p}$; formalmente:${\displaystyle [p]=\{q\mid p\Leftrightarrow q\}}$El conjunto reservado${\displaystyle (X,\Leftarrow )}$es un conjunto dirigido : dadas dos oraciones${\displaystyle p,q\in X}$, su conjunción lógica${\displaystyle p\wedge q}$, pronunciado "ambos"${\displaystyle p}$y${\displaystyle q}$", es un límite superior común de ellos, ya que${\displaystyle p}$es consecuencia de${\displaystyle p\wedge q}$y también lo es${\displaystyle q}$El conjunto parcialmente ordenado${\displaystyle \left(X/\Leftrightarrow ,\Leftarrow \right)}$Por lo tanto, también es un conjunto dirigido. Véase el álgebra de Lindenbaum-Tarski para un ejemplo relacionado.

Si se reemplaza la reflexividad por la irreflexividad (manteniendo la transitividad), entonces obtenemos la definición de un orden parcial estricto en${\displaystyle X}$Por esta razón, el término preorden estricto se utiliza a veces para referirse a un orden parcial estricto. Es decir, se trata de una relación binaria.${\displaystyle \,<\,}$en${\displaystyle X}$que satisface:

1. Irreflexividad o antirreflexividad: no${\displaystyle a<a}$a pesar de${\displaystyle a\in X;}$eso es,${\displaystyle \,a<a}$es falso para todos${\displaystyle a\in X,}$y
2. Transitividad : si${\displaystyle a<b{\text{ and }}b<c{\text{ then }}a<c}$a pesar de${\displaystyle a,b,c\in X.}$

Cada relación binaria${\displaystyle R}$en un plató${\displaystyle X}$puede extenderse a un pedido anticipado en${\displaystyle X}$tomando el cierre transitivo y el cierre reflexivo ,${\displaystyle R^{+=}.}$ El cierre transitivo indica conexión de camino en${\displaystyle R:xR^{+}y}$si y solo si hay una${\displaystyle R}$- camino desde${\displaystyle x}$a${\displaystyle y.}$

Preorden residual izquierdo inducido por una relación binaria

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

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

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

Un pedido anticipado es total si${\displaystyle a\lesssim b}$o${\displaystyle b\lesssim a}$a pesar de${\displaystyle a,b\in X.}$

Una clase reservada es una clase que requiere una reserva previa. Cada conjunto es una clase, por lo que cada conjunto reservado es una clase reservada.

Los pedidos anticipados desempeñan un papel fundamental en diversas situaciones:

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

Nótese que S ( n , k ) se refiere a los números de Stirling de segundo tipo .

Como se explicó anteriormente, existe una correspondencia uno a uno entre los preórdenes y los 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:

For ${\displaystyle a\lesssim b,}$ the interval${\displaystyle [a,b]}$ is the set of points x satisfying ${\displaystyle a\lesssim x}$ and ${\displaystyle x\lesssim b,}$ also written ${\displaystyle a\lesssim x\lesssim b.}$ It contains at least the points a and b. One may choose to extend the definition to all pairs ${\displaystyle (a,b)}$. The extra intervals are all empty.

Using the corresponding strict relation "${\displaystyle <}$", one can also define the interval ${\displaystyle (a,b)}$ as the set of points x satisfying ${\displaystyle a<x}$ and ${\displaystyle x<b,}$ also written ${\displaystyle a<x<b.}$ An open interval may be empty even if ${\displaystyle a<b.}$

Also ${\displaystyle [a,b)}$ and ${\displaystyle (a,b]}$ can be defined similarly.

• Partial order – preorder that is antisymmetric
• Equivalence relation – preorder that is symmetric
• Total preorder – preorder that is total
• Total order – preorder that is antisymmetric and total
• Directed set
• Category of preordered sets
• Prewellordering
• Well-quasi-ordering

• 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