MATEMATIKA DASAR (Himpunan Terurut Parsial (Poset))

MATEMATIKA DASAR (Himpunan Terurut Parsial (Poset)) Antonius Cahya Prihandoko University of Jember Indonesia Jember, 2015

Antonius Cahya Prihandoko (UNEJ)

MDAS - Poset

Jember, 2015

1 / 26

Outline

1

Himpunan Terurut Parsial

2

Himpunan Terurut Total

3

Himpunan Bagian dari Himpunan Terurut

4

Himpunan Bagian Terurut Total

5

Elemen Awal dan Elemen Akhir


MDAS - Poset

Jember, 2015

2 / 26

Outline

1


2


3


4


5



MDAS - Poset

Jember, 2015

2 / 26

Outline

1


2


3


4


5



MDAS - Poset

Jember, 2015

2 / 26

Outline

1


2


3


4


5



MDAS - Poset

Jember, 2015

2 / 26

Outline

1


2


3


4


5



MDAS - Poset

Jember, 2015

2 / 26



MDAS - Poset

Jember, 2015

3 / 26

Ingat

Urutan parsial atau partial order pada sebuah himpunan A adalah suatu relasi yang bersifat: 1

refleksif

2

antisimetris

3

transitif

Jika relasi R pada A mendefinisikan suatu urutan parsial pada A, maka (a, b) ∈ R dinyatakan dengan a ≤ b (dibaca a mendahului b)


MDAS - Poset

Jember, 2015

4 / 26

Ingat


refleksif

2

antisimetris

3

transitif



MDAS - Poset

Jember, 2015

4 / 26

Ingat


refleksif

2

antisimetris

3

transitif



MDAS - Poset

Jember, 2015

4 / 26

Contoh 1

2

3

Jika A suatu himpunan tak kososng. Relasi ”subset” pada keluarga himpunan 2A merupakan urutan partial pada 2A . Jika K sebarang himpunan bagian dari R, maka relasi ”≤” merupakan urutan parsial pada K . Misal V = {A, B, C, D, E} dan diagram yang berarti x ≤ y jika x = y atau jika seseorang dapat pergi dari x ke y mengikuti arah panah pada diagram berikut:

maka diagram tersebut mendefinisikan suatu urutan parsial pada v. Antonius Cahya Prihandoko (UNEJ)

MDAS - Poset

Jember, 2015

5 / 26

Contoh 1

2

3



MDAS - Poset

Jember, 2015

5 / 26

Contoh 1

2

3



MDAS - Poset

Jember, 2015

5 / 26

Definisi

POSET Suatu himpunan A bersama-sama dengan relasi urutan parsial R tertentu pada A disebut himpunan terurut parsial atau Partially Ordered Set (POSET), yang dinyatakan sebagai (A, R) atau (A, ≤). Perhatikan notasi-notasi berikut: a < b berarti a ≤ b dan a 6= b (dibaca: a murni mendahului atau murni membawahi b) b ≥ a berarti a ≤ b (dibaca: b mengikuti atau mengatasi a) b > a berarti a < b (dibaca: b murni mengikuti atau murni mengatasi a)


MDAS - Poset

Jember, 2015

6 / 26

Definisi



MDAS - Poset

Jember, 2015

6 / 26

Definisi



MDAS - Poset

Jember, 2015

6 / 26

Definisi



MDAS - Poset

Jember, 2015

6 / 26

Komparabel dan Urutan Invers

Dua anggota a dan b dari POSET dikatakan tidak komparabel jika a ≤ b dan b ≤ a, yaitu jika tidak ada elemen yan mendahului elemen lainnya. Jika relasi R pada himpunan A mendefinisikan urutan parsial (refleksif, antisimetris dan transitif) maka relasi invers R −1 juga mendefinisikan urutan parsial di A, dan disebut urutan invers.


MDAS - Poset

Jember, 2015

7 / 26

Komparabel dan Urutan Invers

Dua anggota a dan b dari POSET dikatakan tidak komparabel jika a ≤ b dan b ≤ a, yaitu jika tidak ada elemen yan mendahului elemen lainnya. Jika relasi R pada himpunan A mendefinisikan urutan parsial (refleksif, antisimetris dan transitif) maka relasi invers R −1 juga mendefinisikan urutan parsial di A, dan disebut urutan invers.


MDAS - Poset

Jember, 2015

7 / 26



MDAS - Poset

Jember, 2015

8 / 26

Definisi

Urutan total pada himpunan A adalah urutan parsial di A dengan tambahan sifat trikotomi sebagai berikut: a < b,

a = b,

atau a > b

untuk setiap anggota a, b ∈ A. Himpunan A bersama-sama dengan urutan total tertentu di A disebut himpunan terurut total atau totally ordered set (TOSET)


MDAS - Poset

Jember, 2015

