Retículo (matemáticas)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Un retículo, redículo o red 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 superior mínimo o unión) y un mínimo ú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 cual 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 cuales el supremo es el mínimo común múltiplo y el ínfimo es el máximo común divisor.

Las redes 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 red se basa tanto en la teoría del orden como en el álgebra universal. Las semiretículas incluyen celosías, que a su vez incluyen Heyting y álgebras booleanas. Todas estas estructuras reticulares admiten descripciones tanto teóricas como algebraicas.

Definición

Una red se puede definir teóricamente como un conjunto parcialmente ordenado o como una estructura algebraica.

Como conjunto parcialmente ordenado

Un conjunto parcialmente ordenado (poset) ${ estilo de visualización (L, leq)}$ se denomina retícula si es a la vez una unión y una reunión semiretícula, es decir, cada subconjunto de dos elementos ${displaystyle {a,b}subconjunto L}$ tiene una unión (es decir, el límite superior mínimo, denotado por $avee b$ ) y una reunión dual (es decir, el límite inferior mayor). encuadernado, denotado por $a cuña b$ ). Esta definición hace ${ estilo de visualización , cuña ,}$ y ${ estilo de visualización , vee ,}$ operaciones binarias. Ambas operaciones son monótonas con respecto al orden dado: ${displaystyle a_{1}leq a_{2}}$ e ${displaystyle b_{1}leq b_{2}}$ implica que ${displaystyle a_{1}vee b_{1}leq a_{2}vee b_{2}}$ y ${displaystyle a_{1}cuña b_{1}leq a_{2}cuña b_{2}.}$

