Reticle (ordre)

En matemàtica, un reticle és una determinada estructura algebraica amb dues operacions binàries, o bé un conjunt parcialment ordenat amb certes propietats específiques (sent equivalents ambdós enfocaments). El terme "reticle" ve de la forma dels diagrames de Hasse d'aquestes ordres.

Diagrama de Hasse del reticle de particions del conjunt{1,2,3,4}.

Definició com a conjunt ordenat

En teoria de conjunts, un reticle , xarxa o lattice és un conjunt parcialment ordenat en el qual per a cada parell d'elements hi ha un suprem i un ínfim, això és:

Un conjunt parcialment ordenat ( L , ≤) es denomina reticle si satisfà les següents propietats:

Existència del suprem per parells

Per a qualssevol dos elements a i b de L , el conjunt{ a, b }té un suprem : $a\lor b$ (també conegut com mínima fita superior, o join en idioma anglès).

Existència del ínfim per parells

Per a qualssevol dos elements a i b de L , el conjunt{ a, b }té un ínfim : $a\land b$ (també conegut com màxima cota inferior, o meet en idioma anglès).

El suprem i l'ínfim de a i b es denoten per $a\lor b$ i $a\land b$, respectivament, el que defineix a $\lor$ i $\land$ com operacions binàries. El primer axioma diu que L és un semireticle superior, el segon que L és un semireticle inferior. Ambdues operacions són monòtones pel que fa a l'ordre: a ₁ ≤ a ₂ i b ₁ ≤ b ₂ implica que a ₁ $\lor$ b ₁ ≤ a ₂ $\lor$ b ₂ ja ₁ $\land$ b ₁ ≤ a ₂ $\land$ b ₂ .

Se segueix per inducció matemàtica que per tot subconjunt finit no buit d'un reticle hi ha un suprem i un ínfim.

Noteu que encara en un conjunt parcialment ordenat ( L , ≤) arbitrari, l'existència d'algun suprem (o ínfim) z per a un subconjunt finit no buit S de L implica que aquest suprem (o ínfim) z és únic, ja que d'existir dues o més cotes superiors (o inferiors) de S que siguin incomparables entre si, el suprem (o ínfim) per definició no existeix.

Definició algebraica

En àlgebra, en sentit invers, un reticle és un conjunt L , proveït de dos operacions binàries $\wedge$ i $\vee$, tals que per a qualssevol a , b , c en L es compleixen

a $\vee$ b = b $\vee$ a	a $\wedge$ b = b $\wedge$ a	Les lleis de commutativitat
a $\vee$ ( b $\vee$ c ) = ( a $\vee$ b ) $\vee$ c	a $\wedge$ ( b $\wedge$ c ) = ( a $\wedge$ b ) $\wedge$ c	Les lleis de associativitat
a $\vee$ ( a $\wedge$ b ) = a	a $\wedge$ ( a $\vee$ b ) = a	Les lleis d'absorció
condicions de les que es deriven
a $\vee$ a = a	a $\wedge$ a = a	Les lleis de idempotència

Si les dues operacions satisfan aquestes regles algebraiques, llavors al seu torn defineixen un ordre parcial ≤ en L per la regla següent: a ≤ b si i només si a $\vee$ b = b , o, equivalentment, a $\wedge$ b = a .

L , juntament amb l'ordre parcial ≤ així definit, seria llavors un reticle en el sentit esmentat de la teoria de l'ordre.

Inversament, si es dona un reticle ( L , ≤) en termes de la teoria de l'ordre, i escrivim a $\vee$ b per al suprem de{ a , b }i a $\wedge$ b per l'ínfim de{ a , b }, llavors ( L , $\wedge ;\vee$) satisfà tots els axiomes d'un reticle definit algebraicament.

Per tant L és un semireticle respecte a cada operació per separat, és a dir, un semigrup commutatiu, amb idempotència de cadascun dels seus elements. Les operacions interaccionen a través de les lleis d'absorció.

En permutar les operacions s'obté el reticle dual de L .

Homomorfismes

La classe de tots els reticles forma una categoria si definim un homomorfisme entre dos reticles ( L , $\wedge ;\vee$) i ( N , $\wedge ;\vee$) com una funció f : L $\rightarrow$ N tal que

f ( a $\wedge$ b ) = f ( a ) $\wedge$ f ( b );

f ( a $\vee$ b ) = f ( a ) $\vee$ f ( b );

per a tot a i b en L . Si és un homomorfisme bijectiu, llavors el seu invers és també un homomorfisme, i es diu un isomorfisme de reticles. Els dos reticles implicats són llavors isomorfs ; per a tots els propòsits pràctics, són iguals i es diferencien només en la notació dels seus elements.

Cada homomorfisme és una funció monòtona entre els dos reticles, però no cada funció monòtona dona un homomorfisme de reticle: a més necessitem la compatibilitat amb suprems i ínfims finits.

