Celosía (orden)

Conjunto cuyos pares tienen mínimos y máximos.

Una 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 mínimo 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 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 red se basa tanto en la teoría del orden como en el álgebra universal . Las semiredes incluyen redes, que a su vez incluyen álgebras de Heyting y de Boole . Todas estas estructuras en forma de celosía admiten descripciones tanto teóricas del orden como algebraicas.

El subcampo del álgebra abstracta que estudia las redes se llama teoría de redes .

Definición

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

Como conjunto parcialmente ordenado

Un conjunto parcialmente ordenado (poset) se denomina red si es a la vez una semired de unión y de encuentro , es decir, cada subconjunto de dos elementos tiene una unión (es decir, el límite superior mínimo, denotado por ) y un encuentro dual (es decir, el límite inferior más grande). enlazado, denotado por ). Esta definición hace operaciones binarias . Ambas operaciones son monótonas con respecto al orden dado: and implica que y ${\displaystyle (L,\leq )}$ ${\displaystyle \{a,b\}\subseteq L}$ ${\displaystyle a\vee b}$ ${\displaystyle a\wedge b}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle a_{1}\leq a_{2}}$ ${\displaystyle b_{1}\leq b_{2}}$ ${\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}}$ ${\displaystyle a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}.}$

Por un argumento de inducción se deduce 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, es posible sacar más conclusiones; 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 una red, meet y join se restringen a funciones parciales : no están definidas si su valor no está en el subconjunto. La estructura resultante se llama ${\displaystyle H\subseteq L,}$ ${\displaystyle H.}$ ${\displaystyle H}$celosí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]

Como estructura algebraica

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

$${\displaystyle a\vee (a\wedge b)=a}$$

$${\displaystyle a\wedge (a\vee b)=a}$$

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

$${\displaystyle a\vee a=a}$$

$${\displaystyle a\wedge a=a}$$

Estos axiomas afirman que ambos y son semiredes . Las leyes de absorción, los únicos axiomas anteriores en los que ambos se encuentran y se unen, distinguen una red de un par arbitrario de estructuras de semired y aseguran que las dos semiredes interactúen apropiadamente. En particular, cada semired es dual de la otra. Las leyes de absorción pueden verse como un requisito de que las semiredes que se encuentran y se unen definen el mismo orden parcial . ${\displaystyle (L,\vee )}$ ${\displaystyle (L,\wedge )}$

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 pueden verificarse fácilmente para estas operaciones, forman una red en el sentido algebraico. ${\displaystyle \vee }$ ${\displaystyle \wedge .}$ ${\displaystyle (L,\vee ,\wedge )}$

Lo contrario también es cierto. Dada una red definida algebraicamente, se puede definir un orden parcial estableciendo ${\displaystyle (L,\vee ,\wedge ),}$ ${\displaystyle \leq }$ ${\displaystyle L}$

$${\displaystyle a\leq b{\text{ if }}a=a\wedge b,{\text{ or }}}$$

$${\displaystyle a\leq b{\text{ if }}b=a\vee b,}$$

${\displaystyle a,b\in L.}$

$${\displaystyle a=a\wedge b{\text{ implies }}b=b\vee (b\wedge a)=(a\wedge b)\vee b=a\vee b}$$

Ahora se puede comprobar que la relación ≤ introducida de esta manera define un ordenamiento parcial dentro del cual los encuentros y uniones binarias se dan a través de las operaciones originales y ${\displaystyle \vee }$ ${\displaystyle \wedge .}$

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

celosía acotada

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 mínimo (también llamado mínimo o inferior , denotado por o por ), que satisfacen ${\displaystyle 1,}$ ${\displaystyle \top }$ ${\displaystyle 0}$ ${\displaystyle \bot }$

$${\displaystyle 0\leq x\leq 1\;{\text{ for every }}x\in L.}$$

Una red acotada también se puede definir como una estructura algebraica de la forma tal que es una red, (la parte inferior de la red) es el elemento de identidad para la operación de unión y (la parte superior de la red) es el elemento de identidad para la operación de encuentro. ${\displaystyle (L,\vee ,\wedge ,0,1)}$ ${\displaystyle (L,\vee ,\wedge )}$ ${\displaystyle 0}$ ${\displaystyle \vee ,}$ ${\displaystyle 1}$ ${\displaystyle \wedge .}$

$${\displaystyle a\vee 0=a}$$

$${\displaystyle a\wedge 1=a}$$

Un conjunto parcialmente ordenado es una red acotada si y sólo si cada conjunto finito de elementos (incluido el conjunto vacío) tiene una unión y un encuentro. Para cada elemento de un poset es vagamente cierto que y por lo tanto cada elemento de un poset es a la vez un límite superior y un límite inferior del conjunto vacío. Esto implica que la unión de un conjunto vacío es el elemento menor y la unión 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 poset ${\displaystyle x}$ ${\displaystyle {\text{ for all }}a\in \varnothing ,x\leq a}$ ${\displaystyle {\text{ for all }}a\in \varnothing ,a\leq x,}$ ${\textstyle \bigvee \varnothing =0,}$ ${\textstyle \bigwedge \varnothing =1.}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle L,}$

$${\displaystyle \bigvee (A\cup B)=\left(\bigvee A\right)\vee \left(\bigvee B\right)}$$

$${\displaystyle \bigwedge (A\cup B)=\left(\bigwedge A\right)\wedge \left(\bigwedge B\right)}$$

${\displaystyle B}$

$${\displaystyle \bigvee (A\cup \varnothing )=\left(\bigvee A\right)\vee \left(\bigvee \varnothing \right)=\left(\bigvee A\right)\vee 0=\bigvee A}$$

$${\displaystyle \bigwedge (A\cup \varnothing )=\left(\bigwedge A\right)\wedge \left(\bigwedge \varnothing \right)=\left(\bigwedge A\right)\wedge 1=\bigwedge A,}$$

${\displaystyle A\cup \varnothing =A.}$

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

Conexión con otras estructuras algebraicas.

Las celosías tienen algunas conexiones con la familia de estructuras algebraicas de tipo grupo . Debido a que encontrarse y unirse conmutan y asocian, se puede considerar que una red está 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 peculiar de la teoría de redes. También se puede considerar una red acotada como un anillo conmutativo sin el axioma distributivo.

Por conmutatividad, asociatividad e idempotencia se puede pensar en unirse y encontrarse como operaciones en conjuntos finitos no vacíos, en lugar de 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 estén acotadas. ${\displaystyle 0}$ ${\displaystyle 1,}$

La interpretación algebraica de celosías juega un papel esencial en el álgebra universal . ^{[ cita necesaria ]}

Ejemplos

• 
  Foto. 1: Subconjuntos de inclusión inferior al conjunto . El nombre "celosía" lo sugiere la forma del diagrama de Hasse que lo representa. ${\displaystyle \{x,y,z\},}$
• 
  Foto. 2: Celosía de divisores enteros de 60, ordenados por " divisiones ".
• 
  Foto. 3: Celosía de particiones ordenadas por " refinas ". ${\displaystyle \{1,2,3,4\},}$
• 
  Foto. 4: Red de números enteros positivos, ordenados por ${\displaystyle \,\leq ,}$
• 
  Foto. 5: Red de pares de enteros no negativos, ordenados por componentes.

