Grilă (matematică)

În matematică , o rețea ( rețea în engleză) este un set parțial ordonat în care fiecare pereche de elemente are atât o limită inferioară ( inf ), cât și o limită superioară ( sup ). Rețelele pot fi, de asemenea, caracterizate ca structuri algebrice care satisfac anumite identități . Deoarece ambele definiții pot fi utilizate în mod convenabil, teoria rețelelor poate fi aplicată atât din teoria ordinelor, cât și din teoria algebrei universale . Rețelele sunt unul dintre cei mai semnificativi reprezentanți ai structurilor care admit ordinea, precum și structurile algebrice, cum ar fi semireticulele , algebrele Heyting sau algebrele booleene . Termenul rețea derivă din reprezentarea diagramelor Hasse .

Definiție formală

După cum sa menționat anterior, rețeaua poate fi caracterizată atât ca un set parțial ordonat, cât și ca o structură algebrică. Ambele definiții și relația lor sunt explicate mai jos.

Rețelele ca seturi parțial ordonate

Este $(R,\leq )$ ${\ displaystyle (R, \ leq)}$ ${\ displaystyle (R, \ leq)}$ un set parțial comandat. Vom spune asta $(R,\leq )$ ${\ displaystyle (R, \ leq)}$ ${\ displaystyle (R, \ leq)}$ este o rețea dacă pentru fiecare x și y elemente ale lui R , subsetul $\{x,y\}$ ${\ displaystyle \ {x, y \}}$ ${\ displaystyle \ {x, y \}}$ are limita superioară și inferioară în R.

Pentru fiecare x, y elemente ale lui R se desemnează $x\vee y=\mathrm {sup} \{x,y\}$ ${\ displaystyle x \ vee y = \ mathrm {sup} \ {x, y \}}$ ${\ displaystyle x \ vee y = \ mathrm {sup} \ {x, y \}}$ Și $x\wedge y=\mathrm {inf} \{x,y\}$ ${\ displaystyle x \ wedge y = \ mathrm {inf} \ {x, y \}}$ ${\ displaystyle x \ wedge y = \ mathrm {inf} \ {x, y \}}$ .

Rețelele ca structuri algebrice

Să luăm în considerare o structură algebrică $(R,\vee ,\wedge )$ ${\ displaystyle (R, \ vee, \ wedge)}$ ${\ displaystyle (R, \ vee, \ wedge)}$ , unde este $\vee$ ${\ displaystyle \ vee}$ $\ vee$ Și $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ sunt două operații binare definite în R. R este o rețea dacă următoarele identități sunt valabile pentru fiecare element a , b , c din R :

Legile comutative:

a\vee b=b\vee a

{\ displaystyle a \ vee b = b \ vee a}

{\ displaystyle a \ vee b = b \ vee a}

a\wedge b=b\wedge a

{\ displaystyle a \ wedge b = b \ wedge a}

{\ displaystyle a \ wedge b = b \ wedge a}

Legile asociative:

a\vee (b\vee c)=(a\vee b)\vee c

{\ displaystyle a \ vee (b \ vee c) = (a \ vee b) \ vee c}

{\ displaystyle a \ vee (b \ vee c) = (a \ vee b) \ vee c}

a\wedge (b\wedge c)=(a\wedge b)\wedge c

{\ displaystyle a \ wedge (b \ wedge c) = (a \ wedge b) \ wedge c}

{\ displaystyle a \ wedge (b \ wedge c) = (a \ wedge b) \ wedge c}

Legile absorbției:

a\vee (a\wedge b)=a

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

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

a\wedge (a\vee b)=a

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

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

Din identitățile anterioare derivă următoarele

Legile idempotenței:

a\vee a=a

{\ displaystyle a \ vee a = a}

{\ displaystyle a \ vee a = a}

a\wedge a=a

{\ displaystyle a \ wedge a = a}

{\ displaystyle a \ wedge a = a}

Rețineți că pentru legile idempotenței , legile comutative și asociative reprezintă condiția ca ( R , ∨) și ( R , ∧) să constituie două semi-rețele, în timp ce legile absorbției asigură că cele două structuri interacționează corect.

