Red (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 cota superior mínima o unión ) y un ínfimo único (también llamado cota inferior máxima o intersección ). 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 retículas también pueden caracterizarse como estructuras algebraicas que satisfacen ciertas identidades axiomáticas . Dado que ambas definiciones son equivalentes, la teoría de retículas se basa tanto en la teoría del orden como en el álgebra universal . La clase de retículas puede generalizarse a semirretículas , y algunas subclases notables de retículas son las álgebras de Heyting , las álgebras booleanas , las retículas distributivas y las retículas geométricas ( matroides ). Todas estas estructuras reticulares admiten descripciones tanto algebraicas como basadas en la teoría del orden .

El subcampo que estudia las redes se llama teoría de redes .

Una red puede definirse bien desde el punto de vista de la teoría del orden, como un conjunto parcialmente ordenado, o bien como una estructura algebraica.

Una red acotada es una red que además tiene un elemento máximo ( también llamado elemento superior , y denotado por${\displaystyle 1}$o${\displaystyle \top }$) y un elemento mínimo (también llamado mínimo o fondo , denotado por${\displaystyle 0}$o${\displaystyle \bot }$), que satisfacen $${\displaystyle 0\leq x\leq 1\;{\text{ for every }}x\in L.}$$

Un retículo acotado también puede definirse como una estructura algebraica de la forma${\displaystyle (L,\vee ,\wedge ,0,1)}$de tal manera que${\displaystyle (L,\vee ,\wedge )}$es una red,${\displaystyle 0}$(la parte inferior de la red) es el elemento identidad para la operación de unión.${\displaystyle \vee ,}$y${\displaystyle 1}$(la parte superior de la red) es el elemento identidad para la operación de intersección.${\displaystyle \wedge .}$$${\displaystyle a\vee 0=a}$$$${\displaystyle a\wedge 1=a}$$

Se puede demostrar que 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 una intersección.

Cada retículo puede incrustarse en un retículo acotado añadiendo un elemento máximo y un elemento mínimo. Además, todo retículo finito no vacío es acotado, tomando la unión (respectivamente, intersección) de todos los elementos, denotada por${\textstyle 1=\bigvee L=a_{1}\lor \cdots \lor a_{n}}$(respectivamente${\textstyle 0=\bigwedge L=a_{1}\land \cdots \land a_{n}}$) dónde${\displaystyle L=\left\{a_{1},\ldots ,a_{n}\right\}}$es el conjunto de todos los elementos.

Los retículos guardan cierta relación con la familia de estructuras algebraicas de tipo grupo . Dado que las operaciones de intersección y unión conmutan y asocian, un retículo puede considerarse como la suma de dos semigrupos conmutativos con el mismo dominio. En el caso de un retículo acotado, estos semigrupos son, de hecho, monoides conmutativos . La ley de absorción es la única identidad definitoria propia de la teoría de retículos. Un retículo acotado también puede concebirse como una estructura conmutativa sin el axioma distributivo.

Por conmutatividad, asociatividad e idempotencia se puede pensar en unir y encontrar como operaciones sobre conjuntos finitos no vacíos, en lugar de sobre pares de elementos. En un retículo acotado, la unión y el encuentro del conjunto vacío también se pueden definir (como${\displaystyle 0}$y${\displaystyle 1,}$respectivamente). Esto hace que las retículas acotadas sean algo más naturales que las retículas generales, y muchos autores exigen que todas las retículas sean acotadas.

La interpretación algebraica de los retículos juega un papel esencial en el álgebra universal .

• 
  Imagen  1: Subconjuntos de${\displaystyle \{x,y,z\},}$bajo inclusión de conjuntos . El nombre "retículo" está sugerido por la forma del diagrama de Hasse que lo representa.
• 
  Imagen  2: Retículo de divisores enteros de 60, ordenados por " divide ".
• 
  Imagen  3: Retículo de particiones de${\displaystyle \{1,2,3,4\},}$ordenado por " refina ".
• 
  Imagen  4: Retículo de enteros positivos, ordenados por${\displaystyle \,\leq ,}$
• 
  Imagen  5: Retículo de pares de enteros no negativos, ordenados componente a componente.

