Emma Ukkonen
GALOIS’N YHTEYDET
Informaatioteknologian ja viestinnän tiedekunta Pro gradu -tutkielma Marraskuu 2020
Tiivistelmä
Emma Ukkonen: Galois’n yhteydet Pro gradu -tutkielma
Tampereen yliopisto
Matematiikan ja tilastotieteen tutkinto-ohjelma Marraskuu 2020
Tämä tutkielma keskittyy Galois’n yhteyksiin, jotka yleistävät Galois’n teoriassa esitetyt välikuntien ja aliryhmien väliset vastaavuudet. Galois’n yhteys on järjestys- isomorfiaa heikompi osittain järjestettyjen joukkojen välinen kuvaus pari, jolla on paljon sovellusmahdollisuuksia useissa matemaattisissa teorioissa.
Tutkielman alkupuoli tarjoaa välttämätöntä järjestysteorian ja abstraktin algebran tietämystä, jotta tutkielman pääaiheen käsitteleminen olisi mahdollista. Ensimmäi- senä esitellään osittain järjestetty joukko, jonka määritelmään tutkielman loput luvut pohjautuvat. Tämän jälkeen osittain järjestettyjen joukkojen teoriaa syvennetään pe- rehtymällä hiloihin ja täydellisiin hiloihin. Viimeisenä alkupuolessa määritellään vielä neljä erilaista kahden osittain järjestetyn joukon välistä kuvausta ja esitellään näihin liittyviä lauseita.
Alkuosan käsittelyn jälkeen päästään tutkielman pääaiheeseen, josta esitellään ensiksi perusteet, useampi esimerkki sekä tapa yleisesti muodostaa Galois’n yhteys kahden mielivaltaisen joukon inkluusioilla varustettujen potenssijoukkojen välille, kun alkuperäisten joukkojen välillä on binäärirelaatio. Tutkielma keskittyy pääasias- sa monotonisiin Galois’n yhteyksiin, mutta myös antitoniset Galois’n yhteydet esi- tellään kattavasti. Viimeisenä Galois’n yhteyksien perusteista perehdytään Galois’n yhteyksien liittokuvausten yksikäsitteisyyteen ja olemassaoloon liittyviin lauseisiin.
Galois’n yhteyksien perusteiden esittelyn jälkeen syvennytään ensin sulkeuma- systeemien ja sulkeumakuvauksien käsitteisiin. Sulkeumasysteemejä pystytään yh- distämään täydellisiin hiloihin, kun taas sulkeumakuvauksia pystytään yhdistämään sekä täydellisiin hiloihin ja sulkeumasysteemeihin että Galois’n yhteyksiin. Näiden jälkeen taas esitellään Galois’n vastaavuudet, jotka seuraavat Galois’n yhteyksistä, ja Galois’n yhteyksien päälause. Viimeisenä Galois’n vastaavuus esitellään vielä Ga- lois’n teoriassa; esitellään sekä Galois’n alkuperäinen esimerkki että Galois’n teorian päälause, joista Galois’n yhteydet ja vastaavuudet ovat saaneet alkunsa.
Avainsanat: osittain järjestetty joukko, hila, täydellinen hila, Galois’n yhteys, liittokuvaus, sulkeumasysteemi, sulkeumakuvaus, Galois’n vastaavuus
Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck -ohjelmalla.
Sisältö
1 Johdanto 4
2 Osittain järjestetty joukko ja sen duaali 6
2.1 Osittain järjestetyn joukon määritelmä . . . 6
2.2 Osittain järjestetyn joukon duaali . . . 7
3 Hila 9 3.1 Meet ja join . . . 9
3.2 Yläjoukko ja alajoukko . . . 10
3.3 Hilan ja täydellisen hilan määritelmät . . . 12
4 Osittain järjestettyjen joukkojen väliset kuvaukset 17 5 Galois’n yhteydet 22 5.1 Galois’n yhteyksien määritelmä . . . 22
5.2 Eri määritelmien yhtäpitävyys . . . 22
5.3 Perusominaisuudet . . . 24
5.4 Esimerkkejä Galois’n yhteyksistä . . . 25
5.5 Binääriseen relaatioon liittyvä Galois’n yhteys . . . 27
6 Galois’n yhteyksien liittokuvaukset 30 6.1 Liittokuvausten yksikäsitteisyys . . . 30
6.2 Liittokuvausten olemassaolo . . . 32
7 Sulkeumakuvaukset 35 7.1 Sulkeumasysteemin määritelmä . . . 35
7.2 Sulkeumakuvauksen määritelmä . . . 38
7.3 Galois’n yhteydet ja sulkeumakuvaukset . . . 42
8 Galois’n vastaavuudet 44 8.1 Galois’n vastaavuuksien määritelmä . . . 44
8.2 Galois’n vastaavuus Galois’n teoriassa . . . 45
Lähteet 47
1 Johdanto
Yleisen luulon vastaisesti Galois’n yhteys ei ole kuuluisan matemaatikon Évariste Galois’n kehittämä, vaan osittain järjestettyjen joukkojen väliset Galois’n yhteydet ovat yleistys Galois’n teoriassa esitettyjen ryhmien ja kuntalaajennuksien välisistä Galois’n vastaavuuksista, joiden kehittämisestä Galois on tullut tunnetuksi. Galois’n yhteys on järjestysisomorfiaa heikompi osittain järjestettyjen joukkojen välinen ku- vaus pari, jolla on paljon sovellusmahdollisuuksia useissa matemaattisissa teoriois- sa. Tämän tutkielman alkuosa tarjoaa välttämätöntä järjestysteorian ja abstraktin al- gebran tietämystä, jotta tutkielman pääaiheen käsitteleminen olisi mahdollista. Näihin sisältyy osittain järjestettyyn joukkoon ja hilaan liittyvät kolme ensimmäistä lukua heti johdannon jälkeen. Tutkielman loppu keskittyy sekä Galois’n yhteyksien perus- teisiin että aiheen syventämiseen. Viimeisenä esitellään vielä Galois’n vastaavuudet, jotka seuraavat Galois’n yhteyksistä.
Tutkielman ensimmäisessä luvussa käsitellään osittain järjestettyä joukkoa ja sen duaalia. Osittain järjestetty joukko järjestysteoriassa formalisoi ja yleistää intuitiivi- sen käsityksen joukon järjestämisestä, ja nimensä mukaisesti kaikkien alkioparien ei tarvitse olla vertailukelpoisia, eli järjestys on vain osittainen. Osittain järjestet- ty joukko koostuu siis joukosta, ja tämän relaatiosta, joka on osittainen järjestys.
Tutkielman loput luvut pohjautuvat osittain järjestetyn joukon määritelmään.
Luvussa 3 taas käsitellään hilaa, joka on abstrakti rakenne, jota tutkitaan järjes- tysteorian ja abstraktin algebran matemaattisissa osa-alueissa. Hila koostuu osittain järjestetystä joukosta, jossa joukon jokaisella kahdella alkiolla on olemassa sekä suu- rin alaraja että pienin yläraja. Täydellisessä hilassa taas, joka on tässä tutkielmassa keskeisempi käsite, joukon jokaisella osajoukolla on olemassa sekä suurin alaraja että pienin yläraja. Kyseinen luku sisältää useamman lauseen, joita tarvitaan myöhempien lukujen todistuksissa apuna.
Seuraavassa luvussa määritellään vielä neljä erilaista kahden osittain järjestetyn joukon välistä kuvausta ja esitellään näihin liittyviä lauseita. Kyseiset määritelmät ovat monotonisuus, antitonisuus, upotus ja järjestysisomorfismi. Galois’n yhteyden kuvaukset voivat olla joko monotonisia tai antitonisia, ja Galois’n yhteydestä voidaan muodostaa järjestysisomorfia rajoittumalla tiettyihin osajoukkoihin.
Alkuosan jälkeen päästään tutkielman pääaiheeseen, eli Galois’n yhteyksiin. Tut- kielma keskittyy pääasiassa monotoniseen Galois’n yhteyteen, mutta myös antito- ninen Galois’n yhteys esitellään kattavasti. Ensimmäinen Galois’n yhteyksiä käsit- televä luku, luku 5, tuo esille näiden perusteet ja esittelee useamman esimerkin Galois’n yhteyksistä. Näiden lisäksi alaluvussa 5.5 esitellään tapa yleisesti muodos- taa sekä monotoninen että antitoninen Galois’n yhteys kahden mielivaltaisen joukon inkluusioilla varustettujen potenssijoukkojen välille, kun alkuperäisten joukkojen välillä on binäärirelaatio. Luku 6 taas keskittyy Galois’n yhteyksien liittokuvauk- siin, näiden yksikäsitteisyyteen ja olemassaoloon. Näiden lukujen jälkeen Galois’n yhteyksistä on esitelty tarvittavat tiedot aiheen syventämistä varten.
Sulkeumasysteemi jossakin joukossa on osittain järjestetty joukko, joka koos-
tuu kyseisen joukon osajoukoista, ja sisältää jokaisen osajoukkonsa leikkauksen, kuten myös alkuperäisen joukon kokonaisuudessaan. Osittain järjestetyn joukon sul- keumakuvaus taas on kuvaus joukolta itselleen, joka on kasvava, monotoninen ja idempotenssi. Molemmat näistä omaavat duaalit määritelmät, jotka esitellään tut- kielmassa myös lyhyesti. Sulkeumasysteemit ovat täydellisiä hiloja, ja täydelliset hilat ovat taas isomorfisia sulkeumasysteemin kanssa. Lisäksi sulkeumasysteemeil- lä ja sulkeumakuvauksilla on myös selkeä yhteys. Alaluvussa 7.3 taas keskitytään Galois’n yhteyksien ja sulkeumakuvausten yhteyteen.
Tutkielman viimeinen luku esittelee jo aiemmin mainitut Galois’n vastaavuudet, jotka seuraavat Galois’n yhteyksistä. Näihin perehdytään ensin Galois’n vastaavuuk- sien määritelmän kautta, jonka jälkeen esitellään Galois’n yhteyksien päälause. Vii- meisenä Galois’n vastaavuus esitellään vielä Galois’n teoriassa; esitellään sekä Ga- lois’n alkuperäinen esimerkki että Galois’n teorian päälause, joista Galois’n yhteydet ja vastaavuudet ovat saaneet alkunsa.
Päälähdeteoksena luvuissa 4, 5 ja 6 on Smithin artikkeli The Galois Connection between Syntax and Semantics, kun taas luvuissa 3 ja 7 päälähdeteoksena on Priest- leyn artikkelin Ordered Sets and Complete Lattices: A Primer for Computer Science.
Näiden lisäksi tekijöiden Fong ja Spivak teoksen Seven Sketches in Compositionali- ty: An Invitation to Applied Category Theory perusteella on muodostettu alaluvut 3.1 ja 6.2. Mainittakoon vielä, että alaluku 8.2 on muodostettu algebran syventävän kurs- sin ja Stewartin kirjan Galois Theory perusteella. Muihin lähdeluettelosta löytyviin teoksiin viitataan myös useasti. Lukijan oletetaan tuntevan yliopiston matematiikan syventäviä algebran opintoja ja joukko-opin perusidentiteetit.
2 Osittain järjestetty joukko ja sen duaali
Osittain järjestetty joukko järjestysteoriassa formalisoi ja yleistää intuitiivisen käsi- tyksen joukon järjestämisestä ja koostuu sekä joukosta että tämän relaatiosta. Kyseistä relaatiota kutsutaan osittaiseksi järjestykseksi, sillä kaikkien alkioparien ei tarvitse olla vertailukelpoisia, toisin kun taas lineaarijärjestyksessä, jonka yleistys osittainen järjestys on. Tässä luvussa esitellään sekä osittain järjestetty joukko että sen duaa- li, joista ensimmäisenä mainitun määritelmään tämän tutkielman myöhemmät luvut pohjautuvat.
2.1 Osittain järjestetyn joukon määritelmä
Ensimmäisenä käydään läpi osittaisen järjestyksen, osittain järjestetyn joukon (vrt.
[6, s. 1]) ja joukon suurimman ja pienimmän alkion määritelmät (vrt. [5, s. 31] ja [6, s. 17]), kuten myös esimerkkejä näistä. Näiden lisäksi palautetaan mieleen syklin määritelmä (vrt. [6, s. 2]), esitellään kaksi osittain järjestettyihin joukkoihin liittyvää lausetta sekä määritellään osittain järjestetty osajoukko (vrt. [6, s. 4]).
Määritelmä 2.1. Olkoon𝑃joukko. Relaatiota≤kutsutaanosittaiseksi järjestykseksi joukossa𝑃, jos se on refleksiivinen, antisymmetrinen ja transitiivinen, eli jos
1. 𝑥 ≤ 𝑥,
2. jos𝑥 ≤ 𝑦ja𝑦 ≤ 𝑥, niin𝑥= 𝑦, ja 3. jos𝑥 ≤ 𝑦ja𝑦 ≤ 𝑧, niin𝑥 ≤ 𝑧,
aina, kun𝑥 , 𝑦, 𝑧 ∈ 𝑃. Tällöin paria (𝑃,≤) kutsutaanosittain järjestetyksi joukoksi, ja merkitään 𝒫 = (𝑃,≤). Kontekstin ollessa selvä voidaan jatkossa myös kutsua paria (𝑃,≤) lyhyesti osittain järjestetyksi joukoksi 𝑃, tai sanoa, että joukko 𝑃 va- rustettuna relaatiolla ≤, joka on osittainen järjestys, on osittain järjestetty joukko.
Lisäksi jatkossa voidaan kutsua alkiota𝑥 ∈ 𝑃 osittain järjestetyn joukon𝑃alkioksi ja osajoukkoa 𝐴⊆ 𝑃osittain järjestetyn joukon𝑃osajoukoksi.
Määritelmä 2.2. Olkoon𝒫= (𝑃,≤)osittain järjestetty joukko. Alkio⊤on joukon 𝑃 yläraja, jos 𝑝 ≤ ⊤ aina, kun 𝑝 ∈ 𝑃. Jos lisäksi ⊤ ∈ 𝑃, niin alkiota ⊤kutsutaan joukon𝑃suurimmaksi alkioksi. Tästä seuraa, että jos sekä⊤että⊤′ovat molemmat joukon𝑃suurimpia alkioita, niin⊤ ≤ ⊤′ja⊤′≤ ⊤, jolloin⊤=⊤′.
Vastaavasti⊥on joukon𝑃alaraja, jos⊥ ≤ 𝑝aina, kun 𝑝 ∈𝑃. Jos lisäksi⊥ ∈𝑃, niin alkiota⊥kutsutaan joukon𝑃pienimmäksi alkioksi. Tästä seuraa, että jos sekä⊥ että⊥′ovat molemmat joukon𝑃pienimpiä alkioita, niin⊥ ≤ ⊥′ja⊥′ ≤ ⊥, jolloin
⊥=⊥′.
Esimerkki 2.3. Luonnollisten lukujen joukkoℕ={0,1,2, . . .}varustettuna sen ta- vanomaisella relaatiolla, eli 0≤ 1≤ 2 ≤ . . ., on osittain järjestetty joukko. Kyseinen relaatio on tunnetusti osittainen järjestys ja itse asiassa se on myös lineaarijärjestys,
sillä kaikkia alkioita voidaan verrata keskenään. Lisäksi nyt 0 ≤ 𝑛aina, kun 𝑛 ∈ℕ, joten 0 on luonnollisten lukujen joukon pienin alkio. Suurinta alkiota luonnollisten lukujen joukolla ei ole.
Toisaalta taas luonnollisten lukujen joukon relaatio voidaan määritellä seuraavas- ti: kun𝑥 , 𝑦 ∈ ℕ, niin𝑥 ≤ 𝑦, jos ja vain jos on olemassa sellainen𝑧 ∈ℕ, että𝑧𝑥 =𝑦. Tällöin kyseinen relaatio on osittainen järjestys, mutta ei lineaarijärjestys, sillä mit- kään kaksi alkulukua, esimerkiksi luvut 2 ja 3, eivät ole vertailtavissa keskenään.
Lisäksi nyt 1 ≤ 𝑛aina, kun𝑛 ∈ℕ, sillä aina𝑛1 =𝑛. Toisaalta taas 𝑛 ≤ 0 aina, kun 𝑛 ∈ ℕ, sillä aina 0𝑛 = 0. Täten tällä relaatiolla luonnollisten lukujen joukon pienin alkio on siis 1, ja suurin alkio taas on 0.
Esimerkki 2.4. Olkoon P perhe joukkoja. Tällöin P varustettuna inkluusiolla on osittain järjestetty joukko. Relaatio ≤ on inkluusio, jos 𝑋1 ≤ 𝑋2 tarkoittaa, että 𝑋1⊆ 𝑋2aina, kun𝑋1, 𝑋2∈ P. Näin ollen esimerkiksi joukon𝑋osajoukkojen joukko P (𝑋)on osittain järjestetty joukko, kun sen relaationa on inkluusio. Potenssijoukon P (𝑋)pienin alkio on tällöin∅, kun taas suurin on𝑋.
Määritelmä 2.5. Olkoon (𝑃,≤) pari, ja olkoon 𝑝0, 𝑝1, 𝑝2, . . . , 𝑝𝑎 ∈ 𝑃 alkioiden ketju, missä kaikki alkiot ovat erisuuria, ja𝑝0 ≤ 𝑝1 ≤ 𝑝2≤ · · · ≤ 𝑝𝑎 ≤ 𝑝0. Tällaista alkioiden ketjua kutsutaansykliksi.
Lause 2.6. Osittain järjestetyssä joukossa ei ole syklejä.
Todistus(vrt. [6, s. 2]). Olkoon 𝑃 varustettuna osittaisella järjestyksellä ≤ osittain järjestetty joukko. Tehdään vastaoletus, että𝑃sisältää syklin, eli että kaikki alkiot𝑝 ∈ 𝑃ovat erisuuria, ja että𝑝0 ≤ 𝑝1≤ 𝑝2 ≤ · · · ≤ 𝑝𝑎 ≤ 𝑝0, kun𝑝0, 𝑝1, 𝑝2, . . . , 𝑝𝑎 ∈𝑃. Tällöin siis𝑝0 ≤ 𝑝1ja 𝑝1 ≤ 𝑝2, josta seuraa transitiivisuuden nojalla, että 𝑝0 ≤ 𝑝2. Edelleen, koska 𝑝0 ≤ 𝑝2 ja 𝑝2 ≤ 𝑝3, niin transitiivisuuden nojalla saadaan, että 𝑝0 ≤ 𝑝3. Näin jatkamalla saadaan lopulta, että𝑝0 ≤ 𝑝𝑎. Oletuksen nojalla kuitenkin 𝑝𝑎 ≤ 𝑝0. Tästä taas seuraa antisymmetrisyyden nojalla, että 𝑝0 = 𝑝𝑎. Tämä on ristiriidassa sen kanssa, että syklissä kaikkien alkioiden tulee olla erisuuria. Näin ollen osittain järjestetyssä joukossa ei voi olla syklejä. □ Lause 2.7. Olkoon 𝒫 = (𝑃,≤) osittain järjestetty joukko. Tällöin myös pari𝒫′ = (𝑃′,≤′) muodostaa osittain järjestetyn joukon, kun 𝑃′ ⊆ 𝑃, ja ≤′ on joukkoon 𝑃′ rajoitettu relaatio≤.
Todistus(vrt. [6, s. 4]). Olkoon𝒫′=(𝑃′,≤′) pari, missä𝑃′⊆ 𝑃ja≤′on joukkoon 𝑃′rajoitettu relaatio≤. Tällöin ≤′on selvästi myös refleksiivinen, antisymmetrinen ja transitiivinen, kun se on rajoitettu koskemaan vain joukon𝑃′alkioita. Näin ollen pari𝒫′=(𝑃′,≤′) muodostaa osittain järjestetyn joukon. □ Määritelmä 2.8. Olkoon 𝒫 ja 𝒫′kuten lauseessa 2.7. Tällöin osittain järjestettyä joukkoa𝒫′kutsutaan osittain järjestetyn joukon𝒫osittain järjestetyksi osajoukoksi.
2.2 Osittain järjestetyn joukon duaali
Seuraavana esitellään osittain järjestetyn joukon duaali (vrt. [1, s. 4] ja [5, s.31]), esimerkki duaalista sekä lause, jonka mukaan osittain järjestetyn joukon duaali on
myös osittain järjestetty joukko. Näiden lisäksi esitellään duaalisuusperiaate (vrt. [1, s. 4] ja [5, s.31]). Duaalien tarkastelun hyöty tulee siitä, että monia osittain järjestetyn joukon ominaisuuksia vastaa duaalinen ominaisuus duaalissa. Duaalisuusperiaatteen nojalla voidaan todistaa ominaisuuksista vain toinen, kun taas toisen sanotaan pätevän duaalisti.
Määritelmä 2.9. Olkoon 𝒫 = (𝑃,≤) osittain järjestetty joukko. Tällöin voidaan muodostaa pari𝒫𝒹 = (𝑃,≤𝒹) määrittelemällä, että𝑥 ≤𝒹 𝑦, jos ja vain jos𝑦 ≤ 𝑥, aina, kun𝑥 , 𝑦 ∈ 𝑃. Paria 𝒫𝒹 kutsutaan osittain järjestetyn joukon 𝒫 duaaliksi, ja selvästi(𝒫𝒹)𝒹 =𝒫.
Esimerkki 2.10. Esimerkin 2.3 mukaan𝒩 = (ℕ,≤) on osittain järjestetty joukko, kun relaatio≤on määritelty luonnollisille luvuille tuttuun tapaan. Tälle voidaan siis muodostaa duaali𝒩𝒹 = (ℕ,≤𝒹). Nyt siis𝑥 ≤𝒹 𝑦, jos ja vain jos 𝑦 ≤ 𝑥, aina, kun 𝑥 , 𝑦 ∈ℕ. Tällöin luonnollisten lukujen suurin alkio on 0, sillä 0 ≤ 𝑛aina, kun𝑛∈ℕ, jolloin siis𝑛 ≤𝒹 0. Toisaalta taas tällöin luonnollisten lukujen joukolla ei ole pientä alkiota.
Lause 2.11. Olkoon𝒫 = (𝑃,≤) osittain järjestetty joukko. Tällöin myös sen duaali 𝒫𝒹 =(𝑃,≤𝒹) on osittain järjestetty joukko.
Todistus(vrt. [1, s. 4]). Olkoon 𝒫𝒹 = (𝑃,≤𝒹) osittain järjestetyn joukon 𝒫 = (𝑃,≤) duaali. Tällöin selvästi ≤𝒹 on myös refleksiivinen, antisymmetrinen ja tran- sitiivinen. Näin ollen𝒫𝒹 =(𝑃,≤𝒹) on osittain järjestetty joukko. □ Määritelmä 2.12. Olkoon 𝛼 osittain järjestettyjä joukkoja koskeva väite. Tällöin duaalisen väitteen𝛼∗ sanotaan pätevän osittain järjestetyssä joukossa𝒫 = (𝑃,≤), jos ja vain jos𝛼pätee osittain järjestetyssä joukossa𝒫𝒹 =(𝑃,≤𝒹). Duaalinen väite muodostetaan vaihtamalla≤ja≥ keskenään.
Lause 2.13(Duaalisuusperiaate). Jos jokin väite pätee osittain järjestetylle joukolle 𝒫 = (𝑃,≤), niin tällöin väitteen duaalinen väite pätee kyseisen osittain järjestetyn joukon duaalille𝒫𝒹 = (𝑃,≤𝒹).
Lisäksi, jos jokin väite pätee jokaiselle osittain järjestetylle joukolle, niin tällöin myös tämän duaalinen väite pätee jokaiselle osittain järjestetylle joukolle.
Todistus. Olkoon 𝛼 väite, joka pätee osittain järjestetylle joukolle (𝑃,≤). Koska (𝒫𝒹)𝒹 =𝒫, niin väitteen𝛼duaalinen väite𝛼∗osittain järjestetylle joukolle(𝑃,≤𝒹) on sama kuin väite𝛼osittain järjestetylle joukolle(𝑃,≤). Täten väite𝛼∗pätee osittain järjestetylle joukolle(𝑃,≤𝒹).
Oletetaan sitten, että𝛼pätee jokaiselle osittain järjestetylle joukolle. Nyt määri- telmän 2.12 nojalla saadaan suoraan, että𝛼∗pätee osittain järjestetyssä joukossa𝒫, mikäli𝛼pätee osittain järjestetyssä joukossa𝒫𝒹. □
3 Hila
Hila on abstrakti rakenne, jota tutkitaan järjestysteorian ja abstraktin algebran ma- temaattisissa osa-alueissa. Se koostuu osittain järjestetystä joukosta, jossa joukon jokaisella kahdella alkiolla on olemassa sekä meet että join. Tässä tutkielmassa hi- loihin päästään osittain järjestettyihin joukkoihin liittyvien ominaisuuksien, meetin ja joinin, ja yläjoukon ja alajoukon, kautta. Kyseisten määritelmien ymmärrystä tar- vitaan hiloihin perehdyttäessä. Lisäksi perehdytään täydellisen hilan käsitteeseen, jossa taas osittain järjestetyn joukon jokaisella osajoukolla on olemassa sekä meet että join.
3.1 Meet ja join
Tässä alaluvussa esitellään ensimmäisenä meetin ja joinin määritelmät (vrt. [3, s. 23]), jotka ovat infimumin ja supremumin järjestysteoriassa käytetyt nimikkeet. Tämän jälkeen käydään läpi sekä näihin liittyvä esimerkki että lause. Viimeisenä esitellään vielä meetien ja joinien säilyttämisen määritelmät (vrt. [3, s. 26]).
Määritelmä 3.1. Olkoon(𝑃,≤)osittain järjestetty joukko, ja olkoon𝐴 ⊆ 𝑃. Alkiota 𝑝 ∈𝑃kutsutaan osajoukon 𝐴meetiksi, jos
1. 𝑝on joukon 𝐴alaraja, eli 𝑝 ≤ 𝑎aina, kun𝑎 ∈ 𝐴, ja
2. 𝑝 on joukon 𝐴alarajojen joukon suurin alkio, eli aina, kun 𝑞 ∈ 𝑃 pätee, että jos𝑞 ≤ 𝑎aina, kun𝑎 ∈ 𝐴, niin𝑞 ≤ 𝑝.
Tällöin 𝑝 on siis joukon 𝐴 suurin alaraja eliinfimum. Merkitään 𝑝 = ⋀︁
𝐴 ja 𝑝 =
⋀︁
𝑎∈𝐴𝑎. Jos kyseessä oleva osittain järjestetty joukko on epäselvä, niin merkitään𝑝 =
⋀︁
𝑃 𝐴, ja kun käsitellään perhettä joukkoja, niin merkitään 𝑝 = ⋀︁
𝑖∈𝐼 𝐴𝑖, merkinnän 𝑝 = ⋀︁{𝐴𝑖|𝑖 ∈ 𝐼} sijaan. Kahden alkion joukon tapauksessa, 𝐴 = {𝑎, 𝑏}, voidaan merkitä yksinkertaisesti𝑝 =𝑎∧𝑏.
Vastaavasti, alkiota 𝑝 ∈ 𝑃kutsutaan osajoukon 𝐴joiniksi, jos 1. 𝑝on joukon 𝐴yläraja, eli𝑎 ≤ 𝑝aina, kun𝑎 ∈ 𝐴, ja
2. 𝑝 on joukon 𝐴ylärajojen joukon pienin alkio, eli aina, kun 𝑞 ∈ 𝑃 pätee, että jos𝑎 ≤ 𝑞aina, kun𝑎 ∈ 𝐴, niin 𝑝 ≤ 𝑞.
Tällöin 𝑝 on siis joukon 𝐴 pienin yläraja eli supremum. Vastaavasti merkitään 𝑝 =
⋁︁𝐴tai𝑝 =⋁︁
𝑎∈𝐴𝑎. Kahden alkion joukon tapauksessa,𝐴={𝑎, 𝑏}, voidaan merkitä yksinkertaisesti 𝑝 =𝑎∨𝑏.
Esimerkki 3.2. Olkoon (𝑃,≤) osittain järjestetty joukko, jossa 𝑃 = {𝑝, 𝑞, 𝑟}, ja 𝑝 ≤ 𝑞 ≤ 𝑟. Tällöin osajoukon 𝐴 ={𝑝, 𝑞} ⊆ 𝑃suurin alaraja, eli meet, on 𝑝. Tämä seuraa siitä, että 𝑝 ≤ 𝑝 ja 𝑝 ≤ 𝑞, eli se on joukon 𝐴 alaraja. Lisäksi joukolla 𝐴ei ole olemassa toista alarajaa, joten se on alarajoista suurin. Joukon 𝐴pienin yläraja,
eli join, taas on𝑞 ∈ 𝑃. Tämä taas seuraa siitä, että 𝑝 ≤ 𝑞 ja𝑞 ≤ 𝑞, eli𝑞 on joukon 𝐴yläraja. Lisäksi joukon 𝐴ainoa toinen yläraja on𝑟 ja määritelmän nojalla𝑞 ≤ 𝑟, joten𝑞on ylärajoista pienin.
Esimerkki 3.3. (Vrt. [3, s. 25].) Tarkastellaan jälleen osittain järjestettyä joukkoa (P (𝑋),⊆), kun ⊆ on inkluusio, ja olkoot 𝐴, 𝐵 ∈ P (𝑋). Tällöin potenssijoukon P (𝑋) alkioiden 𝐴 ja 𝐵meet on näiden leikkaus, eli 𝐴∧𝐵 = 𝐴∩𝐵, ja vastaavasti join on näiden yhdiste, eli 𝐴∨𝐵 = 𝐴∪ 𝐵. Selvästi näiden joukkojen leikkaus on näiden alaraja, sillä 𝐴 ∩ 𝐵 ⊆ 𝐴 ja 𝐴∩ 𝐵 ⊆ 𝐵, ja tämä on suurin mahdollinen joukko, joka kuuluu molempiin joukkoihin. Täten𝐴∧𝐵= 𝐴∩𝐵. Vastaavasti näiden joukkojen yhdiste on näiden yläraja, sillä𝐴 ⊆ 𝐴∪𝐵ja𝐵⊆ 𝐴∪𝐵, ja tämä on pienin mahdollinen joukko, johon molemmat joukot kuuluvat. Näin ollen 𝐴∨𝐵= 𝐴∪𝐵. Lause 3.4. Olkoon(𝑃,≤)osittain järjestetty joukko, ja olkoot 𝐴 ⊆ 𝐵 ⊆ 𝑃osajouk- koja, joilla on meetit. Tällöin⋀︁
𝐵 ≤ ⋀︁
𝐴.
Vastaavasti, jos osajoukoilla 𝐴ja𝐵on joinit, niin⋁︁
𝐴 ≤ ⋁︁
𝐵.
Todistus(vrt. [3, s. 25]). Olkoon𝑚joukon 𝐴meet ja𝑛joukon𝐵meet, eli𝑚 =⋀︁
𝐴 ja𝑛 =⋀︁
𝐵. Nyt, jos𝑎 ∈ 𝐴, niin𝑎 ∈ 𝐵. Tällöin, koska𝑛 on joukon𝐵 alaraja, niin 𝑛 ≤ 𝑎. Täten𝑛on myös joukon𝐴alaraja. Lisäksi koska𝑚on joukon𝐴suurin alaraja, niin𝑛 ≤ 𝑚. Näin ollen⋀︁
𝐵 ≤ ⋀︁
𝐴.
Olkoon sitten 𝑚 joukon 𝐴 join ja 𝑛 joukon 𝐵 join, eli 𝑚 = ⋁︁
𝐴 ja 𝑛 = ⋁︁
𝐵. Jälleen, jos 𝑎 ∈ 𝐴, niin 𝑎 ∈ 𝐵. Tällöin, koska 𝑛 on joukon 𝐵 yläraja, niin 𝑎 ≤ 𝑛. Täten𝑛on myös joukon 𝐴yläraja. Lisäksi koska𝑚 on joukon𝐴pienin yläraja, niin 𝑚 ≤ 𝑛. Näin ollen⋁︁
𝐴 ≤ ⋁︁
𝐵. □
Määritelmä 3.5. Olkoon 𝑓: 𝑃 → 𝑄 monotoninen kuvaus. Tämän sanotaansäilyt- tävän meetit, jos 𝑓(𝑎∧𝑏) = 𝑓(𝑎) ∧ 𝑓(𝑏)aina, kun𝑎, 𝑏∈ 𝑃.
Vastaavasti kyseisen kuvauksen sanotaansäilyttävän joinit, jos 𝑓(𝑎∨𝑏) = 𝑓(𝑎) ∨ 𝑓(𝑏)aina, kun𝑎, 𝑏∈ 𝑃.
3.2 Yläjoukko ja alajoukko
Seuraavana esitellään ylä- ja alajoukko (vrt. [5, s. 35-36]), esimerkki näistä, kuten myös yksi näihin liittyvä lause. Näiden jälkeen määritellään kaikkien ylä- ja alarajojen joukot (vrt. [5, s. 43]), joiden määritelmissä on käytetty apuna ylä- ja alajoukko operaattoreita. Viimeisenä esitellään vielä kaksi lausetta, jotka liittyvät sekä kaikkien ylä- ja alarajojen joukkoihin että edellisessä alaluvussa määriteltyihin meettiin ja joiniin.
Määritelmä 3.6. Olkoon (𝑃,≤)osittain järjestetty joukko.
1. Olkoon𝑥 ∈𝑃. Tällöinyläjoukko operaattori↑määritellään seuraavasti:
↑𝑥:={𝑦 ∈𝑃|𝑥 ≤ 𝑦}, jaalajoukko operaattori↓määritellään seuraavasti:
↓𝑥 :={𝑦 ∈𝑃|𝑦 ≤𝑥}.
2. Olkoon 𝑌 ⊆ 𝑃. Tällöin joukon 𝑌 sanotaan olevan joukon 𝑃 yläjoukko, jos pätee, että kun𝑥 ∈ 𝑃,𝑥 ≥ 𝑦ja 𝑦 ∈𝑌, niin myös𝑥 ∈𝑌. Vastaavasti joukon𝑌 sanotaan olevan joukon𝑃alajoukko, jos pätee, että kun𝑥 ∈𝑃,𝑦 ≥ 𝑥ja𝑦 ∈𝑌, niin myös𝑥 ∈𝑌.
Huomaa, että joukko↑ 𝑥on yläjoukko ja joukko↓𝑥 on alajoukko aina, kun𝑥 ∈ 𝑃. Joukon𝑃kaikkien yläjoukkojen perhettä merkitään𝒰(𝑃). Vastaavasti joukon𝑃kaik- kien alajoukkojen perhettä merkitään𝒪(𝑃). Molemmat näistä perheistä varustettuna inkluusiolla, eli parit(𝒰(𝑃),⊆)ja (𝒪(𝑃),⊆), ovat osittain järjestettyjä joukkoja.
Esimerkki 3.7. Tarkastellaan osittain järjestettyä joukkoa(ℕ,≤)varustettuna luon- nollisten lukujen joukon tavanomaisella relaatiolla. Tällöin↑0= ℕ= {0,1,2, . . .}, sillä 0 ≤ 𝑛 aina, kun 𝑛 ∈ ℕ. Lisäksi↓ 0 = {0}, sillä ei ole olemassa toista alkiota 𝑛∈ℕ, jolla𝑛 ≤ 0.
Lause 3.8. Olkoon (𝑃,≤) osittain järjestetty joukko, ja olkoot 𝑥 , 𝑦 ∈ 𝑃. Tällöin seuraavat väittämät ovat yhtäpitäviä
1. 𝑥 ≤ 𝑦, 2. ↓𝑥 ⊆↓𝑦,
3. jos 𝑦 ∈𝑌, niin𝑥 ∈𝑌, aina, kun𝑌 ∈𝒪(𝑃).
Todistus(vrt. [5, s. 37]). Oletetaan ensin, että 𝑥 ≤ 𝑦, ja että 𝑧 ∈↓ 𝑥. Tällöin määri- telmän 3.6 nojalla𝑧 ≤ 𝑥. Tästä taas seuraa relaation≤transitiivisuuden nojalla, että myös𝑧 ≤ 𝑦. Täten𝑧∈↓𝑦. Näin ollen↓𝑥 ⊆↓𝑦.
Oletetaan sitten, että↓𝑥 ⊆↓ 𝑦, ja että 𝑦 ∈𝑌 aina, kun𝑌 ∈𝒪(𝑃). Koska𝑦 ∈𝑌, niin määritelmän 3.6 nojalla ↓ 𝑦 ⊆ 𝑌. Oletuksen nojalla tästä seuraa, että myös
↓𝑥 ⊆𝑌. Relaation≤ refleksiivisyyden nojalla taas𝑥 ≤ 𝑥, jolloin𝑥 ∈↓𝑥. Näin ollen 𝑥 ∈𝑌.
Oletetaan vielä, että jos𝑦 ∈𝑌, niin𝑥 ∈𝑌, aina, kun𝑌 ∈𝒪(𝑃). Asetetaan𝑌 :=↓𝑦. Relaation≤refleksiivisyyden nojalla jälleen𝑦 ≤ 𝑦, jolloin𝑦∈↓𝑦. Tästä taas seuraa oletuksen nojalla, että𝑥 ∈↓𝑦, jolloin myös𝑥 ≤ 𝑦. □ Määritelmä 3.9. Olkoon(𝑃,≤)osittain järjestetty joukko, ja olkoon𝐴 ⊆ 𝑃. Tällöin joukon 𝐴kaikkien ylärajojen joukko 𝐴𝓊määritellään seuraavasti:
𝐴𝓊:={𝑥 ∈ 𝑃|𝑎 ≤𝑥 aina, kun𝑎 ∈ 𝐴}, ja joukon𝐴kaikkien alarajojen joukko 𝐴𝓁 määritellään seuraavasti:
𝐴𝓁 :={𝑥 ∈ 𝑃|𝑥 ≤ 𝑎aina, kun𝑎 ∈ 𝐴}.
Lisäksi tällöin∅𝓊 =∅𝓁 =𝑃. Jos 𝐴on epätyhjä, niin nämä voidaan määritellä myös seuraavasti:
𝐴𝓊:=⋂︂
{↑𝑎|𝑎 ∈ 𝐴}ja 𝐴𝓁 :=⋂︂
{↓𝑎|𝑎 ∈ 𝐴}.
Jatkossa esimerkiksi merkinnän(𝐴𝓊)𝓁sijaan käytetään lyhyempää versiota𝐴𝓊𝓁.
Lause 3.10. Olkoon (𝑃,≤) osittain järjestetty joukko, ja olkoot 𝐴 ⊆ 𝑃 ja 𝐵 ⊆ 𝑃. Tällöin
1. 𝐴 ⊆ 𝐴𝓊𝓁ja 𝐴 ⊆ 𝐴𝓁𝓊,
2. jos 𝐴 ⊆ 𝐵, niin𝐵𝓊 ⊆ 𝐴𝓊ja𝐵𝓁 ⊆ 𝐴𝓁, ja 3. 𝐴𝓊 = 𝐴𝓊𝓁𝓊ja 𝐴𝓁 = 𝐴𝓁𝓊𝓁.
Todistus(vrt. [4, s. 66]).
1. Oletetaan, että 𝑥 ∈ 𝐴. Tällöin 𝑥 on jokaisen joukon 𝐴 ylärajan alaraja. Näin ollen𝑥 ∈ 𝐴𝓊𝓁, joten 𝐴 ⊆ 𝐴𝓊𝓁. Samoin saadaan, että 𝐴 ⊆ 𝐴𝓁𝓊.
2. Oletetaan, että 𝐴 ⊆ 𝐵. Nyt, jos𝑥 ∈ 𝐵𝓊, niin 𝑏 ≤ 𝑥 aina, kun 𝑏 ∈ 𝐵. Koska 𝐴 ⊆ 𝐵, niin nyt siis𝑏 ≤ 𝑥aina, kun𝑏 ∈ 𝐴. Täten𝑥 ∈ 𝐴𝓊. Näin ollen𝐵𝓊 ⊆ 𝐴𝓊. Vastaavasti, jos𝑥 ∈ 𝐵𝓁, niin 𝑥 ≤ 𝑏 aina, kun 𝑏 ∈ 𝐵. Tällöin, koska 𝐴 ⊆ 𝐵, niin nyt𝑥 ≤ 𝑏aina, kun𝑏 ∈ 𝐴. Täten𝑥 ∈ 𝐴𝓁. Näin ollen𝐵𝓁 ⊆ 𝐴𝓁.
3. Nyt kohdan 2 nojalla𝐴 ⊆ 𝐴𝓊𝓁, josta seuraa kohdan 3 nojalla, että𝐴𝓊𝓁𝓊 ⊆ 𝐴𝓊. Toisaalta taas kohdan 2 nojalla 𝐴 ⊆ 𝐴𝓁𝓊, joten 𝐴𝓊 ⊆ 𝐴𝓊𝓁𝓊. Näin ollen 𝐴𝓊 = 𝐴𝓊𝓁𝓊. Samoin saadaan, että𝐴𝓁= 𝐴𝓁𝓊𝓁.
□ Lause 3.11. Olkoon(𝑃,≤)osittain järjestetty joukko, ja olkoon 𝐴=∅ ⊆ 𝑃. Tällöin osajoukolla 𝐴on olemassa meet⋀︁
𝐴, jos ja vain jos joukolla𝑃on suurin alkio⊤. Vastaavasti, osajoukolla 𝐴 on olemassa join⋁︁
𝐴, jos ja vain jos joukolla 𝑃on pienin alkio⊥.
Todistus(vrt. [5, s. 44]). Oletetaan ensin, että 𝑝 = ⋀︁
𝐴. Koska 𝐴 = ∅, niin määri- telmän 3.9 nojalla 𝐴𝓁 = 𝑃. Nyt siis joukon 𝐴𝓁 = 𝑃 suurin alkio on 𝑝. Näin ollen joukolla𝑃on suurin alkio 𝑝=⊤. Samoin saadaan, että jos𝑝 =⋁︁
𝐴, niin joukolla𝑃 on pienin alkio⊥.
Oletetaan sitten, että joukolla 𝑃 on suurin alkio ⊤. Määritelmän 3.9 nojalla
∅𝓁 = 𝑃. Tämän joukon suurin alkio taas on joukon𝑃 on suurin alkio⊤. Näin ollen osajoukolla 𝐴 on olemassa meet⋀︁
𝐴 = ⊤. Samoin saadaan, että jos joukolla𝑃 on pienin alkio⊥, niin osajoukolla 𝐴on olemassa join⋁︁
𝐴 =⊥. □
3.3 Hilan ja täydellisen hilan määritelmät
Hila (vrt. [5, s. 40]) ja täydellinen hila (vrt. [5, s. 45]) ovat osittain järjestettyjä joukkoja, jotka on määritelty niiden osajoukkojen ylä- ja alarajojen olemassaolon mukaan. Näiden määritelmien lisäksi esitellään näihin liittyviä esimerkkejä, sekä useampia lauseita, joita tarvitaan myöhemmissä luvuissa. Viimeisenä tässä alaluvus- sa esitellään vielä joukkojen täydellinen hila (vrt. [5, s. 47]).
Määritelmä 3.12. Olkoon ℒ = (𝐿 ,≤) epätyhjä osittain järjestetty joukko. Tällöin tätä paria kutsutaanhilaksi, jos jokaiselle𝑥 , 𝑦 ∈ 𝐿 on olemassa näiden meet,𝑥∧𝑦, ja join,𝑥∨𝑦, joukossa𝐿. Paria (𝐿 ,≤) voidaan tällöin myös kutsua lyhyesti hilaksi 𝐿. Huomaa, että osittain järjestetyn joukon ℒduaaliℒ𝒹 on hila, jos ja vain jos ℒ on hila, kun vaihdetaan∨ja∧keskenään.
Esimerkki 3.13. Tarkastellaan jälleen esimerkin 2.3 osittain järjestettyä joukkoa (ℕ,≤), jonka relaatio on määritelty seuraavasti: kun𝑥 , 𝑦 ∈ℕ, niin𝑥 ≤ 𝑦, jos ja vain jos on olemassa sellainen 𝑧 ∈ ℕ, että 𝑧𝑥 = 𝑦. Kyseinen pari on hila, sillä kahden luonnollisen luvun meet on aina näiden suurin yhteinen tekijä, ja kahden luonnollisen luvun join on aina näiden pienin yhteinen jaettava. Tämä seuraa siitä, että kahden luvun𝑥ja𝑦alaraja on aina mikä tahansa luku, joka jakaa näistä molemmat, ja näistä luvuista suurin on syt(𝑥 , 𝑦). Vastaavasti taas kahden luvun 𝑥 ja 𝑦 yläraja on aina mikä tahansa luku, joka on jaollinen molemmilla näistä, ja näistä luvuista pienin on pyj(𝑥 , 𝑦). Molemmat näistä ovat aina olemassa ja kuuluvat joukkoonℕ. Tämä seuraa relaation määritelmästä, ja siitä, että luonnollisten lukujen pienin alkio, joka on 1, jakaa kaikki luonnolliset luvut, ja suurin alkio, joka on 0, taas on jaollinen jokaisella luonnollisella luvulla.
Lause 3.14. Olkoon (𝐿 ,≤)hila, ja olkoot𝑥 , 𝑦, 𝑧 ∈𝐿. Tällöin
1. (𝑥∨𝑦) ∨𝑧 =𝑥∨ (𝑦∨𝑧) ja(𝑥∧𝑦) ∧𝑧=𝑥∧ (𝑦∧𝑧)(liitännäisyys), 2. 𝑥∨𝑦= 𝑦∨𝑥ja𝑥∧𝑦 =𝑦∧𝑥 (kommutatiivisuus),
3. 𝑥∨𝑥 =𝑥ja𝑥∧𝑥 =𝑥 (idempotenssi), ja 4. 𝑥∨ (𝑥∧𝑦)=𝑥ja𝑥∧ (𝑥∨𝑦) =𝑥 (absorptio).
Todistus(vrt. [5, s. 40]).
1. Osoitetaan, että (𝑥 ∨𝑦) ∨𝑧 = ⋁︁{𝑥 , 𝑦, 𝑧} = 𝑥 ∨ (𝑦∨ 𝑧). Olkoot 𝑎 = 𝑥 ∨ 𝑦 ja 𝑏 = 𝑎∨𝑧, jolloin 𝑎 ≤ 𝑏 ja 𝑧 ≤ 𝑏. Alkio 𝑏 on siis tällöin joukon {𝑥 , 𝑦, 𝑧} yläraja. Olkoon lisäksi𝑐joukon⋁︁{𝑥 , 𝑦, 𝑧} mielivaltainen yläraja, eli𝑥 , 𝑦, 𝑧 ≤ 𝑐. Tällöin 𝑎 = 𝑥∨𝑦 ≤ 𝑐 ja𝑏 = 𝑎 ∨𝑧 ≤ 𝑐. Täten 𝑏 on ylärajoista pienin, eli
⋁︁{𝑥 , 𝑦, 𝑧} =𝑏 =(𝑥∨𝑦) ∨𝑧.
Olkoot sitten, että 𝑎 = 𝑥 ∨ 𝑏 ja 𝑏 = 𝑦∨ 𝑧, jolloin 𝑥 ≤ 𝑎 ja 𝑏 ≤ 𝑎. Alkio 𝑎 on siis tällöin joukon {𝑥 , 𝑦, 𝑧} yläraja. Olkoon lisäksi 𝑐 joukon ⋁︁{𝑥 , 𝑦, 𝑧} mielivaltainen yläraja, eli𝑥 , 𝑦, 𝑧 ≤ 𝑐. Tällöin𝑎 =𝑥∨𝑏 ≤ 𝑐ja𝑏 = 𝑦∨𝑧 ≤ 𝑐. Täten 𝑎 on ylärajoista pienin, eli ⋁︁{𝑥 , 𝑦, 𝑧} = 𝑎 = 𝑥 ∨ (𝑦 ∨𝑧). Näin ollen (𝑥∨𝑦) ∨𝑧 =𝑥∨ (𝑦∨𝑧). Samoin saadaan, että(𝑥∧𝑦) ∧𝑧=𝑥∧ (𝑦∧𝑧). 2. Olkoon 𝑧 = 𝑥 ∨𝑦. Tällöin 𝑧 on siis alkioiden𝑥 ja 𝑦 pienin yläraja. Tämä on
sama asia kuin että𝑧= 𝑦∨𝑥. Näin ollen𝑥∨𝑦 =𝑦∨𝑥. Samoin saadaan, että 𝑥∧𝑦= 𝑦∧𝑥.
3. Relaation ≤ refleksiivisyyden nojalla 𝑥 ≤ 𝑥, eli 𝑥 on joukon {𝑥 , 𝑥} yläraja.
Olkoon𝑙 ∈ 𝐿myös joukon{𝑥 , 𝑥}yläraja, eli𝑥 ≤ 𝑙. Nyt siis joinin määritelmän nojalla𝑥on pienin yläraja, ja täten𝑥∨𝑥 =𝑥. Samoin saadaan, että𝑥∧𝑥 =𝑥.
4. Relaation ≤ refleksiivisyyden nojalla 𝑥 ≤ 𝑥, ja meetin määritelmän nojalla 𝑥 ∧𝑦 ≤ 𝑥. Tästä seuraa, että 𝑥 ∨ (𝑥 ∧𝑦) ≤ 𝑥, sillä 𝑥, joka on nyt näiden alkioiden yläraja, on aina suurempi tai yhtä suuri kuin näiden pienin yläraja.
Toisaalta taas𝑥 ≤ 𝑥∨ (𝑥∧𝑦), sillä alkion𝑥ja jonkin toisen alkion pienin yläraja on aina suurempi tai yhtä suuri kuin molemmat näistä. Näin ollen relaation
≤ antisymmetrisyydestä seuraa, että 𝑥 ∨ (𝑥 ∧ 𝑦) = 𝑥. Samoin saadaan, että 𝑥∧ (𝑥∨𝑦)=𝑥.
□ Määritelmä 3.12 on järjestysteoreettinen, mutta kuten aiemmin mainittu, hila voidaan määritellä myös algebrallisesti. Algebrallisen määritelmän mukaan epätyhjä joukko 𝐿 muodostaa hilanyhdessä kahden binäärioperaation∧ja ∨kanssa, jos ne toteuttavat lauseen 3.14 kohdat 1−4. Täten hilaa(𝐿 ,≤)voidaan siis tarkastella myös algebrana (𝐿 ,∧,∨). (Vrt. [5, s. 40].) Tässä tutkielmassa keskitytään näistä kahdesta määritelmästä järjestysteoreettiseen versioon käsiteltäessä hilaa.
Määritelmä 3.15. Olkoon ℒ = (𝐿 ,≤) epätyhjä osittain järjestetty joukko. Tällöin tätä paria kutsutaan täydelliseksi hilaksi, jos jokaiselle osajoukolle 𝐴 ⊆ 𝐿 on ole- massa⋀︁
𝐴 ja⋁︁
𝐴. Paria (𝐿 ,≤) voidaan tällöin myös kutsua lyhyesti täydelliseksi hilaksi𝐿.
Esimerkki 3.16. Esimerkin 3.13 osittain järjestetty joukko (ℕ,≤) on myös täydel- linen hila. Yhtä lailla luonnollisten lukujen mielivaltaisen osajoukon suurin alaraja on aina tämän alkioiden suurin yhteinen tekijä, ja mielivaltaisen osajoukon pienin yläraja on aina tämän alkioiden pienin yhteinen jaettava.
Esimerkki 3.17. Esimerkin 3.3 nojalla jokaisella 𝐴, 𝐵 ∈ P (𝑋) on olemassa sekä meet𝐴∧𝐵 = 𝐴∩𝐵että join 𝐴∨𝐵= 𝐴∪𝐵. Lisäksi nämä kuuluvat aina joukkoon P (𝑋), sillä potenssijoukko sisältää joukon 𝑋 kaikki osajoukot. Täten potenssijouk- ko varustettuna inkluusiolla on hila. Samoin jokaisella potenssijoukon osajoukolla {𝐴𝑖}𝑖∈𝐼 on aina olemassa sekä meet⋂︁
𝑖∈𝐼 𝐴𝑖 että join ⋃︁
𝑖∈𝐼 𝐴𝑖 joukossa P (𝑋). Näin ollen potenssijoukko varustettuna inkluusiolla on myös täydellinen hila.
Lause 3.18. Olkoon (𝐿 ,≤)epätyhjä osittain järjestetty joukko.
1. Oletetaan, että jokaiselle epätyhjälle osajoukolle 𝐴 ⊆ 𝐿 on olemassa ⋀︁
𝐴. Tällöin jokaiselle osajoukolle𝐴 ⊆ 𝐿, jolla on yläraja joukossa𝐿, on olemassa
⋁︁𝐴joukossa𝐿, ja⋁︁
𝐴=⋀︁
𝐴𝓊. 2. Seuraavat väittämät ovat yhtäpitäviä:
(i) 𝐿on täydellinen hila,
(ii) jokaiselle osajoukolle 𝐴⊆ 𝐿 on olemassa⋀︁
𝐴joukossa𝐿,
(iii) joukolla𝐿on suurin alkio⊤, ja jokaiselle epätyhjälle osajoukolle𝐴 ⊆ 𝐿 on olemassa⋀︁
𝐴. Todistus(vrt. [5, s. 45]).
1. Olkoon 𝐴 ⊆ 𝐿, ja oletetaan, että joukolla𝐴on yläraja joukossa 𝐿. Todistetaan siis, että tällöin tälle on olemassa⋁︁
𝐴joukossa𝐿. Koska joukolla𝐴on yläraja joukossa 𝐿, niin tällöin joukon 𝐴 kaikkien ylärajojen joukko on epätyhjä, eli 𝐴𝓊 ≠ ∅. Täten oletuksen nojalla, koska nyt 𝐴𝓊 on joukon 𝐿 epätyhjä osajoukko, niin tälle on olemassa suurin alaraja𝛼:=⋀︁
𝐴𝓊joukossa 𝐿. Tästä taas seuraa, että ⋁︁
𝐴 = 𝛼. Näin ollen jokaiselle osajoukolle 𝐴 ⊆ 𝐿, jolla on yläraja joukossa𝐿, on olemassa⋁︁
𝐴joukossa 𝐿, ja⋁︁
𝐴=⋀︁
𝐴𝓊.
2. Oletetaan ensin, että 𝐿 on täydellinen hila. Tällöin määritelmän 3.15 nojalla jokaiselle osajoukolle𝐴 ⊆ 𝐿on olemassa⋀︁
𝐴joukossa 𝐿.
Oletetaan sitten, että jokaiselle osajoukolle𝐴 ⊆ 𝐿on olemassa⋀︁
𝐴joukossa 𝐿. Tällöin selvästi joukon 𝐴 suurin alaraja⋀︁
𝐴 on olemassa myös jokaiselle epätyhjälle osajoukolle 𝐴 ⊆ 𝐿. Todistetaan vielä, että joukolla 𝐿 on suurin alkio. Tarkastellaan joukkoa𝐴=∅. Lauseen 3.11 nojalla osajoukolla𝐴=∅on olemassa⋀︁
𝐴, jos ja vain jos joukolla 𝐿 on suurin alkio. Näin ollen joukolla 𝐿 on suurin alkio.
Oletetaan vielä, että joukolla 𝐿 on suurin alkio, ja että jokaiselle epätyhjälle osajoukolle𝐴⊆ 𝐿on olemassa⋀︁
𝐴. Todistetaan, että tällöin𝐿on täydellinen hila. Nyt lauseen 3.11 nojalla jokaiselle osajoukolle 𝐴 ⊆ 𝐿 on olemassa⋀︁
𝐴 joukossa𝐿. Lisäksi, koska joukolla𝐿on suurin alkio, niin jokaiselle𝐴 ⊆ 𝐿on olemassa yläraja joukossa 𝐿. Täten kohdan 1 nojalla saadaan, että jokaiselle osajoukolle 𝐴 ⊆ 𝐿 on olemassa⋁︁
𝐴joukossa 𝐿. Näin ollen𝐿 on täydellinen hila.
□ Seuraava lause sisältää edellisen lauseen väitteiden duaaliset versiot, joita tarvi- taan myös jatkossa. Nämä esitellään luettavuuden vuoksi erillään.
Lause 3.19. Olkoon (𝐿 ,≤)epätyhjä osittain järjestetty joukko.
1. Oletetaan, että jokaiselle epätyhjälle osajoukolle 𝐴 ⊆ 𝐿 on olemassa ⋁︁
𝐴. Tällöin jokaiselle osajoukolle𝐴 ⊆ 𝐿, jolla on alaraja joukossa𝐿, on olemassa
⋀︁𝐴joukossa𝐿, ja⋀︁
𝐴=⋁︁
𝐴𝓁. 2. Seuraavat väittämät ovat yhtäpitäviä:
(i) 𝐿on täydellinen hila,
(ii) jokaiselle osajoukolle 𝐴⊆ 𝐿 on olemassa⋁︁
𝐴joukossa𝐿,
(iii) joukolla𝐿on pienin alkio⊥, ja jokaiselle epätyhjälle osajoukolle𝐴 ⊆ 𝐿 on olemassa⋁︁
𝐴.
Todistus(vrt. [5, s. 45]). □
Lause 3.20. Olkoon (𝐾 ,≤) täydellisen hilan (𝐿 ,≤) epätyhjä osittain järjestetty osajoukko. Tällöin,
jos ⋁︂
𝐿
𝐴 ∈𝐾 , niin ⋁︂
𝐾
𝐴on olemassa ja ⋁︂
𝐾
𝐴 =⋁︂
𝐿
𝐴,
ja
jos ⋀︂
𝐿
𝐴 ∈𝐾 , niin ⋀︂
𝐾
𝐴on olemassa ja ⋀︂
𝐾
𝐴 =⋀︂
𝐿
𝐴,
aina, kun𝐴 ⊆ 𝐾.
Todistus(vrt. [5, s. 47]). Oletetaan ensin, että ⋁︁
𝐿 𝐴 ∈ 𝐾. Asetetaan 𝑙 = ⋁︁
𝐿 𝐴, eli alkio𝑙 ∈ 𝐿on osajoukon𝐴join joukossa𝐿, ja𝑙 ∈𝐾. Nyt siis𝑎 ≤ 𝑙aina, kun𝑎 ∈ 𝐴, joten selvästi𝑙 on joukon 𝐴 yläraja myös joukossa 𝐾. Todistetaan, että𝑙 on lisäksi joukon 𝐴pienin yläraja joukossa𝐾. Olkoon 𝑘 ∈𝐾 joukon 𝐴yläraja, eli𝑎 ≤ 𝑘 aina, kun𝑎 ∈ 𝐴. Koska𝐾 ⊆ 𝐿, niin nyt myös 𝑘 ∈ 𝐿. Mutta, koska𝑙 on osajoukon 𝐴join joukossa𝐿, niin jokaisella𝑙′ ∈𝐿, jolla𝑎 ≤ 𝑙′aina, kun𝑎∈ 𝐴, pätee, että𝑙 ≤ 𝑙′. Nyt siis𝑙 ≤ 𝑘, ja täten𝑙 on joukon 𝐴pienin yläraja myös joukossa 𝐾. Näin ollen⋁︁
𝐾 𝐴 on olemassa, ja⋁︁
𝐾 𝐴=⋁︁
𝐿 𝐴. Oletetaan sitten, että⋀︁
𝐿 𝐴∈𝐾. Asetetaan𝑙 =⋀︁
𝐿 𝐴, eli alkio𝑙 ∈ 𝐿on osajoukon 𝐴 meet joukossa 𝐿, ja 𝑙 ∈ 𝐾. Nyt siis 𝑙 ≤ 𝑎 aina, kun 𝑎 ∈ 𝐴, joten selvästi 𝑙 on joukon 𝐴 alaraja myös joukossa 𝐾. Todistetaan, että 𝑙 on lisäksi joukon 𝐴 suurin alaraja joukossa𝐾. Olkoon𝑘 ∈ 𝐾joukon𝐴alaraja, eli𝑘 ≤ 𝑎aina, kun𝑎 ∈ 𝐴. Koska 𝐾 ⊆ 𝐿, niin nyt myös 𝑘 ∈ 𝐿. Mutta, koska𝑙 on osajoukon 𝐴meet joukossa 𝐿, niin jokaisella𝑙′ ∈ 𝐿, jolla𝑙′ ≤ 𝑎 aina, kun𝑎 ∈ 𝐴, pätee, että 𝑙′ ≤ 𝑙. Nyt siis 𝑘 ≤ 𝑙, ja täten𝑙on joukon 𝐴suurin alaraja myös joukossa𝐾. Näin ollen⋀︁
𝐾 𝐴on olemassa, ja⋀︁
𝐾𝐴 =⋀︁
𝐿 𝐴. □
Määritelmä 3.21. Olkoon(L,⊆)täydellisen hilan(P (𝑋),⊆)osittain järjestetty os- ajoukko, missä L on epätyhjä perhe joukon 𝑋 osajoukkoja ja P (𝑋) on joukon 𝑋 potenssijoukko. Tällöin lauseen 3.20 nojalla L on täydellinen hila, jos ⋃︁
𝑖∈𝐼 𝐴𝑖 ja
⋂︁
𝑖∈𝐼 𝐴𝑖kuuluvat joukkoonLaina, kun{𝐴𝑖}𝑖∈𝐼 ⊆ L. Kun käsitellään osittain järjes- tettyjä joukkoja, joiden relaatioina on inkluusio, niin ⋃︁
ja ⋂︁
vastaavat merkintöjä
⋁︁
L ja⋀︁
L. Tällaista hilaa kutsutaanjoukkojen täydelliseksi hilaksi.
Esimerkki 3.22. (Vrt. [5, s. 47].) Joukkojen täydellisiä hiloja ovat esimerkiksi po- tenssijoukot ja niiden duaalit, kuten myös joukon 𝑃 kaikkien ylä- ja alajoukkojen joukot𝒰(𝑃)ja𝒪(𝑃), kun näiden relaatioina on inkluusiot. Potenssijoukot ovat suo- raan määritelmän 3.21 nojalla joukkojen täydellisiä hiloja, ja joukon𝑃kaikkien ylä- ja alajoukkojen joukot 𝒰(𝑃) ja𝒪(𝑃) sisältävät potenssijoukkojen tavoin kaikkien osajoukkojensa yhdisteet ja leikkaukset.
4 Osittain järjestettyjen joukkojen väliset ku- vaukset
Tutkielman pääaiheen käsittelyä varten on osittain järjestettyjen joukkojen lisäksi perehdyttävä näiden välisiin kuvauksiin. Täten tässä luvussa määritellään neljä eri- laista kahden osittain järjestetyn joukon välistä kuvausta (vrt. [5, s. 33] ja [6, s. 6]), joita tarvitaan jatkossa, ja esitellään näihin liittyviä lauseita.
Määritelmä 4.1. Olkoon 𝒫 = (𝑃,⪯) ja𝒬 = (𝑄 ,⊑) osittain järjestettyjä joukkoja.
Kuvauksen 𝑓: 𝑃→𝑄 sanotaan olevan
1. monotoninentaijärjestyksen säilyttävä, jos aina, kun𝑥 , 𝑦 ∈ 𝑃 niin pätee, että jos𝑥 ⪯ 𝑦, niin 𝑓(𝑥) ⊑ 𝑓(𝑦).
2. antitoninentaijärjestyksen kääntävä, jos aina, kun𝑥 , 𝑦 ∈𝑃niin pätee, että jos 𝑥 ⪯ 𝑦, niin 𝑓(𝑦) ⊑ 𝑓(𝑥).
3. upotus, jos𝑥 ⪯ 𝑦, jos ja vain jos 𝑓(𝑥) ⊑ 𝑓(𝑦), aina, kun𝑥 , 𝑦 ∈ 𝑃. 4. järjestysisomorfismi, jos se on upotus ja surjektio joukolta𝑃joukolle𝑄. Jos joukkojen 𝑃 ja 𝑄 välillä on järjestysisomorfismi, niin sanotaan, että osittain järjestetyt joukot𝒫ja𝒬ovatjärjestysisomorfisiaja merkitään𝒫 ≅ 𝒬.
Seuraavan lauseen nojalla järjestysisomorfismi on aina bijektiivinen, ja täten isomorfia nimitys on pätevä, vaikka määritelmässä ei ole injektiivisyyttä mainit- tu. Tämän jälkeisessä lauseessa taas osoitetaan, miten järjestysisomorfismi saadaan muodostettua kahden osittain järjestetyn joukon välille, joiden välillä on upotus.
Lause 4.2. Osittain järjestettyjen joukkojen 𝒫 = (𝑃,⪯) ja 𝒬 = (𝑄 ,⊑) välinen upotus 𝑓: 𝑃 →𝑄on injektio.
Todistus(vrt. [6, s. 6]). Oletetaan, että 𝑓(𝑥) = 𝑓(𝑦), kun𝑥 , 𝑦 ∈ 𝑃. Osoitetaan, että tällöin𝑥 =𝑦. Nyt relaation⊑refleksiivisyyden nojalla saadaan, että 𝑓(𝑥) ⊑ 𝑓(𝑦)ja 𝑓(𝑦) ⊑ 𝑓(𝑥). Tällöin upotuksen määritelmän nojalla saadaan, että 𝑥 ⪯ 𝑦 ja 𝑦 ⪯ 𝑥. Edelleen, koska ⪯ on antisymmetrinen, niin saadaan, että 𝑥 = 𝑦. Näin ollen 𝑓 on
injektio. □
Lause 4.3. Olkoon 𝑓: 𝑃 →𝑄upotus osittain järjestettyjen joukkojen𝒫 =(𝑃,⪯)ja 𝒬 =(𝑄 ,⊑)välillä. Tällöin 𝑓 on järjestysisomorfismi osittain järjestettyjen joukkojen 𝒫ja(𝑓(𝑃),⊑)välillä.
Todistus(vrt. [6, s. 7]). Todistetaan siis, että kuvaus𝑃 → 𝑓(𝑃)on surjektio ja upo- tus. Nyt 𝑓(𝑃) = {𝑞|∃𝑝 ∈ 𝑃(𝑓(𝑝) = 𝑞)}. Selvästi kuvaus 𝑃 → 𝑓(𝑃) on surjektio.
Lisäksi osittain järjestetyn joukon(𝑓(𝑃),⊑)relaatio on sama kuin osittain järjestetyn joukon𝒬 = (𝑄 ,⊑), mutta rajoitettuna joukkoon 𝑓(𝑃). Näin ollen kuvaus𝑃→ 𝑓(𝑃) on myös upotus. Täten 𝑓 on järjestysisomorfismi osittain järjestettyjen joukkojen𝒫
ja(𝑓(𝑃),⊑)välillä. □
Seuraavaksi keskitytään aiemmin määriteltyjen, tarkemmin monotonisten, upo- tuksien ja järjestysisomorfisten, kuvauksien yhdisteisiin ja todistetaan, että nämä ovat vastaavasti myös monotonisia, upotuksia ja järjestysisomorfioita. Lisäksi esitellään seuraus, jonka mukaan monotonisten kuvausten yhdiste on liitännäinen.
Lause 4.4. Olkoon 𝑓: 𝑃→𝑄monotoninen kuvaus osittain järjestettyjen joukkojen 𝒫= (𝑃,⪯)ja𝒬 =(𝑄 ,⊑)välillä, ja olkoon𝑔: 𝑄→ 𝑅monotoninen kuvaus osittain järjestettyjen joukkojen𝒬 =(𝑄 ,⊑)jaℛ= (𝑅,≤) välillä. Tällöin yhdistetty kuvaus 𝑔 ◦ 𝑓: 𝑃 → 𝑅 on monotoninen kuvaus osittain järjestetyltä joukolta 𝒫 osittain järjestetylle joukolleℛ.
Todistus(vrt. [6, s. 8]). Oletetaan, että 𝑥 ⪯ 𝑦, kun 𝑥 , 𝑦 ∈ 𝑃. Tällöin, koska 𝑓 on monotoninen, niin 𝑓(𝑥) ⊑ 𝑓(𝑦). Tästä taas seuraa, että𝑔(𝑓(𝑥)) ≤ 𝑔(𝑓(𝑦)), sillä𝑔 on monotoninen. Näin ollen, jos𝑥 ⪯ 𝑦, niin𝑔(𝑓(𝑥)) ≤ 𝑔(𝑓(𝑦)) aina, kun𝑥 , 𝑦 ∈ 𝑃.
Täten𝑔◦ 𝑓 on monotoninen. □
Lause 4.5. Monotonisten kuvausten yhdiste on liitännäinen, eli jos 𝑓: 𝑃 → 𝑄, 𝑓: 𝑄 → 𝑅 ja ℎ: 𝑅 → 𝑆 ovat monotonisia, niin (𝑓 ◦𝑔) ◦ ℎ ja 𝑓 ◦ (𝑔 ◦ℎ) ovat monotonisia, ja(𝑓 ◦𝑔) ◦ℎ= 𝑓 ◦ (𝑔◦ℎ).
Todistus(vrt. [6, s. 8]). Tämä seuraa lauseesta 4.4. □ Lause 4.6. Olkoon 𝑓: 𝑃 → 𝑄 upotus (järjestysisomorfismi) osittain järjestettyjen joukkojen𝒫 = (𝑃,⪯) ja𝒬 = (𝑄 ,⊑) välillä, ja olkoon 𝑔: 𝑄 → 𝑅 upotus (järjes- tysisomorfismi) osittain järjestettyjen joukkojen𝒬 = (𝑄 ,⊑) ja ℛ = (𝑅,≤) välillä.
Tällöin𝑔◦ 𝑓 : 𝑃→ 𝑅on upotus (järjestysisomorfismi) osittain järjestetyltä joukolta 𝒫osittain järjestetylle joukolleℛ.
Todistus(vrt. [6, s. 8-9]). Todistetaan ensin, että𝑔◦𝑓 on upotus. Koska 𝑓 on upotus, niin𝑥 ⪯ 𝑦, jos ja vain jos 𝑓(𝑥) ⊑ 𝑓(𝑦), aina, kun𝑥 , 𝑦 ∈𝑃. Lisäksi koska𝑔on upotus, niin 𝑓(𝑥) ⊑ 𝑓(𝑦), jos ja vain jos𝑔(𝑓(𝑥)) ≤𝑔(𝑓(𝑦)), aina, kun𝑥 , 𝑦 ∈ 𝑃. Näin ollen 𝑥 ⪯ 𝑦, jos ja vain jos𝑔(𝑓(𝑥)) ≤𝑔(𝑓(𝑦)), aina, kun𝑥 , 𝑦 ∈𝑃. Täten𝑔◦ 𝑓 on upotus.
Todistetaan sitten, että jos 𝑓 ja 𝑔 ovat surjektioita, niin 𝑔◦ 𝑓 on myös, eli että tällöin𝑔◦ 𝑓 on järjestysisomorfismi. Nyt siis, jos 𝑓 on surjektio, niin𝑄 = 𝑓(𝑃), ja jos𝑔on surjektio, niin𝑅 =𝑔(𝑄). Täten𝑅=𝑔(𝑓(𝑃)). Tällöin selvästi𝑔◦ 𝑓: 𝑃 → 𝑅 on surjektio. Näin ollen𝑔◦ 𝑓: 𝑃 → 𝑅on järjestysisomorfismi osittain järjestetyltä
joukolta𝒫 osittain järjestetylle joukolleℛ. □
Todistetaan sitten, että järjestysisomorfisuus on ekvivalenssirelaatio, ja esitellään lause, jonka nojalla jokainen osittain järjestetty joukko on järjestysisomorfinen osit- tain järjestetyn joukon kanssa, jonka relaationa on inkluusio. Lisäksi esitellään lause, joka yhdistää monotonisia kuvauksia ja yläjoukkoja.
Lause 4.7. Järjestysisomorfisuus on ekvivalenssirelaatio.
Todistus(vrt. [6, s. 9]). Osoitetaan siis, että järjestysisomorfisuus on refleksiivinen, symmetrinen ja transitiivinen. Selvästi järjestysisomorfisuus on refleksiivinen.
Oletetaan sitten, että 𝑓 on järjestysisomorfismi osittain järjestettyjen joukkojen𝒫 ja𝒬välillä, ja että𝑔on järjestysisomorfismi osittain järjestettyjen joukkojen𝒬jaℛ
välillä. Tällöin lauseen 4.6 nojalla𝑔◦𝑓 on järjestysisomorfismi osittain järjestettyjen joukkojen𝒫 jaℛvälillä, eli järjestysisomorfisuus on transitiivinen.
Olkoot𝒫 =(𝑃,⪯)ja𝒬 =(𝑄 ,⊑)osittain järjestettyjä joukkoja. Oletetaan vielä, että 𝑓: 𝑃 → 𝑄 on järjestysisomorfismi osittain järjestetyltä joukolta 𝒫 osittain järjestetylle joukolle𝒬, ja osoitetaan, että tällöin on olemassa järjestysisomorfismi osittain järjestetyltä joukolta𝒬 osittain järjestetylle joukolle 𝒫. Määritellään, että 𝑓−1:𝑄 → 𝑃on sellainen, että 𝑓−1(𝑞) = 𝑝, jos ja vain jos 𝑓(𝑝) =𝑞, aina, kun𝑝 ∈ 𝑃 ja𝑞 ∈𝑄. Tällöin selvästi 𝑓−1on surjektio, joten tarvitsee osoittaa vain, että 𝑓−1on upotus. Koska 𝑓 on upotus, niin
𝑝 ⪯ 𝑝′, jos ja vain jos 𝑓(𝑝) ⊑ 𝑓(𝑝′), aina, kun 𝑝, 𝑝′∈𝑃. Nyt siis
𝑓(𝑝) ⊑ 𝑓(𝑝′), jos ja vain jos 𝑓−1(𝑓(𝑝)) ⪯ 𝑓1(𝑓(𝑝′)), aina, kun 𝑓(𝑝), 𝑓(𝑝′) ∈𝑄. Täten 𝑓−1on järjestysisomorfismi osittain järjestetyltä joukolta𝒬osittain järjestetylle joukolle𝒫, joten järjestysisomorfisuus on siis symmetrinen. Näin ollen järjestysiso-
morfisuus on ekvivalenssirelaatio. □
Lause 4.8. Jokainen osittain järjestetty joukko on järjestysisomorfinen osittain jär- jestetyn joukon kanssa, jonka relaationa on inkluusio.
Todistus(vrt. [6, s. 10-11]). Olkoon 𝑃varustettuna osittaisella järjestyksellä≤osit- tain järjestetty joukko, ja olkoon𝒪(𝑃)={↓ 𝑝|𝑝 ∈𝑃}joukon 𝑃kaikkien alajoukko- jen perhe. Nyt siis𝒪(𝑃)varustettuna inkluusiolla on myös osittain järjestetty joukko.
Osoitetaan, että osittain järjestetty joukko𝑃 on järjestysisomorfinen osittain järjes- tetyn joukon𝒪(𝑃)kanssa, eli että näiden välillä on olemassa kuvaus, joka on upotus ja surjektio joukolta 𝑃 joukolle𝒪(𝑃). Tarkastellaan kuvausta 𝑓: 𝑃 → 𝒪(𝑃), joka kuvaa alkion𝑝 ∈ 𝑃alkioon↓ 𝑝 ∈𝒪(𝑃). Lauseen 3.8 nojalla saadaan, että
𝑝 ≤ 𝑝′, jos ja vain jos 𝑓(𝑝) =↓ 𝑝 ⊆ ↓ 𝑝′= 𝑓(𝑝′).
Täten 𝑓 on upotus, jolloin lauseen 4.2 nojalla tämä on myös injektio. Lisäksi tällöin 𝒪(𝑃) = 𝑓(𝑃), joten 𝑓 on myös surjektio. Näin ollen jokainen osittain järjestetty joukko on järjestysisomorfinen osittain järjestetyn joukon kanssa, jonka relaationa
on inkluusio. □
Lause 4.9. Olkoon 𝑃 osittain järjestetty joukko, ja olkoon {false,true} osittain järjestetty joukko, jossa false ≤ true. Monotoniset kuvaukset 𝑃 → {false,true} ovat bijektiivisiä osittain järjestetyn joukon𝑃yläjoukkojen kanssa.
Todistus(vrt. [3, s. 22]). Olkoon 𝑓: 𝑃 → {false,true} monotoninen kuvaus, olkoot 𝑝, 𝑞 ∈𝑃, ja olkoon𝑈osittain järjestetyn joukon𝑃yläjoukko. Määritellään 𝑓𝑈: 𝑃 → {false,true} siten, että 𝑓𝑈(𝑝) = true, kun 𝑝 ∈ 𝑈, ja 𝑓𝑈(𝑝) = false, kun 𝑝 ∉ 𝑈. Olkoon lisäksi 𝐴: 𝑓 ↦→ 𝑓−1(true) ja 𝐵: 𝑈 ↦→ 𝑓𝑈. Osoitetaan siis, että nämä ovat toistensa käänteiskuvauksia, eli että jokaisella𝑈 ja 𝑓 pätee, että 𝐴(𝐵(𝑈)) = 𝑈 ja 𝐵(𝐴(𝑓))= 𝑓.
Osoitetaan ensin, että osajoukko 𝑓−1(true) ⊆ 𝑃 on yläjoukko. Oletetaan siis, että 𝑝 ∈ 𝑓−1(true), ja että 𝑝 ≤ 𝑞, ja todistetaan, että tällöin myös 𝑞 ∈ 𝑓−1(true).
Koska 𝑝 ∈ 𝑓−1(true), niin true = 𝑓(𝑝), ja koska 𝑓 on monotoninen, niin 𝑓(𝑝) ≤ 𝑓(𝑞). Tällöin siis true ≤ 𝑓(𝑞), josta seuraa osittain järjestetyn joukon {false,true}
määritelmän nojalla, että true= 𝑓(𝑞). Tästä taas seuraa, että𝑞 ∈ 𝑓−1(true), ja täten 𝑓−1(true) on yläjoukko.
Osoitetaan sitten, että 𝑓𝑈 on monotoninen kuvaus. Oletetaan siis, että 𝑝 ≤ 𝑞. Tällöin joko 𝑝 ∈𝑈 tai 𝑝 ∉𝑈. Jos 𝑝 ∈𝑈, niin yläjoukon määritelmän nojalla myös 𝑞 ∈𝑈. Tällöin 𝑓𝑈(𝑝) = true= 𝑓𝑈(𝑞). Jos taas 𝑝 ∉𝑈, niin 𝑓𝑈(𝑝) =false ≤ 𝑓𝑈(𝑞). Molemmissa tapauksissa siis 𝑓𝑈(𝑝) ≤ 𝑓𝑈(𝑞). Näin ollen 𝑓𝑈on monotoninen kuvaus.
Todistetaan nyt siis vielä, että 𝑓−1
𝑈 (true) =𝑈 ja 𝑓
𝑓−1(true) = 𝑓. Oletetaan ensin, että 𝑝 ∈𝑈. Tällöin 𝑓𝑈(𝑝) = true, joten 𝑝 ∈ 𝑓−1
𝑈 (true). Näin ollen𝑈 ⊆ 𝑓−1
𝑈 (true).
Jos taas𝑝 ∈ 𝑓−1
𝑈 (true), niin 𝑓𝑈(𝑝) =true, jolloin𝑝 ∈𝑈. Täten 𝑓−1
𝑈 (true) ⊆𝑈. Näin ollen 𝑓−1
𝑈 (true) =𝑈. Oletuksen nojalla 𝑓
𝑓−1(true)(𝑝) = true, kun 𝑝 ∈ 𝑓−1(true). Tällöin 𝑓(𝑝) =true.
Toisaalta taas 𝑓
𝑓−1(true)(𝑝) = false, kun 𝑝 ∉ 𝑓−1(true). Tällöin 𝑓(𝑝) = false. Näin ollen 𝑓
𝑓−1(true)(𝑝) = 𝑓(𝑝) aina, kun 𝑝 ∈ 𝑃, eli 𝑓
𝑓−1(true) = 𝑓. Täten monotoniset ku- vaukset𝑃→ {false,true}ovat bijektiivisiä osittain järjestetyn joukon𝑃yläjoukkojen
kanssa. □
Viimeisenä keskitytään vielä täydennyksen (vrt. [1, s. 33]) ja Dedekind-MacNeille täydennyksen (vrt. [1, s. 34] ja [4, s. 66]) määritelmiin, kuten myös näihin liittyvään lauseeseen. Näiden nojalla on olemassa upotus osittain järjestetyltä joukolta𝑃täydel- liseen hilaan DM(𝑃). Tässä muodostettu Dedekind-MacNeille täydennys on pienin täydellinen hila, joka sisältää osittain järjestetyn joukon𝑃.
Määritelmä 4.10. Olkoon𝑃osittain järjestetty joukko, ja olkoon𝐿täydellinen hila.
Upotusta𝑃→ 𝐿 kutsutaan osittain järjestetyn joukon𝑃täydennykseksi. Joukkoa DM(𝑃) ={𝐴 ⊆ 𝑃|𝐴= 𝐴𝓊𝓁},
kun relaationa on inkluusio, taas kutsutaan osittain järjestetyn joukon 𝑃 Dedekind- MacNeille täydennykseksi. Tässä siis𝑥 ∈ 𝐴𝓊𝓁, jos ja vain jos se on jokaisen joukon 𝐴ylärajan alaraja.
Lause 4.11. Olkoon𝑃osittain järjestetty joukko. Tällöin DM(𝑃)on täydellinen hila.
Todistus(vrt. [4, s. 66-67]). Jos joukolla𝑃 on pienin alkio⊥, niin∅𝓊 = 𝑃 ja𝑃𝓁 = {⊥}. Jos taas joukolla𝑃ei ole pienintä alkiota, niin∅𝓊=𝑃ja𝑃𝓁 =∅. Molemmissa tapauksissa∅𝓊𝓁 = (∅𝓊𝓁)𝓊𝓁. Lisäksi tällöin∅𝓊𝓁 ⊆ 𝐴𝓊𝓁 = 𝐴aina, kun 𝐴 ∈DM(𝑃). Täten∅𝓊𝓁on joukon DM(𝑃) pienin alkio. Koska DM(𝑃) varustettuna inkluusiolla on epätyhjä osittain järjestetty joukko, niin nyt lauseen 3.19 kohdan 2 nojalla riittää osoittaa, että jokaiselle epätyhjälle osajoukolleA ⊆DM(𝑃)on olemassa⋁︁
A.
Olkoon A = {𝐴𝑖|𝑖 ∈ 𝐼} ⊆ DM(𝑃) ja 𝐴 = ⋃︁
𝑖∈𝐼 𝐴𝑖. Tällöin 𝐴𝓊𝓁 ⊆ 𝑃. Lisäksi lauseen 3.10 kohdan 3 nojalla 𝐴𝓊= 𝐴𝓊𝓁𝓊, joten
𝐴𝓊𝓁 = (𝐴𝓊)𝓁 = (𝐴𝓊𝓁𝓊)𝓁= (𝐴𝓊𝓁)𝓊𝓁.
Täten 𝐴𝓊𝓁 ∈DM(𝑃). Koska𝐴𝑖 ⊆ 𝐴aina, kun 𝐴𝑖 ∈ A, niin lauseen 3.10 kohdan 2 nojalla saadaan, että𝐴𝓊 ⊆ 𝐴𝓊
𝑖 . Tästä seuraa edelleen lauseen 3.10 kohdan 1 nojalla, että 𝐴𝑖 = 𝐴𝓊𝓁
𝑖 ⊆ 𝐴𝓊𝓁. Näin ollen 𝐴𝓊𝓁 on joukon A yläraja joukossa DM(𝑃).
Todistetaan vielä, että tämä on joukonApienin yläraja.
Oletetaan siis, että 𝐴′ ∈ DM(𝑃) on myös joukon A yläraja, eli että 𝐴𝑖 ⊆ 𝐴′ aina, kun 𝐴𝑖 ∈ A. Tällöin siis 𝐴 ⊆ 𝐴′. Tästä seuraa lauseen 3.10 kohdan 2 nojalla, että 𝐴′𝓊 ⊆ 𝐴𝓊, josta seuraa edelleen lauseen 3.10 kohdan 2 nojalla, että 𝐴𝓊𝓁 ⊆ 𝐴′𝓊𝓁. Näin ollen 𝐴𝓊𝓁 on siis joukon A pienin yläraja. Täten jokaiselle epätyhjälle osajoukolle A ⊆ DM(𝑃) on olemassa ⋁︁A, jolloin siis DM(𝑃) on täydellinen
hila. □
5 Galois’n yhteydet
Osittain järjestettyjen joukkojen väliset Galois’n yhteydet yleistävät Galois’n teo- riassa esitetyt välikuntien ja aliryhmien väliset vastaavuudet. Galois’n yhteys on jär- jestysisomorfiaa heikompi osittain järjestettyjen joukkojen välinen kuvaus pari, joka kuitenkin omaa tätä enemmän sovellusmahdollisuuksia. Lisäksi jokaisesta Galois’n yhteydestä saadaan muodostettua järjestysisomorfia rajoittumalla tiettyihin osittain järjestettyihin osajoukkoihin. Myöhemmin luvussa 8 esitelläänkin tätä hyödyntäen myös näistä seuraavat osittain järjestettyjen joukkojen väliset Galois’n vastaavuu- det. Galois’n yhteyksien määritelmän lisäksi tämän luvun ensimmäisissä alaluvuissa perehdytään eri määritelmien yhtäpitävyyteen, kuten myös Galois’n yhteyksien pe- rusominaisuuksiin. Näiden jälkeen Galois’n yhteyksistä esitellään useampi esimerkki ja viimeisenä perehdytään vielä binääriseen relaatioon liittyvään Galois’n yhteyteen.
5.1 Galois’n yhteyksien määritelmä
Ensimmäisenä käydään läpi sekä monotonisten (vrt. [6, s. 12]) että antitonisten (vrt.
[1, s. 14]) Galois’n yhteyksien määritelmät.
Määritelmä 5.1. Olkoot𝒫 = (𝑃,⪯) ja𝒬 = (𝑄 ,⊑) osittain järjestettyjä joukkoja.
Oletetaan, että 𝑓: 𝑃 →𝑄ja𝑔: 𝑄 → 𝑃ovat sellaisia kuvauksia, että (5.1) 𝑓(𝑝) ⊑𝑞, jos ja vain jos 𝑝 ⪯ 𝑔(𝑞),
aina, kun 𝑝 ∈ 𝑃ja𝑞 ∈ 𝑄. Tällöin pari (𝑓 , 𝑔) muodostaaGalois’n yhteydenosittain järjestettyjen joukkojen𝒫ja𝒬välille. Lisäksi sanotaan, että 𝑓 on Galois’n yhteyden vasen liittokuvaus ja vastaavasti 𝑔 on Galois’n yhteyden oikea liittokuvaus. Tässä esitellyt kuvaukset ovat monotonisia, ja tällaista Galois’n yhteyttä kutsutaan myös monotoniseksi Galois’n yhteydeksi.
Määritelmä 5.2. Olkoot𝒫 = (𝑃,⪯) ja𝒬 = (𝑄 ,⊑) osittain järjestettyjä joukkoja.
Oletetaan, että 𝑓: 𝑃 →𝑄ja𝑔: 𝑄 → 𝑃ovat sellaisia kuvauksia, että (5.2) 𝑞 ⊑ 𝑓(𝑝), jos ja vain jos 𝑝 ⪯ 𝑔(𝑞),
aina, kun 𝑝 ∈ 𝑃 ja 𝑞 ∈ 𝑄. Tällöin pari (𝑓 , 𝑔) muodostaa antitonisen Galois’n yhteydenosittain järjestettyjen joukkojen𝒫ja𝒬välille.
Huomaa, että monotoninen yhteys osittain järjestettyjen joukkojen𝒫ja𝒬välillä on siis antitoninen yhteys osittain järjestettyjen joukkojen𝒫ja𝒬𝒹välillä. Jatkossa, kun puhutaan Galois’n yhteydestä, tarkoitetaan monotonista Galois’n yhteyttä.
5.2 Eri määritelmien yhtäpitävyys
Seuraavana esitellään kaksi lausetta, jotka tarjoavat vaihtoehtoisia tapoja määritellä Galois’n yhteys.
Lause 5.3. Olkoot 𝒫 = (𝑃,⪯) ja 𝒬 = (𝑄 ,⊑) osittain järjestettyjä joukkoja, ja olkoot 𝑓: 𝑃 →𝑄 ja𝑔:𝑄 → 𝑃kuvauksia. Tällöin pari (𝑓 , 𝑔)muodostaa Galois’n yhteyden osittain järjestettyjen joukkojen𝒫ja𝒬välille, jos ja vain jos
1. 𝑝 ⪯ 𝑔(𝑓(𝑝))ja 𝑓(𝑔(𝑞)) ⊑ 𝑞aina, kun𝑝 ∈ 𝑃ja𝑞 ∈𝑄, ja 2. kuvaukset 𝑓 ja𝑔ovat molemmat monotonisia.
Todistus(vrt. [6, s. 15-16]). Oletetaan ensin, että (𝑓 , 𝑔) muodostaa Galois’n yhtey- den osittain järjestettyjen joukkojen 𝒫 ja 𝒬 välille ja todistetaan, että molemmat kohdat seuraavat tästä oletuksesta.
1. Nyt siis määritelmän 5.1 nojalla saadaan, että
𝑓(𝑝) ⊑ 𝑓(𝑝), jos ja vain jos 𝑝 ⪯ 𝑔(𝑓(𝑝)), aina, kun𝑝 ∈ 𝑃.
Koska ⊑ on refleksiivinen, niin 𝑓(𝑝) ⊑ 𝑓(𝑝). Täten 𝑝 ⪯ 𝑔(𝑓(𝑝)). Lisäksi määritelmän 5.1 nojalla saadaan, että
𝑓(𝑔(𝑞)) ⊑ 𝑞, jos ja vain jos𝑔(𝑞) ⪯ 𝑔(𝑞), aina, kun𝑞 ∈𝑄.
Jälleen koska ⪯ on refleksiivinen, niin 𝑔(𝑞) ⪯ 𝑔(𝑞). Tästä taas seuraa, että 𝑓(𝑔(𝑞)) ⊑ 𝑞. Näin ollen 𝑝 ⪯ 𝑔(𝑓(𝑝)) ja 𝑓(𝑔(𝑞)) ⊑ 𝑞 aina, kun 𝑝 ∈ 𝑃 ja 𝑞 ∈𝑄.
2. Oletetaan nyt lisäksi, että 𝑝 ⪯ 𝑝′ aina, kun 𝑝, 𝑝′ ∈ 𝑃, ja todistetaan, että tällöin 𝑓(𝑝) ⊑ 𝑓(𝑝′). Edellä osoitettiin, että 𝑝′ ⪯ 𝑔(𝑓(𝑝′))aina, kun 𝑝′∈ 𝑃, joten nyt relaation⪯transitiivisuuden nojalla 𝑝 ⪯ 𝑔(𝑓(𝑝′)). Määritelmän 5.1 nojalla saadaan, että
𝑓(𝑝) ⊑ 𝑓(𝑝′), jos ja vain jos𝑝 ⪯ 𝑔(𝑓(𝑝′)), aina, kun𝑝, 𝑝′∈𝑃. Täten 𝑓(𝑝) ⊑ 𝑓(𝑝′), ja näin ollen 𝑓 on monotoninen. Samoin saadaan, että𝑔 on monotoninen.
Oletetaan sitten, että kohdat 1 ja 2 pätevät ja todistetaan, että tällöin pari (𝑓 , 𝑔) muodostaa Galois’n yhteyden osittain järjestettyjen joukkojen𝒫ja𝒬välille. Olete- taan siis lisäksi, että 𝑓(𝑝) ⊑ 𝑞, kun 𝑝 ∈𝑃 ja𝑞 ∈𝑄. Nyt, koska𝑔on monotoninen, niin𝑔(𝑓(𝑝)) ⪯ 𝑔(𝑞). Lisäksi kohdan 1 mukaan 𝑝 ⪯ 𝑔(𝑓(𝑝)) aina, kun 𝑝 ∈ 𝑃. Täl- löin, koska⪯on transitiivinen, niin saadaan, että 𝑝 ⪯ 𝑔(𝑞). Nyt siis, jos 𝑓(𝑝) ⊑ 𝑞, niin𝑝 ⪯ 𝑔(𝑞)aina, kun 𝑝 ∈𝑃ja𝑞 ∈𝑄.
Oletetaan vastaavasti, että 𝑝 ⪯ 𝑔(𝑞), kun 𝑝 ∈ 𝑃 ja 𝑞 ∈ 𝑄. Nyt koska 𝑓 on monotoninen, niin 𝑓(𝑝) ⊑ 𝑓(𝑔(𝑞)). Lisäksi kohdan 1 mukaan 𝑓(𝑔(𝑞)) ⊑ 𝑞 aina, kun 𝑞 ∈ 𝑄. Tällöin, koska ⊑ on transitiivinen, niin saadaan, että 𝑓(𝑝) ⊑ 𝑞. Nyt siis, jos 𝑝 ⪯ 𝑔(𝑞), niin 𝑓(𝑝) ⊑ 𝑞 aina, kun 𝑝 ∈ 𝑃 ja 𝑞 ∈ 𝑄. Täten 𝑓(𝑝) ⊑ 𝑞, jos ja vain jos𝑝 ⪯ 𝑔(𝑞), aina, kun 𝑝 ∈ 𝑃 ja 𝑞 ∈ 𝑄. Näin ollen pari (𝑓 , 𝑔) muodostaa Galois’n yhteyden osittain järjestettyjen joukkojen𝒫ja𝒬välille. □ Lause 5.4. Olkoot𝒫 =(𝑃,⪯)ja𝒬 =(𝑄 ,⊑)osittain järjestettyjä joukkoja, ja olkoot
𝑓: 𝑃 →𝑄ja𝑔: 𝑄 → 𝑃kuvauksia. Tällöin seuraavat väittämät ovat yhtäpitäviä:
