Háló (matematika)

4 elemű halmaz osztályozásaiból képezett háló Hasse-diagramja.

A matematikában a hálónak két egymással ekvivalens definíciója létezik, az egyik rendezési relációkkal (ld. részbenrendezett halmazok) definiálja a háló fogalmát, a másik pedig (amely R. Dedekindtől ered, aki a német Dualgrouppe (duálcsoport, kettőscsoport) elnevezést találta rá ki^[1]) kétváltozós műveletekkel, kétműveletes algebrai struktúraként. A részbenrendezett halmazok közül azokat nevezzük hálónak, amelyekre bármely kételemű részhalmazára teljesül, hogy az adott kételemű halmaznak van szuprémuma és infimuma. Ha egy részbenrendezett halmaz bármely részhalmazára (tehát nem csak a kételeműekre) teljesül az, hogy létezik szuprémuma és infimuma, akkor teljes hálóról beszélünk. Az algebrai struktúrák felől megközelítve a háló fogalmát azt mondhatjuk, hogy a hálók olyan struktúrák, amelyekben definiálva van két kétváltozós kommutatív, asszociatív művelet, amelyek eleget tesznek az ún. elnyelési azonosságoknak is.

Definíció

A háló alábbi két definíciója ekvivalens:

Definíció részbenrendezett halmazok használatával

Az ${\displaystyle (A;\leq )}$ részbenrendezett halmazt hálónak nevezzük, ha ${\displaystyle A}$ bármely kételemű részhalmazának létezik legkisebb felső korlátja és legnagyobb alsó korlátja.

Az ${\displaystyle (A;\leq )}$ részbenrendezett halmazt teljes hálónak nevezzük, ha ${\displaystyle A}$ bármely részhalmazának létezik legkisebb felső korlátja és legnagyobb alsó korlátja.

Definíció algebrai struktúrák használatával

Az ${\displaystyle (A;\cup ,\cap )}$ kétműveletes algebrai struktúrát hálónak nevezzük, ha ${\displaystyle \cup }$, ${\displaystyle \cap }$ kétváltozós műveletek ${\displaystyle A}$-n, amelyekre tetszőleges ${\displaystyle a,b,c\in A}$ elemekre teljesülnek a következők:

${\displaystyle a\cup b=b\cup a}$, ${\displaystyle a\cap b=b\cap a}$ (kommutativitás),

${\displaystyle (a\cup b)\cup c=a\cup (b\cup c)}$, ${\displaystyle (a\cap b)\cap c=a\cap (b\cap c)}$ (asszociativitás),

${\displaystyle a\cap (a\cup b)=a}$, ${\displaystyle a\cup (a\cap b)=a}$ (elnyelési azonosságok).

Az ${\displaystyle \cup }$ műveletet egyesítésnek, a ${\displaystyle \cap }$ műveletet pedig metszetnek hívjuk.

Ha a két műveletet megcseréljük, akkor a duális hálót kapjuk.

Példák

• Csoport részcsoportjai a generálás és a metszet művelettel hálót alkotnak. Részbenrendezés: tartalmazás. Létezik a normálosztók hálója is.
• Gyűrű részgyűrűi a generálás és a metszet művelettel hálót alkotnak. Részbenrendezés: tartalmazás. Létezik az ideálok hálója is.
• Vektortér alterei a generálás és a metszet művelettel hálót alkotnak. Részbenrendezés: tartalmazás.
• A természetes számok halmazán két számhoz hozzárendelve azok legnagyobb közös osztóját és legkisebb közös többszörösét két olyan műveletet definiálunk, amelyekkel együtt a természetes számok halmaza hálót alkot. Részbenrendezés: oszthatóság.
• Nemüres halmaz részhalmazai hálót alkotnak a halmazelméleti unió és metszet műveletekkel. Részbenrendezés: tartalmazás.

Tulajdonságok

• A hálóaxiómákból következik, hogy a háló mindkét művelete idempotens, azaz

${\displaystyle a\cup a=a}$,

${\displaystyle a\cap a=a}$.

• az idempotencia következményeként a háló részben rendezhető, ahol ${\displaystyle a\leq b}$ ekvivalens ${\displaystyle a\cup b=b}$. Erre a rendezésre minden kételemű halmaznak van legkisebb felső korlátja és legnagyobb alsó korlátja.
• A duális háló rendezése a háló rendezésének megfordítása.
• ${\displaystyle b}$ fedi ${\displaystyle a}$ -t, ha ${\displaystyle a<b}$ , és nincs ${\displaystyle c}$, ${\displaystyle a<c<b}$.

Hasse-diagramok

