Pert 6 [PDF]

Citation preview

HIMPUNAN TERURUT PARSIAL DAN TOTAL



A. Urutan Parsial dan Himpunan Terurut Parsial Definisi 1. Suatu urutan parsial dalam himpunan A adalah suatu relasi R pada A yang bersifat a. Refleksif, yaitu ∀ ∈ A, ( b. Anti-simetris, yaitu ∀ dan



maka



maka



∈ A, jika (



. ) ∈ R dan (



) ∈ R maka



, atau jika



.



c. Transitif, yaitu ∀ dan



) ∈ R atau



∈ A, jika (



) ∈ R dan (



) ∈ R maka (



) ∈ R, atau jika



.



Selanjutnya, jika relasi R pada himpunan A mendefinisikan suatu urutan parsial di A, maka untuk (



) ∈ R dinyatakan dengan



, yang dibaca “ mendahului ”.



Contoh 1 Misal A suatu keluarga himpunan. Relasi R didefinisikan dengan xRy adalah “x adalah himpunan bagian dari y” atau x ⊂ y. R refleksif, karena untuk setiap himpunan x, x ⊂ x. R anti-simetris, karena untuk setiap x, y ∈ A, jika x ⊂ y dan y ⊂ x maka x = y. R transitif, karena untuk setiap x, y, z ∈ A, jika x ⊂ y dan y ⊂ z maka x⊂ z. Karena memenuhi ketiga syarat, maka R merupakan relasi urutan parsial pada himpunan A.



Contoh 2 N = Himpunan bilangan asli. Relasi R didefinisikan dengan xRy adalah “x kurang dari atau sama dengan y” atau ditulis . Relasi R merupakan relasi urutan parsial, karena: R refleksif, yaitu untuk ∀ x ∈ N,



.



R anti-simetris, yaitu untuk setiap x, y ∈ N, jika R transitif, yaitu untuk setiap x, y, z ∈ N, jika



Selanjutnya, relasi



dan dan y



maka maka



. .



(kurang dari atau sama dengan) pada himpunan bilangan disebut urutan



natural. Urutan parsial pada suatu himpunan A tidak perlu setiap pasangan elemennya harus berelasi.



