Määritelmä 3.13. Olkoon P osittain järjestetty joukko jaX ⊂P. Joukon X pienin alkio on a ∈X siten, että a ≤x kaikilla x∈ X. JoukonX suurin alkio vastaavasti on b ∈ X siten, että x ≤ b kaikilla x ∈ X. Joukon X minimaalinen alkio on m ∈ X siten, että jos x≤ m, seuraa m =x kaikilla x ∈ X. Vastaavasti joukonX maksimaalinen alkio on n ∈ X siten, että jos n ≤x, seuraan =x kaikilla x∈X. [2, s. 4]
Pienintä ja suurinta alkiota ei tule sekoittaa minimaaliseen ja maksimaali-seen alkioon. Määritelmästä nähdään, että pienin alkio on aina minimaalinen alkio ja suurin alkio on aina maksimaalinen alkio, mutta päinvastaiset eivät päde. [2, s. 4]
Osittain järjestetyssä joukossa voi olla pienin ja suurin alkio, joita mer-kitään vastaavasti 0 ja 1. Näiden yksikäsitteisyys on helppo osoittaa, mikäli tällaiset alkiot ovat olemassa. Perustellaan malliksi alkion0yksikäsitteisyys.
Olkoon 0∈P, jolle pätee0≤xkaikillax∈P. Jos on olemassa kaksi alkiota a ja b, joille tämä pätee, niin a ≤ b ja b ≤ a, jolloin antisymmetrisyyden nojalla a =b. [2, s. 1-2]
Tarkasteltaessa osittain järjestetyn joukon osajoukkoa tärkeiksi käsitteiksi nousee supremum eli pienin yläraja ja infimum eli suurin alaraja.
Määritelmä 3.14. OlkoonX ⊆P, missä(P,≤)on osittain järjestetty jouk-ko. Alkio i∈P on joukon X infimum eli suurin alaraja jos seuraavat ehdot ovat totta:
1. Kaikilla x∈X pätee i≤x,
2. Jos i0 ∈P ja i0 ≤x kaikilla x∈X, niini0 ≤i.
Merkitään joukon X infimumiai= infX. [5, s. 4]
Määritelmän ensimmäinen ehto tarkoittaa, että i on joukon X alaraja.
Toinen ehto tarkoitttaa, että josi0on myös joukonX alaraja, se on pienempi kuin i, eli i on siis joukon X suurin alaraja. Supremumin määritelmä on samantapainen.
Määritelmä 3.15. OlkoonX ⊆P, missä(P,≤)on osittain järjestetty jouk-ko. Alkios∈P on joukonX supremum elipienin yläraja jos seuraavat ehdot ovat totta:
1. Kaikilla x∈X pätee x≤s,
2. Jos s0 ∈P ja x≤s0 kaikillax∈X, niin s≤s0. Merkitään joukon X supremumia s= supX. [5, s.4]
Osittain järjestetyssä joukossa supremum ja infimum ovat yksikäsitteisiä ja niiden ei tarvitse kuulua osajoukkoon X.
Lause 3.16. OlkoonP osittain järjestetty joukko ja Qsen epätyhjä osajouk-ko. Jos infQ on olemassa, niin tämä infimum on yksikäsitteinen. Vastaavas-ti, jos supQ on olemassa, niin tämä supremum on yksikäsitteinen.
Todistus. Oletetaan, että s1 ja s2 ovat molemmat joukon Q supremum.
Määritelmän 3.15 mukaan jokaiselle joukonQ muulle ylärajalley pätees1 ≤ y. Erityisesti, koskas2 on joukon Qyläraja, niin s1 ≤s2. Toisaalta, koska s2 on joukonQsupremum, jokaiselle joukonQmuulle ylärajalle ypätees2 ≤y.
Erityisesti s2 ≤ s1. Näin ollen s1 = s2 antisymmetrisyyden nojalla, jolloin joukon Q supremumin täytyy olla yksikäsitteinen. Duaalisuuden perusteella myös joukon Q infimum on yksikäsitteinen. [7, s. 398] □
Käytetään joukon {x, y}infimumista ja supremumista merkitöjä x∧y= inf{x, y}
ja
x∨y= sup{x, y}.
Seuraava lemma liittää binäärioperaatiot ∨ ja ∧ yhteen relataation ≤ kanssa.
Lemma 3.17. Olkoon (P,≤)osittain järjestetty joukko ja x, y ∈P. Tällöin 1. x≤y⇔(x∨y) = y,
2. x≤y⇔(x∧y) = x.
Todistus. Todistetaan ensimmäinen väite.
(⇒) Jos x≤ y, niin y on joukon {x, y} yläraja. Koska kaikki joukon {x, y}
muut ylärajat ovat välttämättä suurempia kuin y ja x, niin y on pienin yläraja. Näin ollen (x∨y) =y.
(⇐) Olkoon (x∨y) = y, toisin sanoen y on joukon {x, y} pienin yläraja.
Tällöin pätee erityisesti x≤y.
Duaalisuuden perusteella myös toinen väite pätee. [5, s.5] □
4 Hilat
Tässä luvussa käydään läpi hilateorian perusteita. Hiloja voidaan kuvata kah-della eri tavalla. Ensinnäkin ne voidaan määritellään osittain järjestettyinä joukkoina, joissa kaikille mielivaltaisille alkiopareille on olemassa infimum ja supremum. Toisaalta hiloja voidaan tarkastella algebrallisina rakenteina, eli joukkoina, joissa on laskutoimituksia. Tässä luvussa hilat määritellään näis-tä kahdesta näkökulmasta, tarkastellaan hiloja Hasse-kaavioiden avulla sekä esitellään hiloihin liittyviä ominaisuuksia.
4.1 Hilat osittain järjestettyinä joukkoina
Määritelmä 4.1. Osittain järjestetty joukko(L,≤)onhilajos kaikillax, y ∈ L on olemassa x∨y ja x∧y. [2, s. 6]
Tarkastellaan esimerkkejä hiloista.
Esimerkki 4.2. a) Kaikki ketjut ovat hiloja, missä x∧y on alkioista xja y pienempi ja vastaavasti x∨y on alkioista x ja y suurempi. [2, s. 7]
b) Joukon X kaikkien osajoukkojen joukkoP(X)on hila, jossa osajoukkojen A ja B yhdiste A∪ B on A ∨B ja leikkaus A∩ B on A ∧B [7, s.398].
Esimerkissä 3.5 a) todettiin, että (P(X),⊆) on osittain järjestetty joukko.
Osoitetaan, että A∪B = sup{A, B}. Olkoon A, B ⊆P. SelvästiA⊆A∪B ja B ⊆A∪B eliA∪B on joukon {A, B} yläraja.
Lähteessä [7, s.484] todetaan, että joukkojen yhdisteellä ja leikkauksella on seuraavat ominaisuudet:
Esimerkissä 3.5 b) on todettu, että(Z+,|)on osittain järjestetty joukko.
Osoitetaan, että syt(x, y) = inf{x, y}. Olkoon d = syt(x, y). Tällöin d|x ja d|y, joten d on joukon{x, y} alaraja.
Olkoon c∈Z+ jokin joukon {x, y} alaraja, eli c|x ja c|y. Koska x=cm, y =cn ja lähteen [7, s. 7] nojalla
d=xk+yl jollekin m, n, k, l, niin
d=cmk+cnl =c(mk+nl).
Siis c|d, joten d on suurin joukon {x, y}alaraja.
Vastaavasti on selvää, että pyj(x, y) =:eon joukon{x, y}yläraja. Olkoon c∈Z+ joku joukon {x, y} yläraja, toisin sanoen x|cja y|c. Nyt e|c, sillä jos näin ei ole, niin kokonaislukujen jakoyhtälön (ks. [7, s.2]) nojalla c=ke+r missä 0< r < e. Tällöin r =c−ke on jaollinen sekä luvulla x, että luvulla y, mikä on ristiriita sen kanssa, että e on pienin yhteinen monikerta.
d) Hilan(L,≤) duaali(L,≥) on hila. [4, s. 4]
Lause 4.3. Osittain järjestetty joukko (L,≤) on hila jos ja vain jos supH ja infH ovat olemassa kaikilla joukon L äärellisillä epätyhjillä osajoukoilla H.
Todistus. Riittää todistaa väite suuntaan ⇒, sillä suunta ⇐ on triviaalisti totta.
Olkoon(L,≤)hila jaH ⊆Lepätyhjä ja äärellinen. Todistetaan väite induk-tiolla joukon H alkioiden lukumäärän suhteen. Jos H on yhden tai kahden alkion joukko, väite pätee Määritelmän 4.1 nojalla.
Oletetaan, että supremum on olemassa n −1 alkion tapauksessa ja nimi-tetään sitä s = supH, missä s ∈ L, H = {a0, a1,· · ·an−1} ja n ≥ 2. Siis Määritelmän 3.15 mukaan ai ≤ s kaikilla ai ∈ H ja jos s0 ∈ L ja ai ≤ s0 kaikilla ai, niin s≤s0.
Osoitetaan nyt, että supremum on olemassa n alkion tapauksessa. Olkoon H ={a0, a1,· · ·an},n ≥2. Osoitetaan, että
Duaalisuuden perusteella myös infH on olemassa. □
Määritelmä 4.4. Hila Lontäydellinen, jos sen jokaisella osajoukollaX on supremum ja infimum joukossa L.
Epätyhjä täydellinen hila sisältää aina pienimmän alkion 0 ja suurim-man alkion 1. Äärellinen hila on aina täydellinen. Täydellisen hilan duaali on aina täydellinen hila, duaalissa ∨ ja ∧ vaihtavat paikkoja. Rationaalilu-vut ja reaaliluRationaalilu-vut luonnollisessa järjestyksessään eivät ole täydellisiä hiloja, ellei joukkoihin lisätä +∞ ja −∞. Esimerkissä 4.2 esitetyistä hiloista a)-c) ainoastaan (P(X),⊂) on täydellinen hila. Siinä ∅= 0 ja X = 1. [2, s. 6-7]
Määritelmä 4.5. Olkoon (L,≤) hila. Joukko S ⊂ L on tämän alihila jos kaikilla x, y ∈S pätee x∨y∈S ja x∧y∈S. [2, s. 7]
Jokaisella hilalla L on triviaalit alihilat hila L itse sekä jokainen hilan L yksialkioinen osajoukko. Hilan kaksialkioinen osajoukko {x, y}, jossa x ja y ovat vertailullisia, on alihila. Alihila on on aina hila, mutta hilan osajoukko, joka on hila, ei ole aina alihila, kuten seuraavassa esimerkissä nähdään. [3, s.
16]
Esimerkki 4.6. Olkoon L = (P({1,2,3}),⊂) ja K = (K,⊂), missä K = {∅,{1},{2},{1,2,3}}. Sekä L että K ovat hiloja ja K ⊂ P({1,2,3}). K on hila, sillä operaatio ⊂ määrittää osittaisen järjestyksen siten, että ∅ ⊂ {1},∅ ⊂ {2},∅ ⊂ {1,2,3},{1} ⊂ {1,2,3} ja {2} ⊂ {1,2,3}.
{1,2,3}
{1} {2}
∅
Kuva 2: HilaK
Kuvassa 2 on esitetty osittainen järjestys Hasse-kaaviossa ja siitä nähdään helposti, että jokaisella alkioparilla on olemassa supremum ja infimum.
Hila K ei ole hilanL alihila, sillä hilassa L {1} ∨ {2}={1,2}, kun taas hilassa K {1} ∨ {2}={1,2,3}. HilanKoperaatiot∨ ja ∧eivät siis ole hilan L operaatioita. [3, s. 16]