Pentru a descrie o rețea mărginită, o lege trebuie să includă elementele neutre 0 și 1 pentru a uni operațiile inf și sup în definiția de mai sus.

Echivalența celor două definiții

O rețea dotată cu o relație de ordine are cele două operații binare $\vee$ ${\ displaystyle \ vee}$ $\ vee$ Și $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ . Acum se poate vedea cu ușurință că aceste operații ne permit să luăm în considerare rețeaua ( R , ∨, ∧) în sens algebric. Poate mai surprinzător, se poate obține și inversul acestui rezultat: ia în considerare orice rețea definită algebric ( M , ∨, ∧). Se poate defini o relație de ordine parțială $\leq$ ${\ displaystyle \ leq}$ $\ leq$ pe M considerând pentru fiecare element x și y în ${M}$ ${\ displaystyle {M}}$ ${\ displaystyle {M}}$

$x\leq y$ ${\ displaystyle x \ leq y}$ $x \ leq y$ dacă și numai dacă $x=x\wedge y$ ${\ displaystyle x = x \ wedge y}$ ${\ displaystyle x = x \ wedge y}$

sau echivalent

$x\leq y$ ${\ displaystyle x \ leq y}$ $x \ leq y$ dacă și numai dacă $y=x\vee y$ ${\ displaystyle y = x \ vee y}$ ${\ displaystyle y = x \ vee y}$ .

Legile absorbției arată că ambele definiții sunt efectiv echivalente. Acum puteți verifica dacă relația de comandă $\leq$ ${\ displaystyle \ leq}$ $\ leq$ introdus în acest mod definește o ordonare parțială în care operațiile de sup și inf sunt date de operații $\vee$ ${\ displaystyle \ vee}$ $\ vee$ Și $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ . Dimpotrivă, relația de ordine indusă de rețeaua definită algebric ( R , ∨, ∧) coincide cu ordonarea ${R}$ ${\ displaystyle {R}}$ ${\ displaystyle {R}}$ iniţial.

Astfel, cele două definiții pot fi utilizate într-un sens complet interschimbabil, conform căruia unul este mai convenabil de utilizat pentru un scop specific.

Exemple

Pentru orice set A , setul tuturor subseturilor sale delimitate (inclusiv setul gol ) poate fi comandat cu relația de includere pentru a obține o rețea. Operațiunile rețelei sunt intersecția ( inf ) și respectiv uniunea ( sup ) seturilor. Această rețea are setul gol ca cel mai mic element, dar va conține cel mai mare element numai dacă A este delimitat. În general, nu este o rețea limitată.
Numerele naturale cu relația de ordine comună sunt o rețea. Cel mai mic element este 0, în timp ce cel mai mare element nu există.
Fiecare rețea completă este o rețea delimitată.
Ansamblul elementelor compacte ale unei rețele aritmetice complete este o rețea cu un element mai puțin, în care operațiile sunt date prin limitarea operațiunilor respective ale rețelei aritmetice. Aceasta este o proprietate specifică care distinge rețelele aritmetice de rețelele algebrice, astfel încât compactele formează doar o semireticulă .
Figura prezintă diagramele Hasse ale tuturor rețelelor posibile cu cel mult cinci elemente.

Homomorfisme între rețele

Definiția adecvată a homomorfismului între două rețele poate fi ușor derivată din următoarea definiție algebrică: date două rețele $(R,\vee ,\wedge )$ ${\ displaystyle (R, \ vee, \ wedge)}$ ${\ displaystyle (R, \ vee, \ wedge)}$ Și $(M,\cup ,\cap ),$ ${\ displaystyle (M, \ cup, \ cap),}$ ${\ displaystyle (M, \ cup, \ cap),}$ un homomorfism între rețele este o funcție $f:R\to M$ ${\ displaystyle f: R \ to M}$ ${\ displaystyle f: R \ to M}$ care verifică următoarele proprietăți:

f(x\vee y)=f(x)\cup f(y),

{\ displaystyle f (x \ vee y) = f (x) \ cup f (y),}

{\ displaystyle f (x \ vee y) = f (x) \ cup f (y),}

f(x\wedge y)=f(x)\cap f(y).

{\ displaystyle f (x \ wedge y) = f (x) \ cap f (y).}