Definisi 2. Suatu himpunan A bersama-sama dengan suatu relasi parsial tertentu R di A disebut himpunan terurut parsial. Notasi: (A, R) atau (A, d. Tetapi, d juga mendahului b atau b mendominasi d. Jadi d ≤ b atau b ≥ d. e mendominasi e sendiri, tetapi e tidak secara kuat mendominasi e sendiri. Selanjutnya d dan e merupakan dua elemen yang tidak dapat dibandingkan (tidak comparable).



Jika suatu relasi R di A merupakan relasi refleksif, anti-simetris dan transitif, maka relasi invers



juga refleksif, anti-simentris dan transitif. Dengan kata lain, jika R



mendefinisikan suatu urutan parsial di A, maka parsial di A, yang disebut urutan invers.



juga mendefinisikan suatu urutan



Contoh 7 Dari contoh 3, P = {a, b, c, d, e}. Urutan inversnya



dapat dinyatakan sebagai berikut. Terlihat bahwa



yang disajikan dengan



diagram tersebut merupakan suatu urutan parsial.



C. Urutan Total dan Himpunan Terurut Total Kata "parsial" digunakan dalam mendefinisikan urutan parsial dalam himpunan A karena beberapa elemen dalam A tidak perlu dapat dibandingkan. Dengan kata lain, jika setiap dua elemen dalam himpunan A yang terurut parsial dapat dibandingkan, maka urutan parsial dalam A disebut urutan total. Definisi 3. Suatu urutan parsial



pada himpunan A disebut suatu urutan total atau urutan



linier (total order/linear order), jika ∀



∈



artinya setiap pasangan di A comparable.



Definisi 4. Himpunan A bersama-sama dengan urutan total dalam A, (A,



), disebut



himpunan terurut total.



Contoh 8 Urutan parsial pada himpunan bilangan real dengan urutan natural merupakan urutan total karena setiap



∈



saling comparable.



Contoh 9 Misalkan R adalah suatu urutan parsial di V = {1, 2, 3, 4, 5, 6} dengan definisi “x membagi y”. maka R bukan suatu urutan total di V karena 3 dan 5 tidak comparable.



Contoh 10 Misalkan A dan B adalah himpunan terurut total, maka perkalian Cartesius terurut total sebagai berikut (



)



(



) jika



atau jika



Selanjutnya urutan ini disebut urutan leksikografik dari



dan .



dapat



D. Subset dari Himpunan Terurut Parsial Jika relasi R mendefinisikan suatu urutan parsial pada A, dan B subset pada A, maka urutan parsial R di A akan menginduksi urutan parsial R’ pada B secara alamiah. Urutan parsial R di A menjadi urutan parsial R’ di B dengan cara seperti berikut. Jika



∈ B, (a,b) ∈ R’ maka



berlaku di B j.h.j (



) ∈ R yaitu



juga berlaku di



A. Himpunan terurut (B, R’) disebut himpunan bagian terurut parsial dari himpunan terurut (A,R).



Contoh 11 Misalkan V = {a, b, c, d, e} mempunyai urutan seperti diagram berikut



maka W = {a, d, e} dengan urutan



Tetapi W dengan urutan



adalah subset dari himpunan terurut V.



bukan subset dari himpunan terurut V.



Contoh 12 P = {a, b, c, d, e} terurut parsial seperti berikut.



Misalkan himpunan Q = {a, b, c} dengan urutan parsial seperti berikut. Himpunan Q dengan urutan parsial seperti ini merupakan himpunan bagian dari himpunan terurut P, karena Q ⊂ P dan relasi pada Q juga berlaku pada P.



Misalkan himpunan K = {c, d, e} dengan urutan parsial seperti berikut. Himpunan K = {c, d, e} dengan urutan seperti ini bukan himpunan bagian dari himpunan terurut P meskipun K ⊂ P, karena relasi pada K tidak berlaku pada himpunan terurut P.



E. Subset dari Himpunan Terurut Total Misalkan A himpunan terurut parsial, maka urutan parsial pada A akan menginduksi urutan parsial di setiap subset dari himpunan A, dan beberapa subset dari himpunan A dapat terurut total. Perhatikan bahwa jika A adalah himpunan terurut total, maka setiap subset dari A akan terurut total.



Contoh 13 Misalkan himpunan bilangan asli N terurut oleh “x kelipatan y”. mka N tidak terurut total, karena 4 dan 7 tidak “comparable”. Tetapi himpunan M = {2, 4, 8, …, 2 n, …} merupakan subset terurut total dari himpunan N.



Contoh 14 Misalkan W = {a, b, c, d, e} terurut parsial seperti diagram berikut Himpunan {a, c, d}, {b, d}, {b, c, e}, {a, c, e} dan {a, c} merupakan subset terurut total. Himpunan {a, b, c} dan {d, e} merupakan subset yang tidak terurut total.



F. Elemen Pertama dan Terakhir dari Suatu Himpunan Terurut Parsial Definisi 5. Misalkan A himpunan terurut parsial. a. Elemen



∈



disebut elemen pertama dari A j.h.j ∀ ∈ ,



. Atau



mendahului



setiap elemen di A. b. Elemen



∈



disebut elemen terakhir dari A j.h.j ∀ ∈ ,



setiap elemen di A.



. Atau



mendominasi



Contoh 15 P = {a, b, c, d, e} terurut parsial seperti berikut. Elemen a merupakan elemen terakhir, karena a mendominasi setiap elemen di P. Ingat bahwa a > a atau a mendominasi a sendiri. P dengan urutan tersebut tidak mempunyai elemen pertama, karena tidak ada elemen P yang mendahului setiap elemen di P.



Contoh 16 Pada N = himpunan bilangan asli, dengan urutan natural (kurang dari atau sama dengan), 1 merupakan elemen pertama di N, dan tidak ada elemen terakhirnya.



Contoh 17 A = {x : 0 < x < 1, x ∈



} terurut dengan “x < y”.



A tidak mempunyai elemen pertama dan tidak mempunyai elemen terakhir.



Jika (A, R) himpunan terurut parsial, maka ada kemungkinan A mempunyai elemen pertama atau tidak. Begitu juga ada kemungkinan A mempunyai elemen terakhir atau tidak. Jika A mempunyai elemen pertama, maka paling banyak A mempunyai satu elemen pertama. Begitu juga dengan elemen terakhir. Jika



elemen pertama dan



elemen terakhir dalam A, maka



menjadi elemen terakhir dan



menjadi elemen pertama dalam urutan invers di A.



G. Elemen Minimal dan Maksimal dari Suatu Himpunan Terurut Parsial Definisi 6. Misalkan A himpunan terurut parsial. ∈



a. Suatu elemen



disebut elemen maksimal j.h.j jika



. Dengan kata lain,



( mendahului ) maka



elemen maksimal di A j.h.j tidak ada x ∈



yang murni



mendominasi . b. Suatu elemen ) maka mendahului .



