El orden visto con diagramas de teoría de categorías
(abuseofnotation.github.io)- Una relación binaria sobre un conjunto de elementos forma una estructura de orden cuando satisface leyes como reflexividad, transitividad y antisimetría
- Un orden lineal es una estructura en la que cualquier par de elementos es comparable; si se elimina la totalidad, se obtiene un orden parcial
- En un orden parcial, la estructura puede entenderse mediante cadenas, elemento máximo y mínimo, join y meet y diagramas de Hasse
- La mezcla de colores, la divisibilidad y la relación de inclusión entre conjuntos son ejemplos de orden parcial, y cuando existen tanto join como meet se forma un lattice
- Un preorder es una estructura con solo reflexividad y transitividad, y todo preorder puede interpretarse como una categoría en la que entre dos objetos hay a lo sumo un morfismo
Orden
- Un orden está compuesto por un conjunto de elementos y una relación binaria sobre ese conjunto, y constituye una estructura matemática cuando satisface ciertas leyes
- Más que el criterio de orden en sí, lo importante es qué propiedades tiene la relación entre los elementos
- Una relación binaria es una relación entre dos elementos de un conjunto, y también puede representarse con flechas
- En teoría de conjuntos, un orden puede expresarse originalmente como un subconjunto del producto cartesiano del conjunto consigo mismo; en programación, como una función que compara dos objetos
- Pero no toda función de comparación ni todo conjunto de pares de elementos define un orden; para producir resultados consistentes sin importar la disposición inicial, se necesitan reglas específicas
Orden lineal
-
Un orden lineal** es un orden en el que todos los elementos tienen una posición entre sí, una estructura en la que** no es ambiguo cuál elemento va antes que otro
- Como ejemplo se presenta el orden de los colores según la longitud de onda de la luz o su disposición en el arcoíris
- Un orden lineal se define como una relación binaria que satisface reflexividad, transitividad, antisimetría y totalidad
- Estas cuatro leyes son las condiciones que constituyen una relación de orden
-
Reflexividad
- Todo elemento debe ser mayor o igual que sí mismo, y para todo $a$ se cumple $a \le a$
- Esta es la regla que trata el caso base; si en cambio se define que un elemento no se relaciona consigo mismo, se forma otro tipo parecido a un strict order
-
Transitividad
- Si $a \le b$ y $b \le c$, entonces debe cumplirse $a \le c$
- Es una ley que determina en gran medida la esencia del orden
-
Antisimetría
- Es la regla que prohíbe resultados de comparación contradictorios: si $x \le y$ y $y \le x$, solo se permite cuando $x = y$
- También se resume diciendo que no se permiten empates entre elementos distintos
-
Totalidad
- Todo par de elementos debe ser comparable, y para cualesquiera dos elementos se cumple $a \le b \lor b \le a$
- Cualesquiera dos elementos deben satisfacer que uno es mayor o igual que el otro
- Como la totalidad incluye el caso en que $a$ y $b$ son iguales, incorpora la reflexividad como caso especial
- Si se elimina la totalidad, se obtiene un orden parcial, y el orden lineal también se escribe como total order
-
El orden de los números naturales
- Los números naturales forman un orden lineal bajo la relación mayor o igual que
- Todo orden lineal finito es isomorfo a un subconjunto de los números naturales al hacer corresponder el primer elemento con 1, el segundo con 2, etc.
- Por lo tanto, todos los órdenes lineales finitos del mismo tamaño son isomorfos entre sí
- También se menciona que, desde la perspectiva de la teoría de categorías, los diagramas de todos los órdenes lineales finitos y de la mayoría de los infinitos se ven igual
Orden parcial
- Un orden parcial es una estructura que resulta de quitar la totalidad a un orden lineal y conservar solo reflexividad, transitividad y antisimetría
- También se usa el nombre partially-ordered set, o poset
- Todo orden lineal es un orden parcial, pero no todo orden parcial es lineal
- El orden parcial también se relaciona con la relación de equivalencia: es una estructura en la que se reemplaza la simetría de esa relación por antisimetría
- En el ejemplo de comparar habilidad futbolística, si solo hay algunas personas comparables directa o indirectamente, puede haber un orden lineal, pero si se incluyen personas que nunca jugaron entre sí, la estructura se vuelve no lineal y forma un orden parcial
- Un orden parcial puede no dar siempre una respuesta concluyente a la pregunta de quién es mejor
-
Cadenas
- Un orden parcial puede estar formado por varios subconjuntos lineales, y a esos subconjuntos lineales se les llama chain
- Como ejemplo se dan dos cadenas: $m \to g \to f$ y $d \to o$
- Las cadenas no tienen que estar completamente separadas; mientras no todas las conexiones se unan una a una hasta formar una sola cadena, se mantiene el orden parcial
- En el ejemplo puede saberse que $d \le g$ y $f \le g$, pero la relación entre $d$ y $f$ queda indeterminada
-
Elemento máximo y mínimo
- Si un elemento $a$ satisface $x \le a$ para todo otro elemento $x$, entonces ese elemento es el greatest element
- Algunos órdenes parciales tienen tal elemento; en el diagrama de ejemplo, $m$ es el greatest element
- Aunque varios elementos sean mayores que todos los demás, si no son idénticos entre sí, no existe un greatest element
- De la misma forma se define el least element
-
Join
- La least upper bound de dos elementos conectados se llama join
- La definición tiene dos condiciones
- Debe cumplirse que $A \le G$ y $B \le G$
- Para cualquier otro elemento $P$ que sea mayor que $A$ y $B$, debe cumplirse $G \le P$
- Si un elemento es mayor que el otro, el join es simplemente el elemento mayor
- En un orden lineal, el join de cualquier par de elementos es el elemento mayor
- Si hay varias cotas superiores del mismo nivel, el join no existe, y el join debe ser único
-
Meet
- Entre los elementos que son menores o iguales que dos elementos dados, el mayor de ellos se llama meet
- Se aplican las mismas reglas que para el join, pero en dirección opuesta
-
Diagramas de Hasse
- Los diagramas usados en esta sección son Hasse diagrams
- Existe la regla adicional de colocar siempre más arriba a los elementos mayores
- Si hay flechas, el punto al que apunta la flecha siempre queda más arriba
- Con esta disposición, basta mirar la relación vertical entre dos puntos para saber si son comparables, y el join también puede identificarse buscando el elemento común conectado que esté más abajo entre los superiores comunes
-
Orden parcial de mezcla de colores
- Se presenta un color-mixing partial order definido de manera que cada color apunte a los colores que lo contienen
- El join de cualesquiera dos colores es el color que resulta de mezclarlos
-
Orden parcial de números por divisibilidad
- Si los números se ordenan no por tamaño sino por divisibilidad, se forma un orden parcial
- Se define que $a$ precede a $b$ si $a$ divide a $b$
- Por ejemplo, como $2 \times 5 = 10$, 2 y 5 preceden a 10, pero 3 no precede a 10
- En este orden, el join es el mínimo común múltiplo y el meet es el máximo común divisor
-
Orden parcial por inclusión
- Cuando hay varios conjuntos que incluyen algunos elementos comunes, puede definirse un inclusion order
- Si el conjunto $a$ incluye a $b$, o dicho de otro modo, si $b$ es subconjunto de $a$, entonces $a$ precede a $b$
- En este caso, el join es la unión y el meet es la intersección
- Si se mezclan los colores contenidos en cada conjunto, se obtiene la misma estructura que en el orden parcial de mezcla de colores visto antes
- El orden de divisibilidad de los números es isomorfo al orden de inclusión de conjuntos de primos o de prime powers con repetición permitida
- Esto puede verificarse por el teorema fundamental de la aritmética, según el cual todo número se expresa de manera exacta y única como producto de números primos
Teorema de representación de Birkhoff
- Tanto el orden parcial de mezcla de colores como el de divisibilidad de números pueden representarse como órdenes de inclusión sobre combinaciones posibles de ciertos elementos básicos
- En el primer caso, los elementos básicos son los colores primarios; en el segundo, los números primos o las potencias primas
- El teorema de representación de Birkhoff determina qué órdenes parciales finitos pueden representarse de este modo
- Hay dos condiciones
- Deben existir join y meet para todo par de elementos
- El join y el meet deben ser distributivos entre sí. Usando la notación $∨$ y $∧$, se tiene $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
- Hay dos condiciones
- Un orden parcial en el que todos los elementos tienen join y meet es un lattice
- Si esas operaciones son distributivas entre sí, se trata de un distributive lattice
- Los elementos “primos” que forman un orden de inclusión son aquellos que no pueden expresarse como join de otros elementos, y se llaman join-irreducible elements
- El teorema también puede enunciarse como que todo distributive lattice es isomorfo al inclusion order de sus join-irreducible elements
- Un orden parcial que no sea distributive lattice también puede ser isomorfo a un inclusion order, pero en ese caso corresponde a un inclusion order que no contiene todas las combinaciones posibles
Retícula
- Un lattice es un orden parcial en el que cualquier par de elementos tiene join y meet
- Todo lattice es un orden parcial, pero no todo orden parcial es un lattice
- Muchos órdenes parciales generados por alguna regla son distributive lattices, y los ejemplos de la sección anterior también lo serían si se dibujaran completos
- En el ejemplo de mezcla de colores se agrega una bola negra arriba y una blanca abajo
- De lo contrario, los tres elementos superiores no tendrían join y los tres inferiores no tendrían meet
-
Retícula acotada
- Un lattice que tiene tanto greatest element como least element se llama bounded lattice
- En la lattice de mezcla de colores, la bola negra es el greatest element y la blanca es el least element
- También se menciona que toda lattice finita es bounded
Isomorfismo de orden
- Un isomorfismo de orden es una función invertible entre los conjuntos subyacentes de dos órdenes que además preserva las flechas del orden
- Tomando como ejemplo el orden de divisibilidad de los números y el orden de inclusión de primos, se compone de dos funciones
- La función que va del orden de inclusión de primos al orden numérico es la multiplicación de los elementos del conjunto
- La función que va del orden numérico al orden de inclusión de primos es la prime factorization que descompone el número en factores
- La condición clave de un isomorfismo de orden es que para dos elementos $a$, $b$, $a \le b$ si y solo si $F(a) \le F(b)$
- A esta clase de función se le llama order-preserving
Preorden
- Un preorder es una estructura que resulta de quitar la antisimetría a un orden lineal y conservar solo reflexividad y transitividad
- Si se mira desde el criterio de comparabilidad
- En un orden lineal, $a \le b$ o $b \le a$
- En un orden parcial, puede ocurrir una de las dos o ninguna
- En un preorden, puede ocurrir una de las dos, ninguna, o ambas a la vez
- El preorden difiere del sentido cotidiano de orden, y puede haber una flecha desde cualquier punto hacia otro
- Se presenta el ejemplo del fútbol modelado como “quién le ganó a quién”, incluyendo también las victorias indirectas
- Por la transitividad, las victorias indirectas también se agregan como relaciones directas, y como resultado, si hay relaciones cíclicas, se forma una estructura en la que varios objetos quedan todos conectados entre sí
-
Preorden y relación de equivalencia
- El preorden es una estructura intermedia entre orden parcial y relación de equivalencia
- Esto se debe a que solo falta el punto en que difieren, la (anti)simetría
- Dentro de un preorden, los elementos conectados en ambos sentidos satisfacen simetría, por lo que forman una relación de equivalencia
- Al agrupar esos elementos, se forman las equivalence classes del preorden
- Si luego se trasladan solo las conexiones entre esas clases de equivalencia, dichas conexiones satisfacen antisimetría y forman un orden parcial
- Por lo tanto, para todo preorden puede definirse el orden parcial sobre las clases de equivalencia de ese preorden
Preorden y categoría
- La transitividad de un preorden es la regla por la que si existen $a \le b$ y $b \le c$, entonces aparece $a \le c$, y puede interpretarse como composición de relaciones
- La definición de categoría incluye las dos condiciones siguientes
- Existe un morfismo identidad para cada objeto
- Se pueden componer dos morfismos adecuados, y esa composición debe ser asociativa
- En un preorden, la transitividad cumple el papel de la composición, y la reflexividad cumple el papel del morfismo identidad
- Por lo tanto, todo preorden es una categoría
- En una categoría general puede haber varios morfismos entre dos objetos, pero en un preorden entre dos objetos cualesquiera existe a lo sumo un morfismo
- O bien existe $a \le b$, o no existe
- Así como un monoide es una categoría con un solo objeto, un orden puede describirse como una categoría con a lo sumo un morfismo entre dos objetos
- Debido a esta propiedad, en un preorden todo diagrama conmuta
-
Propiedades categóricas de órdenes parciales y preórdenes
- Tanto los órdenes parciales como los preórdenes son casos especiales de preorden, por lo que también son categorías
- En teoría de categorías, los preórdenes se mencionan como skeletal categories, categorías en las que no coexisten objetos isomorfos distinguidos entre sí
-
Producto y coproducto
- La definición de coproduct en una categoría consiste en dos morfismos $A \to A + B$, $B \to A + B$ y una propiedad universal
- Tiene exactamente la misma forma que la definición de join en un orden
- En un orden, como todos los morfismos son únicos, “ser más grande” corresponde a “existir un morfismo único”
- Por lo tanto, en la categoría de un preorden, el coproduct categórico es el join
- Por dualidad, el product corresponde al meet
-
Definición formal
- En teoría de categorías, las categorías que, como los órdenes, tienen a lo sumo un morfismo entre dos objetos se llaman thin categories
- Todo preorden puede verse como una thin category y, a la inversa, una categoría de ese tipo puede interpretarse como un preorden
- Las thin categories se usan para explorar el concepto de categoría en un contexto más fácil de entender que una categoría general
- Entender meet y join también ayuda a comprender los conceptos más generales de product y coproduct
- También son un marco útil cuando no interesa la diferencia entre varios morfismos entre objetos y solo se necesita una estructura simple
1 comentarios
Comentarios en Hacker News
[1, 3, 2].sort((a, b) => { if (a > b) { return true } else { return false } })no es un comparator válido. La API espera un negativo, 0 o un positivo, pero ahí se devuelve un boolean, y en mi Chrome el resultado siguió siendo[1, 3, 2]. A mí me pareció que la precisión matemática del artículo estaba más o menos al mismo nivel, y dejé observaciones más detalladas en este comentario<=. Claro que hace falta bastante práctica para acostumbrarse, pero justamente al llevar estas ideas una y otra vez a tareas cotidianas, se van volviendo familiares. Entonces empiezas a mirar tests y pensar cosas como: "esta condición se puede modelar con cierto preorder"