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) 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 $(A;\leq )$ részbenrendezett halmazt hálónak nevezzük, ha $A$ bármely kételemű részhalmazának létezik legkisebb felső korlátja és legnagyobb alsó korlátja.

Az $(A;\leq )$ részbenrendezett halmazt teljes hálónak nevezzük, ha $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 $(A;\cup ,\cap )$ kétműveletes algebrai struktúrát hálónak nevezzük, ha $\cup$, $\cap$ kétváltozós műveletek $A$-n, amelyekre tetszőleges $a,b,c\in A$ elemekre teljesülnek a következők:

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

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

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

Az $\cup$ műveletet egyesítésnek, a $\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

$a\cup a=a$,

$a\cap a=a$.

• az idempotencia következményeként a háló részben rendezhető, ahol $a\leq b$ ekvivalens $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.
• $b$ fedi $a$ -t, ha $a<b$ , és nincs $c$, $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:

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

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

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

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

Ez ekvivalens a következővel:

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

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

$a\cap (b\cup (a\cap c))=(a\cap b)\cup (a\cap c)$ minden $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

$a\cap b=0$ és $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 $(L,\sqcup ,\sqcap )$ és $(M,\cup ,\cap )$ két háló. Ha az $f:L\to M$ függvényre teljesül, hogy

$f(a\sqcup b)=f(a)\cup f(b)$

$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 $\cup$ b és a $\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ó

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