• Para cualquier conjunto, la colección de todos los subconjuntos de (llamado conjunto potencia de ) se puede ordenar mediante la inclusión de subconjuntos para obtener una red delimitada por sí misma y el conjunto vacío. En esta red, el supremo lo proporciona la unión de conjuntos y el mínimo lo proporciona la intersección de conjuntos (ver Imagen 1). ${\displaystyle A,}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$
• Para cualquier conjunto, la colección de todos los subconjuntos finitos ordenados por inclusión también es una red y estará acotada si y solo si es finita. ${\displaystyle A,}$ ${\displaystyle A,}$ ${\displaystyle A}$
• Para cualquier conjunto, la colección de todas las particiones ordenadas por refinamiento es una red (ver Imagen 3). ${\displaystyle A,}$ ${\displaystyle A,}$
• Los números enteros positivos en su orden habitual forman una red ilimitada, bajo las operaciones de "min" y "max". 1 es abajo; no hay techo (ver Imagen 4).
• El cuadrado cartesiano de los números naturales, ordenados de manera que si El par es el elemento inferior; no hay techo (ver Imagen 5). ${\displaystyle (a,b)\leq (c,d)}$ ${\displaystyle a\leq c{\text{ and }}b\leq d.}$ ${\displaystyle (0,0)}$
• Los números naturales también forman un entramado 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: si divide es abajo; yo paro. Foto. 2 muestra una subred finita. ${\displaystyle a\leq b}$ ${\displaystyle a}$ ${\displaystyle b.}$ ${\displaystyle 1}$ ${\displaystyle 0}$
• Cada red completa (ver también más abajo) es una red limitada (bastante específica). Esta clase da lugar a una amplia gama de ejemplos prácticos .
• El conjunto de elementos compactos de una red aritmética completa es una red con un elemento mínimo, donde las operaciones de la red se dan restringiendo las operaciones respectivas de la red aritmética. Esta es la propiedad específica que distingue las redes aritméticas de las algebraicas , para las cuales los compactos sólo forman una semired de unión . Ambas clases de redes completas se estudian en teoría de dominios .

Se dan más ejemplos de redes para cada una de las propiedades adicionales que se analizan 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 implica , es una red si y sólo si tiene como máximo un elemento. En particular, el poset discreto de dos elementos no es una red. ${\displaystyle x\leq y}$ ${\displaystyle x=y,}$
• Aunque el conjunto parcialmente ordenado por divisibilidad es un retículo, el conjunto así ordenado no es un retículo porque el par 2, 3 carece de unión; De manera similar, 2, 3 carece de encuentro en ${\displaystyle \{1,2,3,6\}}$ ${\displaystyle \{1,2,3\}}$ ${\displaystyle \{2,3,6\}.}$
• El conjunto parcialmente ordenado por divisibilidad no es un retículo. 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 esos 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 esos tres bajo divisibilidad (2 y 3 no se dividen entre sí). ${\displaystyle \{1,2,3,12,18,36\}}$

Morfismos de celosías

Foto. 9: Mapa monótono entre celosías que no conserva ni une ni encuentra, ya que y ${\displaystyle f}$ ${\displaystyle f(u)\vee f(v)=u^{\prime }\vee u^{\prime }=u^{\prime }}$ ${\displaystyle \neq }$ ${\displaystyle 1^{\prime }=f(1)=f(u\vee v)}$ ${\displaystyle f(u)\wedge f(v)=u^{\prime }\wedge u^{\prime }=u^{\prime }}$ ${\displaystyle \neq }$ ${\displaystyle 0^{\prime }=f(0)=f(u\wedge v).}$

La noción apropiada de un morfismo entre dos redes se deriva fácilmente de la definición algebraica anterior. Dadas dos redes y un homomorfismo de red de L a M es una función tal que para todos ${\displaystyle \left(L,\vee _{L},\wedge _{L}\right)}$ ${\displaystyle \left(M,\vee _{M},\wedge _{M}\right),}$ ${\displaystyle f:L\to M}$ ${\displaystyle a,b\in L:}$

$${\displaystyle f\left(a\vee _{L}b\right)=f(a)\vee _{M}f(b),{\text{ and }}}$$

$${\displaystyle f\left(a\wedge _{L}b\right)=f(a)\wedge _{M}f(b).}$$

Por lo tanto , hay un homomorfismo de las dos semiredes subyacentes . Cuando se consideran redes con más estructura, los morfismos también deberían "respetar" la estructura adicional. En particular, un homomorfismo de red acotada (generalmente llamado simplemente "homomorfismo de red") entre dos redes acotadas y también debería tener la siguiente propiedad: ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle M}$

$${\displaystyle f\left(0_{L}\right)=0_{M},{\text{ and }}}$$

