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 . |
Una celosía es una estructura abstracta estudiada en las subdisciplinas matemáticas de la teoría de órdenes y el álgebra abstracta . Consiste en un conjunto parcialmente ordenado en el que cada dos elementos tienen un supremum único (también llamado límite superior mínimo o unión ) y un infimum único (también llamado límite inferior mayor o encuentro ). Un ejemplo lo dan los números naturales , parcialmente ordenados por divisibilidad , para los cuales el único supremo es el mínimo común múltiplo y el único mínimo es el máximo común divisor .
Las celosías también se pueden caracterizar como estructuras algebraicas que satisfacen ciertas identidades axiomáticas . Dado que las dos definiciones son equivalentes, la teoría de la celosía se basa tanto en la teoría de órdenes como en el álgebra universal . Las semirrejillas incluyen rejillas, que a su vez incluyen las álgebras de Heyting y Boolean . Todas estas estructuras "enrejadas" admiten descripciones tanto teóricas como algebraicas.
Celosías como conjuntos parcialmente ordenados
Si ( L , ≤) es un conjunto parcialmente ordenado (poset), y S ⊆ L es un subconjunto arbitrario, a continuación, un elemento u ∈ L se dice que es un límite superior de S si s ≤ U para cada s ∈ S . Un conjunto puede tener muchos límites superiores o ninguno. Un límite superior u de S se dice que es su extremo superior , o se unen a , o supremo , si u ≤ x para cada límite superior x de S . Un conjunto no necesita tener un límite superior mínimo, pero no puede tener más de uno. Dually , l ∈ L se dice que es un límite inferior de S si l ≤ s para cada s ∈ S . Un límite inferior l de S se dice que es su extremo inferior , o se encuentran , o infimum , si x ≤ l para cada límite inferior x de S . Un conjunto puede tener muchos límites inferiores, o ninguno en absoluto, pero puede tener como máximo un límite inferior máximo.
Un conjunto parcialmente ordenado ( L , ≤) se llama un semirretículo de unión si cada subconjunto de dos elementos { a , b } ⊆ L tiene una unión (es decir, el límite superior mínimo), y se llama semirretículo de encuentro si cada dos elementos subconjunto tiene un conocer (es decir, extremo inferior), denotado por una ∨ b y un ∧ b respectivamente. ( L , ≤) se llama celosía si es a la vez un semirreticulado de unión y de encuentro. Esta definición hace operaciones binarias ∨ y ∧ . Ambas operaciones son monótonas con respecto al orden dado: a 1 ≤ a 2 y b 1 ≤ b 2 implica que a 1 ∨ b 1 ≤ a 2 ∨ b 2 y a 1 ∧ b 1 ≤ a 2 ∧ b 2 .
Se sigue, mediante un argumento de inducción, que todo subconjunto finito no vacío de una celosía tiene un límite superior mínimo y un límite inferior máximo. Con supuestos adicionales, es posible que se obtengan más conclusiones; consulte Integridad (teoría del orden) para obtener más información sobre este tema. Ese artículo también analiza cómo se puede reformular la definición anterior en términos de la existencia de conexiones de Galois adecuadas entre conjuntos relacionados parcialmente ordenados, un enfoque de especial interés para el enfoque teórico de categorías de las celosías y para el análisis formal de conceptos .
Una celosía acotada es una celosía que además tiene un elemento mayor (también llamado elemento máximo o superior , y denotado por 1, o por) y un elemento mínimo (también llamado mínimo , o fondo , denotado por 0 o por), que satisfacen
- 0 ≤ x ≤ 1 para cada x en L .
Cada enrejado se puede incrustar en un enrejado acotado agregando un elemento artificial mayor y menor, y cada enrejado finito no vacío está acotado, tomando la unión (respectivamente, encuentro) de todos los elementos, denotado por (respectivamente ) dónde .
Un conjunto parcialmente ordenado es una celosía acotada si y solo si cada conjunto finito de elementos (incluido el conjunto vacío) tiene una unión y una reunión. Para cada elemento x de un poset, es trivialmente cierto (es una verdad vacía ) que y , y por lo tanto, cada elemento de un poset es tanto un límite superior como un límite inferior del conjunto vacío. Esto implica que la unión de un conjunto vacío es el elemento mínimo, y el encuentro del conjunto vacío es el elemento más grande . Esto es consistente con la asociatividad y conmutatividad de meet and join: la unión de una unión de conjuntos finitos es igual a la unión de las uniones de los conjuntos, y dualmente, la unión de una unión de conjuntos finitos es igual a la unión de los encuentros de los conjuntos, es decir, para los subconjuntos finitos A y B de un poset L ,
y
mantener. Tomando B como el conjunto vacío,
y
lo cual es consistente con el hecho de que .
Se dice que un elemento de celosía y cubre otro elemento x , si y > x , pero no existe una z tal que y > z > x . Aquí, y > x significa x ≤ y y x ≠ y .
Una celosía ( L , ≤) se llama graduada , a veces clasificada (pero consulte la columna clasificada para obtener un significado alternativo), si se puede equipar con una función de rango r de L a ℕ, a veces a ℤ, compatible con el orden (por lo que r ( x ) < r ( y ) siempre que x < y ) tal que siempre que y cubra x , entonces r ( y ) = r ( x ) + 1 . El valor de la función de rango para un elemento de celosía se llama rango .
Dado un subconjunto de un enrejado, H ⊆ L , se encuentran y se unen restringen a funciones parciales - se indefinido si su valor no está en el subconjunto H . La estructura resultante en H se llamacelosía parcial . Además de esta definición extrínseca como un subconjunto de alguna otra estructura algebraica (una red), una red parcial también se puede definir intrínsecamente como un conjunto con dos operaciones binarias parciales que satisfacen ciertos axiomas. [1]
Celosías como estructuras algebraicas
Celosía general
Una estructura algebraica , que consta de un conjunto y dos operaciones binarias, conmutativas y asociativas , y , en es una celosía si las siguientes identidades axiomáticas son válidas para todos los elementos, a veces llamadas leyes de absorción .
Las siguientes dos identidades también se suelen considerar axiomas, aunque se derivan de las dos leyes de absorción tomadas en conjunto. [nota 1] Esas se llaman leyes idempotentes .
Estos axiomas afirman que tanto y son semirreduras . Las leyes de absorción, los únicos axiomas anteriores en los que ambos se encuentran y se unen aparecen, distinguen un retículo de un par arbitrario de estructuras de semirretículo y aseguran que los dos semirreticulos interactúen apropiadamente. En particular, cada semirreticulado es el dual del otro.
Celosía acotada
Una celosía acotada es una estructura algebraica de la forma tal que es una celosía, (la parte inferior de la celosía) es el elemento de identidad para la operación de unión, y (la parte superior de la celosía) es el elemento de identidad para la operación de encuentro .
Ver semirrejilla para más detalles.
Conexión con otras estructuras algebraicas
Las celosías tienen algunas conexiones con la familia de estructuras algebraicas de tipo grupal . Debido a que se reúnen y se unen tanto para conmutar como para asociar, un enrejado puede verse como si consta de dos semigrupos conmutativos que tienen el mismo dominio. Para una red acotada, estos semigrupos son de hecho monoides conmutativos . La ley de absorción es la única identidad definitoria que es peculiar de la teoría de la red.
Por conmutatividad, asociatividad e idempotencia uno puede pensar en unirse y reunirse como operaciones sobre conjuntos finitos no vacíos, en lugar de sobre pares de elementos. En una celosía acotada, la unión y el encuentro del conjunto vacío también se pueden definir (como y , respectivamente). Esto hace que las celosías delimitadas sean algo más naturales que las celosías generales, y muchos autores requieren que todas las celosías estén delimitadas.
La interpretación algebraica de celosías juega un papel esencial en el álgebra universal .
Conexión entre las dos definiciones
Un retículo de la teoría del orden da lugar a las dos operaciones binarias ∨ y ∧. Dado que las leyes conmutativa, asociativa y de absorción se pueden verificar fácilmente para estas operaciones, convierten ( L , ∨, ∧) en una red en el sentido algebraico.
Lo contrario también es cierto. Dada una retícula definida algebraicamente ( L , ∨, ∧) , se puede definir un orden parcial ≤ en L estableciendo
- a ≤ b si a = a ∧ b , o
- a ≤ b si b = a ∨ b ,
para todos los elementos a y b de L . Las leyes de absorción aseguran que ambas definiciones sean equivalentes:
a = a ∧ b implica b = b ∨ ( b ∧ a ) = ( a ∧ b ) ∨ b = a ∨ b
y doblemente para la otra dirección.
Ahora se puede comprobar que la relación ≤ introducida de esta manera define un ordenamiento parcial dentro del cual los encuentros binarios y las uniones se dan a través de las operaciones originales ∨ y ∧.
Dado que las dos definiciones de una celosía son equivalentes, uno puede invocar libremente aspectos de cualquiera de las definiciones de cualquier manera que se adapte al propósito en cuestión.
Ejemplos de
Foto. 1: Subconjuntos de {x, y, z}, bajo inclusión de conjuntos . El nombre "celosía" es sugerido por la forma del diagrama de Hasse que lo representa.
Foto. 2: Celosía de divisores enteros de 60, ordenados por " divide ".
Foto. 3: Celosía de particiones de {1, 2, 3, 4}, ordenadas por " refina ".
Foto. 4: Celosía de enteros positivos, ordenados por ≤.
Foto. 5: Celosía de pares de enteros no negativos, ordenados por componentes.
- Para cualquier conjunto A , la colección de todos los subconjuntos de A (llamado el conjunto de potencias de A ) se puede ordenar mediante la inclusión de subconjuntos para obtener una red delimitada por A y el conjunto vacío. Establecer intersección y unión interpretar encuentro y unión, respectivamente (ver Imagen 1).
- Para cualquier conjunto A , la colección de todos los subconjuntos finitos de A , ordenados por inclusión, es también una red y estará acotada si y solo si A es finito.
- Para cualquier conjunto A , la colección de todas las particiones de A , ordenadas por refinamiento , es una celosía (ver Figura 3).
- Los enteros positivos en su orden habitual forman una celosía, bajo las operaciones de "min" y "max". 1 es la parte inferior; no hay techo (ver Imagen 4).
- El cuadrado cartesiano de los números naturales, ordenados de modo que ( a , b ) ≤ ( c , d ) si un ≤ c y b ≤ d . El par (0, 0) es el elemento inferior; no hay techo (ver Imagen 5).
- Los números naturales también forman un retículo bajo las operaciones de tomar el máximo común divisor y el mínimo común múltiplo , con divisibilidad como relación de orden: a ≤ b si a divide b . 1 es la parte inferior; 0 es superior. Foto. 2 muestra una subred finita.
- Cada celosía completa (ver también más abajo ) es una celosía acotada (bastante específica). Esta clase da lugar a una amplia gama de ejemplos prácticos .
- El conjunto de elementos compactos de una celosía aritmética completa es una celosía con un elemento mínimo, donde las operaciones de la celosía se dan restringiendo las operaciones respectivas de la celosía aritmética. Ésta es la propiedad específica que distingue las celosías aritméticas de las celosías algebraicas , para las cuales los compactos solo forman una semirrejilla de unión . Ambas clases de celosías completas se estudian en teoría de dominios .
Se dan más ejemplos de celosías para cada una de las propiedades adicionales que se describen a continuación.
Ejemplos de no celosías
La mayoría de los conjuntos parcialmente ordenados no son celosías, incluidos los siguientes.
- Un poset discreto, es decir, un poset tal que x ≤ y implica x = y , es una celosía si y solo si tiene como máximo un elemento. En particular, el poset discreto de dos elementos no es una celosía.
- Aunque el conjunto {1, 2, 3, 6} parcialmente ordenado por divisibilidad es un retículo, el conjunto {1, 2, 3} así ordenado no es un retículo porque el par 2, 3 carece de unión; de manera similar, 2, 3 carece de un encuentro en {2, 3, 6}.
- El conjunto {1, 2, 3, 12, 18, 36} parcialmente ordenado por divisibilidad no es una celosía. Cada par de elementos tiene un límite superior y un límite inferior, pero el par 2, 3 tiene tres límites superiores, a saber, 12, 18 y 36, ninguno de los cuales es el menor de los tres bajo divisibilidad (12 y 18 no dividen El uno al otro). Del mismo modo, el par 12, 18 tiene tres límites inferiores, a saber, 1, 2 y 3, ninguno de los cuales es el mayor de los tres bajo divisibilidad (2 y 3 no se dividen entre sí).
Morfismos de celosías
La noción apropiada de un morfismo entre dos celosías fluye fácilmente de la definición algebraica anterior . Dadas dos celosías ( L , ∨ L , ∧ L ) y ( M , ∨ M , ∧ M ) , un homomorfismo de celosía de L a M es una función f : L → M tal que para todo a , b ∈ L :
- f ( a ∨ L b ) = f ( a ) ∨ M f ( b ), y
- f ( una ∧ L segundo ) = f ( una ) ∧ M f ( segundo ).
Por tanto, f es un homomorfismo de las dos semirretículas subyacentes . Cuando se consideran celosías con más estructura, los morfismos también deben "respetar" la estructura extra. En particular, un homomorfismo de celosía acotada (generalmente llamado simplemente "homomorfismo de celosía") f entre dos celosías limitadas L y M también debería tener la siguiente propiedad:
- f (0 L ) = 0 M , y
- f (1 L ) = 1 M .
En la formulación de la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de celosías es una función que conserva los encuentros y uniones binarios. Para celosías delimitadas, la preservación de los elementos menores y mayores es solo la preservación de la unión y el encuentro del conjunto vacío.
Cualquier homomorfismo de celosías es necesariamente monótono con respecto a la relación de ordenación asociada; consulte Función de conservación de límites . Lo contrario no es cierto: la monotonicidad de ninguna manera implica la preservación requerida de los encuentros y uniones (ver Fig. 9), aunque una biyección que preserva el orden es un homomorfismo si su inversa también preserva el orden.
Dada la definición estándar de isomorfismos como morfismos invertibles, un isomorfismo reticular es solo un homomorfismo reticular biyectivo . De manera similar, un endomorfismo reticular es un homomorfismo reticular de un reticulado a sí mismo, y un automorfismo reticular es un endomorfismo reticular biyectivo. Las celosías y sus homomorfismos forman una categoría .
Dejar y ser dos celosías con 0 y 1 . Un homomorfismo de a se llama 0,1 - separando iff (separa 0 ) y ( separa 1).
Subrejillas
Una subred de un entramado L es un subconjunto de L que es un enrejado con el mismo se encuentran y se unen a las operaciones como L . Es decir, si L es un enrejado y M es un subconjunto de L tal que para cada par de elementos a , b en M tanto un ∧ b y una ∨ b están en M , entonces M es una subred de L . [2]
Una subred M de un entramado L es una subred convexa de L , si x ≤ z ≤ y y x , y en M implica que z pertenece a M , para todos los elementos x , y , z en L .
Propiedades de las celosías
A continuación, presentamos una serie de propiedades importantes que conducen a interesantes clases especiales de celosías. Uno, la delimitación, ya se ha discutido.
Lo completo
Un poset se llama celosía completa si todos sus subconjuntos tienen tanto una combinación como una reunión. En particular, cada celosía completa es una celosía acotada. Si bien los homomorfismos de celosía acotada en general conservan solo uniones y encuentros finitos, se requieren homomorfismos de celosía completos para preservar uniones y encuentros arbitrarios.
Cada poset que es una semirrejilla completa es también una celosía completa. Relacionado con este resultado está el interesante fenómeno de que existen varias nociones de homomorfismo en competencia para esta clase de posets, dependiendo de si se ven como retículas completas, semirretículas de unión completas, semirreticulaciones de reunión completas, o como unión-completa o reunión- celosías completas.
Tenga en cuenta que "celosía parcial" no es lo contrario de "celosía completa", sino que "celosía parcial", "celosía" y "celosía completa" son definiciones cada vez más restrictivas.
Completitud condicional
Una celosía condicionalmente completa es una celosía en la que cada subconjunto no vacío que tiene un límite superior tiene una unión (es decir, un límite superior mínimo). Tales celosías proporcionan la generalización más directa del axioma de completitud de los números reales . Una celosía condicionalmente completa es una celosía completa o una celosía completa sin su elemento máximo 1, su elemento mínimo 0 o ambos.
Distributividad
Dado que las celosías vienen con dos operaciones binarias, es natural preguntarse si una de ellas se distribuye sobre la otra, es decir, si una u otra de las siguientes leyes duales se cumple para cada tres elementos a , b , c de L :
- Distributividad de ∨ sobre ∧
- una ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( una ∨ c ).
- Distributividad de ∧ sobre ∨
- un ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( una ∧ c ).
Una red que satisface el primero o, de manera equivalente (como resulta), el segundo axioma, se llama red distributiva . Las únicas celosías no distributivas con menos de 6 elementos se denominan M 3 y N 5 ; [3] se muestran en las imágenes 10 y 11, respectivamente. Una red es distributiva si y solo si no tiene una subred isomorfa a M 3 o N 5 . [4] Cada red distributiva es isomorfa a una red de conjuntos (con unión e intersección como unión y encuentro, respectivamente). [5]
Para obtener una descripción general de las nociones más sólidas de distributividad que son apropiadas para celosías completas y que se utilizan para definir clases más especiales de celosías, como marcos y celosías completamente distributivas , consulte distributividad en teoría de órdenes .
Modularidad
Para algunas aplicaciones, la condición de distributividad es demasiado fuerte y la siguiente propiedad más débil suele ser útil. Una celosía ( L , ∨, ∧) es modular si, para todos los elementos a , b , c de L , se cumple la siguiente identidad.
- Identidad modular
- ( Una ∧ c ) ∨ ( b ∧ c ) = (( una ∧ c ) ∨ b ) ∧ c .
Esta condición es equivalente al siguiente axioma.
- Ley modular
- a ≤ c implica a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ c .
Una celosía es modular si y solo si no tiene una subred isomorfa a N 5 (se muestra en la Imagen 11). [4] Además de las celosías distributivas, ejemplos de celosías modulares son la celosía de ideales de dos lados de un anillo , la celosía de submódulos de un módulo y la celosía de subgrupos normales de un grupo . El conjunto de términos de primer orden con el ordenamiento " es más específico que " es un enrejado no modular utilizado en el razonamiento automatizado .
Semimodularidad
Una celosía finita es modular si y solo si es semimodular superior e inferior . Para una celosía graduada, la semimodularidad (superior) es equivalente a la siguiente condición en la función de rango r :
- r ( x ) + r ( y ) ≥ r ( x ∧ y ) + r ( x ∨ y ).
Otra condición equivalente (para celosías graduadas) es la condición de Birkhoff :
- para cada x y y en L , si x y y tanto la cubierta x ∧ y , a continuación, x ∨ Y cubiertas tanto x y y .
Una celosía se llama semimodular inferior si su dual es semimodular. Para las celosías finitas, esto significa que las condiciones anteriores se mantienen con ∨ y ∧ intercambiados, "cubiertas" intercambiadas con "está cubierto por" y las desigualdades se invierten. [6]
Continuidad y algebraicidad
En la teoría de dominios , es natural buscar aproximar los elementos en un orden parcial mediante elementos "mucho más simples". Esto conduce a la clase de posets continuos , que consisten en posets donde cada elemento puede obtenerse como el supremo de un conjunto dirigido de elementos que están muy por debajo del elemento. Si se pueden restringir adicionalmente estos a los elementos compactos de un poset para obtener estos conjuntos dirigidos, entonces el poset es incluso algebraico . Ambos conceptos se pueden aplicar a las celosías de la siguiente manera:
- Una celosía continua es una celosía completa que es continua como un poset.
- Una celosía algebraica es una celosía completa que es algebraica como un poset.
Ambas clases tienen propiedades interesantes. Por ejemplo, las celosías continuas se pueden caracterizar como estructuras algebraicas (con operaciones infinitas) que satisfacen ciertas identidades. Si bien no se conoce tal caracterización para las redes algebraicas, se pueden describir "sintácticamente" a través de los sistemas de información de Scott .
Complementos y pseudo-complementos
Deje que L sea un enrejado limitado con el elemento más grande 1 y menos elemento 0. Dos elementos x y y de L son complementos el uno del otro si y sólo si:
- x ∨ y = 1 y x ∧ y = 0 .
En general, algunos elementos de una celosía acotada pueden no tener un complemento y otros pueden tener más de un complemento. Por ejemplo, el conjunto {0, ½, 1} con su orden habitual es una celosía acotada y ½ no tiene complemento. En la red acotada N 5 , el elemento a tiene dos complementos, a saber. b y c (ver. Pico 11). Una celosía acotada para la cual cada elemento tiene un complemento se llama celosía complementada .
Un enrejado complementado que también es distributivo es un álgebra de Boole . Para una red distributiva, el complemento de x , cuando existe, es único.
En el caso de que el complemento sea único, escribimos ¬ x = y y, de manera equivalente, ¬ y = x . La correspondiente operación unaria sobre L , llamada complementación, introduce un análogo de la negación lógica en la teoría de la red.
Las álgebras de Heyting son un ejemplo de retículas distributivas donde algunos miembros pueden carecer de complementos. Todo elemento x de un álgebra de Heyting tiene, por otro lado, un pseudocomplemento , también denotado ¬ x . El pseudocomplemento es el elemento más grande y tal que x ∧ y = 0 . Si el pseudo-complemento de cada elemento de un álgebra de Heyting es de hecho un complemento, entonces el álgebra de Heyting es de hecho un álgebra booleana.
Estado de la cadena Jordan-Dedekind
Una cadena de x 0 a x n es un conjunto, dónde . La longitud de esta cadena es n , o uno menos que su número de elementos. Una cadena es máxima si x i cubre x i −1 para todo 1 ≤ i ≤ n .
Si por cualquier par, x y y , donde x < y , todas las cadenas maximales de x a y tienen la misma longitud, entonces el enrejado se dice para satisfacer la condición de cadena Jordan-Dedekind .
Celosías libres
Se puede usar cualquier conjunto X para generar el FX de semirretículo libre . La semirrejilla libre se define como formada por todos los subconjuntos finitos de X , con la operación de semirrejilla dada por la unión de conjuntos ordinarios . La semirrejilla libre tiene la propiedad universal . Para el enrejado libre sobre un conjunto X , Whitman dio una construcción basada en polinomios sobre los miembros de X. [7] [8]
Nociones importantes de la teoría de la celosía
Ahora definimos algunas nociones de la teoría del orden de importancia para la teoría de la red. A continuación, dejar que x sea un elemento de algunos de celosía L . Si L tiene un elemento inferior 0, a veces se requiere x ≠ 0 . x se llama:
- Únete irreductible si x = un ∨ b implica x = una o x = b para todos un , b en L . Cuando la primera condición se generaliza a combinaciones arbitrarias, x se llama unir completamente irreducible (o ∨-irreducible). La noción dual es irreductibilidad de encuentro (∧-irreducible). Por ejemplo, en Pic. 2, los elementos 2, 3, 4 y 5 son irreductibles, mientras que 12, 15, 20 y 30 son irreductibles. En el entramado de números reales con el orden habitual, cada elemento se une irreductible, pero ninguno es completamente irreductible.
- Únase a primo si x ≤ a ∨ b implica x ≤ a o x ≤ b . Esto también se puede generalizar para obtener la noción de unir completamente primo . La noción dual es primordial . Cada elemento de unión-primo también es irreducible, y cada elemento de reunión-primo también es irreducible. Lo contrario se cumple si L es distributivo.
Sea L un elemento inferior 0. Un elemento x de L es un átomo si 0 < x y no existe un elemento y de L tal que 0 < y < x . Entonces L se llama:
- Atómico si para cada elemento x distinto de cero de L , existe un átomo a de L tal que a ≤ x ;
- Atomista si cada elemento de L es un supremo de átomos.
Las nociones de ideales y la noción dual de filtros se refieren a tipos particulares de subconjuntos de un conjunto parcialmente ordenado y, por lo tanto, son importantes para la teoría de la red. Los detalles se pueden encontrar en las entradas respectivas.
Ver también
- Únete y conoce
- Mapa de celosías
- Celosía ortocomplementada
- Orden total
- Ideal y filtro (nociones duales)
- Skew lattice (generalización para unirse y reunirse no conmutativos)
- Celosía euleriana
- Celosía de publicación
- Celosía Tamari
- Celosía Young – Fibonacci
- Celosía 0,1-simple
Aplicaciones que utilizan la teoría de celosía
Tenga en cuenta que en muchas aplicaciones los conjuntos son solo celosías parciales: no todos los pares de elementos tienen un encuentro o unión.
- Topología sin sentido
- Celosía de subgrupos
- Espacio espectral
- Subespacio invariante
- Operador de cierre
- Interpretación abstracta
- Celosía de subsunción
- Teoría de conjuntos difusos
- Algebraizaciones de lógica de primer orden
- Semántica de lenguajes de programación
- Teoría del dominio
- Ontología (informática)
- Herencia múltiple
- Análisis de conceptos formales y Lattice Miner (teoría y herramienta)
- Filtro de floración
- Flujo de información
- Optimización ordinal
- Lógica cuántica
- Gráfico de mediana
- Espacio de conocimiento
- Aprendizaje regular de idiomas
- Modelado analógico
Notas
- ^ a ∨ a = a ∨ ( a ∧ ( a ∨ a )) = a , y doblemente para la otra ley idempotente. Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler", Braunschweiger Festschrift : 1–40.
Referencias
- ↑ Grätzer , 1996 , p. 52 .
- ^ Burris, Stanley N. y Sankappanavar, HP, 1981. Un curso de álgebra universal . Springer-Verlag. ISBN 3-540-90578-2 .
- ^ Davey y Priestley (2002) , Ejercicio 4.1, p. 104 .
- ↑ a b Davey y Priestley (2002) , Teorema 4.10, p. 89 .
- ^ Davey y Priestley (2002) , Teorema 10.21, págs. 238-239 .
- ^ Stanley, Richard P , Combinatoria enumerativa (vol. 1) , Cambridge University Press, págs. 103-104, ISBN 0-521-66351-2
- ^ Philip Whitman (1941). "Celosías libres I". Annals of Mathematics . 42 : 325–329. doi : 10.2307 / 1969001 .
- ^ Philip Whitman (1942). "Celosías libres II". Annals of Mathematics . 43 : 104-115. doi : 10.2307 / 1968883 .
Monografías disponibles gratis en línea:
- Burris, Stanley N. y Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN 3-540-90578-2 .
- Jipsen, Peter y Henry Rose, Varieties of Lattices , Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN 0-387-56314-8 .
- Nación, JB, Notas sobre la teoría de celosía . Capítulos 1-6. Capítulos 7-12; Apéndices 1–3.
Textos elementales recomendados para personas con madurez matemática limitada :
- Donnellan, Thomas, 1968. Lattice Theory . Pergamon.
- Grätzer, George , 1971. Teoría de la celosía: Primeros conceptos y celosías distributivas . WH Freeman.
El texto introductorio contemporáneo estándar, algo más difícil que el anterior:
- Davey, BA; Priestley, HA (2002), Introducción a las celosías y el orden , Cambridge University Press , ISBN 978-0-521-78451-1
Monografías avanzadas:
- Garrett Birkhoff , 1967. Lattice Theory , 3ª ed. Vol. 25 de Publicaciones del Coloquio AMS. Sociedad Matemática Estadounidense .
- Robert P. Dilworth y Crawley, Peter, 1973. Teoría algebraica de celosías . Prentice Hall. ISBN 978-0-13-022269-5 .
- Grätzer, George (1996) [1978]. Teoría general de la celosía (Segunda ed.). Basilea: Birkhäuser. ISBN 978-3-7643-6996-5.
En celosías libres:
- R. Freese, J. Jezek y JB Nation, 1985. "Free Lattices". Encuestas y monografías matemáticas Vol. 42. Asociación Matemática de América .
- Johnstone, PT , 1982. Espacios de piedra . Estudios de Cambridge en Matemáticas Avanzadas 3. Cambridge University Press.
Sobre la historia de la teoría de la celosía:
- Štĕpánka Bilová (2001). Eduard Fuchs (ed.). Teoría de la celosía: su nacimiento y vida (PDF) . Prometeo. págs. 250-257.
Sobre las aplicaciones de la teoría de la celosía:
- Garrett Birkhoff (1967). James C. Abbot (ed.). ¿Qué puede hacer Lattices por ti? . Van Nostrand. Tabla de contenido
enlaces externos
- "Grupo ordenado en celosía" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Weisstein, Eric W. "Lattice" . MathWorld .
- JB Nation, Notes on Lattice Theory , notas inéditas del curso disponibles en dos archivos PDF.
- Ralph Freese, "Página de inicio de la teoría de celosía" .
- Secuencia OEIS A006966 (Número de celosías sin etiquetar con n elementos)