stringtranslate.com

Enrejado (orden)

Un retículo es una estructura abstracta estudiada en las subdisciplinas matemáticas de la teoría del orden y el álgebra abstracta . Consiste en un conjunto parcialmente ordenado en el que cada par de elementos tiene un supremo único (también llamado límite inferior mínimo o unión ) y un ínfimo único (también llamado límite inferior máximo o encuentro ). Un ejemplo lo da el conjunto potencia de un conjunto, parcialmente ordenado por inclusión , para el que el supremo es la unión y el ínfimo es la intersección . Otro ejemplo lo dan los números naturales , parcialmente ordenados por divisibilidad , para los que el supremo es el mínimo común múltiplo y el ínfimo es el máximo común divisor .

Las retículas también pueden caracterizarse como estructuras algebraicas que satisfacen ciertas identidades axiomáticas . Dado que las dos definiciones son equivalentes, la teoría de retículas se basa tanto en la teoría del orden como en el álgebra universal . Las semirretículas incluyen retículas, que a su vez incluyen las álgebras de Heyting y de Boole . Todas estas estructuras de tipo retícula admiten descripciones tanto teóricas del orden como algebraicas.

El subcampo del álgebra abstracta que estudia los retículos se llama teoría de retículos .

Definición

Una red puede definirse desde el punto de vista teórico como un conjunto parcialmente ordenado o como una estructura algebraica.

Como conjunto parcialmente ordenado

Un conjunto parcialmente ordenado (poset) se denomina retículo si es a la vez un semirretículo de unión y de encuentro , es decir, cada subconjunto de dos elementos tiene un semirretículo de unión (es decir, el límite superior mínimo, denotado por ) y dualmente un encuentro (es decir, el límite inferior máximo, denotado por ). Esta definición hace que y operaciones binarias . Ambas operaciones son monótonas con respecto al orden dado: y implica que y

De ello se deduce, mediante un argumento de inducción , que todo subconjunto finito no vacío de una red tiene un límite superior mínimo y un límite inferior máximo. Con suposiciones adicionales, pueden ser posibles otras conclusiones; véase Completitud (teoría del orden) para una discusión más amplia de 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 parcialmente ordenados relacionados, un enfoque de especial interés para el enfoque de la teoría de categorías de las redes y para el análisis de conceptos formales .

Dado un subconjunto de una red, las funciones de encuentro y unión se restringen a funciones parciales ; no están definidas si su valor no está en el subconjunto. La estructura resultante se denominared parcial . Además de esta definición extrínseca como un subconjunto de alguna otra estructura algebraica (una red), una red parcial también puede definirse intrínsecamente como un conjunto con dos operaciones binarias parciales que satisfacen ciertos axiomas.[1]

Como estructura algebraica

Una red es una estructura algebraica , que consta de un conjunto y dos operaciones binarias, conmutativas y asociativas y que satisface las siguientes identidades axiomáticas para todos los elementos (a veces llamadas leyes de absorción ):

Las dos identidades siguientes también suelen considerarse axiomas, aunque se deduzcan de las dos leyes de absorción tomadas en conjunto. [2] Éstas se denominan leyes idempotentes .

Estos axiomas afirman que tanto y son semirretículos . Las leyes de absorción, los únicos axiomas anteriores en los que aparecen tanto el encuentro como la unión, distinguen un retículo de un par arbitrario de estructuras de semirretículos y aseguran que los dos semirretículos interactúan apropiadamente. En particular, cada semirretículo es el dual del otro. Las leyes de absorción pueden verse como un requisito de que los semirretículos de encuentro y unión definan el mismo orden parcial .

Conexión entre las dos definiciones

Una red de teoría de 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, forman una red en el sentido algebraico.

El recíproco también es cierto. Dada una red definida algebraicamente, se puede definir un orden parcial en estableciendo para todos los elementos Las leyes de absorción garantizan que ambas definiciones sean equivalentes: y dualmente para la otra dirección.

Ahora se puede comprobar que la relación introducida de esta manera define un ordenamiento parcial dentro del cual se dan encuentros y uniones binarias a través de las operaciones originales y

Dado que las dos definiciones de red son equivalentes, uno puede invocar libremente aspectos de cualquiera de las definiciones de cualquier manera que se ajuste al propósito en cuestión.

Red limitada

Una red acotada es una red que además tiene un elemento mayor (también llamado máximo o elemento superior , y denotado por o por ) y un elemento menor (también llamado mínimo o inferior , denotado por o por ), que satisfacen

Una red acotada también puede definirse como una estructura algebraica de la forma tal que es una red, (la parte inferior de la red) es el elemento identidad para la operación de unión y (la parte superior de la red) es el elemento identidad para la operación de encuentro.