{\ displaystyle f (x \ wedge y) = f (x) \ cap f (y).}

Dacă rețelele au cel mai mic element și cel mai mare element $1,$ ${\ displaystyle 1,}$ ${\ displaystyle 1,}$ apoi $f$ ${\ displaystyle f}$ $f$ trebuie să păstreze și aceste elemente:

f(0)=0,

{\ displaystyle f (0) = 0,}

{\ displaystyle f (0) = 0,}

f(1)=1.

{\ displaystyle f (1) = 1.}

{\ displaystyle f (1) = 1.}

În formularea teoretică a ordinii, condiția corectă este aceea că un homomorfism între rețele este o funcție care păstrează operațiile binare inf și sup .

Rețineți că orice omomorfism între rețele este în mod necesar monoton în raport cu relația de ordine asociată. Inversul nu este adevărat: monotonia nu implică deloc proprietățile necesare de conservare.

Folosind definiția standard a izomorfismelor ca omomorfisme inversabile, constatăm că un izomorfism între rețele este exact un omomorfism bijectiv între rețele. Rețelele și omomorfismele lor formează evident o categorie .

Două rețele izomorfe au aceeași diagramă Hasse.

Proprietățile rețelelor

Există o serie de proprietăți importante, care vor fi introduse acum, dintre care multe conduc la luarea în considerare a unor categorii speciale de rețele.

Cea mai imediată proprietate pentru un rețea R este poate aceea de a fi delimitat . Vedem de fapt că, dacă, în general, cel mai mic (minim) element este indicat cu simbolul 0 și cel mai mare (maxim) cu simbolul 1, se spune că o rețea R este limitată dacă are un maxim și un minim.

Completitudine

Extrem de relevantă categorie este cea a latici complet. O rețea este completă dacă fiecare subset al acesteia are atât inf cât și sup . Această definiție pare să fie opusă definiției rețelei în care este necesară doar existența inf sau sup (nu gol). Se pare că existența tuturor infurilor pune capăt existenței tuturor supurilor și invers. De asemenea, rețineți că rețelele complete sunt întotdeauna limitate. Exemple de rețele complete sunt:

Setul de subseturi ale unui set dat, ordonate după relația de incluziune . Sup este dat de unirea subseturilor și inf de intersecția subseturilor.
Intervalul unitar [0,1] este linia reală, cu relația de ordine totală și sup și inf ordinare.
Numere întregi non-negative, ordonate după relația de divizibilitate. Cel mai mic element al acestei rețele este numărul 1, deoarece împarte orice alt număr. În mod surprinzător, probabil, cel mai mare element este 0, deoarece poate fi împărțit cu orice alt număr. Sup de mulțimi delimitate este dat de cel mai mic multiplu comun și inf de cel mai mare divizor comun. Pentru mulțimile infinite, sup va fi întotdeauna 0 în timp ce inf este mai mare decât 1. De exemplu, mulțimea tuturor numerelor pare are 2 ca cel mai mare divizor comun. Dacă 0 este eliminat din această structură, rămâne un rețea, dar încetează să mai fie complet.
Subgrupurile unui grup , sortate după relația de incluziune. Sup este dat de subgrupul generat de unirea grupurilor în timp ce inf este dat de intersecție .
Submodulele unui modul sunt sortate după relația de incluziune. Sup este dat de unirea submodulelor în timp ce inf de intersecție.
Idealurile unui inel , ordonate de relația de incluziune. Sup este dat de uniunea idealurilor în timp ce inf de intersecție .
Seturile deschise ale unui spațiu topologic , ordonate după relația de incluziune. Sup este dat de unirea seturilor deschise în timp ce inf este dat de intersecția internă.
Subseturile convexe ale unui spațiu real sau complex de vectori ordonat de relația de incluziune. Inf este dat de intersecția seturilor convexe în timp ce sup de învelișul convex al uniunii.
Topologiile pe un set, ordonate după relația de finețe . Inf este dat de intersecția topologiilor în timp ce sup de topologia generată de unirea topologiilor.
Rețeaua oricărei relații binare tranzitive pe un set.
Rețeaua fiecărui submultiplu al unui multiset .
Rețeaua fiecărei relații de echivalență pe un set; simbolul de echivalență ~ este considerat a fi restrictiv pentru ≈; x ~ y implică întotdeauna x ≈ y .

