Osittain järjestetty joukko

Osittain järjestetty joukko on matemaattinen rakenne, joka on esijärjestetyn joukon ohella yksinkertaisin "järjestyksen" käsitystä formalisoiva rakenne. Osittain järjestetty joukko koostuu joukosta sekä binäärirelaatiosta tässä joukossa. Relaatiota itseään kutsutaan osittaisjärjestykseksi.

Täsmällisesti, relaatiota kutsutaan osittaisjärjestykseksi jos se on refleksiivinen, transitiivinen ja antisymmetrinen.

Osittaisuus tarkoittaa, ettei joukon kaikista alkiopareista voi välttämättä sanoa kumpi on "suurempi", "järjestyksessä ensin" tms. Järjestys ei välttämättä tarkoita mitään tavanomaista suuruusjärjestystä, vaikka luonnollisten lukujen sekä reaalilukujen tavanomainen suuruusjärjestys onkin esimerkki osittaisjärjestyksestä, jossa kaikki alkiot ovat vertailtavissa. Näin ollen osittain järjestetyn joukon voidaan ajatella olevan täysin järjestetyn joukon yleistys. Esimerkiksi tason pisteiden etäisyys origosta muodostaa osittaisen järjestyksen. Jos $x$ on kauempana kuin $y$ ja $y$ kauempana kuin $z$, niin $x$ on kauempana kuin $z$. Järjestys ei ole täydellinen, koska esimerkiksi pisteistä $(1,2)$ ja $(2,1)$ kumpikaan ei ole kauempana kuin toinen.

Määritelmä

Pari $(P,\le )$, jossa $P$ on joukko ja $\le$ binäärirelaatio joukossa $P$, on osittain järjestetty joukko jos kaikille joukon $P$ alkioille $a,b$ ja $c$ pätee

1. $a\le a$ (refleksiivisyys),
2. jos $a\le b$ ja $b\le c$, niin $a\le c$ (transitiivisuus),
3. jos $a\le b$ ja $b\le a$, niin $a=b$ (antisymmetrisyys).

Toisin sanottuna osittain järjestetty joukko on esijärjestetty joukko, joka on myös symmetrinen. On tavanomaista merkitä osittain järjestettyä joukkoa pelkällä joukolla $P$, mikäli on selvää, mistä binäärirelaatiosta on kyse. On myöskin tavanomaista määritellä binäärirelaatio $\ge$ siten että $a\ge b$ jos ja vain jos $b\le a$.

Esimerkkejä

Antilla on tyttäret Bertta ja Cecilia, joista viimeksi mainitulla poika David. Määritellään $x\ge y$ tarkoittamaan "x on y tai y:n esivanhempi". Tällöin esimerkiksi Antti $\ge$ David, mutta Bertta ja David eivät ole vertailtavissa.

Vaa'an tarkkuus on kolme kiloa kumpaankin suuntaan. Antti painaa 60±3 kg, Bertta 65±3 kg, Cecilia 70±3 kg ja David 75±3 kg. Määritellään $x\ge y$ tarkoittamaan "x on ainakin yhtä painava kuin y". Tuloksena ei ole täydellinen järjestys, koska esimerkiksi Antti ja Bertta eivät ole vertailtavissa.

Määritellään positiivisten kokonaislukujen joukossa $x\ge y$ tarkoittamaan "x voidaan jakaa tasan luvulla y". Selvästi jos luku $z$ jakaa tasan luvun $y$ ja $y$ jakaa tasan luvun $x$, niin $z$ jakaa luvun $x$. Ei-vertailtavia ovat esimerkiksi luvut 2 ja 3.

Kirjallisuutta

• Malline:Kirjaviite
• Malline:Kirjaviite
• Malline:Kirjaviite
• Malline:Kirjaviite