∈



disebut elemen minimal bila dan hanya bila jika



. Dengan kata lain,



( mendahului



elemen minimal di A j.h.j tidak ada x ∈



yang murni



Contoh 18 P = {a, b, c, d, e} dengan urutan seperti berikut. Elemen d dan e merupakan elemen minimal karena tidak ada elemen di A yang murni mendahului d maupun e. Elemen a merupakan elemen maksimal, karena tidak ada elemen di A yang murni mendominasi a.



Contoh 19 B = {1, 2, 3, 4, 5, 6} dengan urutan “x pembagi dari y”. Elemen 1 adalah elemen minimal di B, karena tidak ada elemen di B yang murni mendahului 1. Elemen 4, 5, dan 6 merupakan elemen maksimal, karena tidak ada elemen di B yang murni mendominasi 4, 5, dan 6.



Contoh 20 N = {1, 2, 3, ... } dengan urutan natural (kurang dari atau sama dengan}. 1 adalah elemen pertama yang sekaligus juga merupakan elemen minimal, tetapi tidak ada elemen terakhir maupun elemen maksimal.



Perhatikan bahwa, untuk himpunan terurut parsial A berlaku sifat-sifat seperti berikut. 1. Jika x merupakan elemen pertama, maka x juga merupakan elemen minimal dan x merupakan satu-satunya elemen minimal di A. Begitu juga jika y elemen terakhir, maka y juga elemen maksimal dan merupakan satu-satunya elemen maksimal di A. 2. Jika A finit, maka A paling sedikit mempunyai satu elemen minimal dan paling sedikit mempunyai satu elemen maksimal. Sedangkan jika A infinit, A mungkin tidak mempunyai elemen minimal atau elemen maksimal.



H. Batas Atas dan Batas Bawah Definisi 7. Misalkan B merupakan himpunan bagian dari himpunan terurut parsial A. a. Elemen p ∈ A disebut batas bawah dari B j.h.j ∀ x ∈ B, p < x (p mendahului setiap elemen di B). Jika p batas bawah dan p mendominasi batas bawah dari B yang lain, maka p disebut batas bawah terbesar atau infimum dari B, yang dinotasikan dengan inf (B). b. Elemen q ∈ A disebut batas atas dari B j.h.j ∀ x ∈ B, x < q (q mendominasi setiap elemen di B). Jika q batas atas dan q mendahului batas atas dari B yang lain, maka q disebut batas atas terkecil atau supremum dari B, yang dinotasikan dengan sup (b).



Contoh 21 A = {a, b, c, d, e, f, g} terurut sebagai berikut.



B = {c, d, e} himpunan bagian dari A, terurut seperti pada diagram. Elemen f merupakan batas bawah dari B, karena f mendahului setiap elemen di B. Elemen g bukan batas bawah dari B, karena ada d ∈ B dan g tidak mendahului d. Elemen c merupakan batas atas dari B, karena c mendominasi setiap elemen di B. Begitu juga dengan a dan b, juga merupakan batas atas dari B.



Perhatikan bahwa batas bawah maupun batas atas dari B tidak harus merupakan elemen dari B.



Karena batas bawah dari B hanya f, maka f merupakan batas bawah terbesar dari B, atau infimum dari B atau, inf (B) = f. Batas atas dari B adalah c, a, dan b. Elemen c merupakan batas atas dari B yang mendahului batas atas yang lain (yaitu a dan b). Jadi c merupakan batas atas terkecil dari B, atau supremum dari B atau sup (B) = c.



I. Himpunan yang Similar Definisi 8. Suatu himpunan terurut A dikatakan similar dengan himpunan terurut B yang dinyatakan dengan A ≈ B, j.h.j terdapat fungsi f : A → B yang satu-satu dan onto sehingga untuk sebarang elemen x, y ∈ A, x < y j.h.j f(x) < f(y). Atau, terdapat fungsi f : A → B yang satu-satu dan onto sehingga untuk x, y ∈ A, x murni mendahului y j.h.j f(x) murni mendahului f(y). Selanjutnya, fungsi f disebut mapping similaritas dari A ke B.



Contoh 22 A = {1, 2, 6, 8} terurut dengan “x adalah pembagi dari y”. Diagram dari A adalah:



B = {a, b, c, d} terurut seperti pada diagram berikut.



A ≈ B, karena ada fungsi



: A → B yang didefinisikan dengan diagram berikut



yang merupakan fungsi satu-satu dan onto. Jadi



merupakan mapping similaritas.



Perhatikan bahwa g = {(1, d), (2, c), (6, b), (8, a)} juga merupakan mapping similaritas.



Contoh 23 Diberikan N = {1, 2, 3, ... } dan M = {-1, -2, -3, ... }, keduanya terurut dengan urutan natural “x



y”. N tidak similar dengan M. Karena jika ada mapping similaritas



∈ , jika



maka mengakibatkan



mempunyai elemen pertama maka



( )



tidak akan ada.



( ), ∀ ( ) ∈



: N → M, maka ∀ . Karena M tidak



Contoh 24 Himpunan bilangan asli N = {1, 2, 3, …} similar dengan himpunan bilangan genap E = {2, 4, 6, …}. Karena fungsi



dengan definisi ( )



merupakan mapping similaritas.



J. Latihan 1.



X = { 2, 4, 6, 8, 10}. Relasi R didefinisikan dengan xRy sebagai x faktor dari y. a. Apakah R merupakan urutan parsial? b. Apakah (X, R) merupakan himpunan terurut parsial?



2.



Misalkan N adalah himpunan bilangan asli. Relasi ≥ (lebih besar sama dengan) adalah sebuah relasi pada N. Selidiki apakah (N, ≥) merupakan himpunan terurut parsial (poset). Jika (A, ≥) poset, selidiki apakah (N, ≥) merupakan himpunan terurut total.



3.



Misalkan relasi pada himpunan bilangan asli N yang didefinisikan oleh “x membagi y” merupakan urutan parsial. a. Sisipkan simbol yang tepat,



,



, atau



(tidak comparable) antara setiap pasangan



elemen berikut: (a) 2 … 8



(b) 18 … 24



(c) 9 … 3



(d) 5 … 15



b. Selidiki apakah masing-masing himpunan bagian dari N berikut terurut total atau tidak: (a) {24, 2, 6} (b) {3, 15, 5} (c) {15, 5, 30} (d) {2, 8, 32, 4} (e) {1, 2, 3,…} (f) {7}



4.



Misalkan V = {a, b, c, d, e} terurut menurut diagram berikut.



a. Sisipkan simbol yang tepat, ,



, atau



(tidak comparable) antara setiap pasangan



elemen-elemen berikut: b. a … c



(2) b … c



(3) d … a



(4) c … d



b. Bentuklah sebuah diagram dari elemen-elemen pada V yang mendefinisikan urutan invers.



5.



Suatu relasi pada himpunan bilangan asli N yang didefinisikan oleh “x adalah kelipatan y” adalah sebuah urutan parsial. a. Sisipkanlah simbol yang tepat,



,



, atau



(tidak comparable) di antara setiap



pasangan elemen berikut: (a) 3…..7



(b) 2……8



(c) 6……1



(d) 3 ……33



b. Selidiki apakah masing-masing himpunan bagian dari N berikut terurut total atau tidak:



6.



(a) {8, 2, 24}



(b) {5}



(c) {5, 1, 9}



(d) {2, 4, 8, 24}



(e) {2, 4, 6, 8, …} (f) {15, 3, 9}



Misalkan W = {1, 2, 3, 4, 5, 6} terurut sebagai berikut:



a. Sisipkanlah simbol yang tepat,



,



, atau



(tidak comparable) di antara setiap



pasangan elemen berikut. (a) 1…6



(b) 4 … 5



(c) 5 … 1



(d) 4 … 2



b. Bentuklah sebuah diagram dari elemen-elemen pada W yang mendefinisikan urutan invers. c. Tentukan semua subset terurut total dari W, yang masing-masing memuat paling sedikit tiga elemen. d. Tentukan semua subset terurut total dari W dengan urutan invers, yang masingmasing memuat paling sedikit tiga elemen.



7.



Misalkan A = (N, ≤ ), yakni himpunan bilangan asli dengan urutan natural, misalkan B = (N, ≥), yakni himpunan bilangan asli dengan urutan invers, dan misalkan diurut secara leksikografik. Sisipkanlah simbol yang tepat, comparable) , di antara setiap pasangan elemen dari (a) (1, 3) … (1,5)