• Para cualquier conjunto${\displaystyle A,}$la colección de todos los subconjuntos de${\displaystyle A}$(llamado el conjunto potencia de${\displaystyle A}$) se puede ordenar mediante la inclusión de subconjuntos para obtener una red acotada por${\displaystyle A}$el conjunto mismo y el conjunto vacío. En este retículo, el supremo viene dado por la unión de conjuntos y el ínfimo por la intersección de conjuntos (véase la figura  1).
• Para cualquier conjunto${\displaystyle A,}$la colección de todos los subconjuntos finitos de${\displaystyle A,}$ordenado por inclusión, también es un retículo, y estará acotado si y solo si${\displaystyle A}$es finito.
• Para cualquier conjunto${\displaystyle A,}$la colección de todas las particiones de${\displaystyle A,}$ordenado por refinamiento , es una red (ver Fig.  3).
• Los enteros positivos, en su orden habitual, forman una red ilimitada bajo las operaciones de "mínimo" y "máximo". El 1 es el mínimo; no hay máximo (véase la figura  4).
• El cuadrado cartesiano de los números naturales, ordenado de tal manera que${\displaystyle (a,b)\leq (c,d)}$si${\displaystyle a\leq c{\text{ and }}b\leq d.}$La pareja${\displaystyle (0,0)}$es el elemento inferior; no hay parte superior (ver Fig.  5).
• Los números naturales también forman una red 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:${\displaystyle a\leq b}$si${\displaystyle a}$divide${\displaystyle b.}$${\displaystyle 1}$es el fondo;${\displaystyle 0}$es la parte superior. La imagen  2 muestra una subred finita.
• Toda red completa (véase también más abajo ) es una red acotada (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 definen restringiendo las operaciones respectivas 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 retículos completos se estudian en la teoría de dominios .

A continuación se proporcionan ejemplos adicionales de redes para cada una de las propiedades adicionales que se analizan.

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

• Un poset discreto, es decir, un poset tal que${\displaystyle x\leq y}$implica${\displaystyle x=y,}$Un retículo es un retículo si y solo si tiene como máximo un elemento. En particular, el conjunto parcialmente ordenado discreto de dos elementos no es un retículo.
• Aunque el conjunto${\displaystyle \{1,2,3,6\}}$parcialmente ordenado por divisibilidad es un retículo, el conjunto${\displaystyle \{1,2,3\}}$Por lo tanto, ordenado no es un retículo porque al par 2, 3 le falta una unión; de manera similar, a 2, 3 le falta una intersección en${\displaystyle \{2,3,6\}.}$
• El conjunto${\displaystyle \{1,2,3,12,18,36\}}$Un retículo 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: 12, 18 y 36, ninguno de los cuales es el menor de los tres según la divisibilidad (12 y 18 no se dividen entre sí). De igual manera, el par 12, 18 tiene tres límites inferiores: 1, 2 y 3, ninguno de los cuales es el mayor de los tres según la divisibilidad (2 y 3 no se dividen entre sí).

La noción apropiada de un morfismo entre dos retículos se deriva fácilmente de la definición algebraica anterior . Dados dos retículos${\displaystyle \left(L,\vee _{L},\wedge _{L}\right)}$y${\displaystyle \left(M,\vee _{M},\wedge _{M}\right),}$un homomorfismo reticular de L a M es una función${\displaystyle f:L\to M}$de tal manera que para todos${\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).}$$

De este modo${\displaystyle f}$es un homomorfismo de las dos semirretículas subyacentes . Cuando se consideran retículas con más estructura, los morfismos también deben "respetar" la estructura adicional. En particular, un homomorfismo de retícula acotada (generalmente llamado simplemente "homomorfismo de retícula")${\displaystyle f}$entre dos retículos acotados${\displaystyle L}$y${\displaystyle M}$También debería tener la siguiente propiedad: $${\displaystyle f\left(0_{L}\right)=0_{M},{\text{ and }}}$$$${\displaystyle f\left(1_{L}\right)=1_{M}.}$$

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

Todo homomorfismo de retículos es necesariamente monótono con respecto a la relación de orden asociada; véase Función que preserva el límite. Lo contrario no es cierto: la monotonicidad no implica en absoluto la preservación requerida de las intersecciones y uniones (véase la figura  9), aunque una biyección que preserva el orden es un homomorfismo si su inversa también lo preserva.

Dada la definición estándar de isomorfismos como morfismos invertibles, un isomorfismo de retículos es simplemente un homomorfismo de retículos biyectivo . De manera similar, un endomorfismo de retículos es un homomorfismo de retículos de un retículo a sí mismo, y un automorfismo de retículos es un endomorfismo de retículos biyectivo. Los retículos y sus homomorfismos forman una categoría .

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

