Relaciones binarias | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Todas las definiciones requieren tácitamente transitividad y reflexividad . |
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 ≤ puede usarse 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.
En palabras, cuando a ≤ b , 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 ≤.
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 set dado para que por definición, es un subconjunto de y la notación se usa en lugar de Luego se llama preorden o cuasorden si es reflexivo y transitivo ; es decir, si satisface:
- Reflexividad : para todos y
- Transitividad ; Si y luego para todos
Un conjunto que está equipado con un pedido anticipado se denomina conjunto pedido anticipado (o proset ). [1] 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 la irreflexividad (mientras se mantiene la transitividad), el resultado se denomina preorden estricto; explícitamente, una reserva estricta en es una relación binaria homogénea en que es transitivo y también satisface la siguiente condición:
- Irreflexividad o antirreflexividad : es falso para todos
Todo pedido parcial estricto es (por definición) un pedido anticipado estricto; a la inversa, dado que toda relación transitiva irreflexiva es necesariamente asimétrica , todo preorden estricto es también un orden parcial estricto. En consecuencia, una relación binaria es un preorden estricto si y solo si es un orden parcial estricto. 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) .
Definiciones relacionadas
Si un pedido anticipado también es antisimétrico , es decir, y implica entonces es un pedido parcial .
Por otro lado, si es simétrico , es decir, si implica entonces es una relación de equivalencia .
Un pedido anticipado es total si o para todos
La noción de un conjunto preordenado puede formularse 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 dey 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 2 = (0 → 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, donde x ≤ y 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 x ≤ y ). Sin embargo, muchos gráficos diferentes pueden tener el mismo preorden de accesibilidad que los demá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).
Todo espacio topológico finito da lugar a un preorden en sus puntos al definir x ≤ y si y solo si x pertenece a cada vecindario 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.
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 x ≤ y si f ( x ) ≤ f ( y ) , donde f es una función en algún preorden.
- La relación definida por x ≤ y 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 .
- 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. [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 inclusión en el conjunto de términos , definido por s ≤ t si un subtermo de t es una instancia de sustitución de s .
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. [3]
Construcciones
Cada relación binaria R en un conjunto S puede extenderse a un preorden en S tomando el cierre transitivo y el cierre reflexivo , R + = . El cierre transitivo indica una conexión de ruta en R: x R + y si y solo si hay una ruta R- de xay .
Dada una orden previo ≲ en S se puede definir una relación de equivalencia ~ en S tal que un ~ b si y sólo si una ≲ b y b ≲ una . (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).
Usando esta relación, es posible construir un orden parcial sobre el conjunto cociente de la equivalencia, S / ~ , el conjunto de todas las clases de equivalencia de ~. Tenga en cuenta que si el preorden es R + = , S / ~ es el conjunto de clases de equivalencia de ciclo R : x ∈ [ y ] si y solo si x = y o x está en un ciclo R con y . En cualquier caso, en S / ~ , es posible definir [ x ] ≤ [ y ] si y solo si x ≲ y . Por la construcción de ~, esta definición es independiente de los representantes elegidos y la relación correspondiente está bien definida. Se verifica fácilmente que esto produce un conjunto parcialmente ordenado.
A la inversa, a partir de un orden parcial en una partición de un conjunto S, se puede construir un preorden en S. Existe una correspondencia 1 a 1 entre preordenes y pares (partición, orden parcial).
Para un preorden "≲", una relación "<" se puede definir como a < b si y solo si ( a ≲ b y no b ≲ a ), o de manera equivalente, usando la relación de equivalencia introducida anteriormente, ( a ≲ b y no a ~ b ). Es una orden parcial estricta ; todo orden parcial estricto puede ser el resultado de tal construcción. Si el orden previo es antisimétrica, por lo tanto, un orden parcial "≤", la equivalencia es la igualdad, por lo que la relación "<" también se puede definir como un < b si y sólo si ( a ≤ b y un ≠ b ).
La relación "<" está no define como: un < b si y sólo si ( un ≲ b y un ≠ b ). Hacerlo causaría problemas si el preorden no fuera antisimétrico, ya que la relación resultante "<" no sería transitiva (piense en cómo se relacionan los elementos equivalentes no iguales).
Por el contrario, a ≲ b si y solo si a < b o a ~ b . Ésta es la razón por la que se utiliza la notación "≲"; "≤" puede ser confuso para un orden previo que no es antisimétrica, se puede sugerir que un ≤ b implica que un < b o un = b .
Con esta construcción, múltiples preordenes "≲" pueden dar la misma relación "<", 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:
- Definir un ≤ b como un < b o un = b (es decir, tomar el cierre reflexiva 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 ~.
- Defina a ≲ b como "no b < a " (es decir, tome el complemento inverso de la relación), que corresponde a definir a ~ b como "ni a < b ni b < a "; estas relaciones ≲ y ~ no son en general 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 .
Dada una relación binaria , la composición complementada forma un preorden llamado residuo izquierdo , [4] dondedenota la relación inversa de, y denota la relación de complemento de, tiempo denota la composición de la relación .
Número de pedidos anticipados
Elementos | Alguna | 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 | ∑n k = 0 k ! S ( n , k ) | n ! | ∑n k = 0 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:
- para n = 3 :
- 1 partición de 3, dando 1 preorden
- 3 particiones de 2 + 1 , dando 3 × 3 = 9 preordenes
- 1 partición de 1 + 1 + 1 , dando 19 preordenes
- para 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 7 × 3 = 21 preordenes
- 6 particiones de 2 + 1 + 1 , dando 6 × 19 = 114 preordenes
- 1 partición de 1 + 1 + 1 + 1 , dando 219 pedidos por adelantado
Intervalo
Para a ≲ b , el intervalo [ a , b ] es el conjunto de puntos x que satisfacen a ≲ x y x ≲ b , también escrito a ≲ x ≲ b . Contiene al menos los puntos de una y b . Se puede optar por ampliar la definición a todos los pares ( a , b ) . Los intervalos adicionales están todos vacíos.
Usando la correspondiente relación estricta "<", también se puede definir el intervalo ( a , b ) como el conjunto de puntos x que satisfacen a < x y x < b , también escrito a < x < b . Un intervalo abierto puede estar vacío incluso si a < b .
También [ a , b ) y ( a , b ] se pueden definir de manera similar.
Ver también
- Pedido parcial: pedido anticipado que es antisimétrico
- Relación de equivalencia - preorden que es 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
- ^ 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.
- ^ 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.
- ^ Kunen, Kenneth (1980), Teoría de conjuntos, Introducción a las pruebas de independencia , Estudios en lógica y fundamentos de las matemáticas, 102 , Ámsterdam, Países Bajos: Elsevier.
- ^ En este contexto, ""no significa" establecer diferencia ".
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