Un conjunto parcialmente ordenado es una red acotada si y solo si cada conjunto finito de elementos (incluido el conjunto vacío) tiene una unión y un encuentro. Para cada elemento de un conjunto parcial es vacuamente cierto que y y por lo tanto cada elemento de un conjunto parcial 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 menor y el encuentro del conjunto vacío es el elemento mayor Esto es consistente con la asociatividad y conmutatividad de encuentro y unión: la unión de una unión de conjuntos finitos es igual a la unión de las uniones de los conjuntos, y dualmente, el encuentro de una unión de conjuntos finitos es igual al encuentro de los encuentros de los conjuntos, es decir, para subconjuntos finitos y de un conjunto parcial y se mantienen. Tomando como el conjunto vacío, y lo cual es consistente con el hecho de que

Cada red se puede incluir en una red acotada añadiendo un elemento mayor y un elemento menor. Además, toda red finita no vacía se acota tomando la unión (respectivamente, encuentro) de todos los elementos, denotada por (respectivamente ) donde es el conjunto de todos los elementos.

Conexión con otras estructuras algebraicas

Las redes tienen algunas conexiones con la familia de estructuras algebraicas de tipo grupo . Debido a que la reunión y la unión conmutan y asocian, una red puede considerarse como formada por 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 redes. Una red acotada también puede considerarse como una red conmutativa sin el axioma distributivo.

Por conmutatividad, asociatividad e idempotencia se puede pensar en la unión y el encuentro como operaciones sobre conjuntos finitos no vacíos, en lugar de sobre pares de elementos. En una red acotada, la unión y el encuentro del conjunto vacío también se pueden definir (como y respectivamente). Esto hace que las redes acotadas sean algo más naturales que las redes generales, y muchos autores exigen que todas las redes sean acotadas.

La interpretación algebraica de los retículos desempeña un papel esencial en el álgebra universal . [ cita requerida ]

Ejemplos

Se dan más ejemplos de redes para cada una de las propiedades adicionales que se analizan a continuación.

Ejemplos de no-redes

La mayoría de los conjuntos parcialmente ordenados no son redes, incluidos los siguientes.

Morfismos de retículas

Imagen 9: Aplicación monótona entre redes que no conserva ni uniones ni encuentros, ya que y

La noción apropiada de un morfismo entre dos retículos se desprende fácilmente de la definición algebraica anterior. Dados dos retículos y un homomorfismo reticular de L a M es una función tal que para todo

Por lo tanto, se trata de un homomorfismo de las dos semirredes subyacentes . Cuando se consideran retículas con más estructura, los morfismos también deberían "respetar" la estructura adicional. En particular, un homomorfismo de retícula acotada (normalmente llamado simplemente "homomorfismo de retícula") entre dos retículas acotadas también debería tener la siguiente propiedad:

En la formulación de la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de retículos es una función que preserva los encuentros y las uniones binarias. Para retículos acotados, la preservación de los elementos mínimo y máximo es simplemente la preservación de los encuentros y las uniones del conjunto vacío.