$${\displaystyle f\left(1_{L}\right)=1_{M}.}$$

En la formulación de la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de redes es una función que preserva encuentros y uniones binarias. Para celosías acotadas, la preservación de los elementos mínimos y mayores es simplemente la preservación de la unión y el encuentro del conjunto vacío.

Cualquier homomorfismo de redes es necesariamente monótono con respecto a la relación de orden 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 encuentros y uniones (ver figura 9), aunque una biyección que preserva el orden es un homomorfismo si su inverso 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 a sí mismo, y un automorfismo reticular es un endomorfismo reticular biyectivo. Las celosías y sus homomorfismos forman una categoría .

Sean y dos redes con 0 y 1 . Un homomorfismo de a se llama 0 , 1 , separando si y solo si ( separa 0 ) y ( separa 1). ${\displaystyle \mathbb {L} }$ ${\displaystyle \mathbb {L} '}$ ${\displaystyle \mathbb {L} }$ ${\displaystyle \mathbb {L} '}$ ${\displaystyle f^{-1}\{f(0)\}=\{0\}}$ ${\displaystyle f}$ ${\displaystyle f^{-1}\{f(1)\}=\{1\}}$ ${\displaystyle f}$

Subredes

Una subred de una red es un subconjunto de 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 ambos y están en entonces es una subred de ^{[ 3]} ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L.}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle a,b\in M}$ ${\displaystyle a\wedge b}$ ${\displaystyle a\vee b}$ ${\displaystyle M,}$ ${\displaystyle M}$ ${\displaystyle L.}$

Una subred de una red es una subred convexa de si e implica que pertenece a todos los elementos ${\displaystyle M}$ ${\displaystyle L}$ ${\displaystyle L,}$ ${\displaystyle x\leq z\leq y}$ ${\displaystyle x,y\in M}$ ${\displaystyle z}$ ${\displaystyle M,}$ ${\displaystyle x,y,z\in L.}$

Propiedades de las celosías

Ahora presentamos una serie de propiedades importantes que conducen a interesantes clases especiales de redes. Uno de ellos, la limitación, ya ha sido discutido.

Lo completo

Un poset se llama red completa si todos sus subconjuntos tienen tanto una unión como un encuentro. En particular, toda red completa es una red acotada. Si bien los homomorfismos de red 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 sea una semired completa también lo es. Relacionado con este resultado está el interesante fenómeno de que existen varias nociones competitivas de homomorfismo para esta clase de posets, dependiendo de si se los ve como redes completas, semirretículas de unión completa, semirretículas de encuentro completas o como conjuntos de unión completa o de encuentro. celosías completas.

"Enrejado parcial" no es lo opuesto a "Enrejado completo"; más bien, "Enrejado parcial", "Enrejado" y "Enrejado completo" 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, su elemento mínimo o ambos. ^{[4] [5]} ${\displaystyle 1,}$ ${\displaystyle 0,}$

Distributividad

Dado que las redes 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 : ${\displaystyle a,b,c\in L,}$

Distributividad de más ${\displaystyle \vee }$ ${\displaystyle \wedge }$

$${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c).}$$

Distributividad de más ${\displaystyle \wedge }$ ${\displaystyle \vee }$

$${\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c).}$$

Una red que satisface el primero o, de manera equivalente (como resulta), el segundo axioma, se llama red distributiva . Las únicas redes no distributivas con menos de 6 elementos se denominan M ₃ y N ₅ ; ^[6] 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 ₅ . ^[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 obtener 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 resultar ú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 ₅ (mostrado en la Imagen 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 de dos lados de un anillo y la red 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 . ${\displaystyle (L,\vee ,\wedge )}$ ${\displaystyle a,b,c\in L,}$ ${\displaystyle (a\wedge c)\vee (b\wedge c)=((a\wedge c)\vee b)\wedge c.}$
${\displaystyle a\leq c}$ ${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge c.}$

Semimodularidad

Una red finita es modular si y sólo 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 ${\displaystyle r\colon }$

${\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).}$

Otra condición equivalente (para celosías graduadas) es la condición de Birkhoff :

para cada uno y en si y ambos cubren entonces cubre ambos y ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle L,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\wedge y,}$ ${\displaystyle x\vee y}$ ${\displaystyle x}$ ${\displaystyle y.}$

