Järjestysrelaatio

Järjestysrelaatio on joukon binäärirelaatio, joka on refleksiivinen, antisymmetrinen ja transitiivinen.

Motivaatio

Järjestys on tuttu käsite myös arkielämästä. Monia asioita voidaan jotenkin järjestää – sanat aakkosjärjestykseen, oppilaat koulussa pituuden mukaan, tavarat hinnan mukaan. Kaikkea tätä kuvaa järjestysrelaatio, jota merkitään yleensä symbolilla ≤. Siihen liittyvät symbolit ovat <, > ja ≥. Niiden merkitys on selvä.

Mitä tällaiselta relaatiolta odotettaisiin? Jo symbolista näkyy, että järjestysrelaatiossa on mukana alkioita, jotka ovat samat – tarkoitus on siis määritellä relaation ”pienempi tai yhtä suuri” ominaisuudet. Tällaisen relaation pitäisi olla refleksiivinen. Täytyy päteä a ≤ a.

Entä sitten? Symmetrisyys ei varmasti päde – jos järjestetään hinnan mukaan ja auto on halvempi kuin leipä, ei varmasti samalla leipä ole halvempi kuin auto. Mitä yleisesti odotettaisiin, jos sattuisi olemaan a ≤ b ja samalla b ≤ a? Olisiko siinä koskaan järkeä? On, jos a = b. Ainoa tapaus, jossa relaatioon pantavien alkioiden järjestyksellä ei ole väliä, on se, että alkiot ovat samat – järjestys on siis antisymmetrinen.

Lopuksi, jos tiedetään, että auto on kalliimpi kuin leipä ja lentokone on vielä kalliimpi kuin auto, odotetaan, että lentokone on varmasti kalliimpi kuin leipä. Tätä kuvaa transitiivisuus.

Osittaisjärjestys

Se, mitä edellä määriteltiin, on itse asiassa vain osittaisjärjestys, ei täydellinen järjestys. Miksi se ei ole täydellinen? Yritetään määritellä järjestys joukoille. Miten kaksi joukkoa voitaisiin verrata toisiinsa?

Sanotaan, että joukko A on pienempi tai yhtä suuri kuin joukko B, jos A ⊆ B, eli jos A on joukon B osajoukko. Tässä on järkeä, sillä jos A = {1, 2} ja B = {1, 2, 3}, voidaan sanoa, että A on pienempi – joukossa B on samat alkiot kuin joukossa A ja lisäksi luku kolme. Esimerkiksi siis pätee:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Vaikeus syntyy, kun halutaan verrata näitä joukkoja: A = {a, b} ja B = {a, c}. Kumpi niistä on pienempi tai suurempi? Vaikka molemmissa joukoissa on alkio a, toinen alkio on kummassakin eri. Kumpikaan joukko ei ole toisen osajoukko, joten ei päde A ≤ B eikä B ≤ A. Tällaiset joukot ovat tämän järjestyksen mielessä vertailukelvottomia.

Siksi määritellään täydellisesti järjestetty joukko eli ketju niin, että mitkä tahansa kaksi joukon alkiota ovat vertailukelpoisia. Tällaisia joukkoja ovat esimerkiksi lukujoukot tavallisella järjestyksellä. Mille tahansa kahdelle reaaliluvulle a, b voit ratkaista, onko a ≤ b vai b ≤ a.

Esimerkkejä arkielämästä

Esimerkki siitä, milloin kannattaa jättää vertaamatta, voisi olla järjestys kauneuden mukaan, jolloin relaatio < tarkoittaisi ”olla rumempi”. Ehkä se pitäisi määritellä mieluummin toisin päin niin, että > tarkoittaa ”olla kauniimpi”, jotta oltaisiin korrektimpia :-). Kahden naisen vertaamisessa on luultavasti järkeä, esimerkiksi ”Helmi” < ”Ella” siinä mielessä, että Ella on kauniimpi kuin Helmi. Samoin kahden miehen: ”Eino” < ”Leevi” siinä mielessä, että Leevi on kauniimpi kuin Eino.

Ongelma on se, että miehen ja naisen kauneutta on tuskin mahdollista verrata. Onko kauniimpi Ella vai Leevi? Onko rumempi Helmi vai Eino? Parempi olla tutkimatta…

Jos viimeisessä esimerkissä rajoitutaan vaikkapa vain naisiin, voidaan sanoa, että joukko on täydellisesti järjestetty, koska kaikkien naisten kauneutta voidaan verrata keskenään.

Minimaalinen ja maksimaalinen alkio, pienin ja suurin alkio

Olkoon M järjestetty joukko. Alkiota min ∈ M kutsutaan minimaaliseksi, jos ei ole sellaista alkiota x ∈ M, että x < min. Ei siis voida löytää alkiota, joka olisi pienempi kuin alkio min.

Alkiota max ∈ M kutsutaan maksimaaliseksi, jos ei ole sellaista alkiota x ∈ M, että x > max. Ei siis voida löytää alkiota, joka olisi suurempi.

Nämä kaksi käsitettä eroavat käsitteistä pienin ja suurin alkio.

Alkiota a ∈ M kutsutaan pienimmäksi, jos kaikille x ∈ M pätee a ≤ x. Pienin alkio a on siis pienempi tai yhtä suuri kuin kaikki muut joukon M alkiot.

