Retícula (teoría da orde)

Relacións binarias transitivas v c e
Simétrica Antisimétrica Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Relación de equivalencia  Si  Non  Non  Non  Non  Non  Si  Non  Non Preorde (Cuasiorde)  Non  Non  Non  Non  Non  Non  Si  Non  Non Orde parcial  Non  Si  Non  Non  Non  Non  Si  Non  Non Preorde total  Non  Non  Si  Non  Non  Non  Si  Non  Non Orde total  Non  Si  Si  Non  Non  Non  Si  Non  Non Pre-Ben ordenada  Non  Non  Si  Si  Non  Non  Si  Non  Non Cuasi-Ben ordenada  Non  Non  Non  Si  Non  Non  Si  Non  Non Ben ordenada  Non  Si  Si  Si  Non  Non  Si  Non  Non Retícula  Non  Si  Non  Non  Si  Si  Si  Non  Non Semiretícula superior (join)  Non  Si  Non  Non  Si  Non  Si  Non  Non Semiretícula inferior (meet)  Non  Si  Non  Non  Non  Si  Si  Non  Non Orde estrita parcial  Non  Si  Non  Non  Non  Non  Non  Si  Si Orde estrita feble  Non  Si  Non  Non  Non  Non  Non  Si  Si Orde estrita total  Non  Si  Si  Non  Non  Non  Non  Si  Si Simétrica Antisimétrica Conexa Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica Definicións, para todo ${\displaystyle a,b}$ e ${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{non }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}}$
Si indica que a columna da propiedade é sempre verdadeira no termo da fila (na esquerda de todo), mentres que  Non indica que a propiedade non está garantida en xeral (pode cumprirse ou non). Por exemplo, toda relación de equivalencia é simétrica, mais non necesariamente antisimétrica, está indicada por  Si na columna "Simétrica" e  Non na columna "Antisimétrica". Todas as definicións requiren tacitamente que a relación homoxénea ${\displaystyle R}$ sexa transitiva: para todo ${\displaystyle a,b,c,}$ se ${\displaystyle aRb}$ e ${\displaystyle bRc}$ entón ${\displaystyle aRc.}$ Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.

Unha retícula (en inglés lattice) é unha estrutura abstracta estudada nas subdisciplinas matemáticas da teoría da orde e da álxebra abstracta. Consiste nun conxunto parcialmente ordenado no que cada par de elementos ten un supremo único (tamén chamado límite superior mínimo ou join) e un ínfimo único (tamén chamado límite inferior máximo ou meet). Un exemplo é o conxunto de partes dun conxunto, parcialmente ordenado por inclusión, para o cal o supremo é a unión e o ínfimo é a intersección. Outro exemplo son os números naturais, parcialmente ordenados pola divisibilidade, para os que o supremo é o mínimo común múltiplo e o ínfimo é o máximo común divisor.

Unha retícula pode definirse tanto na teoría da orde como un conxunto parcialmente ordenado ou como unha estrutura alxébrica.

Un conxunto parcialmente ordenado (poset) ${\displaystyle (L,\leq )}$ chámase retícula se é á vez unha semiretícula join e meet, é dicir, cada subconxunto de dous elementos ${\displaystyle \{a,b\}\subseteq L}$ ten unha join (é dicir, límite superior mínimo, denotado por ${\displaystyle a\vee b}$ ) e dualmente un meet (é dicir, límite inferior máximo, denotado por ${\displaystyle a\wedge b}$). Esta definición fai ${\displaystyle \,\wedge \,}$ e ${\displaystyle \,\vee \,}$ operacións binarias. Ambas as operacións son monótonas en relación á orde dada: ${\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}}$ e ${\displaystyle a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}.}$

Unha retícula é unha estrutura alxébrica ${\displaystyle (L,\vee ,\wedge )}$, composta por un conxunto ${\displaystyle L}$ e dúas operacións binarias, conmutativas e asociativas ${\displaystyle \vee }$ e ${\displaystyle \wedge }$ en ${\displaystyle L}$ satisfacendo as seguintes identidades axiomáticas para todos os elementos ${\displaystyle a,b\in L}$ (ás veces chamadas leis de absorción): $${\displaystyle a\vee (a\wedge b)=a}$$$${\displaystyle a\wedge (a\vee b)=a}$$

As dúas identidades seguintes tamén son consideradas como axiomas, aínda que se deducen das dúas leis de absorción anteriores.^[1] Estas son as chamadas leis de idempotencia . $${\displaystyle a\vee a=a}$$$${\displaystyle a\wedge a=a}$$