Una red se llama semimodular inferior si su dual es semimodular. Para redes finitas, esto significa que las condiciones anteriores se cumplen con e intercambiadas, "cubre" se intercambia con "está cubierto por" y las desigualdades se invierten. ^[9] ${\displaystyle \vee }$ ${\displaystyle \wedge }$

Continuidad y algebraicidad.

En teoría de dominios , es natural buscar aproximar los elementos en un orden parcial mediante 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 celosías de la siguiente manera:

• Una red continua es una red completa que es continua como poset.
• Una red algebraica es una red completa que es algebraica 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 las redes algebraicas, se pueden describir "sintácticamente" a través de los sistemas de información de Scott .

Complementos y pseudocomplementos

Sea una red acotada con mayor elemento 1 y mínimo elemento 0. Dos elementos y de son complementarios entre sí si y solo si: ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle L}$

$${\displaystyle x\vee y=1\quad {\text{ and }}\quad x\wedge y=0.}$$

En general, algunos elementos de una red acotada pueden no tener complemento y otros pueden tener más de un complemento. Por ejemplo, el conjunto con su orden habitual es un entramado acotado y no tiene complemento. En la red acotada N ₅ , el elemento tiene dos complementos, a saber. y (ver Imagen 11). Una red acotada para la cual cada elemento tiene un complemento se llama red complementada . ${\displaystyle \{0,1/2,1\}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$

Una red complementada que también es distributiva es un álgebra de Boole . Para una red distributiva, el complemento de cuando existe es único. ${\displaystyle x,}$

En el caso de que el complemento sea único, escribimos y de manera equivalente, La operación unaria correspondiente, llamada complementación, introduce un análogo de la negación lógica en la teoría de celosías. ${\textstyle \lnot x=y}$ ${\textstyle \lnot y=x.}$ ${\displaystyle L,}$

Las álgebras de Heyting son un ejemplo de redes distributivas en las que algunos miembros pueden carecer de complementos. Cada elemento de un álgebra de Heyting tiene, por otro lado, un pseudocomplemento , también denominado El pseudocomplemento es el mayor elemento tal que Si el pseudocomplemento de cada elemento de un álgebra de Heyting es de hecho un complemento, entonces el El álgebra de Heyting es, de hecho, un álgebra de Boole. ${\displaystyle z}$ ${\textstyle \lnot x.}$ ${\displaystyle y}$ ${\displaystyle x\wedge y=0.}$

Condición de la cadena Jordan-Dedekind

Una cadena desde hasta 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 a todos. ${\displaystyle x_{0}}$ ${\displaystyle x_{n}}$ ${\displaystyle \left\{x_{0},x_{1},\ldots ,x_{n}\right\},}$ ${\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}.}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i-1}}$ ${\displaystyle 1\leq i\leq n.}$

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

Calificado/clasificado

Una celosía se llama graduada , a veces clasificada (pero consulte Poset clasificado para un significado alternativo), si a veces puede equiparse con una función de clasificación , compatible con el orden (por lo tanto, siempre ) de modo que siempre cubra entonces El valor de la función de clasificación para un elemento reticular se llama rango . ${\displaystyle (L,\leq )}$ ${\displaystyle r:L\to \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle r(x)<r(y)}$ ${\displaystyle x<y}$ ${\displaystyle y}$ ${\displaystyle x,}$ ${\displaystyle r(y)=r(x)+1.}$

Se dice que un elemento reticular cubre otro elemento si no existe uno tal que Aquí, significa y ${\displaystyle y}$ ${\displaystyle x,}$ ${\displaystyle y>x,}$ ${\displaystyle z}$ ${\displaystyle y>z>x.}$ ${\displaystyle y>x}$ ${\displaystyle x\leq y}$ ${\displaystyle x\neq y.}$

celosías libres