Multe teoreme ale teoriei ordinii iau forme simple odată enunțate pentru rețele complete. De exemplu, teorema Knaster-Tarski afirmă că setul de puncte fixe ale unei funcții monotone pe o rețea completă este încă o rețea completă.

Distributivitate

Deoarece fiecare rețea are două operații binare , este firesc să se ia în considerare legile distributive relative. O rețea ( R , ∨, ∧) este distributivă dacă pentru fiecare element se menține x , y , z în R

x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)

{\ displaystyle x \ vee (y \ wedge z) = (x \ vee y) \ wedge (x \ vee z)}

{\ displaystyle x \ vee (y \ wedge z) = (x \ vee y) \ wedge (x \ vee z)}

În mod surprinzător, poate, această condiție ajunge să fie echivalentă cu

x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)

{\ displaystyle x \ wedge (y \ vee z) = (x \ wedge y) \ vee (x \ wedge z)}

{\ displaystyle x \ wedge (y \ vee z) = (x \ wedge y) \ vee (x \ wedge z)}

Pentru rețele complete, se pot formula proprietăți mai puternice prin obținerea categoriilor de rețele complete și distributive.

Există rețele nedistributive; următorul este diagrama Hasse a celor mai mici rețele nedistributive.

Deoarece este ușor de verificat că fiecare rețea distributivă este un singur complement, se pune întrebarea dacă opusul este adevărat, adică dacă există rețele cu un singur complement care nu sunt distributive.

Răspunsul la această întrebare este da, există rețele nedistributive de complement unic (teorema lui Dilwhort). Din păcate, nu există încă exemple de astfel de rețele în matematică (și poate că nu există nicio speranță de a le găsi), se poate vedea doar că există.

Putem observa, însă, unele proprietăți care trebuie să aibă neapărat astfel de rețele. Cel mai imediat este că ele trebuie să fie infinite, adică trebuie să aibă un număr infinit de elemente. De fapt, o rețea cu complement unic finit este cu siguranță distributivă.

Modularitate

Distributivitatea este adesea o condiție prea puternică pentru anumite aplicații. O proprietate strict mai slabă este modularitatea: o rețea ( R , ∨, ∧) este modulară dacă pentru fiecare element x , y , z din R avem

x\vee (y\wedge (x\vee z))=(x\vee y)\wedge (x\vee z)

{\ displaystyle x \ vee (y \ wedge (x \ vee z)) = (x \ vee y) \ wedge (x \ vee z)}

{\ displaystyle x \ vee (y \ wedge (x \ vee z)) = (x \ vee y) \ wedge (x \ vee z)}

.

O altă condiție echivalentă este următoarea: dacă x ≤ z atunci pentru toate y

x\vee (y\wedge z)=(x\vee y)\wedge z

{\ displaystyle x \ vee (y \ wedge z) = (x \ vee y) \ wedge z}

{\ displaystyle x \ vee (y \ wedge z) = (x \ vee y) \ wedge z}

De exemplu, rețeaua submodulelor unui modul și rețeaua subgrupurilor normale ale unui grup au această proprietate. Mai mult, fiecare grătar distributiv este efectiv modular.

Continuitate și algebraicitate

În teoria domeniului , suntem deseori interesați de aproximarea elementelor unei rețele dotate cu un ordin parțial, prin intermediul unor elemente „mult mai simple”. Acest lucru duce la categoria rețelelor ordonate continue, constând din rețele cu o relație de ordine în care fiecare element poate fi obținut ca un suport al unui set direct de elemente care sunt legate de elementul însuși. Dacă elementele compacte ale unei rețele ordonate pot fi restricționate în continuare pentru a obține aceste seturi directe, atunci rețeaua este, de asemenea, algebrică. Ambele concepte pot fi aplicate rețelelor după cum urmează:

O rețea continuă este o rețea completă care este continuă ca o rețea ordonată.
O rețea algebrică este o rețea completă care este algebrică ca o rețea ordonată.