A véges rendezett halmazok irányított gráfokkal ábrázolhatók, amiben az elemek a pontok, és egy a-b él akkor létezik, ha b fedi a-t. Ezeket a gráfokat Hasse-diagramoknak nevezzük. Az ilyen gráfok úgy is ábrázolhatók, hogy az összes él felfelé mutasson. Így is szokás ábrázolni őket, de irányítás nélkül.

Speciális hálók

Az L háló disztributív, ha mindkét művelet disztributív a másikra:

${\displaystyle a\cup (b\cap c)=(a\cup b)\cap (a\cup c)}$ minden ${\displaystyle a,b,c\in L}$ és

${\displaystyle a\cap (b\cup c)=(a\cap b)\cup (a\cap c)}$ minden ${\displaystyle a,b,c\in L}$ -re.

Az L háló moduláris, ha:

${\displaystyle a\leq c\Longrightarrow a\cup (b\cap c)=(a\cup b)\cap c}$ minden ${\displaystyle a,b,c\in L}$ -re.

Ez ekvivalens a következővel:

${\displaystyle a\geq c\Longrightarrow a\cap (b\cup c)=(a\cap b)\cup c}$ minden ${\displaystyle a,b,c\in L}$ -re.

${\displaystyle a\cup (b\cap (a\cup c))=(a\cup b)\cap (a\cup c)}$ minden ${\displaystyle a,b,c\in L}$ -re.

${\displaystyle a\cap (b\cup (a\cap c))=(a\cap b)\cup (a\cap c)}$ minden ${\displaystyle a,b,c\in L}$ -re.

A disztributivitásból következik a modularitás, de fordítva nem.

Az L háló teljes, ha tetszőleges részhalmazának van legkisebb felső korlátja és legnagyobb alsó korlátja is. Ezt a tulajdonságot az egész hálóra alkalmazva kapjuk, hogy van legnagyobb és legkisebb eleme.

Speciális elemek

Ha az egyesítésnek van neutrális eleme, akkor ezt a háló nullelemének (0) nevezzük. Ha létezik, akkor egyértelmű, és a háló legkisebb eleme. Duálisan, ha a metszetnek van neutrális eleme, akkor az a háló egységeleme (1). Ez szintén egyértelmű, ha létezik, és a háló legnagyobb eleme.

Ha az L hálóban van 0 és 1, és valamely a elemhez van b elem, hogy

${\displaystyle a\cap b=0}$ és ${\displaystyle a\cup b=1}$,

akkor b-t a komplementerének hívjuk. Ha L minden elemének van komplementere, és az egyértelmű, akkor az L háló komplementumos.

A komplementumos disztributív háló Boole-háló, más néven Boole-algebra.

Homomorfizmusok és részhálók

Legyen ${\displaystyle (L,\sqcup ,\sqcap )}$ és ${\displaystyle (M,\cup ,\cap )}$ két háló. Ha az ${\displaystyle f:L\to M}$ függvényre teljesül, hogy

${\displaystyle f(a\sqcup b)=f(a)\cup f(b)}$

${\displaystyle f(a\sqcap b)=f(a)\cap f(b)}$,

akkor f hálóhomomorfizmus. Ha f bijektív, akkor izomorfizmus.

A hálóhomomorfizmusok rendezéstartók, azaz monoton függvények: ha

a ≤ b, akkor f(a) ≤ f(b).

Ez az állítás nem fordítható meg, azaz nem minden monoton hálófüggvény homomorfizmus.

M részhálója L-nek, ha zárt az L-beli műveletekre nézve, azaz minden a és b elemére

a ${\displaystyle \cup }$ b és a ${\displaystyle \cap }$ b eleme M-nek.

M háló az L-beli műveletek M-re vett leszűkítésével.

Lásd még

• Disztributív háló
• Moduláris háló
• Atomos háló

Jegyzetek

1. Dean, E. T.: Dedekind's treatment of Galois Theory in the Vorlesungen Archiválva 2014. május 11-i dátummal a Wayback Machine-ben. A Dietrich College of Humanities and Social Sciences Filozófiai Tanszékének közleményei, 109. sz., 2009; 3. oldal. Angol nyelven, PDF. Hozzáférés: 2012-04-27.

Hivatkozások

• Szász Gábor: Bevezetés a hálóelméletbe, Akadémiai Kiadó, Budapest, 1959
• Czédli Gábor: Boole-függvények, Polygon, Szeged, 1995
• Fried Ervin: Algebra
• Pelikán József: Algebra (PDF/Postscript). Összeállította Gröller Ákos. ELTE TTK

Források

A Wikimédia Commons tartalmaz Háló (matematika) témájú médiaállományokat.

• Háló definíciója Archiválva 2006. szeptember 25-i dátummal a Wayback Machine-ben a PlanetMath oldalán