De ello se deduce por un argumento de inducción que cada 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 conclusiones adicionales; consulte Completitud (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 parcialmente ordenados relacionados, un enfoque de especial interés para el enfoque teórico de categorías de las redes y para el análisis de conceptos formales.

Dado un subconjunto de un enrejado, ${displaystyle Hsubseteq L,}$ cumplir y unir se restringen a funciones parciales; no están definidas si su valor no está en el subconjunto $h$ . La estructura resultante $H$ se llama uncelosía parcial. Además de esta definición extrínseca como un subconjunto de alguna otra estructura algebraica (un retículo), un retículo parcial también puede definirse intrínsecamente como un conjunto con dos operaciones binarias parciales que satisfacen ciertos axiomas.

Como estructura algebraica

Una red es una estructura algebraica ${ estilo de visualización (L, uve, cuña)}$ , que consta de un conjunto $L$ y dos operaciones binarias, conmutativas y asociativas ${ estilo de visualización , vee ,}$ y que satisfacen $,cuña$ las $L$ siguientes identidades axiomáticas para todos los elementos ${ estilo de visualización a, b en L}$ (a veces llamadas leyes de absorción):

Las dos identidades siguientes también suelen considerarse axiomas, aunque se derivan de las dos leyes de absorción tomadas juntas. Estas se llaman leyes idempotentes.

Estos axiomas afirman que ambos ${ estilo de visualización (L, vee)}$ y ${ estilo de visualización (L, cuña)}$ son semirretículos. Las leyes de absorción, los únicos axiomas anteriores en los que se encuentran y se unen, distinguen una red de un par arbitrario de estructuras semiredes y aseguran que las dos semiredes 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 las semiredes se encuentren y se unan definan el mismo orden parcial.

Conexión entre las dos definiciones

Una red teórica de orden da lugar a las dos operaciones binarias ${ estilo de visualización , vee ,}$ y ${ estilo de visualización , cuña.}$ Dado que las leyes conmutativa, asociativa y de absorción pueden verificarse fácilmente para estas operaciones, forman ${ estilo de visualización (L, uve, cuña)}$ una red en el sentido algebraico.

Lo contrario también es cierto. Dada una red definida algebraicamente ${ estilo de visualización (L, uve, cuña),}$ , se puede definir un orden parcial mediante ${ estilo de visualización , leq ,}$ el $L$ establecimiento de

{displaystyle aleq b{text{ si }}a=awedge b,{text{ o }}}

{displaystyle aleq b{text{si}}b=avee b,}

para todos los elementos ${ estilo de visualización a, b en L.}$ Las leyes de absorción aseguran que ambas definiciones sean equivalentes:

{displaystyle a=acuña b{text{ implica }}b=bvee (bcuña a)=(acuña b)vee b=avee b}

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 los encuentros binarios y las uniones se dan a través de las operaciones originales ${ estilo de visualización , vee ,}$ y ${ estilo de visualización , cuña.}$

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

Enrejado delimitado

Una red acotada es una red que además tiene un elemento mayor (también llamado máximo o elemento superior, y denotado por 1 o por ${ estilo de visualización , arriba}$ ) y un elemento mínimo (también llamado mínimo o inferior, denotado por 0 o por ${ estilo de visualización , bot}$ ), que satisfacen

{displaystyle 0leq xleq 1;{text{ para cada }}xin L.}

Una retícula acotada también se puede definir como una estructura algebraica de la forma ${ estilo de visualización (L, uve, cuña, 0,1)}$ tal que ${ estilo de visualización (L, uve, cuña)}$ es una retícula, ${ estilo de visualización 0}$ (la parte inferior de la retícula) es el elemento de identidad para la operación de unión ${ estilo de visualización , vee, ,}$ y $1$ (la parte superior de la retícula) es el elemento de identidad para la operación de reunión ${ estilo de visualización , cuña.}$

Un conjunto parcialmente ordenado es un retículo acotado si y solo si todo conjunto finito de elementos (incluido el conjunto vacío) tiene una unión y un encuentro. Para cada elemento $X$ de un poset es vacuamente cierto que ${displaystyle {text{ para todos }}ain varnada,xleq a}$ y ${displaystyle {text{ para todos }}ain varnada,aleq x,}$ , 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 menor ${displaystyle bigvee varnada =0,}$ y la reunión del conjunto vacío es el elemento mayor ${displaystyle bigwedge varnada =1.}$ Esto es consistente con la asociatividad y conmutatividad de la reunión y la 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 conjuntos de los conjuntos, es decir, para subconjuntos finitos ${displaystyle A{text{ y }}B}$ de un poset $L,$

{displaystyle bigvee (Acup B)=left(bigvee Aright)vee left(bigvee Bright)}

{displaystyle bigwedge (Acup B)=left(bigwedge Aright)wedge left(bigwedge Bright)}

mantener. Tomando B como el conjunto vacío,

{displaystyle bigvee (Acup varnothing)=left(bigvee Aright)vee left(bigvee varnothing right)=left(bigvee Aright)vee 0=bigvee UN}

{displaystyle bigwedge (Acup varnothing)=left(bigwedge Aright)wedge left(bigwedge varnothing right)=left(bigwedge Aright)wedge 1=bigwedge UN}

lo cual es consistente con el hecho de que ${displaystyle Ataza varnada =A.}$

Cada celosía se puede incrustar en una celosía acotada agregando un elemento mayor y menor. Además, cada red finita no vacía está limitada tomando la unión (respectivamente, encuentro) de todos los elementos, denotada por ${displaystyle 1=bigvee L=a_{1}lor cdots lor a_{n}}$ (respectivamente ${displaystyle 0=bigwedge L=a_{1}land cdots land a_{n}}$ ) donde ${displaystyle L=left{a_{1},ldots,a_{n}right}}$ es el conjunto de todos los elementos.

Conexión con otras estructuras algebraicas

Los retículos tienen algunas conexiones con la familia de estructuras algebraicas similares a grupos. Debido a que se encuentran y se unen tanto para conmutar como para asociar, se puede considerar que una red 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 unir y encontrar como operaciones en conjuntos finitos no vacíos, en lugar de pares de elementos. En una red acotada también se pueden definir la unión y el encuentro del conjunto vacío (como ${ estilo de visualización 0}$ y $1,$ respectivamente). Esto hace que los retículos acotados sean algo más naturales que los retículos generales, y muchos autores exigen que todos los retículos estén acotados.

La interpretación algebraica de las redes juega un papel esencial en el álgebra universal.

Ejemplos

Foto. 1: Subconjuntos de ${ estilo de visualización {x, y, z },}$ inclusión bajo conjunto. El nombre "celosía" se sugiere por la forma del diagrama de Hasse que lo representa.
Foto. 2: Celosía de divisores enteros de 60, ordenados por " divides ".
Foto. 3: Celosía de tabiques de ${ estilo de visualización {1,2,3,4 },}$ ordenada por " refina ".
Foto. 4: Celosía de enteros positivos, ordenados por ${ estilo de visualización , leq,}$
Foto. 5: Enrejado de pares enteros no negativos, ordenados por componentes.

Para cualquier conjunto, $UN,$ la colección de todos los subconjuntos de $UN$ (llamado conjunto potencia de $UN$ ) se puede ordenar a través de la inclusión de subconjuntos para obtener una red delimitada por $UN$ sí mismo y el conjunto vacío. Intersección de conjuntos y unión de conjuntos interpretan encuentro y unión, respectivamente (ver Fig. 1).
Para cualquier conjunto, $UN,$ la colección de todos los subconjuntos finitos de $UN,$ ordenados por inclusión, también es un retículo, y estará acotado si y solo si $UN$ es finito.
Para cualquier conjunto, $UN,$ la colección de todas las particiones $UN,$ ordenadas por refinamiento es una red (ver Fig. 3).
Los enteros positivos en su orden habitual forman una red, bajo las operaciones de "min" y "max". 1 es inferior; no hay tapa (ver Fig. 4).
El cuadrado cartesiano de los números naturales, ordenados de forma que ${ estilo de visualización (a, b) leq (c, d)}$ si ${displaystyle aleq c{text{ y }}bleq d.}$ El par $(0,0)$ es el elemento inferior; no hay tapa (ver Fig. 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 la divisibilidad como relación de orden: $a leq b$ si $un$ divide es fondo; yo paro. Foto. 2 muestra una subred finita. ${ estilo de visualización b.}$ $1$ ${ estilo de visualización 0}$
Cada retícula completa (también ver más abajo) es una retícula delimitada (bastante específica). Esta clase da lugar a una amplia gama de ejemplos prácticos.
El conjunto de elementos compactos de un retículo aritmético completo es un retículo con un elemento mínimo, donde las operaciones del retículo se dan restringiendo las respectivas operaciones del retículo aritmético. Esta es la propiedad específica que distingue a los retículos aritméticos de los retículos algebraicos, para los cuales los compactos solo forman un semirretículo de unión. Ambas clases de redes completas se estudian en la teoría de dominios.

Se dan más ejemplos de retículas para cada una de las propiedades adicionales discutidas a continuación.

Ejemplos de no celosías

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

Un poset discreto, es decir, un poset tal que $xleq y$ implica que ${ estilo de visualización x = y,}$ es una red si y solo si tiene como máximo un elemento. En particular, el poset discreto de dos elementos no es una red.
Aunque el conjunto ${ estilo de visualización {1,2,3,6 }}$ parcialmente ordenado por divisibilidad es un retículo, el conjunto ${ estilo de visualización {1,2,3 }}$ así ordenado no es un retículo porque el par 2, 3 carece de unión; Del mismo modo, 2, 3 carece de un encuentro en ${ estilo de visualización {2,3,6 }.}$
El conjunto ${ estilo de visualización {1,2,3,12,18,36 }}$ parcialmente ordenado por divisibilidad no es una red. 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 entre sí). Asimismo, 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 retículas fluye fácilmente de la definición algebraica anterior. Dados dos retículos ${ estilo de visualización izquierda (L, vee _ {L}, cuña _ {L} derecha)}$ y ${ estilo de visualización izquierda (M, vee _ {M}, cuña _ {M} derecha),}$ un homomorfismo de retículo de L a M es una función ${ estilo de visualización f: L a M}$ tal que para todo ${ estilo de visualización a, b en L:}$

{displaystyle fleft(avee_{L}bright)=f(a)vee_{M}f(b),{text{ y }}}

{ Displaystyle f left (a cuña _ {L} b derecha) = f (a) cuña _ {M} f (b).}

Por lo tanto $F$ , es un homomorfismo de las dos semiredes 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 acotadas $L$ y $METRO$ también debe tener la siguiente propiedad:

{displaystyle fleft(0_{L}right)=0_{M},{text{ y }}}

{ estilo de visualización f izquierda (1_ {L} derecha) = 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 encuentros y uniones binarias. Para celosías acotadas, la preservación de los elementos mínimos y máximos 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 orden asociada; ver Función de conservación de límites. Lo contrario no es cierto: la monotonicidad de ninguna manera implica la preservación requerida de 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 de celosía es solo un homomorfismo de celosía biyectivo. De manera similar, un endomorfismo de celosía es un homomorfismo de celosía de una celosía a sí mismo, y un automorfismo de celosía es un endomorfismo de celosía biyectivo. Las redes y sus homomorfismos forman una categoría.

Sean $matemáticas {L}$ y ${ estilo de visualización mathbb {L} '}$ sean dos celosías con 0 y 1. Un homomorfismo de $matemáticas {L}$ a ${ estilo de visualización mathbb {L} '}$ se llama 0,1 - separando si y solo si ${displaystyle f^{-1}{f(0)}={0}}$ ( $F$ separa 0) y ${displaystyle f^{-1}{f(1)}={1}}$ ( $F$ separa 1).

Subredes

Una subred de una red $L$ es un subconjunto de $L$ que es una red con las mismas operaciones de encuentro y unión que $l$ Es decir, si $L$ es una red y $METRO$ es un subconjunto de $L$ tal que para cada par de elementos ${ estilo de visualización a, b en M}$ ambos $a cuña b$ y $avee b$ están en ${ estilo de visualización M,}$ entonces $METRO$ es una subred de $l$

Una subred $METRO$ de una red $L$ es una subred convexa de $L,$ if ${ estilo de visualización x leq z leq y}$ e $x, y en M$ implica que $z$ pertenece a ${ estilo de visualización M,}$ para todos los elementos ${ estilo de visualización x, y, z en L.}$

Propiedades de las redes

Ahora presentamos una serie de propiedades importantes que conducen a interesantes clases especiales de retículas. Uno, la delimitación, ya se ha discutido.

Lo completo

Un poset se llama red completa si todos sus subconjuntos tienen una unión y una reunión. En particular, todo retículo completo es un retículo acotado. Mientras que los homomorfismos de celosía acotados en general conservan solo uniones y encuentros finitos, se requieren homomorfismos de celosía completos para preservar uniones y encuentros arbitrarios.

Todo poset que es 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 de homomorfismo en competencia para esta clase de posets, dependiendo de si se ven como retículas completas, semirretículas de unión completas, semiretículas 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"; más bien, "celosía parcial", "celosía" y "celosía 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). Estos retículos 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, $1,$ su elemento mínimo ${ estilo de visualización 0,}$ o ambos.

Distributividad

Dado que los retículos vienen con dos operaciones binarias, es natural preguntarse si una de ellas se distribuye sobre la otra, es decir, si se cumple una u otra de las siguientes leyes duales para cada tres elementos ${ estilo de visualización a, b, c en L,}$ :Distributividad de ${ estilo de visualización , vee ,}$ más ${ estilo de visualización , cuña ,}$

{displaystyle avee (bcuña c)=(avee b)cuña (avee c).}

Distributividad de ${ estilo de visualización , cuña ,}$ más ${ estilo de visualización , vee ,}$

{displaystyle acuña (bvee c)=(acuña b)vee (acuña c).}

Un retículo que satisface el primero o, de manera equivalente (como resulta), el segundo axioma, se llama retículo distributivo. Las únicas redes no distributivas con menos de 6 elementos se denominan M ₃ y N ₅; se muestran en las Imágenes 10 y 11, respectivamente. Una red es distributiva si y sólo si no tiene una subred isomorfa a M ₃ o N ₅. Cada retícula distributiva es isomorfa a una retícula de conjuntos (con unión e intersección como unión y encuentro, respectivamente).

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

Modularidad

Para algunas aplicaciones, la condición de distributividad es demasiado fuerte y, a menudo, es útil la siguiente propiedad más débil. Una red ${ estilo de visualización (L, uve, cuña)}$ es modular si, para todos los elementos ${ estilo de visualización a, b, c en L,}$ , se cumple la siguiente identidad: ${displaystyle (acuña c)vee (bcuña c)=((acuña c)vee b)cuña c.}$ (Identidad modular)Esta condición es equivalente al siguiente axioma: ${displaystyle aleq c}$ implica ${displaystyle avee (bcuña c)=(avee b)cuña c.}$ (Ley modular)Una red es modular si y solo si no tiene una subred isomorfa a N ₅ (mostrado en la imagen 11). Además de los retículos distributivos, ejemplos de retículos modulares son el retículo de ideales de dos lados de un anillo, el retículo de submódulos de un módulo y el retículo de subgrupos normales de un grupo. El conjunto de términos de primer orden con el orden "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 ${ estilo de visualización r:}$ ${displaystyle r(x)+r(y)geq r(xcuña y)+r(xvee y).}$

Otra condición equivalente (para celosías graduadas) es la condición de Birkhoff:para cada uno $X$ y $y$ en $L,$ si $X$ y $y$ ambos cubren ${ estilo de visualización x cuña y,}$ entonces $xvee y$ cubre ambos $X$ y $y.$

Una red se llama semimodular inferior si su dual es semimodular. Para celosías finitas, esto significa que las condiciones anteriores se mantienen con ${ estilo de visualización , vee ,}$ e ${ estilo de visualización , cuña ,}$ intercambiadas, "cubre" intercambiadas con "está cubierto por" y las desigualdades se invierten.

Continuidad y algebraicidad

En la teoría del dominio, es natural buscar aproximar los elementos en un orden parcial por elementos "mucho más simples". Esto lleva a la clase de posets continuos, que consisten en posets donde cada elemento se puede obtener como el supremo de un conjunto dirigido de elementos que están muy por debajo del elemento. Si además se pueden restringir 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 redes de la siguiente manera:

Una red continua es una red completa que es continua como poset.
Un retículo algebraico es un retículo completo que es algebraico como poset.

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

Complementos y pseudocomplementos

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

{displaystyle xvee y=1quad {text{ y }}quad xwedge y=0.}

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 ${ estilo de visualización {0.1 / 2.1 }}$ con su orden habitual es un retículo acotado y ${tfrac{1}{2}}$ no tiene complemento. En la red acotada N ₅, el elemento $un$ tiene dos complementos, a saber. $b$ y $C$ (ver imagen 11). Una red acotada para la cual cada elemento tiene un complemento se llama red complementada.

Un retículo complementado que también es distributivo es un álgebra booleana. 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 equivalentemente, ¬ y = x. La correspondiente operación unaria sobre la $L,$ denominada 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 de un álgebra de Heyting tiene, por otra parte, un pseudocomplemento, también denotado $z$ ¬x. El pseudocomplemento es el elemento mayor 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 booleana. $y$ $x cuña y = 0.$

Condición de la cadena Jordan-Dedekind

Una cadena de $x_{0}$ a $x_{n}$ es un conjunto ${displaystyle left{x_{0},x_{1},ldots,x_{n}right},}$ donde <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d05f6554dee997cb19abc3928ffbc13631894f45" alt="{displaystyle x_{0}<x_{1}<x_{2}<ldots La longitud de esta cadena es n, o uno menos que su número de elementos. Una cadena es máxima si $x_{yo}$ cubre $x_{i-1}$ todos $1 leq i leq n.$

Si para cualquier par, $X$ y $y,$ donde <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3eecf73c55d04fd4e7005b8008f862185c93044a" alt="{ estilo de visualización xtodas las cadenas máximas tienen $X$ la $y$ misma longitud, se dice que la red cumple la condición de la cadena Jordan-Dedekind.

Calificado/clasificado

Un enrejado ${ estilo de visualización (L, leq)}$ se denomina clasificado, a veces clasificado (pero consulte Poset clasificado para un significado alternativo), si puede equiparse con una función de rango ${displaystyle r:Lto mathbb {N} }$ a veces a ℤ, compatible con el orden (entonces <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/301fc2a6002846081737e59441528b1bea03cc24" alt="{ estilo de visualización r (x) siempre que <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aeb239de6fee56ea8b6a65f7858d95b87632069f" alt="x) de tal manera que siempre $y$ cubra $X,$ el ${ estilo de visualización r (y) = r (x) + 1.}$ valor del rango función para un elemento de red se llama su rango.

Se dice que un elemento reticular $y$ cubre otro elemento $X,$ si x,}">pero no existe $z$ tal que z> x.}"> Aquí, x}">significa $xleq y$ y ${displaystyle xneq y.}$

Redes libres

$X$ Se puede usar cualquier conjunto para generar la semired ${ Displaystyle FX.}$ libre. La semired libre se define como compuesta por todos los subconjuntos finitos de $X,$ con la operación de semiredes dada por la unión ordinaria de conjuntos. La semired libre tiene la propiedad universal. Para la red libre sobre un conjunto, $X,$ Whitman dio una construcción basada en polinomios sobre los miembros de. $X$

Nociones importantes de teoría de celosía

Ahora definiremos algunas nociones de teoría del orden de importancia para la teoría de redes. En lo siguiente, $X$ sea un elemento de alguna red $l$ Si a veces se requiere $L$ un elemento inferior. se llama: ${ estilo de visualización 0,}$ $x neq 0$ $X$

Unión irreducible si ${displaystyle x=avee b}$ implica ${displaystyle x=a{text{ o }}x=b.}$ para todos ${ estilo de visualización a, b en L.}$ Cuando la primera condición se generaliza a las uniones arbitrarias se denomina unión completamente irreducible (o -irreducible). La noción dual se encuentra con la irreductibilidad (-irreducible). Por ejemplo, en la imagen. 2, los elementos 2, 3, 4 y 5 son irreductibles unidos, mientras que 12, 15, 20 y 30 son irreductibles. En la red de números reales con el orden habitual, cada elemento es irreductible de unión, pero ninguno es completamente irreductible de unión. ${displaystyle bigvee_{iin I}a_{i},}$ $X$ $vee$ $cuña$
Join prime if ${displaystyle xleq avee b}$ implica ${displaystyle xleq a{text{ o }}xleq b.}$ Esto también se puede generalizar para obtener la noción completamente join prime. La noción dual es cumplir primo. Cada elemento primo de unión también es irreducible de unión, y cada elemento primo de encuentro también es irreducible de encuentro. Lo contrario se cumple si $L$ es distributivo.

Sea $L$ un elemento inferior 0. Un elemento $X$ de $L$ es un átomo si <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/35b0ac4e2c02e608588f1525eac793c53eb7c55f" alt="{ estilo de visualización 0 y no existe ningún elemento $y en L$ tal que <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70838217257cf695417498fdb9745dcb7d6e6649" alt="{ estilo de visualización 0 <y Entonces $L$ se llame:

Atómico si por cada elemento distinto de cero $X$ de $L,$ existe un átomo $un$ de $L$ tal que ${displaystyle aleq x;}$
Atomístico 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 redes. Los detalles se pueden encontrar en las entradas respectivas.

Aplicaciones que utilizan la teoría de la red

Tenga en cuenta que en muchas aplicaciones los conjuntos son solo retículas parciales: no todos los pares de elementos se encuentran o se unen.

Topología sin sentido
Red de subgrupos
espacio espectral
Subespacio invariante
Operador de cierre
Interpretación abstracta
Red de subsunción
Teoría de conjuntos borrosos
Algebraizaciones de la lógica de primer orden
Semántica de los lenguajes de programación.
teoría del dominio
Ontología (ciencias de la computación)
Herencia múltiple
Análisis de concepto formal 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 la mediana
espacio de conocimiento
Aprendizaje regular de idiomas
Modelado analógico

Contenido relacionado

Más resultados...