Ambele categorii au proprietăți interesante. De exemplu, rețelele continue pot fi caracterizate ca structuri algebrice (cu operații infinite) care satisfac anumite identități. În timp ce o proprietate similară nu este cunoscută pentru rețelele algebrice care pot fi descrise „sintactic” prin intermediul sistemelor informaționale ale lui Scott.

Complimente și pseudo-complemente

Conceptul de complement introduce ideea „negației” în teoria zăbrelelor. Luați în considerare o rețea delimitată cu 1 ca cel mai mare element și 0 ca cel mai mic element. Se spune că un element x completează elementul y dacă:

$x\vee y=1$ ${\ displaystyle x \ vee y = 1}$ ${\ displaystyle x \ vee y = 1}$ Și $x\wedge y=0$ ${\ displaystyle x \ wedge y = 0}$ ${\ displaystyle x \ wedge y = 0}$

O rețea delimitată în care fiecare element are un complement se numește rețea complementată. Rețineți că complementul nu trebuie să fie unic și nici să fie „special” în niciun sens dintre toate complementele existente. În schimb, o algebră booleană are un complement unic pentru fiecare element x care poate fi astfel notat cu ¬ x .

Într-o rețea distributivă complementară, dacă un element are un complement, este unic. De fapt, dacă un element x avea două complemente, y și z

y=y\vee 0=y\vee (x\wedge z)=(y\vee x)\wedge (y\vee z)=(z\vee x)\wedge (y\vee z)=z\vee (x\wedge y)=z\vee 0=z

{\ displaystyle y = y \ vee 0 = y \ vee (x \ wedge z) = (y \ vee x) \ wedge (y \ vee z) = (z \ vee x) \ wedge (y \ vee z) = z \ vee (x \ wedge y) = z \ vee 0 = z}

{\ displaystyle y = y \ vee 0 = y \ vee (x \ wedge z) = (y \ vee x) \ wedge (y \ vee z) = (z \ vee x) \ wedge (y \ vee z) = z \ vee (x \ wedge y) = z \ vee 0 = z}

Algebrele Heyting sunt exemple de rețele delimitate, în cadrul cărora complementele nu există de obicei. Cu toate acestea, fiecare element x dintr-o algebră Heyting are un pseudo-complement care este de obicei notat și cu ¬ x . Este caracterizat, fiind cel mai mare dintre toate elementele y de către proprietate

x\wedge y=0

{\ displaystyle x \ wedge y = 0}

{\ displaystyle x \ wedge y = 0}

.

Dacă pseudo-complementele unei algebre Heyting sunt de fapt complementare, atunci avem o algebră booleană .

Sub-grilă