Cualquier homomorfismo de redes es necesariamente monótono con respecto a la relación de ordenación asociada; véase Función que preserva el límite . Lo inverso no es cierto: la monotonía de ninguna manera implica la preservación requerida de encuentros y junturas (véase Figura 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 simplemente un homomorfismo reticular biyectivo . De manera similar, un endomorfismo reticular es un homomorfismo reticular de un retículo hacia sí mismo, y un automorfismo reticular es un endomorfismo reticular biyectivo. Los retículos y sus homomorfismos forman una categoría .

Sean y dos retículos con 0 y 1. Un homomorfismo de a se llama 0 , 1 - separando si y solo si ( separa 0 ) y ( separa 1).

Subredes

Una subred de una red es un subconjunto de que es una red con las mismas operaciones de encuentro y unión que Es decir, si es una red y es un subconjunto de tal que para cada par de elementos tanto y están en entonces es una subred de [3]

Una subred de una red es una subred convexa de si e implica que pertenece a para todos los elementos

Propiedades de las redes

Ahora presentamos una serie de propiedades importantes que conducen a clases especiales de redes interesantes. Una de ellas, la acotación, ya se ha analizado.

Lo completo

Un conjunto parcial se denomina red completa si todos sus subconjuntos tienen una unión y un encuentro. En particular, cada red completa es una red acotada. Si bien los homomorfismos de red acotados en general conservan solo las uniones y los encuentros finitos, se requieren homomorfismos de red completos para conservar las uniones y los encuentros arbitrarios.

Todo conjunto parcial que sea un semirretículo completo es también un retículo completo. Relacionado con este resultado está el interesante fenómeno de que existen varias nociones en competencia de homomorfismo para esta clase de conjuntos parciales, dependiendo de si se los considera retículos completos, semirretículos de unión completos, semirretículos de encuentro completos o retículos de unión completos o de encuentro completos.

"Red parcial" no es lo opuesto a "red completa"; más bien, "red parcial", "red" y "red completa" son definiciones cada vez más restrictivas.

Completitud condicional

Una red condicionalmente completa es una red 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 redes proporcionan la generalización más directa del axioma de completitud de los números reales . Una red condicionalmente completa es una red completa, o una red completa sin su elemento máximo ni su elemento mínimo , o ambas. [4] [5]

Distributividad

Como las redes vienen con dos operaciones binarias, es natural preguntar 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 :

Distributividad de sobre

Distributividad de sobre

Una red que satisface el primer o, equivalentemente (como se ha demostrado), el segundo axioma, se denomina red distributiva . Las únicas redes no distributivas con menos de 6 elementos se denominan M 3 y N 5 ; [6] se muestran en las figuras 10 y 11, respectivamente. Una red es distributiva si y solo si no tiene una subred isomorfa a M 3 o N 5 . [7] Cada red distributiva es isomorfa a una red de conjuntos (con unión e intersección como unión y encuentro, respectivamente). [8]

Para una descripción general de nociones más sólidas de distributividad que son apropiadas para redes completas y que se utilizan para definir clases más especiales de redes, como marcos y redes completamente distributivas , consulte distributividad en la teoría del orden .

Modularidad

Para algunas aplicaciones, la condición de distributividad es demasiado fuerte, y la siguiente propiedad más débil suele ser útil. Una red es modular si, para todos los elementos, se cumple la siguiente identidad: ( Identidad modular ) Esta condición es equivalente al siguiente axioma: implica ( Ley modular ) Una red es modular si y solo si no tiene una subred isomorfa a N 5 (mostrada en la Fig. 11). [7] Además de las redes distributivas, ejemplos de redes modulares son la red de submódulos de un módulo (por lo tanto modular ), la red de ideales bilaterales de un anillo y la red de subgrupos normales de un grupo . El conjunto de términos de primer orden con el ordenamiento "es más específico que" es una red no modular utilizada en el razonamiento automatizado .

Semimodularidad

Una red finita es modular si y solo si es semimodular tanto superior como inferior . Para una red graduada, la semimodularidad (superior) es equivalente a la siguiente condición en la función de rango

Otra condición equivalente (para redes graduadas) es la condición de Birkhoff :

para cada uno y en si y ambos cubren entonces cubre ambos y

Una red se denomina semimodular inferior si su dual es semimodular. Para redes finitas esto significa que las condiciones anteriores se cumplen con y intercambiadas, "cubre" intercambiado con "está cubierto por", y las desigualdades se invierten. [9]

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 conjuntos parciales continuos , que consisten en conjuntos parciales donde cada elemento puede obtenerse como el supremo de un conjunto dirigido de elementos que están muy por debajo del elemento. Si uno puede restringirlos adicionalmente a los elementos compactos de un conjunto parcial para obtener estos conjuntos dirigidos, entonces el conjunto parcial es incluso algebraico . Ambos conceptos pueden aplicarse a los retículos de la siguiente manera:

Ambas clases tienen propiedades interesantes. Por ejemplo, las redes continuas se pueden caracterizar como estructuras algebraicas (con operaciones infinitarias) que satisfacen ciertas identidades. Si bien no se conoce tal caracterización para las redes algebraicas, se las puede describir "sintácticamente" a través de los sistemas de información de Scott .

Complementos y pseudocomplementos

Sea una red acotada con el mayor elemento 1 y el menor elemento 0. Dos elementos y de son complementarios entre sí si y solo si:

En general, algunos elementos de una red acotada pueden no tener un complemento, y otros pueden tener más de un complemento. Por ejemplo, el conjunto con su ordenamiento habitual es una red acotada y no tiene un complemento. En la red acotada N 5 , el elemento tiene dos complementos, a saber, y (ver Figura 11). Una red acotada para la que cada elemento tiene un complemento se llama red complementada .

Un retículo complementado que también es distributivo es un álgebra de Boole . Para un retículo distributivo, el complemento de cuando existe es único.

En el caso de que el complemento sea único, escribimos y equivalentemente, La operación unaria correspondiente sobre llamada complementación, introduce un análogo de la negación lógica en la teoría de celosía.

Las álgebras de Heyting son un ejemplo de retículos distributivos en los que algunos miembros pueden carecer de complementos. Por otra parte, cada elemento de un álgebra de Heyting tiene un pseudocomplemento , también denotado El pseudocomplemento es el elemento más grande tal que Si el pseudocomplemento de cada elemento de un álgebra de Heyting es de hecho un complemento, entonces el álgebra de Heyting es de hecho un álgebra de Boole.

Estado de la cadena Jordan-Dedekind

Una cadena de a es un conjunto donde la longitud de esta cadena es n , o uno menos que su número de elementos. Una cadena es máxima si cubre todos los

Si para cualquier par, y donde todas las cadenas máximas de a tienen la misma longitud, entonces se dice que la red satisface la condición de cadena de Jordan-Dedekind .

Calificado/clasificado

Una red se llama graduada , a veces clasificada (pero vea Conjunto ordenado por rangos para un significado alternativo), si se puede equipar con una función de rango a veces a , compatible con el ordenamiento (por lo tanto, siempre que ) tal que siempre que cubra entonces El valor de la función de rango para un elemento de red se llama su rango .

Se dice que un elemento de red cubre otro elemento si pero no existe un tal que Aquí, significa y

Rejillas libres

Cualquier conjunto puede utilizarse para generar la semirretícula libre La semirretícula libre se define como compuesta por todos los subconjuntos finitos de con la operación de semirretícula dada por la unión de conjuntos ordinaria . La semirretícula libre tiene la propiedad universal . Para la red libre sobre un conjunto, Whitman dio una construcción basada en polinomios sobre los miembros de . [10] [11]

Nociones importantes de teoría reticular

Definiremos ahora algunas nociones de orden teórico de importancia para la teoría de retículos. A continuación, un elemento de un retículo se denomina:

Sea 0 el elemento inferior. Un elemento de es un átomo si y no existe ningún elemento tal que Entonces se llama:

Sin embargo, muchas fuentes y comunidades matemáticas utilizan el término "atómico" para significar "atomista" como se define anteriormente. [ cita requerida ]

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 retículos. Se pueden encontrar detalles en las entradas respectivas.

Véase también

Aplicaciones que utilizan la teoría de redes

Tenga en cuenta que en muchas aplicaciones los conjuntos son solo redes parciales: no todos los pares de elementos tienen un punto de encuentro o unión.

Notas

  1. ^ Grätzer 2003, pág. 52.
  2. ^ Birkhoff 1948, p. 18. "desde y dualmente". Birkhoff atribuye esto a Dedekind 1897, p. 8
  3. ^ Burris, Stanley N., y Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN  3-540-90578-2 .
  4. ^ Baker, Kirby (2010). "Complete Lattices" (PDF) . Departamento de Matemáticas de la UCLA . Consultado el 8 de junio de 2022 .
  5. ^ Kaplansky, Irving (1972). Teoría de conjuntos y espacios métricos (2.ª ed.). Nueva York: AMS Chelsea Publishing . p. 14. ISBN. 9780821826942.
  6. ^ Davey y Priestley (2002), Ejercicio 4.1, pág. 104.
  7. ^ ab Davey y Priestley (2002), Teorema 4.10, pág. 89.
  8. ^ Davey y Priestley (2002), Teorema 10.21, págs. 238-239.
  9. ^ Stanley, Richard P (1997), Combinatoria enumerativa (vol. 1) , Cambridge University Press, págs. 103-104, ISBN 0-521-66351-2
  10. ^ Philip Whitman (1941). "Redes libres I". Anales de Matemáticas . 42 (1): 325–329. doi :10.2307/1969001. JSTOR  1969001.
  11. ^ Philip Whitman (1942). "Free Lattices II". Anales de Matemáticas . 43 (1): 104–115. doi :10.2307/1968883. JSTOR  1968883.
  12. ^ Davey y Priestley 2002, pág. 53.
  13. ^ Hoffmann, Rudolf-E. (1981). Posets continuos, espectros primos de redes completas completamente distributivas y compactificaciones de Hausdorff . Redes continuas. Vol. 871. págs. 159–208. doi :10.1007/BFb0089907.
  14. ^ Grätzer 2003, p. 246, Ejercicio 3.
  15. ^ Grätzer 2003, pág. 234, después de Def.1.

Referencias

Monografías disponibles gratuitamente en línea:

Textos elementales recomendados para personas con madurez matemática limitada :

El texto introductorio contemporáneo estándar, algo más difícil que el anterior:

Monografías avanzadas:

Sobre redes libres:

Sobre la historia de la teoría reticular:

Sobre las aplicaciones de la teoría de redes:

Enlaces externos