Reticle (ordre)

De Viquipèdia
Dreceres ràpides: navegació, cerca
Diagrama de Hasse del reticle de particions del conjunt{1,2,3,4}.

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.

Definició com a conjunt ordenat[modifica | modifica el codi]

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 semiretículo superior, el segon que L és un semiretículo inferior. Ambdues operacions són monòtones pel que fa a l'ordre: a 1a 2 i b 1b 2 implica que a 1  \lor b 1 ≤ a 2  \lor b 2 ja 1  \land b 1 ≤ a 2  \land b 2 .

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[modifica | modifica el codi]

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: ab 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 dóna 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 semiretículo 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[modifica | modifica el codi]

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 biyectivo, 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 dóna un homomorfisme de reticle: a més necessitem la compatibilitat amb suprems i ínfims finits.

Reticles particulars[modifica | modifica el codi]

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 subretículo.

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

  •  A \vee 0 = a,

a aquest l'hi denomina el '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 l'hi denomina el 'element un' 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

l'hi 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 lloc 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 \le 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[modifica | modifica el codi]

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 < math> \wedge </math> 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[modifica | modifica el codi]

  • 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 pel interior de la intersecció.
  • 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 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 xi .

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 xz 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[modifica | modifica el codi]

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

  • xa  \vee b implica xa o xb ,
  • Si L0 , 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.

Referències[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Reticle (ordre) Modifica l'enllaç a Wikidata