3. Nevezetes kétváltozós relációk

3.1. Az ekvivalenciareláció

Legyen 'A' tetszőleges halmaz. Az 'A' halmazon értelmezett ρ⊆AΧA kétváltozós (binér) relációt ekvivalenciarelációnak nevezzük, ha reflexív, szimmetrikus és tranzitív.

Például a természetes számokon értelmezett egyenlőség ( = ) ekvivalenciareláció.

Legyen 'A' tetszőleges véges halmaz,
Η = { A₁, A₂, ..., A_n } pedig az A halmaz nem üres részhalmazainak halmaza, amelyekre teljesül, hogy
   (a) A_i⊆A és A_i≠∅ (i=1, 2, ..., n),
   (b) a részhalmazok páronként diszjunktak, azaz minden 1 ≤ i≠j ≤ n esetén A_i ∩ A_j = ∅, és
   (c) a részhalmazok uniója magát az A halmazt adja, azaz
A₁ ∪ A₂ ∪ ... ∪ A_n = A teljesül.

A Η⊆2^A halmazt az 'A' halmaz egy osztályozásának nevezzük, az A_i∈Η részhalmazokat (1 ≤ i ≤ n) pedig osztályoknak.

Legyen 'A' egy tetszőleges halmaz. Az 'A' halmaz részhalmazainak egy Η⊆2^A rendszere osztályozás, ha
– Η nem tartalmazza az üres halmazt,
– Η elemei (az ún. osztályok) páronként diszjunktak, és
– Η elemeinek uniója az 'A' halmazt adja.

Egy halmaz elemeinek osztályozását Venn-diagram segítségével például a következőképpen szemléltethetjük:

Például tekintsük a korábban bevezetett, 10 tanulóból álló 'I' osztályt^⇒ és értelmezzük a tanulók között a ψ⊆IΧI relációt a következőképpen:

ψ(x,y) ⇆ "az 'x' és 'y' tanulók érdemjegye megegyezik matematikából"

Ha bevezetjük a tárgyak
T = {"magyar", "matek", "tesi", "angol", ...}
halmazát és a
jegy : IΧT→{1, 2, 3, 4, 5}
"osztályozó" függvényt^⇒, a fenti reláció formálisan
ψ = {(x,y) | x∈I, y∈I, jegy(x,"matek")=jegy(y,"matek")}
módon adható meg.

Például jegy("Fercsi","matek")=5 és jegy("Kata","matek")=5 esetében ("Fercsi","Kata")∈ψ, azaz ψ("Fercsi","Kata") teljesül.

A ψ reláció ekvivalenciareláció, mert

• bármely x∈I tanulóra ψ(x,x) nyilvánvalóan teljesül (reflexivitás);
• ha az x∈I és y∈I tanulókra ψ(x,y) teljesül, akkor ψ(y,x) is teljesül (szimmetria);
• ha az x∈I és y∈I tanulókra ψ(x,y) teljesül, valamint az y∈I és z∈I tanulókra ψ(y,z) szintén teljesül, akkor ψ(x,z) is teljesül (tranzitivitás).

Hozzuk létre az 'I' osztályban az alábbi halmazokat a tanulók matematikából kapott jegyei alapján:

I_i = {x∈I | jegy(x,"matek")=i} (i=1,2,...,5)

Vegyük észre, hogy az egyes I_i halmazokba sorolt tanulók matematikai jegye megegyezik:

• az I₅ halmazban mindenki jelest kapott matematikából ("jeles" tanulók);
• az I₄ halmazban mindenki jót kapott matematikából ("jó" tanulók);
• az I₃ halmazban mindenki közepest kapott matematikából ("közepes" tanulók);
• az I₂ halmazban mindenki elégségest kapott matematikából ("gyenge" tanulók);
• az I₁ halmazban mindenki elégtelent kapott matematikából ("problémás" tanulók).

Mindegyik I_i halmazra igaz, hogy a halmazba tartozó bármelyik két x∈I_i és y∈I_i tanuló esetén ψ(x,y) teljesül (azaz az 'x' és 'y' tanulók jegye azonos matematikából).

Vegyük azokat az I_i halmazokat, amelyek nem üresek, és hozzuk létre ezekből a Η halmazrendszert:

Η = {I_i | I_i≠∅, i=1,2,...,5}

(a) Az így definiált Η halmazrendszer az 'I' osztály egy ψ reláció szerinti osztályozása, mivel Η nem tartalmazza az üres halmazt, továbbá
– az I_i halmazok diszjunktak (minden tanuló pontosan egy I_i halmazba tartozik), és
– az I_i halmazok uniója a teljes 'I' osztályt adja (azaz minden tanuló beletartozik valamelyik I_i halmazba).

(b) Az előző gondolatsor megfordítása is igaz: ha adottak az egyes I_i halmazok, amelyekbe az 'i' érdemjegyet kapott tanulók tartoznak bele (1≤i≤5), a segítségükkel értelmezett
ψ' = {(x,y) | x∈I, y∈I, és van olyan I_i halmaz, amelyre x∈I_i és y∈I_i teljesül}
reláció megegyezik a korábban definiált^⇒ ψ relációval.

---

