Háló (matematika)

A Wikipédiából, a szabad enciklopédiából
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ó[szerkesztés | forrásszöveg szerkesztése]

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

Definíció részbenrendezett halmazok használatával[szerkesztés | forrásszöveg szerkesztése]

Az (A; ) 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; ) 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

  • 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<=b ekvivalens a \cup b = b. Erre a rendezésre minden kételemű halmaznak van legkisebb felső korlátja és legnagyobb alsó korlátja.
  • b fedi a -t, ha a<b , és nincs c, a<c<b.

Hasse-diagramok[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

ab, 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[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Dean, E. T.: Dedekind's treatment of Galois Theory in the Vorlesungen. 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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

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