Se puede utilizar cualquier conjunto para generar la semired libre. La semired libre se define como compuesta por todos los subconjuntos finitos de con la operación de semired dada por la unión de conjuntos ordinarios . La semired libre tiene la propiedad universal . Para la red libre sobre un conjunto, Whitman dio una construcción basada en polinomios sobre los miembros de ' s. ^{[10] [11]} ${\displaystyle X}$ ${\displaystyle FX.}$ ${\displaystyle X,}$ ${\displaystyle X,}$ ${\displaystyle X}$

Nociones importantes de la teoría de celosías

Ahora definimos algunas nociones de teoría del orden de importancia para la teoría de redes. En lo siguiente, sea un elemento de alguna red que se llame: ${\displaystyle x}$ ${\displaystyle L.}$ ${\displaystyle x}$

• Unirse irreducible si implica para todos Si tiene un elemento inferior que algunos autores requieren . ^[12] Cuando la primera condición se generaliza a uniones arbitrarias se denomina unión completamente irreducible (o -irreducible). La noción dual es cumplir irreductibilidad ( -irreductible). Por ejemplo, en Pic. 2, los elementos 2, 3, 4 y 5 son irreducibles, mientras que 12, 15, 20 y 30 son irreducibles. Dependiendo de la definición, el elemento inferior 1 y el elemento superior 60 pueden considerarse o no unirse irreducibles y unirse irreducibles, respectivamente. En la red de números reales con el orden habitual, cada elemento es irreducible, pero ninguno es completamente irreducible. ${\displaystyle x=a\vee b}$ ${\displaystyle x=a{\text{ or }}x=b.}$ ${\displaystyle a,b\in L.}$ ${\displaystyle L}$ ${\displaystyle 0,}$ ${\displaystyle x\neq 0}$ ${\displaystyle \bigvee _{i\in I}a_{i},}$ ${\displaystyle x}$ ${\displaystyle \vee }$ ${\displaystyle \wedge }$
• Unirse a primo si implica De nuevo, algunos autores requieren , aunque esto es inusual. ^[13] Esto también se puede generalizar para obtener la noción de unión completa de primos . La noción dual es satisfacer prima . Cada elemento de unión principal también es irreducible de unión, y cada elemento de unión principal también es irreducible de unión. Lo contrario se cumple si es distributivo. ${\displaystyle x\leq a\vee b}$ ${\displaystyle x\leq a{\text{ or }}x\leq b.}$ ${\displaystyle x\neq 0}$ ${\displaystyle L}$

Tengamos un elemento inferior 0. Un elemento de es un átomo si y no existe ningún elemento tal que Entonces se llame: ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle 0<x}$ ${\displaystyle y\in L}$ ${\displaystyle 0<y<x.}$ ${\displaystyle L}$

• Atómico si por cada elemento distinto de cero existe un átomo tal que ^[14] ${\displaystyle x}$ ${\displaystyle L,}$ ${\displaystyle a}$ ${\displaystyle L}$ ${\displaystyle a\leq x;}$
• Atomístico si cada elemento de es un supremo de átomos. ^[15] ${\displaystyle L}$

Sin embargo, muchas fuentes y comunidades matemáticas utilizan el término "atómico" en el sentido de "atomista" como se define anteriormente. ^{[ cita necesaria ]}

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 tanto, son importantes para la teoría de redes. Los detalles se pueden encontrar en las entradas respectivas.

Ver también

• Únase y conozca  – Concepto en teoría del orden
• Mapa de celosías  – Concepto en matemáticas
• Red ortocomplementada
• Orden total  : orden cuyos elementos son todos comparables
• Ideal : subconjunto y filtro  no vacíos, con límite superior y cerrado hacia abajo (nociones duales)
• Celosía sesgada  : estructura algebraica Pages displaying wikidata descriptions as a fallback(generalización para unión y encuentro no conmutativo)
• celosía euleriana
• Red de Post  : red de todos los clones (conjuntos de conectivos lógicos cerrados bajo composición y que contienen todas las proyecciones) en un conjunto de dos elementos {0, 1}, ordenados por inclusiónPages displaying wikidata descriptions as a fallback
• Red de Tamari  : objeto matemático formado por un orden en la forma de poner entre paréntesis una expresiónPages displaying wikidata descriptions as a fallback
• Red de Young-Fibonacci
• 0,1-red simple