A fenti konkrét példából is jól látszik, hogy ekvivalenciarelációk és az osztályozások között szoros kapcsolat van:
   (a) minden ρ ⊆ AΧA ekvivalenciarelációnak megfelel az 'A' halmaz egy "természetes" Η osztályozása (az egyes osztályokat a ρ szerint ekvivalens elemek alkotják);
   (b) az 'A' halmaz minden Η osztályozása "természetes" módon meghatároz egy ρ ⊆ AΧA ekvivalenciarelációt (azokat az elemeket tekintjük ρ szerint ekvivalensnek, amelyek azonos osztályba tartoznak).

(a) Ha adott egy ρ⊆AΧA ekvivalenciareláció, akkor az 'A' halmaznak pontosan azokat az x, y∈A elemeit soroljuk egy osztályba, amelyekre ρ(x,y) teljesül, azaz az elemek ρ szerint ekvivalensek.

Mivel a ρ reláció reflexív, az osztályok nem üresek. Mivel a ρ reláció szimmetrikus, két elem csak egy osztályba tartozhat, és a reláció tranzitivitása miatt ez nemcsak kettő, hanem három (négy, öt, ...) elemre is igaz. Ha tehát két osztálynak lenne közös eleme, akkor a ρ reláció szimmetriája és tranzitivitása miatt az oszályok egybeesnének, ezért a különböző osztályok diszjunktak. Mivel pedig minden elem beletartozik valamelyik osztályba, ezért az osztályok uniója lefedi a teljes 'A' halmazt.

Tekintsük például a Dienes Zoltán által kifejlesztett logikai készletet:

A készlet elemei között számos olyan közös tulajdonság található (színek, formák stb.), amelyek a segítségével a készlet összes eleme diszjunkt csoportokba sorolható, vagyis osztályozható. Az osztályozás alapját képező ekvivalenciareláció nemcsak egy, hanem több közös tulajdonságot is magába foglalhat (pl. ρ(x,y) ⇋ "'x' és 'y' azonos színű és egyforma méretű" stb.)

(b) Ha adott az 'A' halmaz egy Η osztályozása, akkor az 'A' halmaznak pontosan azokat az x, y∈A elemeit tekintjük egymással relációban állóknak (ρ szerint ekvivalenseknek), amelyek azonos osztályba tartoznak.

Mivel minden elem önmagával azonos osztályban van, az "egy halmazba tartozás" reflexív reláció. Ha két elem ugyanabban az osztályban van, akkor sorrendtől függetlenül relációban vannak, tehát a reláció szimmetrikus. Ha pedig egy adott elem két másikkal azonos osztályban van, akkor biztos, hogy azok az elemek is ugyanabban az osztályban vannak, tehát a reláció tranzitív is.

Az előző feladat megfordítása: alakítsunk ki (diszjunkt) csoportokat a logikai készlet elemeiből és határozzuk meg a csoportosítás alapjául szolgáló közös tulajdonságot vagy tulajdonságokat!

3.1.1. Példák

Az 'A' halmaz elemei között értelmezett egyenlőség (=) reláció ekvivalenciareláció, amelyhez az 'A' halmaz triviális

Η_A = {{x} | x∈A}

osztályozása tartozik. (Például ha A={a,b,c}, akkor Η_A = {{a},{b},{c}}, azaz minden osztály egy egyelemű halmaz, és az osztályok száma megegyezik 'A' elemeinek számával, azaz |Η_A|=3 teljesül.)

A halmazelemek közti egyenlőség reláció és pl. a racionális számok között értelmezett egyenlőség reláció nem esik egybe. Tekintsük például a
    P={1, 2/2, 0.5, 1/2, 2/4}⊆ℚ, |R|=5
halmazt. A P halmaznak a racionális számok között értelmezett egyenlőség (=) reláció szerinti osztályozása
    P₁={1, 2/2} és P₂={0.5, 1/2, 2/4}.

---

Egy négy elemből álló A = {1, 2, 3, 4} halmaz összes lehetséges Η osztályozását (vagy felbontását, partícionálását) a következőképpen kaphatjuk meg:^⇒