Unha retícula limitada é unha retícula que ten a maiores un elemento maior (denotado por ${\displaystyle 1,}$ ou por ${\displaystyle \top }$) e un elemento menor(denotado por ${\displaystyle 0}$ ou por ${\displaystyle \bot }$), que satisfán $${\displaystyle 0\leq x\leq 1\;{\text{ para todo }}x\in L.}$$

Unha retícula limitada tamén se pode definir como unha estrutura alxébrica da forma ${\displaystyle (L,\vee ,\wedge ,0,1)}$ tal que ${\displaystyle (L,\vee ,\wedge )}$ é unha retícula, ${\displaystyle 0}$ (o elemento menor) é o elemento identidade para a operación join ${\displaystyle \vee ,}$ e ${\displaystyle 1}$ (o elemento maior) é o elemento identidade para a operación meet ${\displaystyle \wedge .}$$${\displaystyle a\vee 0=a.}$$$${\displaystyle a\wedge 1=a.}$$

Un conxunto parcialmente ordenado é unha retícula limitada se e só se cada conxunto finito de elementos (incluíndo o conxunto baleiro) ten un join e un meet.

Toda retícula pode ser mergullada nunha retícula limitada engadindo un elemento maior e un menor. A maiores, toda retícula finita non baleira está limitada, tomando o join (respectivamente o meet) de todos os elementos, denotado por ${\textstyle 1=\bigvee L=a_{1}\lor \cdots \lor a_{n}}$ (respectivamente ${\textstyle 0=\bigwedge L=a_{1}\land \cdots \land a_{n}}$ ) onde ${\displaystyle L=\left\{a_{1},\ldots ,a_{n}\right\}}$ é o conxunto de todos os elementos.

As retículas teñen algunhas conexións coa familia de estruturas alxébricas de tipo grupo. Debido a que o join e o meet teñen a propiedade conmuttiva e asociativa, unha retícula pode ser vista como dous semigrupos conmutativos que teñen o mesmo dominio. Para unha retícula limitada, estes semigrupos son de feito monoides conmutativos. A lei de absorción é a única identidade definitoria que é propia da teoría de retículas. Unha retícula limitada tamén se pode pensar como un semianel conmutativo sen o axioma distributivo.

• 
  Imaxe.1: Subsconxuntos de ${\displaystyle \{x,y,z\},}$ baixo a inclusión de conxuntos.
• 
  Imaxe.2: Retícula de enteiros divisores de 60, ordenados por "divide a".
• 
  Imaxe.3: Reticula de particións de ${\displaystyle \{1,2,3,4\},}$ ordenado por "refina".
• 
  Imaxe.4:Retícula de enteiros positivos, ordenados por ${\displaystyle \,\leq ,}$
• 
  Imaxe.5: Retícula de pares de enteiros non negativos, ordenados compoñente a compoñente.

A noción apropiada dun morfismo entre dúas retículas flúe facilmente da definición alxébrica dada previamente na parte superior do artigo. Dadas dúas retículas ${\displaystyle \left(L,\vee _{L},\wedge _{L}\right)}$ e ${\displaystyle \left(M,\vee _{M},\wedge _{M}\right),}$ un homomorfismo reticular de L a M é unha función ${\displaystyle f:L\to M}$ tal que para todos os ${\displaystyle a,b\in L:}$$${\displaystyle f\left(a\vee _{L}b\right)=f(a)\vee _{M}f(b),{\text{ e mesmo }}}$$$${\displaystyle f\left(a\wedge _{L}b\right)=f(a)\wedge _{M}f(b).}$$

En particular, un homomorfismo de retícula limitada (xeralmente chamado só "homomorfismo de retícula") ${\displaystyle f}$ entre dúas retículas limitadas ${\displaystyle L}$ e ${\displaystyle M}$ tamén debe ter as seguintes propiedades: $${\displaystyle f\left(0_{L}\right)=0_{M},{\text{ e }}}$$$${\displaystyle f\left(1_{L}\right)=1_{M}.}$$

Unha subretícula dunha retícula ${\displaystyle L}$ é un subconxunto de ${\displaystyle L}$ que é unha retícula coas mesmas operacións de join e meet que ${\displaystyle L.}$ É dicir, se ${\displaystyle L}$ é unha retícula e ${\displaystyle M}$ é un subconxunto de ${\displaystyle L}$ tal que para cada par de elementos ${\displaystyle a,b\in M}$ ambos os ${\displaystyle a\wedge b}$ e ${\displaystyle a\vee b}$ están en ${\displaystyle M,}$ entón ${\displaystyle M}$ é unha subretícula de ${\displaystyle L.}$^[2]

