Diskreetti matematiikka, syksy 2010
Harjoitus 6 (28. ja 29.10., to 16-18 M107, pe 12-14 M107)
Olen työmatkalla 20.-26.10.2010, ja tämän takia tiistain 19.10. luennon jälkeen on viikon loma tästä kurssista niin, että tapaamme taas luennon merkeissä keskiviikkona 27.10.
  1. Todista: Jos f: X ® Y on kuvaus, niin
    2. Pf : = { f-1(y) | y Î f(X) }
    on joukon X ositus.
    Kääntäen, jos P on joukon X ositus, on olemassa joukko Y ja kuvaus f:X® Y, joille P = Pf.

     
  2. Olkoon R relaatio joukossa X. Osoita, että on olemassa suppein relaation R sisältävä ekvivalenssi, nk. ekvivalenssisulkeuma, [`(R)]e Í X×X. Vihje: osoita ensin, että ekvivalenssien leikkaus on ekvivalenssi.

    3.  
  3. Onko jokin seuraavista joukon X = {a,b,c,d} relaatioista osittainen tai jopa totaali järjestys?
    4. a) R: = {(a,a),(a,b),(a,c),(a,d),(b,d),(c,c),(c,d),(d,d)}
    b) S: = {(a,a),(a,b),(a,c),(a,d),(b,b),(b,d),(c,c),(c,d),(d,c),(d,d)}
    c) T: = {(a,a),(a,b),(a,c),(a,d),(b,b),(b,d),(c,c),(c,d),(d,d)}
    d) U: = {(a,a),(a,b),(a,c),(b,b),(b,d),(c,c),(c,d),(d,d)}
    Piirrä järjestyksistä Hassen kaaviot.

     
  4. Todista Lause 7.2.5: Olkoon R Í X×X ekvivalenssirelaatio ja x, y Î X. Tällöin
    5. a) x Î R(x)
    b) [ R(x) ÇR(y) ¹ Æ ] Û  [ x R y ]
    c) [ R(x) = R(y) ]  Û  [ x R y ].

     
  5. Onko seuraavan kaavion määrittelemä relaatio transitiivinen?
    6. DM06041K.png
    Jos tarpeen, lisää sellaiset nuolet, että tulee transitiivinen. Onko se järjestysrelaatio sitten, kun vielä lisätään silmukat kuhunkin alkioon (otetaan siis vielä refleksiivinen sulkeuma)?

     
  6. Olkoon E : = { f :R® R | f funktio }. Määritellään relaatio \preceq Í E×E,
    7. [ f\preceq g ]     Û     [ g-fkasvava ].
    Onko pari (E, \preceq) osittainen järjestys tai jopa täydellinen?

     
  7. Olkoon (E, £ ) järjestetty joukko. Osoita, että
    8. a) joukossa E on korkeintaan yksi pienin ja yksi suurin alkio.
    b) osajoukolla F Í E on korkeintaan yksi infimum ja supremum.
     

File translated from TEX by TTH, version 3.33.
On 13 Oct 2010, 10:44.