9 / 26

Contoh

Misal R himpunan bilangan riil (dengan urutan asal), maka setiap dua elemen dalam R selalu komparabel, maka urutan parsial pada R merupakan urutan total. Misal M = {1, 2, 3, 4, 5} dan didefinisikan relasi R sebagai ”kelipatan dari”, maka R merupakan urutan parsial, tetapi bukan urutan total, sebab 3 bukan kelipatan 2, 5 bukan kelipatan 3.


MDAS - Poset

Jember, 2015

10 / 26

Contoh

Misal R himpunan bilangan riil (dengan urutan asal), maka setiap dua elemen dalam R selalu komparabel, maka urutan parsial pada R merupakan urutan total. Misal M = {1, 2, 3, 4, 5} dan didefinisikan relasi R sebagai ”kelipatan dari”, maka R merupakan urutan parsial, tetapi bukan urutan total, sebab 3 bukan kelipatan 2, 5 bukan kelipatan 3.


MDAS - Poset

Jember, 2015

10 / 26



MDAS - Poset

Jember, 2015

11 / 26

Definisi

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 0 pada B secara alamiah: Untuk a, b ∈ B, (a, b) ∈ R 0 atau a ≤ b berlaku di B jika hanya jika (a, b) ∈ R atau a ≤ b juga berlaku di A. Himpunan terurut (B, R 0 ) disebut himpunan bagian (urutan parsial) dari himpunan terurut (A, R).


MDAS - Poset

Jember, 2015

12 / 26

Definisi

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 0 pada B secara alamiah: Untuk a, b ∈ B, (a, b) ∈ R 0 atau a ≤ b berlaku di B jika hanya jika (a, b) ∈ R atau a ≤ b juga berlaku di A. Himpunan terurut (B, R 0 ) disebut himpunan bagian (urutan parsial) dari himpunan terurut (A, R).


MDAS - Poset

Jember, 2015

12 / 26

Contoh

Jika V = {A, B, C, D, E} mempunyai urutan seperti diagram berikut:

Tentukan subset-subset dari V .


MDAS - Poset

Jember, 2015

13 / 26



MDAS - Poset

Jember, 2015

14 / 26

Totally Ordered Subset Misal A himpunan terurut parsial, maka urutan parsial pada A akan menginduksi urutan parsial pada subset-subsetnya, dan beberapa subset dapat memiliki urutan total.

Subset-subset {b, a, c}, {e, a, c}, dan {e, d, c} merupakan himpunan bagian terurut total. Subset-subset {b, a, e}, {a, c, d}, dan {a, e, d} bukan merupakan himpunan bagian terurut total. Antonius Cahya Prihandoko (UNEJ)

MDAS - Poset

Jember, 2015

15 / 26

Totally Ordered Subset Misal A himpunan terurut parsial, maka urutan parsial pada A akan menginduksi urutan parsial pada subset-subsetnya, dan beberapa subset dapat memiliki urutan total.

Subset-subset {b, a, c}, {e, a, c}, dan {e, d, c} merupakan himpunan bagian terurut total. Subset-subset {b, a, e}, {a, c, d}, dan {a, e, d} bukan merupakan himpunan bagian terurut total. Antonius Cahya Prihandoko (UNEJ)

MDAS - Poset

Jember, 2015

15 / 26



MDAS - Poset

Jember, 2015

16 / 26


Misal A adalah himpunan terurut. Elemen a ∈ A disebut elemen awal dari A jika dan hanya jika a mendahului setiap elemen dari A. Elemen b ∈ A disebut elemen akhir dari A jika dan hanya jika b mengatasi setiap elemen dari A.


MDAS - Poset

Jember, 2015

17 / 26


Misal A adalah himpunan terurut. Elemen a ∈ A disebut elemen awal dari A jika dan hanya jika a mendahului setiap elemen dari A. Elemen b ∈ A disebut elemen akhir dari A jika dan hanya jika b mengatasi setiap elemen dari A.


MDAS - Poset

Jember, 2015

17 / 26

Contoh Pada himpunan terurut berikut:

tidak memiliki elemen awal, tetapi memiliki elemen akhir yaitu c. Himpunan bilangan asli memiliki elemen awal, yakni 1, tetapi tidak memiliki elemen akhir. Jika R merupakan relasi ”subset” pada himpunan 2A , maka (2A , R) merupakan POSET dan bukan TOSET. Elemen awal dari 2A adalah π dan elemen akhirnya adalah A. Jika W = {x ∈ R|0 < x < 1} dan relasi R didefinisikan sebagai ”≤”, maka (W , R) merupakan TOSET, tetapi W tidak memiliki elemen awal dan elemen akhir. Mengapa? Antonius Cahya Prihandoko (UNEJ)

MDAS - Poset

Jember, 2015

18 / 26