Reticles particulars

A continuació, per "reticle L " sempre ens referirem a ( L , $\wedge$, $\vee$).

Un reticle L s'anomena distributiu, si les seves operacions són doblement distributives:

• $A\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$ per tot $a,b,c\in L$ i
• $A\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$ per tot $a,b,c\in L$.

Com aquests dos judicis són equivalents entre ells, només cal exigir l'acompliment d'una de les dues lleis distributives.

Un reticle L s'anomena modular, si es compleix que:

• $A\leq c\longrightarrow a\vee (b\wedge c)=(a\vee b)\wedge c$ per tot $a,b,c\in L$ .

Per a un reticle L al seu torn són equivalents:

• L és modular.
• $A\geq c\longrightarrow a\wedge (b\vee c)=(a\wedge b)\vee c$ per tot $a,b,c\in L$ .
• $A\vee (b\wedge (a\vee c))=(a\vee b)\wedge (a\vee c)$ per tot $a,b,c\in L$.
• $A\wedge (b\vee (a\wedge c))=(a\wedge b)\vee (a\wedge c)$ per tot $a,b,c\in L$.

Tot reticle distributiu és modular, però el judici invers no es compleix. Un reticle no modular sempre conté al reticle $N_{5}$ com subreticle.

En cas que l'operació $\vee$ tingui un element neutre 0,

• $A\vee 0=a,$

a aquest se'l denomina l'element zero del reticle. És únic i és l'element més petit pel que fa a l'ordre natural del reticle:

• $A\wedge 0=0$ i $0=\bigwedge V.$

El reticle s'anomena llavors reticle amb cota inferior .

En cas que l'operació $\wedge$ tingui un element neutre 1,

• $A\wedge 1=a,$

a aquest se'l denomina 'element u' del reticle. És únic i és l'element més gran pel que fa a l'ordre natural del reticle:

• $A\vee 1=1$ i
• $1=\bigvee V.$

El reticle s'anomena llavors reticle amb cota superior .

L'element neutral d'una de les operacions és llavors un element absorbent de l'altra. Un reticle es denomina acotat si té fita superior i inferior, és a dir, si ambdues operacions tenen element neutre.

Per a un element donat a d'un reticle acotat, l'element b amb la propietat

• $A\wedge b=0$ i
• $A\vee b=1$

se'l denomina complement de a . Un reticle acotat, en el qual cada un els seus elements té complement, es denomina complementat .

Un reticle distributiu complementat s'anomena àlgebra de Boole o reticle de Boole, quan en comptes del complement només hi ha un així anomenat pseudocomplemento relatiu, es parla d'una àlgebra de Heyting.

Un reticle L s'anomena complet si tot subconjunt (inclosos els subconjunts buit o possiblement suconjuntos infinit s) té un suprem i un ínfim.

Per a cada subconjunt M n'hi ha prou exigir l'existència del suprem, ja que

• $\bigwedge M=\bigvee \{x\in L:(\forall \,i\in M:x\leq i)\}.$

Un element a d'un reticle complet L s'anomena compacte (segons una propietat similar a topologia), si tot subconjunt M de L amb

• $A\leq \bigvee M$

conté un subconjunt finit E tal que

• $A\leq \bigvee I$.

Un reticle L s'anomena algebraic , si és complet i si tot element de L és un suprem d'elements compactes.

Propietats

Tot reticle complet L és tancat, amb

• $0=\bigwedge L=\bigvee \emptyset$ i
• $1=\bigvee L=\bigwedge \emptyset .$

Tot reticle finit, no buit L és complet, de manera que també és acotat.

En un reticle distributiu i acotat, el complement d'un element a és únic si existeix, el que sol denotar com a ^c (particularment en el cas de reticles de subconjunts) o bé ¬ a (particularment en aplicacions de lògica).

• Demostració: Siguin b i c complements de a , volem mostrar que b = c . Ara es compleix que b = b $\wedge$ 1 = b $\wedge$ ( a $\vee$ c ) = ( b $\wedge$ a ) $\vee$ ( b $\wedge$ c ) = b $\wedge$ c . Anàlogament es mostra que c = b $\wedge$ c , per la qual cosa b = c .

No obstant això, si el reticle no és distributiu, poden existir diversos complements; aquí un exemple més endavant.

En un reticle distributiu acotat es verifica

• ¬ 0 = 1, ¬ 1 = 0.

Si a té un complement ¬ a , llavors també ¬ a té un complement, que és:

• ¬ (¬ a ) = a .

Per altres propietats dels reticles booleans vegeu aquest article.

Exemples de reticles