8.



(b) (4, 1) … (2, 18)



,



, atau



(tidak



berikut.



(c) (4, 30) … (4, 4)



(d) (2, 2) … (15, 15)



Misalkan D = {1, 2, 3, 4, 6, 9, 12, 18, 36}. Himpunan D terurut parsial dengan relasi “x membagi y”. Gambarkan diagram hassenya.



9.



B = {2, 3, 4, ..., 9, 10} terurut dengan “x pembagi y”. Tentukan elemen minimal, elemen maksimal, elemen pertama, dan elemen terakhir dari B.



10. Perhatikan himpunan D = {1, 2, 3, 4, 5} yang terurut secara linier seperti gambar berikut. Gambarkan diagram untuk urutan invers dalam D.



11. A = {1, 2, 3, 4, 5} terurut seperti diagram berikut. Carilah elemen minimal dan elemen maksimal dari A.



12. K = {1, 2, 3, 4, 5, 6, 7, 8} dan L = {4, 5, 6} merupakan subset dari K terurut seperti pada diagram berikut. a. Carilah batas bawah dan batas atas dari L. b. Carilah infimum dan supremum dari L.



13. M = {1, 2, 3, 4, 5, 6} dan N = {2, 3, 4} merupakan subset dari M terurut seperti berikut. a. Carilah batas atas dan batas bawah dari N. b. Carilah infimum dan supremum dari N.



14. A = {{2, 3}, {2, 5}, {2, 3, 8}, {2, 3, 5, 8}} terurut dengan “x himpunan bagian dari y”.



Tentukan elemen minimal dan maksimal, elemen pertama, dan elemen terakhir dari A. 15. B = {2, 3, 4, ..., 10} terurut dengan “x adalah kelipatan y”. Tentukan elemen minimal, elemen maksimal, elemen pertama, dan elemen terakhir dari B. 16. A = {2, 3, 4, 6, 8} yang terurut dengan “x pembagi dari y”. B = {p, q, r, s, t} dengan urutan seperti berikut. Apakah himpunan A similar dengan himpunan B?



17. Misalkan A={1,2,5,10} adalah himpunan terurut dengan relasi ”faktor dari” dan B={t,u,v,w}juga himpunan terurut dengan diagram sebagai berikut Apakah himpunan A similar dengan himpunan B?



18. C = {2, 4, 6, 8, 10} terurut seperti diagram berikut. Tentukan elemen pertama dan elemen terakhir dari C.



19. R = Himpunan bilangan real, terurut dengan urutan natural P = { ∈ R:



< 4}.



a. Apakah P memiliki batas atas dan batas bawah? Jika ya, tentukan batas atas dan batas bawahnya. b. Apakah sup (P) dan inf (P) ada? Jika ya, tentukan sup (P) dan inf (P). 20. Misalkan M = {2, 3, 4, …} dan misalkan (



)



(



terurut sebagai berikut.



) jika a membagi c dan jika b lebih kecil atau sama dengan d.



a. Tentukan semua elemen minimal.



b. Tentukan semua elemen maksimal



21. K = {p, q, r, s, t, u}, L = {p, q, r} terurut dengan diagram berikut. Tentukan elemen pertama, elemen terakhir, elemen minimal, elemen maksimal, infimum dan supremum dari L.



22. Misalkan B = {a, b, c, d,e, f} diurut sebagai berikut: a. Tentukan elemen minimal dan elemen maksimal dari B. b. Apakah B mempunyai elemen pertama? Jika ya, tentukan elemen pertamanya. c. Apakah B mempunyai elemen terakhir? Jika ya, tentukan elemen terakhirnya. 23. Misalkan X = {2, 3, 6, 12, 24, 36}. Didefinisikan x ≤ y sebagai y habis dibagi x. a. Gambarlah diagram Hasse dari (X, ≤) b. Tentukan batas atas dan supremum dari {2, 3} c. Tentukan batas bawah dan infimum dari {24, 36} 24. Misalkan X = {2, 5, 10, 20, 40, 100}. Didefinisikan x ≤ y sebagai y habis dibagi oleh x. a. Buatlah diagram Hasse untuk (X, ≤) b. Tentukan batas atas dan supremum dari {2, 5} c. Tentukan batas bawah dan infimum dari {40, 100}



25. Tinjaulah Q, yakni himpunan bilanan rasional dengan urutan natural, dan subsetnya A didefinisikan sebagai * | ∈



+



a. Apakah A memiliki batas atas? Jika ya, tentukan batas atasnya. b. Apakah A memiliki batas bawah? Jika ya, tentukan batas bawahnya. c. Apakah sup (A) ada? Jika ya, tentukan sup (A). d. Apakah inf (A) ada? Jika ya, tentukan inf (A).