Unha subretícula ${\displaystyle M}$ dunha retícula ${\displaystyle L}$ é unha retícula convexa de ${\displaystyle L,}$ se ${\displaystyle x\leq z\leq y}$ e ${\displaystyle x,y\in M}$ implica que ${\displaystyle z}$ pertence a ${\displaystyle M,}$ para todos os elementos ${\displaystyle x,y,z\in L.}$

Agora introducimos unha serie de propiedades importantes que levan a clases especiais interesantes das retículas. Unha delas xa foi tratada co concepto de limitada.

Un poset chámase retícula completa se todos os seus subconxuntos teñen un join e un meet. En particular, toda retícula completa é unha retícula limitada. Mentres que os homomorfismos de retículas limitadas en xeral só conservan os joins e os meets finitos, para os homomorfismos de retículas completas é necesario preservar joins e meets arbitrarios.

"Reticula parcial" non é o contrario de "retícula completa"; máis ben, "retícula parcial", "retícula" e "retícula completa" son definicións cada vez máis restritivas.

Unha retícula condicionalmente completa é unha retícula na que cada subconxunto non baleiro que ten un límite superior ten un join (é dicir, un límite superior mínimo). Esas retículas proporcionan a xeneralización máis directa do axioma de completude dos números reais. Unha retícula condicionalmente completa é unha retícula completa ou unha retícula completa sen o seu elemento máximo ${\displaystyle 1,}$ o seu elemento mínimo ${\displaystyle 0,}$ ou sen ambos os dous.^[3][4]

Dado que as retícula veñen con dúas operacións binarias, é natural preguntarse se unha delas se distribúe sobre a outra, é dicir, se unha ou outra das seguintes leis duais cúmprese para cada tres elementos. ${\displaystyle a,b,c\in L,}$ :

Distributividade de ${\displaystyle \vee }$ sobre ${\displaystyle \wedge }$

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

Distributividade de ${\displaystyle \wedge }$ sobre ${\displaystyle \vee }$

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

Unha retícula que satisfai o primeiro ou o segundo axioma, chámase retícula distributiva. As únicas retículas non distributivas con menos de 6 elementos chámanse M₃ e N₅;^[5] móstranse nas imaxes 10 e 11, respectivamente. Unha retícula é distributiva se e só se non ten unha subretícula isomorfa a M₃ ou N₅.^[6] Cada retícula distributiva é isomorfa a unha retícula de conxuntos (con unión e intersección como join e meet, respectivamente). ^[7]

Para algunhas aplicacións a condición de distributividade é demasiado forte, e a seguinte propiedade máis débil adoita ser útil. Unha retícula ${\displaystyle (L,\vee ,\wedge )}$ é modular se, para todos os elementos ${\displaystyle a,b,c\in L,}$ ten a seguinte identidade: ${\displaystyle (a\wedge c)\vee (b\wedge c)=((a\wedge c)\vee b)\wedge c.}$ (Identidade modular)Esta condición é equivalente ao seguinte axioma: ${\displaystyle a\leq c}$ implica ${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge c.}$ (Lei modular)Unha retícula é modular se e só se non ten unha subretículas isomorfas a N₅ (mostrada na Fig. 11).^[6] A maiores das retículas distributivas, exemplos de retículas modulares son as retículas de submódulos dun módulo (polo tanto, modular), a retícula de ideais bilaterais dun anel e a retícula de subgrupos normais dun grupo.

Unha retícula finita é modular se e só se é semimodular tanto superiormente como inferiormente. Para unha retícula graduada, a semimodularidade (superior) é equivalente á seguinte condición na función de rango ${\displaystyle r\colon }$

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

Na teoría de dominios, é natural buscar aproximar os elementos nunha orde parcial mediante elementos "moito máis simples". Isto leva á clase de posets continuos, que consiste en posets onde todo elemento se pode obter como o supremo dun conxunto dirixido de elementos que están moi por debaixo do elemento. Se se pode restrinxir adicionalmente estes aos elementos compactos dun poset para obter estes conxuntos dirixidos, entón o poset é mesmo alxébrico. Ambos os conceptos pódense aplicar ás retículas do seguinte xeito:

• Unha retícula continua é unha retícula completa que é continua como poset.
• Unha retícula alxébrica é unha retícula completa que é alxébrica como poset.

Sexa ${\displaystyle L}$ unha retícula limitada co elemento maior 1 e o elemento menor 0. Dous elementos ${\displaystyle x}$ e ${\displaystyle y}$ de ${\displaystyle L}$ son complementos entre si, se e só se: $${\displaystyle x\vee y=1\quad {\text{ e }}\quad x\wedge y=0.}$$