• Els subconjunts d'un conjunt donat, ordenats per inclusió. El suprem està donat per la unió i l'ínfim per la intersecció de subconjunts.
• L'interval unitat [0, 1] i la recta estesa de nombres reals, amb l'ordre total familiar i els usuals suprem i ínfim.
• Els sencers no negatius, ordenats per divisibilitat. El suprem ve donat pel mínim comú múltiple i l'ínfim pel màxim comú divisor.
• Els subgrups d'un grup, ordenat per la inclusió. El suprem ve donat pel subgrup generat per la unió dels grups i l'ínfim ve donat per la intersecció.
• Els submòduls d'un mòdul, ordenat per la inclusió. El suprem ve donat per de la suma de submòduls i l'ínfim per la intersecció.
• Els ideals d'un anell, ordenat per la inclusió. El suprem ve donat per la suma d'ideals i l'ínfim per la intersecció.
• Els conjunts oberts d'un espai topològic, ordenats per la inclusió. El suprem ve donat per la unió de conjunts oberts i l'ínfim per l'interior de la intersecció.
• Els subconjunts convexs d'un espai vectorial real o complex, ordenat per la inclusió. L'ínfim ve donat per la intersecció de conjunts convexos i el suprem per la cloenda convexa de la unió.
• Les topologies en un conjunt, ordenades per la inclusió. L'ínfim ve donat per la intersecció de topologies, i el suprem per la topologia generada per la unió de les topologies.
• El reticle de totes les relacions binàries transitives en un conjunt.
• El reticle de totes les relacions d'equivalència en un conjunt, la relació d'equivalència # es considera ser més petit (o "més fi") que ≈ si x # i implica sempre x ≈ i .

El teorema de Knaster-Tarski estableix que el conjunt de punts fixos d'una funció monòtona en un reticle complet és així mateix un reticle complet.

El reticle de submòduls d'un mòdul i el reticle dels subgrups normals d'un grup tenen la propietat especial que x $\vee$ ( i $\wedge$ ( x $\vee$ z )) = ( x $\vee$ i ) $\wedge$ ( x $\vee$ z ) per a tot x , i i z en el reticle. Un reticle amb aquesta propietat es diu un reticle modular . La condició de la modularitat pot també ser establerta de la manera següent: Si x ≤ z llavors per a tot i tenim la identitat x $\vee$ ( i $\wedge$ z ) = ( x $\vee$ i ) $\wedge$ z .

Un reticle es diu distributiu si $\wedge$ distribueix a $\vee$, és a dir, x $\wedge$ ( i $\vee$ z ) = ( x $\wedge$ i ) $\vee$ ( x $\wedge$ z ). equivalentment, $\vee$ distribueix $\wedge$. Tots els reticles distributius són modulars. Dos tipus importants de reticles distributius són els conjunts totalment ordenats i les àlgebres booleanes (com el reticle de tots els subconjunts d'un conjunt donat). El reticle dels nombres naturals, ordenats per divisibilitat, és també distributiu. Altres lleis comunes de distributivitat (especialment la llei de distributivitat completa ) es donen en l'article sobre distributivitat en teoria de l'ordre.

Nocions importants de la teoria de reticles

En el següent, sigui L un reticle. Definim algunes nocions de la teoria de l'ordre que són d'importància particular en teoria de reticles.

Un element x de L es diu suprem-irreductible si i només si

• x = a $\vee$ b implica x = a o x = b per a qualsevol a , b en L ,
• Si L té un 0 , de x es requereix de vegades ser diferent de 0 .

Quan la primera condició es generalitza a suprems arbitraris Va _i , x es diu totalment suprem-irreductible . la noció dual es diu ínfim-Irreducibilitat . De vegades un també utilitza els termes $\vee$-irreductibles i $\wedge$-irreductibles, respectivament.

Un element x de L es diu suprem-cosí si i només si

• x ≤ a $\vee$ b implica x ≤ a o x ≤ b ,
• Si L té 0 , de x es requereix de vegades ser diferent de 0 .

Una vegada més això es pot generalitzar per obtenir la noció totalment suprem-cosí i dualitzar per ínfim-cosí . Qualsevol element suprem-cosí és també suprem-irreductible, i qualsevol element ínfim-cosí és també ínfim-irreductible. Si el reticle és distributiu l'invers és també veritat.

Altres nocions importants en teoria de reticles són ideal i la seva noció dual filtre. Ambdós termes descriuen subconjunts especials d'un reticle (o de qualsevol conjunt parcialment ordenat en general). Els detalls es poden trobar en els articles respectius.

Bibliografia

• Garrett Birkhoff, 1967. Lattice Theory , 3rd ed. Vol 25 of AMS Colloquium Publications. American Mathematical Society. ISBN 9780821810255
• Robert P. Dilworth i Crawley, Peter, 1973. Algebraic Theory of Lattice . Prentice-Hall. ISBN 9780130222695.
• George Gratz, 1978. General Lattice Theory . Birkhäuser. ISBN 9783764369965.
• Hans Hermes, 1963. La Teoría de Retículos y Su Aplicación a la Lógica Matemática. Consejo Superior de Investigaciones Científicas. ISBN 9788400031039

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Reticle