Aplicaciones que utilizan la teoría de la red

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

• Topología inútil
• 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 la lógica de primer orden
• Semántica de los 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

1. Grätzer 2003, pag. 52.
2. Birkhoff 1948, pag. 18. "desde y dualmente". Birkhoff atribuye esto a Dedekind 1897, p. 8 ${\displaystyle a=a\vee (a\wedge (a\vee a))=a\vee a}$
3. Burris, Stanley N. y Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN  3-540-90578-2 .
4. Panadero, Kirby (2010). «Celosías Completas» (PDF) . Departamento de Matemáticas de UCLA . Consultado el 8 de junio de 2022 .
5. Kaplansky, Irving (1972). Teoría de conjuntos y espacios métricos (2ª ed.). Ciudad de Nueva York: AMS Chelsea Publishing . pag. 14.ISBN _ 9780821826942.
6. Davey y Priestley (2002), Ejercicio 4.1, pág. 104.
7. Davey y Priestley (2002), Teorema 4.10, p. 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). "Celosías libres I". Anales de Matemáticas . 42 (1): 325–329. doi :10.2307/1969001. JSTOR  1969001.
11. Philip Whitman (1942). "Celosías libres 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 compactaciones de Hausdorff . Celosías Continuas. vol. 871, págs. 159-208. doi :10.1007/BFb0089907.
14. Grätzer 2003, pag. 246, Ejercicio 3.
15. Grätzer 2003, pag. 234, después de Def.1.

Referencias

Monografías disponibles gratis online:

• Burris, Stanley N. y Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN 3-540-90578-2 . 
• Jipsen, Peter y Henry Rose, Variedades de celosías , Apuntes de conferencias de matemáticas 1533, Springer Verlag, 1992. ISBN 0-387-56314-8 . 

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

• Donnellan, Thomas, 1968. Teoría del entramado . Pérgamo.
• Grätzer, George , 1971. Teoría de la red: primeros conceptos y redes distributivas . WH Freeman.

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

• Davey, Licenciatura en Letras; Priestley, HA (2002), Introducción a las celosías y al orden , Cambridge University Press , ISBN 978-0-521-78451-1

Monografías avanzadas:

• Garrett Birkhoff , 1967. Teoría del entramado , 3ª ed. vol. 25 de las publicaciones del coloquio de 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 (2003). Teoría general de la red (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 red:

• Štĕpánka Bilová (2001). Eduard Fuchs (ed.). Teoría de la red: su nacimiento y vida (PDF) . Prometeo. págs. 250–257.
• Birkhoff, Garrett (1948). Teoría de la celosía (2ª ed.).Libro de texto con numerosas atribuciones en las notas a pie de página.
• Schlimm, Dirk (noviembre de 2011). "Sobre el papel creativo de la axiomática. El descubrimiento de las celosías por Schröder, Dedekind, Birkhoff y otros". Síntesis . 183 (1): 47–68. CiteSeerX  10.1.1.594.8898 . doi :10.1007/s11229-009-9667-9. S2CID  11012081.Resumen de la historia de las celosías.
• Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler" (PDF) , Braunschweiger Festschrift , doi : 10.24355/dbbs.084-200908140200-2

Sobre aplicaciones de la teoría de la red:

• Garrett Birkhoff (1967). James C. Abad (ed.). ¿Qué puede hacer Lattices por usted? . Van Nostrand.Tabla de contenido

enlaces externos

• "Grupo ordenado en celosía", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Enrejado". MundoMatemático .
• JB Nation, Notes on Lattice Theory, notas del curso, revisado en 2017.
• Ralph Freese, "Página de inicio de la teoría del entramado".
• Secuencia OEIS A006966 (Número de redes sin etiquetar con n elementos)