Unha cadea de ${\displaystyle x_{0}}$ a ${\displaystyle x_{n}}$ é un conxunto ${\displaystyle \left\{x_{0},x_{1},\ldots ,x_{n}\right\},}$ onde ${\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}.}$ A lonxitude desta cadea é n, ou un menos que o seu número de elementos. Unha cadea é máximal se ${\displaystyle x_{i}}$ cubre ${\displaystyle x_{i-1}}$ para todos os ${\displaystyle 1\leq i\leq n.}$

Se para calquera par, ${\displaystyle x}$ e ${\displaystyle y,}$ onde ${\displaystyle x<y,}$ todas as cadeas maximais de ${\displaystyle x}$ a ${\displaystyle y}$ teñen a mesma lonxitude, entón dise que a retícula satisfai a condición da cadea de Jordan-Dedekind.

Definimos agora algunhas nocións da teoría da orde importantes para a teoría de retículas. No seguinte, denominamos como ${\displaystyle x}$ un elemento dalgunha retícula ${\displaystyle L.}$ Así ${\displaystyle x}$ chámase:

• Join irreducíbel se ${\displaystyle x=a\vee b}$ implica ${\displaystyle x=a{\text{ ou }}x=b.}$ para todos os ${\displaystyle a,b\in L.}$ Se ${\displaystyle L}$ ten un elemento menor ${\displaystyle 0,}$ algúns autores requiren ${\displaystyle x\neq 0}$.^[8] Cando a primeira condición se xeneraliza a joins arbitrarios ${\displaystyle \bigvee _{i\in I}a_{i},}$ ${\displaystyle x}$ chámase join completamente irreducíbel (ou ${\displaystyle \vee }$-irreducíbel). A noción dual é meet irreducíbel (${\displaystyle \wedge }$-irreducíbel). Por exemplo, na imaxe.2, os elementos 2, 3, 4 e 5 son join irreducíbeis, mentres que 12, 15, 20 e 30 son meet irreducibeis. Dependendo da definición, o elemento menor 1 e o elemento maior 60 poden considerarse ou non join irreducíbeis e meet irreducíbeis respectivamente. Na retícula de números reais coa orde habitual, cada elemento é join irreducíbele mais ningún é completamente join irreducíbel.
• Join primo se ${\displaystyle x\leq a\vee b}$ implica ${\displaystyle x\leq a{\text{ ou }}x\leq b.}$ De novo algúns autores requiren ${\displaystyle x\neq 0}$, aínda que isto é infrecuente. Isto tamén se pode xeneralizar para obter a noción join completamente primo. A noción dual é meet primo. Todo elemento join primo tamén é join irreducíbel, e todo elemento meet primo tamén é meet irreducíbel. A inversa cúmprese se ${\displaystyle L}$ é distributiva.

Teña ${\displaystyle L}$ un elemento menor 0. Un elemento ${\displaystyle x}$ de ${\displaystyle L}$ é un átomo se ${\displaystyle 0<x}$ e non existe ningún elemento ${\displaystyle y\in L}$ tal que ${\displaystyle 0<y<x.}$ Entón ${\displaystyle L}$ chámase:

• Atómica se para cada elemento distinto de cero ${\displaystyle x}$ de ${\displaystyle L,}$ existe un átomo ${\displaystyle a}$ de ${\displaystyle L}$ tal que ${\displaystyle a\leq x;}$ ^[9]
• Atomista se cada elemento de ${\displaystyle L}$ é un supremo de átomos. ^[10]

Wikimedia Commons ten máis contidos multimedia na categoría:  Retícula

• Burris, Stanley N., and Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
• Jipsen, Peter, and Henry Rose, Varieties of Lattices, Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN 0-387-56314-8.

Textos elementais:

• Donnellan, Thomas, 1968. Lattice Theory. Pergamon.
• Grätzer, George, 1971. Lattice Theory: First concepts and distributive lattices. W. H. Freeman.

Texto contemporáneos introdutorios, algo máis duros que os anteriores:

• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order. Cambridge University Press. ISBN 978-0-521-78451-1. 

• Join e meet
• Mapa de retículas
• Retícula ortocomplementeda
• Orde total
• Ideal (teoría da orde) e Filtro (matemáticas) (nocións duais)
• Retícula Euleriana
• Retícula de Post
• Retícula de Tamari

• "Lattice-ordered group". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 
• Weisstein, Eric W. "Lattice". MathWorld. 
• J.B. Nation, Notes on Lattice Theory, course notes, revised 2017.
• Ralph Freese, "Lattice Theory Homepage".
• (secuencia A006966 na OEIS) Number of unlabeled lattices with n elements