Alkiota b ∈ M kutsutaan suurimmaksi, jos kaikille x ∈ M pätee b ≥ x. Suurin alkio b on suurempi tai yhtä suuri kuin kaikki muut joukon M alkiot.

Mikä on ero suurimman ja maksimaalisen alkion välillä? Maksimaalisia alkioita voi olla useita, koska joukon ei välttämättä tarvitse olla täydellisesti järjestetty. Palataan esimerkkiin, jossa ihmisiä verrataan ulkonäön perusteella. Voidaan sanoa, että Emma on kaunein nainen ja Onni on kaunein mies. Näitä kahta henkilöä ei kuitenkaan voida enää verrata keskenään, ei tiedetä, onko kauniimpi Emma vai Onni.

Molemmat alkiot ovat siis maksimaalisia. Ei voida löytää henkilöä, joka olisi kauniimpi kuin Onni – Onni on kauniimpi kuin kaikki muut miehet, ja naisiin häntä ei voi verrata. Samoin Emma on kauniimpi kuin kaikki naiset, ja miehiin häntä ei voi verrata.

Kumpikaan heistä ei kuitenkaan ole suurin eli tässä mielessä kaunein. Jotta Onni olisi kaunein/suurin, hänen pitäisi olla kauniimpi kuin kaikki henkilöt, myös kaikki naiset. Mutta edellä todettiin, ettei häntä voi verrata naisiin, joten hän ei voi olla kaunein ihminen, vaan hän on järjestysteorian terminologiassa vain maksimaalinen.

On helppo nähdä, että jos joukolla on suurin alkio, tämä alkio on samalla myös maksimaalinen. Jos alkio a on suurempi kuin kaikki muut joukon alkiot (suurimman alkion määritelmä), ei varmasti löydetä alkiota, joka olisi vielä suurempi (maksimaalisen alkion määritelmä).

Esimerkki joukosta, jolla on suurin ja pienin alkio, on suljettu väli [0, 1]. Jos valitaan sama väli avoimena, sillä ei olisi suurinta eikä pienintä alkiota: ]0, 1[.

Jos haluttaisiin äärettömän monta minimaalista alkiota, voitaisiin järjestys R määritellä seuraavasti. Määritellään ensin apujoukot M_x. Joukot ovat tätä muotoa: jokaiselle välin ]0, 1[ luvulle x määritellään joukko M_x = {y ∣ y = x + n}, missä n on ei-negatiivinen kokonaisluku. Näin saadaan esimerkiksi seuraavanlaisia joukkoja:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Jokaiselle joukolle M_x määritellään tavallinen järjestys, jota merkitään R_x. Lopuksi nämä järjestykset yhdistetään: R = ∪ R_x. Tässä järjestyksessä voidaan aina verrata vain alkuperäisten ketjujen sisällä. Voidaan siis selvittää, onko 0,5 ≤ 2,5, mutta ei voida selvittää, onko 0,5 ≤ 2,7, koska nämä luvut eivät olleet samassa joukossa M_x, joten niiden suhdetta ei ole määritelty.

Tässä järjestysrelaatiossa jokainen välin ]0, 1[ alkio on minimaalinen alkio.

Hassen kaaviot

Järjestetyt joukot voidaan piirtää Hassen kaavion avulla. Se on graafi, jonka solmut esittävät joukon alkioita ja solmujen väliset kaaret (a, b) kertovat, että a < b ja samalla ei ole olemassa sellaista c, että a < c < b. Alkioiden a ja b välissä ei siis ole mitään muuta alkiota. Lisäksi täytyy päteä, että graafissa solmu a on alempana kuin solmu b. Esimerkki Hassen kaaviosta:

Tämä Hassen kaavio esittää järjestettyä joukkoa {A, B, C, D, E, F}. Siinä pätee: A < B, B < E, lisäksi tietysti pätee A < E, mutta näiden solmujen välillä ei ole kaarta, koska on olemassa solmu B, jolle pätee A < B < E. Alkiot E ja D ovat vertailukelvottomia, koska kumpikaan ei ole toisen yläpuolella tai alapuolella.

Vaikka Hassen kaaviot piirretään yleensä näin siististi tasattuina, se ei ole ehdottoman välttämätöntä. Edellinen Hassen kaavio voi näyttää myös tältä:

Toinen esimerkki voisi olla joukko A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Nämä ovat luvun 60 positiiviset tekijät. Jaollisuuden mukainen järjestys voidaan esittää näin:

Jaollisuuden mukainen järjestys tarkoittaa, että (a, b) ∈ R täsmälleen silloin, kun a jakaa luvun b. Kaaviosta voidaan huomata, että jokaisen luvun yläpuolella ovat luvut, jotka se jakaa. Esimerkiksi luvun 6 yläpuolella ovat luvut 12, 30 ja 60. Luvun 4 yläpuolella ovat luvut 12, 20 ja 60. Jne. Sen sijaan luvun 3 yläpuolella ei ole lukua 10, koska se ei jaa sitä – huomaa, että luku 10 on visuaalisesti luvun 3 yläpuolella, mutta sinne ei johda ”alhaalta ylöspäin” mitään viivaa. Jos luvusta 3 liikutaan vain ylöspäin, voidaan päästä lukuihin 15 ja 6 ja niistä lukuun 30. Lukuun 10 päästäisiin vain laskeutumalla alaspäin, mikä ei ole sallittua.