MDAS - Poset

Jember, 2015

18 / 26



MDAS - Poset

Jember, 2015

18 / 26



MDAS - Poset

Jember, 2015

18 / 26

Elemen Maksi dan Elemen Mini

Misal A merupakan suatu himpunan terurut. Suatu elemen a ∈ A disebut elemen maksi jika tidak ada elemen A yang murni mengikuti a. Suatu elemen b ∈ A disebut elemen mini jika tidak ada elemen A yang murni mendahului b.


MDAS - Poset

Jember, 2015

19 / 26

Elemen Maksi dan Elemen Mini

Misal A merupakan suatu himpunan terurut. Suatu elemen a ∈ A disebut elemen maksi jika tidak ada elemen A yang murni mengikuti a. Suatu elemen b ∈ A disebut elemen mini jika tidak ada elemen A yang murni mendahului b.


MDAS - Poset

Jember, 2015

19 / 26


Elemen maksi adalah c dan elemen mini adalah b dan e. Jika W = {x ∈ R|0 < x < 1} dan relasi R didefinisikan sebagai ”≤”, maka (W , R) merupakan TOSET, tetapi W tidak memiliki baik elemen maksi maupun elemen mini.


MDAS - Poset

Jember, 2015

20 / 26


Elemen maksi adalah c dan elemen mini adalah b dan e. Jika W = {x ∈ R|0 < x < 1} dan relasi R didefinisikan sebagai ”≤”, maka (W , R) merupakan TOSET, tetapi W tidak memiliki baik elemen maksi maupun elemen mini.


MDAS - Poset

Jember, 2015

20 / 26

Batas Atas dan Batas Bawah

Misal B adalah subset dari suatu himpunan terurut parsial A. Suatu elemen b ∈ A disebut batas bawah dari B jika untuk setiap x ∈ B, b ≤ x, yaitu b membawahi setiap elemen B. Jika suatu batas bawah dari B mengatasi setiap batas bawah yang lain dari B, maka batas bawah itu disebut batas bawah terbesar atau infrimum dari B dan dinotasikan dengan inf (B). Suatu elemen a ∈ A disebut batas atas dari B jika untuk setiap x ∈ B, x ≤ a, yaitu a mengatasi setiap elemen B. Jika suatu batas atas dari B mengatasi setiap batas atas yang lain dari B, maka batas atas itu disebut batas atas terkecil atau suprimum dari B dan dinotasikan dengan sup(B).


MDAS - Poset

Jember, 2015

21 / 26




MDAS - Poset

Jember, 2015

21 / 26




MDAS - Poset

Jember, 2015

21 / 26




MDAS - Poset

Jember, 2015

21 / 26

Contoh Misal V = {a, b, c, d, e, f , g} merupakan himpunan terurut dengan diagram:

Jika W = {b, c, e} maka 1

batas atas dari W adalah c, a dan d.

2

batas atas terkecil (sup(W )) = c

3

batas bawah dari W adalah g

4

batas bawah terbesar dari W (inf (W )) = g.


MDAS - Poset

Jember, 2015

22 / 26




2


3


4



MDAS - Poset

Jember, 2015

22 / 26




2


3


4



MDAS - Poset

Jember, 2015

22 / 26




2


3


4



MDAS - Poset

Jember, 2015

22 / 26

Himpunan yang Similar

Suatu himpunan terurut A dikatakan similar dengan himpunan terurut B dan dinyatakan A = B jika dan hanya jika ada fungsi f : A ⇒ B yang satu-satu dan onto, serta untuk setiap a1 , a2 ∈ A berlaku a1 < a2 ⇔ f (a) < f (b) Pemetaan f disebut pemetaan similar dari A ke B.


MDAS - Poset

Jember, 2015

23 / 26

Contoh Misal 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:

maka A dan B merupakan dua himpunan yang similar karena terdapat fungsi f : A ⇒ B dimana f = {(1, v ), (2, u), (5, w), (10, t)}


MDAS - Poset

Jember, 2015

24 / 26

Contoh

Diketahui A = {1, 2, 3, ...} dan N = {−1, −2, −3, ...} merupakan himpunan terurut dengan urutan alamiah ”x ≤ y ”. Kita perhatikan bahwa 1 ≤ 2 tetapi −1 ≥ −2 dan tidak ada elemen awal dari N, sehingga tidak terdapat fungsi similar f . Jadi A tidak similar dengan N. Bagaimana jika A0 adalah himpunan dari 10 elemen pertama A dan N 0 adalah himpunan dari 10 elemen pertama N?


MDAS - Poset

Jember, 2015

25 / 26

Terima kasih

Selamat belajar dan sukses


MDAS - Poset

Jember, 2015

26 / 26

MATEMATIKA DASAR (Himpunan Terurut Parsial (Poset))

Recommend Documents