• kiindulunk magából az 'A' halmazból, amely egy osztályból álló osztályozásnak tekinthető (azaz minden elemét ekvivalensnek tekintjük) (Η={A₁}, ahol A₁=A={1, 2, 3, 4} );
• képezzük a két osztályból álló osztályozásokat: az 'A' halmaz elemeit két diszjunkt osztályra bontjuk az összes lehetséges módon (pl. az ábra második sorában szereplő első osztályozás, '14/23' jelentése: Η={A₁, A₂}, ahol A₁={1, 4} és A₂={2, 3} );
• képezzük a három osztályból álló osztályozásokat: a két osztályból álló osztályozásokat tovább bontjuk úgy, hogy egy kiválasztott osztályt két további osztályra bontunk az összes lehetséges módon (pl. az ábra harmadik sorában szereplő első osztályozás, '1/23/4' jelentése: Η={A₁, A₂, A₃}, ahol A₁={1}, A₂={2, 3} és A₃={4} );
• végül megkapjuk a négy osztályból álló osztályozást: egy ilyen osztályozás van, amelyben az egyes osztályok az 'A' halmaz egy elemű részhalmazai (Η={A₁, A₂, A₃, A₄}, ahol A₁={1}, A₂={2}, A₃={3}, A₄={4} (vegyük észre, hogy ez az osztályozás megegyezik a korábban említett Η_A triviális osztályozással).

Figyeljük meg, hogy mindegyik osztályozást egy másik osztályozásból kaptunk úgy, hogy egy kiválasztott osztályt felbontottunk két további (diszjunkt) osztályra. Ezért a kiinduló osztály minden esetben tartalmazza a felbontással ("finomítással") kapott osztályokat. A lehetséges osztályozások szemléletesen ábrázolhatóak egy ún. Hasse-diagramon,^⇒ ahol az osztályok közötti relációkat vonallal jelöltük. A diagramon a kiinduló osztályozás mindig feljebb, a felbontás eredményeként kapott osztályozás pedig mindig lejjebb szerepel, ezért a felbontás (az osztályok közötti "felbontási reláció") irányát nem szükséges feltüntetni.

Az osztályok közötti "felbontási" reláció egy lehetséges definíciója két tetszőleges Η_x és Η_y osztályra:
Η_x≼Η_y ⇋ ∀A_i∈Η_x ∃A_j∈Η_y (A_i⊆A_j)
Az így definiált ≼ reláció könnyen beláthatóan reflexív, antiszimmetrikus és tranzitív (vagyis rendezési reláció, amivel a következőkben fogunk foglalkozni).

Végül figyeljük meg, hogy az ábrán 2⁴−1=15 csomópont található, ami a négy elemből álló (véges) 'A' halmaz összes lehetséges osztályozásainak számát adja meg. Mivel a 'k'-dik szinten lehetséges osztályozás lehetséges ('n' elemből 'k' osztályt választunk ki az elemek sorrendjétől függetlenül), az összefüggés a binomiális tétel alapján könnyen belátható.

---

Az osztályozások egyik leggyakoribb formája egy adott halmaz elemeinek megkülönböztetése több különböző tulajdonság alapján, és ennek megfelelően az elemek elrendezése egy hierarchikus, ún. fastruktúrában (vagy fadiagramon).

Tekintsük például a következő feladatot (vö. Miklovicz 2018: 16-17):

Juli azon gondolkodik, milyen ruhát vegyen fel. A szekrényében a következő ruhák vannak:

• két sapka (piros, zöld),
• három blúz (kék, piros, sárga) és
• két szoknya (kék, zöld).

Legyen az 'R' halmaz Juli összes lehetséges öltözete:

R = {(piros sapka, kék blúz, kék szoknya), (piros sapka, kék blúz, zöld szoknya), (piros sapka, piros blúz, kék szoknya), ..., (zöld sapka, sárga blúz, zöld szoknya)}

(az 'R' halmaz elemszáma: |R|=2*3*2=12)

Az 'R' halmazt három tulajdonság segítségével osztályozzuk:
sapka_szine : R→{piros, zöld}
bluz_szine : R→{kék, piros, sárga}
szoknya_szine : R→{kék, zöld}

Alakítsuk ki a következő négy osztályozást:

• kiindulunk magából az 'R' halmazból, amely egy osztályból álló osztályozásnak tekinthető
  
  • Η₀={R}, |Η₀|=1
• képezzük a sapka színe szerinti osztályozást: az 'R' halmaz elemeit annyi osztályra bontjuk, ahány különböző színű sapkája van Julinak
  
  • Η₁={S_piros, S_zöld}, |Η₁|=2, ahol
    • S_piros={x∈R | sapka_szine(x)=piros} és
    • S_zöld={x∈R | sapka_szine(x)=zöld};
  • mivel S_piros∩S_zöld=∅ és S_piros∪S_zöld=R teljesül, ezért Η₁ az 'R' halmaz osztályozása
• képezzük a blúz színe szerinti osztályozást: a sapka színe szerint képzett osztályokat (pl. S_piros) annyi további osztályra bontjuk, ahány különböző színű blúza van Julinak
  
  • Η₂={B_piros−kék, B_{piros−piros}, ..., B_{zöld−sárga}}, |Η₂|=2*3=6, ahol pl.
    • B_piros−kék={x∈R | sapka_szine(x)=piros, bluz_szine(x)=kék}
    • B_{piros−piros}={x∈R | sapka_szine(x)=piros, bluz_szine(x)=piros}
    • ...
    • B_{zöld−sárga}={x∈R | sapka_szine(x)=zöld, bluz_szine(x)=sárga}
  • S_piros=B_piros−kék∪B_{piros−piros}∪B_{piros−sárga}
  • S_zöld=B_zöld−kék∪B_{zöld−piros}∪B_{zöld−sárga}
• végül képezzük a szoknya színe szerinti osztályozást: a sapka és a blúz színe szerint képzett osztályokat (pl. B_piros−kék) annyi további osztályra bontjuk, ahány különböző színű szoknyája van Julinak
  
  • Η₃={Z_{piros−kék−kék}, Z_{piros−kék−zöld}, ..., Z_{zöld−sárga−zöld}}, |Η₃|=2*3*2=12, ahol az egyes osztályok az 'R' halmaz elemeiből képzett egyelemű halmazok (mivel feltettük, hogy Julinak minden színű sapkából, blúzból és szoknyából egy darab van), pl.
    • Z_{piros−kék−kék}={x∈R | sapka_szine(x)=piros, bluz_szine(x)=kék, szoknya_szine(x)=kék}={(piros sapka, kék blúz, kék szoknya)}
    • Z_{piros−kék−zöld}={x∈R | sapka_szine(x)=piros, bluz_szine(x)=kék, szoknya_szine(x)=zöld}={(piros sapka, kék blúz, zöld szoknya)}
    • ...
  • B_piros−kék=Z_{piros−kék−kék}∪Z_{piros−kék−zöld}
  • B_{piros−piros}=Z_{piros−piros−kék}∪Z_{piros−piros−zöld}
  • ...

Ábrázoljuk a különböző osztályozásokat egy négy szintű fadiagramon! (A szekrénynek a Η₀ osztályozás, a sapkák hierarchia­szintjének a Η₁ osztályozás, a blúzok hierarchia­szintjének a Η₂ osztályozás, végül a szoknyák hierarchia­szintjének a Η₃ osztályozás felel meg.)

• A fadiagram minden szintje az adott 'R' halmaz egy osztályozásának felel meg.
• A fadiagram élei az egyes osztályok kapcsolatát mutatják: a magasabb hierarchiaszinten levő ("szülő") osztályokhoz kapcsolt ("leszármazott") osztályok a szülő osztály elemeit bontják fel diszjunkt alosztályokra.

Jegyezzük meg, hogy az ábrázolt fadiagram felhasználható arra is, hogy segítse Julit a megfelelő ruhaválasztásban. Juli először sapkát választ (például pirosat; innentől már csak 6 öltözet közül választhat), utána ruhát (pélául sárgát; innentől már csak 2 öltözet közül választhat), majd végül szoknyát (például kéket; ezzel megvan az az öltözet, amely mellett döntött). A választás minden lépésben egy adott tulajdonság kiválasztását jelenti, amely meghatározza, hogy a fa melyik ágán kell tovább haladnunk, míg végül eljutunk a legalsó szintig. Ebben az értelemben a fadiagramot döntési fának is nevezhetjük.

Természetesen Juli megválaszthatja az öltözetét úgy is, hogy először egy szoknyát választ, ezután a kiválasztott szoknyához egy blúzt, majd végül egy sapkát mint kiegészítőt. Ez az alábbi döntési fának felel meg:

A fastruktúra legfelső csomópontját gyökérelemnek szokás nevezni, a fastruktúra legalsó szintjén levő csomópontokat pedig levélelemeknek.

Figyeljük meg, hogy a levélelemeket leszámítva minden csomópontból egy vagy több él indul ki; és a gyökérelemet leszámítva minden csomópontba pontosan egy él fut be. Ezt úgy is kifejezhetjük, hogy
– a gyökérelemnek nincs szülőeleme, de több leszármazottja lehet,
– a levélelemeknek pontosan egy szülőeleme van, de nincsenek leszármazott elemei,
– minden további csomópontnak pontosan egy szülőeleme és több leszármazottja lehet.

Egy fastruktúrában a gyökérelemből kiindulva és végig lefelé haladva a struktúrában minden levélelemhez pontosan egy út vezet.

3.2. Rendezési relációk

Legyen 'A' tetszőleges halmaz. Az 'A' halmazon értelmezett ρ⊆AΧA kétváltozós (binér) relációt reflexív (vagy "gyenge") rendezési relációnak nevezzük, ha reflexív, antiszimmetrikus és tranzitív.

Legyen 'A' tetszőleges halmaz. Az 'A' halmazon értelmezett ρ⊆AΧA kétváltozós (binér) relációt irreflexív (vagy "szigorú") rendezési relációnak nevezzük, ha irreflexív, aszimmetrikus és tranzitív.

Ha az 'A' halmazon értelmezve van egy ρ rendezési reláció, azt (A; ρ) módon jelöljük.

• Ha a ρ rendezési reláció trichotóm, akkor teljes rendezési relációnak nevezzük, az (A; ρ) halmazt pedig teljesen rendezett halmaznak (a ρ reláció szerint) (szokásos a lineárisan rendezett halmaz elnevezés is, Szendrei 1975: 41);
• ha a ρ rendezési reláció nem trichotóm, akkor parciális rendezési relációnak nevezzük, az (A; ρ) halmazt pedig részben (vagy parciálisan) rendezett halmaznak (a ρ reláció szerint).

Például a természetes számokon (ℕ) értelmezett

• "kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk gyenge és teljes rendezési relációk, mert reflexívek, antiszimmetrikusak és tranzitívek, valamint trichotómak;
• "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk szigorú és teljes rendezési relációk, mert irreflexívek, aszimmetrikusak és tranzitívek, valamint trichotómak.
• oszthatóság ( | ) gyenge és parciális rendezési reláció, mert reflexív, antiszimmetrikus és tranzitív, azonban nem trichotóm (mivel pl. a 3 és 7 természetes számok nem osztói egymásnak, és nem egyenlőek);

Például az 'I' halmaz 2^I hatványhalmazán (azaz az 'I' halmaz összes részhalmazának halmazán) értelmezett

• részhalmaz (⊆) reláció gyenge és parciális rendezési reláció a 2^I hatványhalmazon, mert reflexív, antiszimmetrikus és tranzitív, de nem trichotóm; tehát (2^I; ⊆) parciálisan rendezett halmaz (mivel pl. az {a,b} és {a,c} halmazok között sem a részhalmaz reláció, sem az egyenlőség nem áll fenn, a ⊆ reláció nem trichotóm);
• valódi részhalmaz (⊂ ) reláció szigorú és parciális rendezési reláció a 2^I hatványhalmazon, mert irreflexív, aszimmetrikus és tranzitív, de nem trichotóm; tehát (2^I; ⊂) szintén parciálisan rendezett halmaz

---

Legyen az (A; ρ) halmaz részben rendezett. Vezessük be az egymással rendezési relációban levő a, b∈A elemekre az a≼b ⇋ ρ(a,b) jelölést (a≼b ⇋ "a előtte van b-nek" vagy "a megelőzi b-t").

Láttuk korábban, hogy minden binér reláció ábrázolható egy irányított gráf segítségével. Rendezési relációk esetén a gráf ábrázolása jelentősen leegyszerűsíthető.

Ha az (A; ρ) részben rendezett halmaz véges, akkor ábrázolhatjuk egy irányított gráf, az ún. Hasse-diagram segítségével. A Hasse-diagramot a következőképpen állíthatjuk elő:

• az 'A' halmaz elemeit a gráf csomópontjaiként ábrázoljuk;
• csak azok között az x, y∈A (x≠y) elemek között rajzolunk élt, amelyekre
  • egyrészt x≼y teljesül,
  • másrészt nem létezik olyan "köztes" z∈A (z≠x, z≠y) elem, amelyre x≼z≼y teljesül (ilyenkor azt mondjuk, hogy az 'x' elem közvetlenül megelőzi az 'y' elemet, vagy másképpen az 'y' elem fedi az 'x' elemet, vö. Kiss 2007: 336) ;
• a gyenge rendezési reláció reflexivitásából^⇒ adódó hurokéleket a diagramon nem ábrázoljuk;^⇒
• ha az x, y∈A (x≠y) elemekre x≼y teljesül, akkor x-et lejjebb, y-t feljebb ábrázoljuk. Ilyen ábrázolás esetén a csomópontok elhelyezkedése meghatározza a relációt jelző él irányát (mivel az élek mindig felfelé mutatnak, a gráfban a rendezési reláció irányát követve "felfelé haladunk"), ezért a relációban álló csomópontokat irányítás nélkül is összeköthetjük.

A Hasse-diagram két fontos tulajdonsága:

• a diagramban, ha kiindulunk egy csomópontból, az élek irányában haladva sosem jutunk vissza a kiinduló csomópontba (a rendezési reláció antiszimmetriája és tranzitivitása miatt a diagram nem tartalmaz önmagába záruló irányított utat, "kört")
• ha a diagramot "fejjel lefelé" fordítjuk, egy "duális" Hasse-diagramhoz jutunk, ahol
  • az első diagram az (A; ≼) rendezésnek felel meg
  • a második diagram pedig az (A; ≽) rendezésnek felel meg (ahol a≽b ⇔ b≼a teljesül)

Például ábrázoljuk az A={a, b, c} halmaz esetén a (2^A; ⊆) részben rendezett halmaz elemeit Hasse-diagrammal:

Szemléletesen azt is mondhatjuk, hogy a fenti diagramon az üreshalmaz a "legkisebb" (legalsó) elem, amely minden elemnek részhalmaza; az A={a, b, c} halmaz pedig a "legnagyobb" (legfelső) elem, amelynek minden, az ábrán szereplő elem a részhalmaza.

Figyeljük meg, hogy egyes csomópontokból több él indulhat ki, bizonyos csomópontokba több él futhat be, és a "legkisebb" elemből több különböző irányított úton keresztül is eljuthatunk a "legnagyobb" elemhez. Visszafelé azonban egyetlen csomópontból sem vezet út, a fenti diagramon csak "felfelé" haladhatunk.

---

Korábban már ábrázoltuk táblázatos formában egy három elemű alaphalmaz részhalmazai között értelmezett részhalmaz relációt.^⇒ Ábrázoljuk most az A={a b c} alaphalmaz tetszőleges P, Q∈2^A elemei közötti részhalmaz relációt (P⊆Q) egy táblázatban a következőképpen:
– a relációban álló elemeket a megfelelő cellában 1 értékkel jelöljük;
– a "közvetlenül" relációban álló (egymást fedő) elemeket a megfelelő cellában piros színnel kiemeljük, a "nem közvetlenül" relációban álló elemek esetében pedig fekete háttért alkalmazunk;
– a relációban nem álló elemeket pedig a megfelelő cellában 0 értékkel jelöljük.

P⊆Q	←Q→
↓P↓	∅	{a}	{b}	{c}	{a,b}	{a,c}	{b,c}	{a,b,c}
∅	1	1	1	1	1	1	1	1
{a}	0	1	0	0	1	1	0	1
{b}	0	0	1	0	1	0	1	1
{c}	0	0	0	1	0	1	1	1
{a,b}	0	0	0	0	1	0	0	1
{a,c}	0	0	0	0	0	1	0	1
{b,c}	0	0	0	0	0	0	1	1
{a,b,c}	0	0	0	0	0	0	0	1
↑P↑	∅	{a}	{b}	{c}	{a,b}	{a,c}	{b,c}	{a,b,c}

Figyeljük meg, hogy a Hasse-diagramon pontosan annyi élt ábrázoltunk, ahány cellában pirossal kiemelt 1 érték szerepel a táblázatban (összesen 12).

---

Az A={a, b, c} halmaz esetén a (2^A; ⊆) részben rendezett halmaz elemeit ábrázoló Hasse-diagram számos információt szolgáltat:

• az élekkel összekötött csomópontok részhalmaz relációban (⊆) állnak (egy vagy több köztes csomópont esetén az összekötött csomópontok közötti részhalmaz relációt az ábra a reláció tranzitivitása miatt közvetve ábrázolja)
  • általánosan megfogalmazva a rendezési reláció (≼) iránya alulról felfelé mutat (azaz a "kisebb" elemből a "nagyobb" elem felé) (pl. {a}→{a,b} tehát {a}⊆{a,b})
• az ábrán a "legnagyobb" elem maga az 'A' halmaz, amelynek minden, az ábrán szereplő elem a részhalmaza
• az ábrán a "legkisebb" elem az üreshalmaz (∅), amely minden elemnek részhalmaza
• két részhalmaz unióját úgy kapjuk meg, hogy az ábrán felfelé haladva megkeressük az első (relatíve "legkisebb") olyan közös csomópontot, amelyhez mindkét részhalmazból él vezet; például
  • {a}→{a,b} és {b}→{a,b} tehát {a}∪{b}={a,b}
  • {a}→{a,b}→{a,b,c} és {b,c}→{a,b,c} tehát {a}∪{b,c}={a,b,c}
  • {a}→{a,b} tehát {a}∪{a,b}={a,b} (ebben a példában a közös csomópont egybeesik az egyik részhalmazzal)
• két részhalmaz metszetét úgy kapjuk meg, hogy az ábrán lefelé haladva megkeressük az első (relatíve "legnagyobb") olyan közös csomópontot, amelyből mindkét részhalmazhoz él vezet; például
  • {a}→{a,b} és {a}→{a,c} tehát {a,b}∩{a,c}={a}
  • ∅→{a} és ∅→{b}→{b,c} tehát {a}∩{b,c}=∅
  • {a}→{a,b} tehát {a}∩{a,b}={a} (ebben a példában a közös csomópont most is egybeesik az egyik részhalmazzal)

Összefoglalva, ha egy 'A' halmaz összes részhalmazát a részhalmaz-reláció szerint parciálisan elrendezzük és a rendezést egy Hasse-diagramon ábrázoljuk, akkor

• Ha 'P' és 'Q' az ábrán szereplő két tetszőleges csomópont, akkor az uniójukat jelentő csomópont (C) az a "legkisebb" olyan halmaz, amelyre mind P⊆C, mind Q⊆C teljesül.^⇒
• Ha 'P' és 'Q' az ábrán szereplő két tetszőleges csomópont, akkor a metszetüket jelentő csomópont (C) az a "legnagyobb" olyan halmaz, amelyre mind C⊆P, mind C⊆Q teljesül.^⇒

Jegyezzük meg, hogy a fenti megállapítások akkor is teljesülnek, ha az 'A' halmaz részhalmazainak egy olyan B⊆2^A halmazát rendezzük el a fenti módon, amely zárt az unióképzés és metszetképzés műveleteire (azaz bármely két P, Q∈B halmazra P∪Q∈B és P∩Q∈B teljesül).

Például ha a P⊆A és Q⊆A elemek unióját keressük, akkor
    (1) induljunk ki a C₀=A={a,b,c} halmazból és vizsgáljuk meg az összes C₀-t közvetlenül megelőző csomópontot;
    (2) ha találunk egy olyan C₁→C₀ elemet, amelyre mind P⊆C₁ , mind Q⊆C₁ teljesül (amely egybeeshet P-vel vagy Q-val), akkor a következő lépésben a C₁-t közvetlenül megelőző csomópontokat vizsgáljuk meg (majd ismételjük meg ugyanezt C₂→C₁-re, C₃→C₂-re stb.);
    (3) a legutolsó C_i csomópont, amelyre mind Q⊆C_i , mind P⊆C_i teljesül, éppen a keresett unió lesz, azaz C_i=Q∪P teljesül.^⇒

---

Ezek után ábrázoljuk az A={1, 2, 3, 4} számhalmaz esetén az (A; ≤) teljesen vagy lineárisan rendezett halmaz elemeit Hasse-diagrammal. Az előző ábrával összehasonlítva figyeljük meg a parciális és teljes rendezés közötti különbséget a Hasse-diagramon:

Vegyük észre, hogy a diagram a teljes rendezés miatt egy egyenesre egyszerűsödött.

Ha egy véges 'A' halmazon értelmezünk egy ρ⊆AΧA teljes rendezési relációt, akkor egy megfelelő algoritmus segítségével az 'A' halmaz elemei "lineárisan" sorba rendezhetők.

---

A parciális és teljes rendezés közötti különbséget azzal is jól tudjuk szemléltetni, ha a részben (parciálisan), ill. teljesen rendezett halmazok megfelelő elemeire értelmezzük a "legkisebb" ("legnagyobb") elem, ill. "minimális" ("maximális") elem fogalmakat.

Legyen ρ⊆AΧA az 'A' halmazon értelmezett (parciális vagy teljes) rendezési reláció, és vezessük be most is az egymással relációban levő a, b∈A elemekre az a≼b ⇋ ρ(a,b) jelölést. Ekkor az (A; ≼) (részben vagy teljesen) rendezett halmaz

• legkisebb eleme az az x_lk∈A elem, amelyre igaz, hogy minden y∈A elemre x_lk≼y teljesül;
• legnagyobb eleme az az x_ln∈A elem, amelyre igaz, hogy minden y∈A elemre y≼x_ln teljesül;
• minimális eleme az az x_min∈A elem, amelyre igaz, hogy nem létezik olyan y∈A, y≠x_min elem, amelyre y≼x_min teljesül (vagyis nincs az 'A' halmaznak másik olyan eleme, amely a minimális elemnél "kisebb");
• maximális eleme az az x_max∈A elem, amelyre igaz, hogy nem létezik olyan y∈A, y≠x_max elem, amelyre x_max≼y teljesül (vagyis nincs az 'A' halmaznak másik olyan eleme, amely a maximális elemnél "nagyobb").

A legkisebb / legnagyobb és minimális / maximális elemekre teljesülnek az alábbi tételek:

(részben rendezett halmazokra)

Ha létezik egy részben rendezett halmaznak legnagyobb eleme, akkor az egyúttal maximális elem is. Ha létezik egy részben rendezett halmaznak legkisebb eleme, akkor az egyúttal minimális elem is (vö. Bogya 2018: 19).

Egy részben rendezett halmazban legnagyobb, ill. legkisebb elemből legfeljebb egy darab létezhet, ugyanakkor maximális, ill. minimális elemből több is lehet (vö. Bogya 2018: 19).

(teljesen rendezett halmazokra)

Teljesen rendezett halmazok esetében a legkisebb elem és a minimális elem, valamint a legnagyobb elem és a maximális elem egybeesik (vö. Nagy 2017: 5. ea.).

Egy teljesen rendezett halmaznak legfeljebb egy minimális eleme és legfeljebb egy maximális eleme lehet (Dringó-Kátai 1986: 29).

---

Legyen például A={1,2,...,8}, és tekintsük az 'A' halmazon az oszthatósági relációt (amely gyenge parciális rendezési reláció). Ekkor

• az 'A' halmaz legkisebb eleme 1 (mivel 1 minden természetes számnak osztója, tehát 'A' minden elemének is osztója);
• az 'A' halmaznak legnagyobb eleme nem létezik (ugyanis 'A'-ban nincs olyan elem, amelynek 'A' minden eleme osztója lenne);
• az 'A' halmaz minimális eleme 1 (mert nincs olyan természetes szám, amely rajta kívül osztója lenne, tehát 'A' elemei között sincs ilyen szám);
• az 'A' halmaz maximális elemei az 5, 6, 7 és 8 számok (ugyanis 'A'-ban nincs olyan elem, amelynek ezek a számok osztói lennének).

Az (A; |) oszthatóság szerint részben rendezett halmaz Hasse-diagramja:

Ha az 'A' halmazt kibővítjük úgy, hogy 'A' tetszőleges két elemének legkisebb közös többszöröse is eleme legyen a halmaznak (azaz az 'A' halmaz elemein kívül a {2,3,5,7}, {2²=4,3,5,7} és {2³=8,3,5,7} számokból képezhető összes 2,3 és 4 tényezőből álló különböző részszorzat), akkor az így kapott

A^K=A∪{10, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 56, 60, 70, 84, 120, 125, 140, 147, 210, 280, 420, 840}

kibővített halmaznak egy legkisebb eleme (1) lesz, amely egyben minimális elem is, és egy legnagyobb eleme lesz (2³*3*5*7=840), amely egyben maximális elem is. Emellett az így képzett A^K halmaz zárt lesz a halmaz elemei között értelmezett legkisebb közös többszörös (lkkt) műveletre.

Jegyezzük meg, hogy bizonyos feltételek fennállása mellett a természetes számok között értelmezett oszthatósági relációt (|) ábrázoló Hasse-diagram a korábbi, az A={a, b, c} halmaz részhalmazait ábrázoló Hasse-diagramhoz hasonló információkat szolgáltat.
(1) A részhalmazok közötti unió műveletének a diagramon ábrázolt természetes számok között értelmezett legkisebb közös többszörös (lkkt) művelet felel meg (például [2,3]=6 stb.).
(2) A részhalmazok közötti metszet műveletének pedig a diagramon ábrázolt természetes számok között értelmezett legnagyobb közös osztó (lnko) művelet felel meg (például (4,6)=2 stb.).

Mindennek az a feltétele, hogy az (A; |) részben rendezett halmaz mind az lkkt, mind az lnko műveletekre zárt legyen (a fenti diagramon ábrázolt 'A' halmazra ez nyilván nem teljesül, pl. [3,4]=12 vagy [3,5]=15 nem eleme A-nak).

---

Legyen A={1, 2, 3, 5, 6, 10, 15, 30} és ábrázoljuk az (A; |) részben rendezett halmazt Hasse-diagram segítségével:

Figyeljük meg, hogy az (A; |) halmaz zárt az lkkt és az lnko műveletekre, azaz bármely két a, b∈A⊆ℕ természetes szám esetén (a,b)∈A és [a,b]∈A teljesül.

3.3. Hálók (kiegészítő anyag)

Azokat a korábban bevezetett (A; ≼) részben rendezett halmazokat, amelyek zártak az elemek között értelmezett (és meghatározott tulajdonságokkal rendelkező) metszet (vagy lnko stb.), és unió (vagy lkkt stb.) műveletekre, hálóknak nevezzük, és (A; ⌢, ⌣) módon jelöljük (vö. Birkhoff-Bartee 1974: 218; Szendrei 1975: 416).

Az (A; ≼) részben rendezett halmazon értelmezett műveleteket bizonyos feltételek fennállása esetén a ≼ rendezési reláció segítségével is definiálhatjuk.

Az (A; ≼) részben rendezett halmaz egy tetszőleges R⊆A (R≠∅) részhalmazának a legnagyobb alsó korlátja (infimuma) alatt azt az X_inf∈A elemet értjük, amelyre
(1) ∀X∈R (X_inf≼X) (azaz az X_inf elem megelőzi 'R' minden elemét), és
(2) ∀Y∈A (∀X∈R (Y≼X) ⊃. Y≼X_inf) (azaz azok az elemek, amelyek megelőzik 'R' minden elemét, megelőzik az X_inf elemet is)
teljesül. Az 'R' részhalmaz legnagyobb alsó korlátját inf R módon jelöljük.

Például a (2^I,⊆) részben rendezett halmazon P∩Q=inf {P, Q} teljesül minden P, Q∈2^I (azaz P, Q⊆I) részhalmazra (vö. Szendrei 1975: 416).

Az (A; ≼) részben rendezett halmaz tetszőleges egy R⊆A (R≠∅) részhalmazának a legkisebb felső korlátja (szuprémuma) alatt azt az X_sup∈A elemet értjük, amelyre
(1) ∀X∈R (X≼X_sup) (azaz 'R' minden eleme megelőzi az X_sup elemet), és
(2) ∀Y∈A (∀X∈R (X≼Y) ⊃. X_sup≼Y) (azaz az X_sup elem megelőzi az összes olyan elemet, amelyeket 'R' minden eleme megelőz)
teljesül. Az 'R' részhalmaz legkisebb felső korlátját sup R módon jelöljük.

Például a (2^I,⊆) részben rendezett halmazon P∪Q=sup {P, Q} teljesül minden P, Q∈2^I (azaz P, Q⊆I) részhalmazra (vö. Szendrei 1975: 416).

Ha egy (A; ≼) részben rendezett halmaz bármely két P, Q∈A eleme esetén léteznek a P⌢Q ⇋ inf {P, Q} és a P⌣Q ⇋ sup {P, Q} elemek (azaz P⌢Q∈A és P⌣Q∈A teljesül), akkor az (A; ≼) részben rendezett halmaz meghatároz egy (A; ⌢, ⌣) hálót.

Egy adott alaphalmaz esetében a metszet és unió művelet legfontosabb tulajdonságait korábban már megismertük.^⇒ Ezek közül egy tetszőleges (A; ⌢, ⌣) háló esetében az alábbi tulajdonságok megléte szükséges (ahol X, Y és Z a háló tetszőleges elemei, azaz X, Y, Z∈A):

• X⌢X=X (idempotencia)
• X⌢Y=Y⌢X (kommutativitás)
• (X⌢Y)⌢Z=X⌢(Y⌢Z) (asszociativitás)
• X⌢(X⌣Y) = X (abszorpció, elnyelés)
• X⌣X=X (idempotencia)
• X⌣Y=Y⌣X (kommutativitás)
• (X⌣Y)⌣Z=X⌣(Y⌣Z) (asszociativitás)
• X⌣(X⌢Y) = X (abszorpció, elnyelés)

Abban az esetben, ha az 'A' halmaz véges (|A|=n, n∈ℕ⁺), akkor az (A; ⌢, ⌣) hálónak mindig van legkisebb eleme (zéruseleme vagy nulleleme, o∈A), ill. legnagyobb eleme (egységeleme, i∈A), amelyekre teljesülnek az alábbi azonosságok (vö. Jaglom 1982: 65):
o=a₁⌢a₂⌢...⌢a_n (a_i∈A, 1<=i<=n)
i=a₁⌣a₂⌣...⌣a_n (a_i∈A, 1<=i<=n)

Például az alábbi hálók esetében a hálók legkisebb eleme (zéruseleme vagy nulleleme), ill. legnagyobb eleme (egységeleme) a következő:
– ha A=2^I (ahol I egy meghatározott alaphalmaz), akkor (A; ⊆) háló; ekkor 'o' az üreshalmazt (∅), 'i' pedig magát az 'I' halmazt jelenti (amely megkapható, mint az 'A' halmaz összes elemének uniója);
– ha A⊆ℕ⁺ az 1-et tartalmazó és az lnko és lkkt műveletekre zárt, véges számhalmaz, akkor (A; |) háló; ekkor 'o' az 1 természetes számot, 'i' pedig 'A' összes elemének legkisebb közös többszörösét jelenti.

Ha egy (A; ⌢, ⌣) háló esetében további tulajdonságok is teljesülnek, egy gyakorlati szempontból nagyon fontos struktúrához jutunk el. Ehhez először definiáljuk a háló egy tetszőleges elemének a komplementumát.

Ha az (A; ⌢, ⌣) hálónak van o∈A zéruseleme és i∈A egységeleme, akkor a háló egy a∈A elemének a komplementuma az az a'∈A elem (ha ilyen elem létezik), amelyre a⌢a'=o és a⌣a'=i teljesül. Általános esetben lehetséges, hogy egy elemnek nincs komplementuma, ill. az is lehet, hogy több komplementuma is létezik. Ha viszont az (A; ⌢, ⌣) hálóban értelmezett ⌢ és ⌣ műveletekre tetszőleges a,b,c∈A elemek esetén teljesül az
a⌢(b⌣c)=(a⌢b)⌣(a⌢c)
azonosság (disztributivitás), akkor a háló minden elemének legfeljebb egy komplementuma létezhet. Azokat a hálókat, amelyekben teljesül a disztributivitás fenti azonossága, disztributív hálóknak nevezzük (vö. Szendrei 1975: 418-420).

Az olyan, zéruselemmel és egységelemmel rendelkező, disztributív hálót, amelyben minden elemnek létezik komplementuma, Boole-algebrának (vagy Boole-hálónak) nevezzük.

Például egy adott 'I' alaphalmaz részhalmazainak halmaza (azaz a 2^I hatványhalmaz) a korábban megismert tulajdonságok^⇒ alapján Boole-algebra.