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  on kauempana kuin  ja  kauempana kuin , niin  on kauempana kuin . Järjestys ei ole täydellinen, koska esimerkiksi pisteistä  ja  kumpikaan ei ole kauempana kuin toinen.

 Määritelmä 
Pari , jossa  on joukko ja  binäärirelaatio joukossa , on osittain järjestetty joukko jos kaikille joukon  alkioille  ja  pätee
  (refleksiivisyys),
 jos  ja , niin  (transitiivisuus),
 jos  ja , niin  (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 , mikäli on selvää, mistä binäärirelaatiosta on kyse. On myöskin tavanomaista määritellä binäärirelaatio  siten että  jos ja vain jos .

 Esimerkkejä 

Antilla on tyttäret Bertta ja Cecilia, joista viimeksi mainitulla poika David. Määritellään  tarkoittamaan "x on y tai y:n esivanhempi". Tällöin esimerkiksi Antti  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  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  tarkoittamaan "x voidaan jakaa tasan luvulla y". Selvästi jos luku  jakaa tasan luvun  ja  jakaa tasan luvun , niin  jakaa luvun . Ei-vertailtavia ovat esimerkiksi luvut 2 ja 3.

Kirjallisuutta





Luokka:Abstrakti algebra
Luokka:Järjestysteoria