Fie ( R , ∨, ∧) o rețea și fie ( R ' , ≤) un subset ordonat al acestuia . Atunci R ' se numește subrețea lui R dacă pentru fiecare x , y ∈ R' implică x ∨ y ∈ R ' și x ∧ y ∈ R' .

Rețineți că x ∨ y și x ∧ y sunt sup și inf din { x , y } calculate în R.

Exemplu

Să luăm în considerare rețeaua L din figură

Rețeaua L ' = L \ { c }

nu este o subrețea a lui L , deoarece a ∧ b = c nu aparține lui L ' . În schimb, L \ { d } este o subrețea a lui L ; în plus, L ' este o rețea, chiar dacă nu este o subrețea.

Tiparele libere

Folosind definiția clasică a algebrei universale , o rețea liberă pe un set S este o rețea R cu o funcție i : S → R , astfel încât orice funcție f din S pe setul de bază al unei rețele generice M poate fi descompusă numai printr-o homomorfism f ° între rețelele de la R peste M. Altfel, pentru fiecare element s al lui S putem găsi elemente astfel încât f ( s ) = f ° ( i ( s )) și f ° să fie singurul homomorfism de rețea cu această proprietate. Aceste condiții ne determină să spunem că există o legătură între categoria mulțimilor și funcțiilor la categoria rețelelor și a omomorfismelor dintre rețele.

Ne ocupăm de cazul rețelelor mărginite, adică a structurilor algebrice cu cele două operații binare $\vee$ ${\ displaystyle \ vee}$ $\ vee$ Și $\wedge$ ${\ displaystyle \ wedge}$ $\ wedge$ și cele două constante (operații nule) 0 și 1. Setul tuturor expresiilor corecte (bine formate) care pot fi formulate folosind aceste operații elemente dintr-un set dat de generatoare S vor fi denumite de W ( S ). Acest set conține multe expresii care se dovedesc a fi aceleași în fiecare rețea. De exemplu, dacă a este un element al lui S , atunci a ∨ 1 = 1 și a ∧ 1 = a . Problema rețelelor este care dintre aceste elemente trebuie identificate.

Răspunsul la această problemă este următorul. Definim o relație <~ pe W ( S ) scriind w <~ v dacă și numai dacă una dintre următoarele condiții este îndeplinită:

w = v (acest lucru poate fi limitat la cazul în care w și v sunt elemente ale lui S ),
w = 0 sau v = 1,
w = w1 ∨ w2 e (inclusiv) w1 <~ v și w2 <~ v ,
w = w1 ∧ w2 e (exclusiv) w1 <~ v sau w2 <~ v ,
v = v1 ∨ v2 e (exclusiv) w <~ v1 sau w <~ v2 ,
v = v1 ∧ v2 e (inclusiv) w <~ v1 e w <~ v2 .

Aceasta definește o precomandă <~ pe W ( S ). Mulțimea parțial ordonată indusă de această precomandă (adică mulțimea obținută prin identificarea tuturor elementelor w și v cu w <~ v și v <~ w ) este rețeaua liberă de pe S.

Una dintre consecințele acestei definiții este că rețeaua liberă generată de un set de trei elemente este deja infinită. Într-adevăr, se poate demonstra chiar că fiecare rețea liberă generată de trei elemente conține o subrețea care este gratuită pentru un set generat de patru elemente. Prin inducție, această condiție face o sub- rețea numărabilă liberă pe multe elemente generatoare.

Cazul rețelelor care nu sunt delimitate este tratat în mod similar, folosind doar cele două operații binare din construcția de mai sus.

Noțiuni teoretice importante asupra rețelelor

Fie R o rețea. Definim câteva noțiuni teoretice de ordine care sunt de o importanță deosebită în teoria zăbrelelor.

Se spune că un element x din R este ireductibil de sus dacă și numai dacă

x = a ∨ b implică x = a sau x = b pentru fiecare a , b în R ,
dacă R are 0 , uneori x trebuie să fie diferit de 0 .

Când prima condiție este generalizată de o uniune $\cup$ ${\ displaystyle \ cup}$ $\ ceașcă$ la _i , x se spune că este complet ireductibil din partea de sus . Definiția duală este numită inferior ireductibilă . Uneori se folosesc termenii ∪-ireductibil și ∩-ireductibil.

Un element x din R se spune mai sus mai întâi dacă și numai dacă

x ≤ a v b implică x ≤ a sau x ≤ b ,
dacă R are 0 , uneori x trebuie să fie diferit de 0 .

În mod similar, această definiție poate fi generalizată pentru a obține definiția primului complet superior și a primului său dual inferior . Fiecare element superior superior este, de asemenea, ireductibil superior. Dacă rețeaua este distributivă, inversul este, de asemenea, adevărat.

Alte noțiuni importante în teoria zăbrelelor sunt idealurile și noțiunea conexă de filtru . Ambii termeni descriu subseturile speciale ale unei rețele (sau, în general, ale oricărui set parțial ordonat).

Bibliografie

Garrett Birkhoff (1967): The Lattice Theory , ediția a III-a, American Mathematical Society
E. Mendelson (1973): Introducere în algebră booleană și circuite de comutare , McGraw-Hill
SN Burris, HP Sankappanavar (1981): Un curs în algebră universală , Springer. Acum, de asemenea, disponibil gratuit online
PT Johnstone (1982): Stone spaces , Cambridge University Press,
BA Davey, HA Priestley (2002): Introducere în zăbrele și ordine . Cambridge University Press, ISBN 0-521-78451-4
G. Gierz, KH Hofmann, K. Keimel, JD Lawson, M. Mislove, DS Scott (2003): Lattices and Domains Continuous , Cambridge University Press, ISBN 0-521-80338-1