Una subred de una red${\displaystyle L}$es un subconjunto de${\displaystyle L}$que es una red con las mismas operaciones de encuentro y unión que${\displaystyle L.}$ Es decir, si${\displaystyle L}$es una red y${\displaystyle M}$es un subconjunto de${\displaystyle L}$de tal manera que para cada par de elementos${\displaystyle a,b\in M}$ambos${\displaystyle a\wedge b}$y${\displaystyle a\vee b}$están en${\displaystyle M,}$entonces${\displaystyle M}$es una subred de${\displaystyle L.}$^{[ 3 ]}

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

A continuación, presentamos una serie de propiedades importantes que dan lugar a interesantes clases especiales de retículos. Una de ellas, la acotación, ya se ha tratado.

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

Cualquier conjunto${\displaystyle X}$puede utilizarse para generar la semirretícula libre${\displaystyle FX.}$El semirretículo libre se define como compuesto por todos los subconjuntos finitos de${\displaystyle X,}$con la operación de semirretículo dada por la unión de conjuntos ordinaria . El semirretículo libre tiene la propiedad universal . Para el retículo libre sobre un conjunto${\displaystyle X,}$Whitman propuso una construcción basada en polinomios sobre${\displaystyle X}$miembros de . ^{[ 13 ] [ 14 ]}

Cualquier conjunto (generalmente de varios elementos)${\displaystyle X}$También puede utilizarse para definir un retículo plano , el retículo más pequeño en el que los elementos del conjunto son incomparables o, equivalentemente, el retículo de rango 3 donde${\displaystyle X}$es precisamente el conjunto de elementos de rango intermedio. ^{[ 15 ]}

Ahora definimos algunas nociones de teoría del orden importantes para la teoría de retículos. En lo que sigue, sea${\displaystyle x}$ser un elemento de alguna red${\displaystyle L.}$${\displaystyle x}$se llama:

• Unir irreducible si${\displaystyle x=a\vee b}$implica${\displaystyle x=a{\text{ or }}x=b.}$a pesar de${\displaystyle a,b\in L.}$Si${\displaystyle L}$tiene un elemento inferior${\displaystyle 0,}$algunos autores requieren${\displaystyle x\neq 0}$. ^{[ 16 ]} Cuando la primera condición se generaliza a uniones arbitrarias${\displaystyle \bigvee _{i\in I}a_{i},}$${\displaystyle x}$se llama unión completamente irreducible (o${\displaystyle \vee }$-irreducible). La noción dual es encontrarse con la irreductibilidad (${\displaystyle \wedge }$-irreducible). Por ejemplo, en la Fig.  2, los elementos 2, 3, 4 y 5 son irreducibles por unión, mientras que 12, 15, 20 y 30 son irreducibles por intersección. Según la definición, el elemento inferior 1 y el elemento superior 60 pueden o no ser considerados irreducibles por unión e irreducibles por intersección, respectivamente. En el retículo de números reales con el orden usual, cada elemento es irreducible por unión, pero ninguno es completamente irreducible por unión.
• Únete a Prime si${\displaystyle x\leq a\vee b}$implica${\displaystyle x\leq a{\text{ or }}x\leq b.}$Nuevamente, algunos autores requieren${\displaystyle x\neq 0}$, aunque esto es inusual. ^{[ 17 ]} Esto también se puede generalizar para obtener la noción de unión prima completa . La noción dual es encuentro prima . Todo elemento de unión prima es también irreducible de unión, y todo elemento de encuentro prima es también irreducible de encuentro. Lo contrario se cumple si${\displaystyle L}$es distributiva.

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

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

Sin embargo, muchas fuentes y comunidades matemáticas utilizan el término "atómico" para referirse a "atomístico" tal como se definió anteriormente.

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. Encontrará más detalles en las entradas correspondientes.

• Únete y reúnete – Concepto en teoría del orden 
• Mapa de retículos : concepto en matemáticas 
• Retículo ortocomplementado : Retículo ligado en el que cada elemento tiene un complemento. Páginas que muestran breves descripciones de destinos de redirección. 
• Pedido total : pedido cuyos elementos son todos comparables. 
• Ideal : subconjunto y filtro no vacío, acotado superiormente y cerrado inferiormente (nociones duales). 
• Retículo sesgado (generalización a la unión y encuentro no conmutativos)
• red euleriana
• Retículo de Post – Retículo en álgebra universal 
• Retículo de Tamari – Estructura algebraica 
• Red de Young-Fibonacci : estructura en secuencias de dígitos 1 y 2. 
• Red simple 0,1