hipotesis kontinuum
Post on 12-Jan-2017
222 Views
Preview:
TRANSCRIPT
HIPOTESIS KONTINUUM
SKRIPSI
Diajukan untuk Memenuhi Salah Satu Syarat
Memperoleh Gelar Sarjana Sains Program Studi Matematika
Oleh:
R. Pudji Tursana
NIM: 943114004 NIRM: 940051122808120004
PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SANATA DHARMA YOGYAKARTA
2002
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
ii
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
iii
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
“ ... dipersembahkan untuk para pengungsi yang
terlupakan, yang hingga saat ini masih di
tanah asing, dan mengenali kata “rumah”, sebagai sebuah mimpi, cita-
cita, dan harapan.... “
iv
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Pernyataan Keaslian Karya
Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini
tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan
dalam Daftar Pustaka, sebagaimana layaknya karya ilmiah.
Yogyakarta, 1 April 2002
Penulis
R. Pudji Tursana
v
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
vi
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
vii
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
ABSTRAK Himpunan A dikatakan mempunyai kardinalitas (bilangan kardinal) yang sama dengan himpunan B, yaitu ⏐A⏐ = ⏐B⏐, jika A berkorespondensi satu-satu dengan B. Kardinalitas himpunan hingga adalah banyaknya elemen dalam himpunan tersebut. Kardinalitas himpunan takhingga didasarkan pada sifat tercacah atau taktercacahnya himpunan tersebut. Pada himpunan tercacah B, ⏐B⏐ = ⏐R⏐ = c. Kardinalitas himpunan taktercacah disebut kardinalitas kontinuum. Suatu hubungan antara c dan ℵ 0 adalah c = 2 . Timbul suatu dugaan bahwa tidak ada bilangan kardinal x sedemikian hingga ℵ < x < c. Dugaan ini pertama kali dicetuskan oleh George Cantor dan kemudian diberi nama Hipotesis Kontinuum. Hipotesis Kontinuum Umum menyatakan bahwa ℵ = 2 , yaitu selalu dapat ditemukan bilangan kardinal yang lebih besar dari bilangan kardinal yang diberikan.
0ℵ
0
1+n0ℵ
viii
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
ABSTRACT
Two sets A and B are said to have the same cardinality (cardinal number), which is written ⏐A⏐ = ⏐B⏐, if there exists a one-to-one correspondence between A and B. Cardinality of a finite set is the number of elements of the set. Cardinality of an infinite set is depending on the denumerable or non-denumerable property of the set. A denumerable set B has ⏐B⏐ = ⏐R⏐ = c. The cardinality of a non-denumerable set is called continuum cardinality. The relation between c and ℵ is c = 2 . There is a conjecture that there is no cardinal x such that ℵ < x < c. George Cantor is the first person who proposed the conjecture which is later called Continuum Hypothesis. The Generalized Continuum Hypothesis notes that ℵ = 2 , i.e. there is always a greater cardinal number than a given one.
0
0ℵ0
1+n0ℵ
ix
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
KATA PENGANTAR
Saya mengucapkan syukur yang sebesar-besarnya kepada Tuhan Yang
Maha Rahim untuk segala keajaiban yang diberikan kepada saya dalam usaha
menyelesaikan skripsi ini. Topik yang saya pilih untuk skripsi ini pun tidak
terlepas dari campur tangan dan persetujuanNya.
Tujuan saya menulis skripsi ini selain untuk memenuhi salah satu syarat
memperoleh gelar akademis, adalah untuk belajar bagaiamana menulis ilmiah
dengan baik dan benar.
Saya juga bersyukur untuk setiap orang yang dikirimNya kepada saya
sebagai orang tua, guru, saudara, sahabat, teman seperjalanan, dan teman sekerja.
Penghargaan dan rasa terima kasih yang sangat besar saya berikan kepada mereka.
1. Papa Mama Boni Tatang yang telah menghadirkan saya ke dunia ini
dengan segala talenta yang saya miliki sampai saat ini.
2. Bapak Drs. Y. Eka Priyatma, M. Sc. sebagai Dekan Fakultas MIPA.
3. Romo Dr. F. Susilo, SJ sebagai Dosen Wali dan Dosen Pembimbing
Skripsi yang telah membimbing penulisan skripsi ini dengan sabar.
4. Ibu M. V. Ani Herawati, M. Si. sebagai Dosen Pembimbing Skripsi
yang telah membimbing penulisan skripsi ini dalam proses
penyelesaian dengan sabar.
5. Ibu Dra. Maria Agustiani, M.Si. yang telah bertindak sebagai Guru,
Ibu, dan Sahabat, yang menemani saya dalam saat-saat sulit.
x
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
6. Ibu P. H. Prima Rosa, M. Sc. yang telah meletakkan dasar keteguhan
hati bagi saya sebagai pembelajar pada masa awal perkuliahan saya.
7. Bapak Ir. Ign. Aris Dwiatmaka, M. Sc. yang telah bertindak sebagai
Guru, pemberi energi positif, dan Sahabat yang selalu memberi
semangat.
8. Bapak Prof. R. Soemantri yang dengan sangat sabar membantu
kelancaran kuliah saya.
9. Hongky Julie yang telah membantu saya dalam proses belajar
menjelang ujian dengan rendah hati dan sabar.
10. Sr. Benedict, CB sebagai Ibu dan Sahabat yang telah menunggu
dengan sabar proses pendidikan saya.
11. Komunitas FCJ yang telah menemani saya dalam suka duka
pengenalan diri.
12. Komunitas Syantikara dan PSP Pingit sebagai tempat saya belajar
tentang hidup dan menjadi dewasa.
13. Para sahabat: Ike, Ika, Dian, Eva, Bulan, Sekar, Sukma, dan Fajar yang
telah menemani saya dalam suka dan duka dan selalu memberikan
energi positif .
14. Tia untuk selalu menjadi adik yang baik dan sabar dalam suka dan
duka.
15. Ari yang selalu menjadi semangat, menemani, dan menerima setiap
perubahan saya.
xi
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
16. Agus Supriyadi yang menjadi teman “Emausan” dan membantu saya
kembali kepada rantai komitmen yang lebih tepat.
17. Komunitas Jesuit Refugee Service (JRS) Indonesia yang telah memberi
kesempatan dan ruang bagi saya untuk belajar lebih dalam tentang
hidup dan sejarah manusia.
18. Staff dan karyawan kesekretariatan MIPA dan Perpustakaan
Universitas Sanata Dharma, yang telah memberi bantuan peminjaman
pustaka dalam suasana yang bersahabat.
19. Semua saja yang telah membantu saya dalam proses pendidikan saya.
Saya menyadari sepenuhnya bahwa skripsi ini masih belum sempurna.
Untuk itu kritik dan saran yang membangun saya harapkan demi perbaikan skripsi
ini. Harapan saya, skripsi ini dapat memberi manfaat khususnya bagi para
pemerhati matematika.
Penulis
xii
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
DAFTAR ISI
HALAMAN JUDUL................................................................................................ i
HALAMAN PERSETUJUAN PEMBIMBING ..................................................... ii
HALAMAN PENGESAHAN................................................................................ iii
HALAMAN PERSEMBAHAN ............................................................................ iv
PERNYATAAN KEASLIAN KARYA ..................................................................v
HAK CIPTA .......................................................................................................... vi
ABSTRAK ............................................................................................................ vii
ABSTRACT......................................................................................................... viii
KATA PENGANTAR ........................................................................................... ix
DAFTAR ISI......................................................................................................... xii
BAB I. PENDAHULUAN.......................................................................................1
1. Latar Belakang .............................................................................................1
2. Rumusan Masalah ........................................................................................2
3. Tujuan Penulisan..........................................................................................2
4. Manfaat Penulisan........................................................................................2
5. Metode Penulisan.........................................................................................2
BAB II. HIMPUNAN, RELASI DAN FUNGSI .....................................................3
1. Konsep Dasar Teori Himpunan....................................................................3
2. Produk Kartesius, Relasi, dan Fungsi ........................................................10
3. Sistem Aljabar dan Homomorfisma...........................................................27
BAB III. HIMPUNAN TERCACAH ....................................................................31
1. Himpunan Hingga dan Himpunan Takhingga ...........................................31
xiii
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
2. Himpunan Tercacah dan Himpunan Terbilang ..........................................32
3. Himpunan Kuasa........................................................................................48
BAB IV. HIPOTESIS KONTINUUM...................................................................57
1. Bilangan Kardinal ......................................................................................57
2. Hipotesis Kontinuum .................................................................................62
BAB V. PENUTUP................................................................................................65
DAFTAR PUSTAKA ............................................................................................67
xiv
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
BAB I
PENDAHULUAN
1. Latar Belakang
Himpunan adalah kumpulan obyek-obyek yang berbeda. Himpunan kuasa
dari himpunan A adalah himpunan semua himpunan bagian dari A, dan ditulis
℘[A]. Selanjutnya, dapat dibentuk himpunan kuasa dari ℘[A], himpunan kuasa
dari ℘[℘[A]], ....
Pada himpunan hingga, jumlah elemen dari ℘[A] hingga dan pada
himpunan takhingga jumlah elemen dari ℘[A] takhingga. Bilangan kardinal dari
himpunan hingga A menyatakan jumlah elemen A. Secara umum bilangan
kardinal dari himpunan A sebarang adalah sama dengan bilangan kardinal dari
himpunan yang berkorespondensi satu-satu dengannya. Bilangan kardinal dari
℘[A] selalu lebih besar dari bilangan kardinal A.
Jika diberikan N = {1,2,3,4,5,....}, maka bilangan kardinal dari ℘[N] sama
dengan bilangan kardinal dari himpunan semua bilangan real atau semua titik
pada sebuah garis lurus. Oleh karena itu ℘[N] disebut bilangan kardinal dari dari
kontinuum.
Hipotesis kontinuum mengatakan bahwa tidak ada bilangan kardinal x
sedemikian hingga ⏐N⏐ < x < ⏐R⏐. Dalam skripsi pembahasan hipotesis
kontinumm dibatasi hanya sampai pada proses pemunculan ide hipotesis
kontinuum tersebut.
1
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
2. Rumusan Masalah
Pokok permasalahan yang akan dibahas dalam tulisan ini dirumuskan
sebagai berikut:
- Apakah yang dimaksud dengan hipotesis kontinuum?
- Bagaimana proses terjadinya (munculnya) hipotesis kontinuum?
- Bagaimana keberadaan hipotesis kontinuum sampai saat ini?
3. Tujuan Penulisan
Tujuan penulisan skripsi ini adalah untuk memahami bagaimana proses
terjadinya suatu hipotesis, yang dalam hal ini adalah hipotesis kontinuum, dan
untuk memahami konsep teori himpunan dan himpunan tercacah lebih mendalam.
4. Manfaat Penulisan
Dengan mempelajari proses terjadinya hipotesis kontinuum lalu
menuliskannya diperoleh manfaat sebagai berikut:
- Penulis semakin memahami konsep teori himpunan dan himpunan
tercacah.
- Penulis menjadi paham dengan proses bagaimana sebuah hipotesis terjadi.
- Penulis menjadi paham bagaimana menulis suatu tulisan ilmiah.
5. Metode Penulisan
Untuk menulis skripsi ini digunakan metode studi pustaka, yaitu
mempelajari materi-materi terkait yang terdapat pada beberapa buku acuan.
2
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
BAB II
HIMPUNAN, RELASI, DAN FUNGSI
Pada Bab II ini dibahas materi dasar teori himpunan. Pembahasan dimulai
dari konsep-konsep dasar teori himpunan dan operasi-operasinya. Lalu ditinjau
Produk Kartesius, relasi, dan fungsi, dan akhirnya sistem aljabar dan
homomorfisma.
1. Konsep Dasar Teori Himpunan
Sekotak kapur, sekaleng permen, dan sekeranjang buah-buahan adalah
contoh himpunan. Pada matematika suatu himpunan didefinisikan dengan
menyatakan syarat keanggotaannya. Anggota suatu himpunan disebut unsur atau
elemen. Terdapat beberapa cara untuk mendefinisikan suatu himpunan:
1. Dengan menuliskan anggota-anggotanya. Contoh: A = {1,2,3,4}.
2. Dengan menggunakan notasi pembentuk himpunan. Contoh: A = {x ⏐1 ≤ x
≤ 4}.
3. Dengan menggunakan ungkapan deskriptif verbal. Contoh: A = {bilangan
asli dari satu sampai empat}.
Untuk menyatakan keanggotaan suatu himpunan digunakan notasi ∈, sedangkan
notasi ∉ digunakan untuk menyatakan bahwa suatu obyek bukan elemen suatu
himpunan.
3
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Selain hubungan keanggotaan di atas, ada prinsip mendasar lain yaitu
prinsip kesamaan dua himpunan. Jika himpunan A sama dengan himpunan B
ditulis A = B. Jika tidak sama ditulis A ≠ B. Jika A = B maka setiap elemen dari A
adalah elemen dari B dan sebaliknya. Demikian pula jika himpunan A dan
himpunan B memiliki elemen yang sama maka A = B.
Prinsip ini dirumuskan dalam sebuah definisi sebagai berikut:
Definisi 2.1.1: Aksioma Perluasan
A = B bila dan hanya bila (∀x) [x ∈ A ⇔ x ∈ B]
Perlu diketahui pula bahwa suatu himpunan dapat menjadi himpunan bagian dari
himpunan lain.
Definisi 2.1.2: Himpunan A disebut himpunan bagian dari himpunan B, ditulis
A ⊆ B, bila dan hanya bila setiap anggota A adalah anggota B.
A ⊆ B ⇔ (∀x) [x ∈ A ⇒ x ∈ B]
Dari definisi tersebut diperoleh beberapa sifat, yaitu :
Teorema 2.1.1: Jika A, B, dan C adalah himpunan-himpunan, maka
1. (∀A) [A ⊆ A ] (Refleksif)
2. (∀A,B) [ A ⊆ B dan B ⊆ A ⇔ A = B ] (Antisimetris)
3. (∀A,B,C) [ A ⊆ B dan B ⊆ C ⇒ A = C ] (Transitif)
4
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Bukti:
1. Akan dibuktikan: (∀A) [A ⊆ A].
Andaikan A ⊄ A, maka ada paling sedikit satu x ∈ A dan x ∉ A. Terjadi
kontradiksi, maka pengandaian salah, sehingga benar bahwa (∀A) [A ⊆ A].
Jadi terbukti bahwa A ⊆ A.
2. Akan dibuktikan: (∀A,B) [A ⊆ B dan B ⊆ A ⇔ A = B]
Untuk setiap himpunan A dan B berlaku A ⊆ B dan B ⊆ A bila dan hanya
bila (∀x) [x ∈ A ⇒ x ∈ B] dan (∀x) [x ∈ B ⇒ x ∈ A] bila dan hanya bila
(∀x) [x ∈ A ⇔ x ∈ B] bila dan hanya bila A = B.
Jadi terbukti bahwa A ⊆ B dan B ⊆ A ⇔ A = B.
3. Akan dibuktikan: (∀A,B,C) [A ⊆ B dan B ⊆ C ⇒ A = C]
Diketahui A ⊆ B dan B ⊆ C. Ambil sebarang x ∈ A, maka x ∈ B. Karena
diketahui bahwa B ⊆ C dan x ∈ B, maka x ∈ C, sehingga x ∈ A ⇒ x ∈ C.
Jadi benar bahwa A = C.
Jadi terbukti bahwa A ⊆ B dan B ⊆ C ⇒ A = C
Definisi 2.1.3: Himpunan A disebut himpunan bagian sejati dari himpunan B,
ditulis A ⊂ B, bila dan hanya bila A ⊆ B dan A ≠ B.
5
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Pada umumnya himpunan didefinisikan dengan menyatakan sifatnya.
Misalkan Φ adalah suatu sifat obyek-obyek. Prinsip himpunan mengatakan
bahwa:
I. Ada paling sedikit satu himpunan yang elemen-elemennya adalah obyek-obyek
dengan sifat Φ.
Andaikan ada dua himpunan yang elemen-elemennya adalah sebarang obyek-
obyek dengan sifat Φ, maka kedua himpunan tersebut mempunyai elemen-elemen
yang sama, sehingga dengan aksioma perluasan mereka adalah sama. Jadi
II. Ada paling banyak satu himpunan yang elemen-elemennya adalah obyek-
obyek dengan sifat Φ.
Dengan menggabungkan I dan II: Ada tepat satu himpunan yang elemen-
elemennya adalah obyek-obyek dengan sifat Φ, dilambangkan dengan { x⏐Φ (x) }
dengan Φ (x) berarti “ x mempunyai sifat Φ ”.
Jadi jika Φ suatu sifat, maka:
( i ) { x⏐Φ (x) } adalah sebuah himpunan, dan
( ii ) (∀y) [ y ∈ { x⏐Φ (x) } ⇔ Φ (y) ]
Andaikan A = { x⏐Φ (x) } dan B = { x ⏐Ψ (x) }, maka berlaku:
A = B ⇔ ∀ x [ Φ (x) ⇔ Ψ (x) ]
6
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
A ⊆ B ⇔ ∀ x [ Φ (x) ⇒ Ψ (x) ]
Andaikan Φ (x) adalah x ≠ x sedemikian hingga dapat dibentuk suatu
himpunan {x⏐x ≠ x}. Himpunan ini tidak mempunyai elemen sebab tidak ada
himpunan yang elemennya tidak sama dengan elemen itu sendiri. Jadi ada tepat
satu himpunan yang tidak mempunyai elemen yang disebut himpunan kosong dan
dilambangkan dengan φ.
Teorema 2.1.2: Himpunan kosong adalah himpunan bagian dari sebarang
himpunan yaitu (∀A) [φ ⊆ A].
Bukti:
Diberikan himpunan A. Andaikan φ ⊄ A, maka ada elemen dalam φ tetapi
tidak dalam A. Padahal φ tidak mempunyai elemen, sehingga terjadi
kontradiksi. Pengandaian salah, sehingga φ ⊆ A.
Jadi terbukti ∀ A [ φ ⊆ A ].
Diberikan himpunan A dan himpunan B, maka gabungan dari himpunan A
dan himpunan B, ditulis A ∪ B, didefinisikan sebagai himpunan yang elemen-
elemennya terdiri dari elemen-elemen himpunan A atau himpunan B. Dengan kata
lain:
A ∪ B = { x ⏐ x ∈ A ∨ x ∈ B }
7
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Sedangkan irisan dari himpunan A dan himpunan B, ditulis A ∩ B, didefinisikan
sebagai himpunan yang elemen-elemennya terdiri dari elemen-elemen himpunan
A dan himpunan B. Dengan kata lain:
A ∩ B = { x ⏐ x ∈ A ∧ x ∈ B }
Sifat-sifat yang berlaku pada operasi gabungan dan irisan himpunan adalah
sebagai berikut:
1. A ∪ φ = A ; A ∩ φ = φ
2. A ∪ B = B ∪ A ; A ∩ B = B ∩ A (Komutatif)
3. (A ∪ B) ∪ C = A ∪ (B ∪ C) ; (A ∩ B) ∩ C = A ∩ (B ∩ C) (Asosiatif)
4. A ∪ A = A ; A ∩ A = A (Idempotan)
5. A ⊆ B bila dan hanya bila A ∪ B = B bila dan hanya bila A ∩ B = A.
6. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ; A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
(Distributif)
Jika A ∩ B = φ maka dikatakan bahwa himpunan A dan himpunan B saling asing.
Selisih antara himpunan A dengan himpunan B, ditulis A – B, didefinisikan
sebagai berikut:
Definisi 2.1.4: A – B = {x⏐x ∈ A ∧ x ∉ B}
8
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Selisih antara himpunan semesta pembicaraan S dengan himpunan A, ditulis A ,
disebut
c
komplemen dari A, didefinisikan sebagai berikut:
Definisi 2.1.5: A c = S – A = { x ⏐ x ∈ S ∧ x ∉ A } = { x ⏐ x ∉ A }
Sifat-sifat yang berlaku pada operasi komplemen adalah:
1. (A ) = A c c
2. a. φ = S ; S = φ c c
b. A ∩ A = φ ; A ∪ A c = S di mana S adalah himpunan semesta. c
3. A ⊆ B bila dan hanya bila B ⊆ A c c
4. (A ∪ B) = A c ∩ B ; (A ∩ B) c = A c ∪ B (Hukum De Morgan) c c c
Keluarga himpunan adalah himpunan yang elemen-elemennya adalah
himpunan-himpunan. Digunakan himpunan indeks I = {1,2,3,..., n} untuk
menunjukkan setiap elemennya. Misalkan A 1 , A , A 3 , ..., A adalah himpunan-
himpunan terindeks dengan I = {1,2,3,...,n} adalah himpunan indeks. Gabungan
dan irisan dari himpunan-himpunan ini didefinisikan sebagai berikut:
2 n
Definisi 2.1.6: Diberikan keluarga himpunan A = { A 1 , A , A 3 , ..., A }, dengan 2 n
A 1 , A , A , ..., A masing-masing adalah himpunan, maka: 2 3 n
1. A i = { x ⏐(∃ i ∈ I) x ∈ A i } I = {1,2,3,...,n} n
i 1=U
9
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
2. A i = { x ⏐(∀ i ∈ I) x ∈ A i } I = {1,2,3,...,n} n
i 1=I
2. Produk Kartesius, Relasi, dan Fungsi
Produk Kartesius A B× dari himpunan A dan himpunan B didefinisikan
sebagai himpunan semua pasangan terurut (a,b) dengan a ∈ A dan b ∈ B.
Definisi 2.2.1: BA× = { (a,b) ⏐ a ∈ A ∧ b ∈ B }
Teorema 2.2.1: Produk Kartesius bersifat distributif terhadap operasi gabungan
dan irisan:
)()()( CABACBA ×∪×=∪×
)()()( CABACBA ×∩×=∩×
Bukti:
1. Akan ditunjukkan: )()()( CABACBA ×∪×=∪×
(⇒) Ambil sebarang (a,b) ∈ )( CBA ∪× , maka a ∈ A dan b ∈ (B ∪ C).
Karena b ∈ (B ∪ C), maka b ∈ B atau b ∈ C. Jika b ∈ B, maka
a ∈ A dan b ∈ B, sehingga (a,b) ∈ )( BA× . Jika b ∈ C, maka
a ∈ A dan b ∈ C, sehingga (a,b) ∈ )( CA× . Jadi (a,b) ∈
atau (a,b) ∈
)( BA×
)( CA× , sehingga (a,b) ∈ [ )( BA× ∪ ]. )( CA×
Jadi ⊆ )( CBA ∪× )( BA× ∪ )( CA× .... (1)
10
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
(⇐) Ambil sebarang (a,b) ∈ )( BA× ∪ )( CA× , maka (a,b) ∈
atau (a,b) ∈
)( BA×
)( CA× , sehingga (a ∈ A dan b ∈ B) atau (a ∈ A dan
b ∈ C). Oleh karena itu a ∈ A dan (b ∈ B atau b ∈ C), sehingga
a ∈ A dan b ∈ (B ∪ C). Berdasarkan Definisi 2.2.1, maka
(a,b) ∈ . )( CBA ∪×
Jadi ∪ )( BA× )( CA× ⊆ )( CBA ∪× . .... (2)
Dari (1) dan (2) terbukti: )( CBA ∪× = )( BA× ∪ . )( CA×
2. Akan ditunjukkan: )()()( CABACBA ×∩×=∩×
(⇒) Ambil sebarang (a,b) ∈ )( CBA ∩× , maka a ∈ A dan b ∈ (B ∩ C).
Karena b ∈ (B ∩ C), maka b ∈ B dan b ∈ C, sehingga a ∈ A dan
b ∈ B. Oleh karena itu (a,b) ∈ )( BA× , dan a ∈ A dan b ∈ C,
sehingga (a,b) ∈ )( CA× , maka (a,b) ∈ )( BA× dan (a,b) ∈
, sehingga (a,b) ∈ )( CA× ( BA )× ∩ ( )CA× .
Jadi ⊆ )( CBA ∩× )( BA× ∩ )( CA× . .....(1)
(⇐) Ambil sebarang (a,b) ∈ )( BA× ∩ )( CA× , maka (a,b) ∈
dan (a,b) ∈
)( BA×
)( CA× , sehingga (a ∈ A dan b ∈ B) dan (a ∈ A dan b
∈C). Oleh karena itu a ∈ A dan (b ∈ B dan b ∈C), sehingga a ∈ A
11
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
dan b ∈ (B ∩ C). Berdasarkan Definisi 2.2.1, maka (a,b) ∈
. Jadi )( CBA ∩× )( BA× ∩ )( CA× ⊆ )( CBA ∩× ....(2)
Dari (1) dan (2) terbukti: )()()( CABACBA ×∩×=∩×
Kesamaan pasangan terurut didefinisikan sebagai berikut:
Definisi 2.2.2: (a,b) = (c,d) bila dan hanya bila a = c dan b = d.
Jika diberikan himpunan X dan himpunan Y, maka relasi biner R antara elemen-
elemen himpunan X dan elemen-elemen himpunan Y adalah suatu himpunan
bagian dari Y× . X
Definisi 2.2.3: R adalah relasi biner antara elemen-elemen X dan elemen-elemen Y
bila dan hanya bila R ⊆ Y× . X
Kalimat (x,y) ∈ R seringkali ditulis dengan notasi xRy atau R(x,y) dan dibaca x
berelasi dengan y.
Relasi biner pada himpunan X adalah himpunan bagian dari XX × .
Definisi 2.2.4: Untuk R ⊆ YX × didefinisikan:
Dom R = { x ∈ X ⏐(∃ y ∈ Y) xRy} (domain / daerah asal dari R)
Ran R = { y ∈ Y ⏐ (∃ x ∈ X) xRy} (range / daerah hasil dari R)
Andaikan R adalah relasi pada himpunan H, maka:
12
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
R dikatakan bersifat refleksif bila dan hanya bila (∀ x ∈ H) xRx
R dikatakan bersifat simetris bila dan hanya bila (∀ x, y ∈ H) xRy ⇒ yRx
R dikatakan bersifat transitif bila dan hanya bila
(∀ x, y, z ∈ H) xRy ∧ yRz ⇒ xRz
Definisi 2.2.5: Suatu relasi R pada himpunan H yang tidak kosong disebut relasi
ekivalensi bila dan hanya bila R bersifat refleksif, simetris, dan
transitif.
Relasi kongruensi modulo n pada Z adalah salah satu contoh relasi
ekivalensi. Dua bilangan bulat berelasi kongruensi modulo n (di mana n adalah
suatu bilangan bulat positif) bila dan hanya bila keduanya menghasilkan sisa yang
sama bila dibagi n. Relasi ini dilambangkan dengan x ≡ y (mod n), dibaca “ x
kongruen terhadap y modulo n ”.
Jika H suatu himpunan yang tidak kosong dan R adalah suatu relasi
ekivalensi pada H maka:
1. Dua eleman x, y ∈ H dikatakan ekivalen terhadap relasi R bila dan hanya bila
xRy.
2. Untuk setiap x ∈ H pasti terdapat paling tidak satu elemen dalam H yang
ekivalen dengan x terhadap R, yaitu x itu sendiri (karena R refleksif). Himpunan
13
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
semua elemen dalam H yang ekivalen dengan x disebut klas ekivalensi dengan
wakil x, ditulis sebagai . x
(∀ x ∈ H) x = {y ∈ H⏐ xRy}
3. Keluarga dari semua klas ekivalensi dari suatu himpunan H terhadap relasi
ekivalensi R dinyatakan dengan RH = { x ⏐x ∈ H}, dan disebut H modulo R
atau H mod R.
Sifat-sifat klas-klas ekivalensi dijelaskan dalam teorema berikut:
Teorema 2.2.2: Jika R adalah suatu relasi ekivalensi pada himpunan H, maka
(∀ x, y ∈ H) x = y bila dan hanya bila xRy.
Bukti:
(⇒) Diketahui bahwa R adalah relasi ekivalensi pada himpunan H dan x, y ∈
H. Andaikan x = y . Akan ditunjukkan xRy. Karena R refleksif, maka
berlaku yRy, sehingga y ∈ y . Karena x = y , maka y ∈ x . Jadi xRy.
(⇐) Andaikan xRy. Akan ditunjukkan x = y . Ambil sebarang z ∈ y , maka
yRz, sehingga diperoleh xRy dan yRz. Karena R transitif, maka berlaku
xRz. Jadi z ∈ , sehingga z ∈ x y ⇒ z ∈ x , maka y ⊆ . .......(1) x
14
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Sekarang andaikan z ∈ x , maka xRz. Karena xRy dan R simetris, maka
berlaku yRx, sehingga diperoleh yRx dan xRz. Karena R transitif, maka
berlaku yRz. Jadi z ∈ y , sehingga z ∈ ⇒ z ∈ x y , maka x ⊆ y .
.......(2)
Dari (1) dan (2) terbukti bahwa x = y
Jadi terbukti (∀ x, y ∈ H) x = y bila dan hanya bila xRy.
Teorema 2.2.3: Klas-klas ekivalensi yang terbentuk dari suatu relasi ekivalensi R
pada himpunan tidak kosong H bersifat sebagai berikut:
1. (∀ x ∈ H) x ≠ φ
2. (∀ x, y ∈ H) x ∩ y ≠ φ ⇒ x = y
Bukti:
1. Ambil sebarang x ∈ H. Karena R relasi ekivalensi, maka R refleksif
sehingga xRx. Jadi x ∈ . Terbukti ≠ φ. x x
2. Akan ditunjukkan: x ∩ y ≠ φ ⇒ x = y . Ambil sebarang z ∈ ( x ∩
y ) ≠ φ, maka z ∈ dan z ∈ x y , sehingga berlaku xRz dan yRz. R
bersifat simetris, maka zRy. R bersifat transitif dan xRz dan zRy, maka
xRy. Dengan Teorema 2.2.2 diperoleh x = y .
Terbukti (∀ x, y ∈ H) x ∩ y ≠ φ ⇒ x = y
15
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Relasi ekivalensi pada suatu himpunan H berkaitan erat dengan partisi dari
himpunan H. Partisi dari H adalah keluarga himpunan bagian dari H yang tidak
kosong dan saling asing yang gabungannya adalah H. Himpunan bagian dari H
yang elemennya dari partisi disebut sel dari partisi. Hubungan erat ini ditunjukkan
lewat teorema di bawah ini.
Teorema 2.2.4: Relasi Ekivalensi dan Partisi
1. Setiap relasi ekivalensi R yang didefinisikan pada himpunan takkosong
H membangkitkan satu partisi P pada H.
2. Untuk setiap partisi P pada H ada suatu relasi ekivalensi R yang
didefinisikan pada H.
Bukti:
1. Andaikan H suatu himpunan yang tidak kosong dan R adalah suatu relasi
ekivalensi yang didefinisikan pada H. Akan diperlihatkan bahwa RH ,
yaitu himpunan klas-klas ekivalensi dari H yang diakibatkan oleh R,
adalah suatu partisi dari H.
RH = { x ⏐ x ∈ H} dengan x = {y⏐y ∈ H ∧ xRy}
Akan ditunjukkan:
a. Setiap klas tidak kosong.
b. Klas-klas yang berbeda saling asing.
16
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
c. Gabungan dari semua klas adalah himpunan H.
a. Dalam Teorema 2.2.3 no. 1, telah dibuktikan bahwa setiap klas
ekivalensi tidak kosong.
b. Telah dibuktikan dalam Teorema 2.2.3 no. 2 bahwa (∀x, y ∈ H)
x ∩ y ≠ φ ⇒ x = y , sehingga (∀x, y ∈ H) x ≠ y ⇒ x ∩ y = φ
(kontraposisi). Jadi klas-klas yang berbeda saling asing.
c. Ambil sebarang z ∈ H. Karena z ∈ z , maka z adalah elemen dari
gabungan semua klas ekivalensi. Jadi H adalah himpunan bagian dari
gebungan semua klas ekivalensi. Jelas bahwa gabungan dari semua
klas ekivalensi adalah himpunan bagian dari H. Jadi gabungan semua
klas ekivalensi dari H adalah himpunan H.
2. Andaikan P suatu partisi dari H, di mana P = { ⏐δ ∈ Δ, untuk suatu
himpunan indeks Δ}. Akan ditunjukkan bahwa ada suatu relasi
ekivalensi pada H yang berkaitan dengan P. Didefinisikan suatu relasi R
pada H sebagai berikut (∀x, y ∈ H) xRy bila dan hanya bila (∃δ ∈ Δ)
(x ∈ ∧ y ∈ ). Artinya x berelasi dengan y bila dan hanya bila x
dan y berada dalam sel yang sama.
δH
δH H
H
δ
Akan ditunjukkan bahwa R bersifat refleksif, simetris, dan transitif.
i. Setiap x ∈ H berada pada suatu sel, sehingga (∃δ ∈ Δ) ( x ∈
∧ x ∈ ). Jadi xRx, yaitu R bersifat refleksif.
δH
δ
17
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
ii. Andaikan xRy, maka (∃δ ∈ Δ) (x ∈ ∧ y ∈ ), sehingga
(∃δ ∈ Δ) (y ∈ ∧ x ∈ ), yaitu yRx. Jadi R bersifat
simetris.
δH δH
δH H
H H H
H H H
H H
δ
iii. Andaikan xRy dan yRz, maka sel ∈ P, sehingga x, y ∈ ,
dan ada sel ∈ P, sehingga y, z ∈ . Jadi y ∈ dan y ∈
, yaitu ∩ ≠ φ. Karena P adalah partisi dari H, maka
= . Jadi x, y, dan z berada dalam sel yang sama,
sehingga xRz. Jadi R bersifat transitif.
δH δH
r r δ
r δ r
δ r
Dari i, ii, dan iii terbukti bahwa R adalah relasi ekivalensi pada H.
Terbukti untuk setiap partisi P pada H ada suatu relasi ekivalensi R yang
didefinisikan pada H.
Salah satu relasi biner yang khusus adalah relasi urutan. Ada dua macam
relasi urutan yang dapat didefinisikan pada himpunan:
1. Relasi urutan Parsial
Andaikan S adalah suatu himpunan dan R adalah suatu relasi biner pada S.
Relasi R disebut relasi urutan parsial pada S bila dan hanya bila
1. R refleksif: (∀ a ∈ S) aRa
2. R antisimetris: (∀ a, b ∈ S) aRb ∧ bRa ⇒ a = b
18
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
3. R transitif: (∀ a, b, c ∈ S) aRb ∧ bRc ⇒ aRc
Jika S adalah himpunan yang tidak kosong dan S mempunyai relasi urutan
parsial R yang didefinisikan padanya, maka pasangan terurut (S,R) disebut
himpunan terurut parsial (poset). Jika (S,R) adalah suatu poset maka dua
elemen a dan b dikatakan terbanding bila dan hanya bilsa aRb atau bRa (atau
keduanya, yang berarti a = b). Perlu diperhatikan tidak semua elemen dalam
poset itu terbanding.
2. Relasi Urutan Total
Andaikan S adalah suatu himpunan dan R adalah suatu relasi biner pada S.
Relasi R disebut relasi urutan total pada S bila dan hanya bila R adalah suatu
relasi urutan parsial yang mempunyai sifat (∀a, b ∈ S) aRb ∨ bRa.
Perbedaan utama dari relasi urutan parsial dan relasi urutan total pada
himpunan S adalah pada keterbandingan dari elemen-elemen pada S. Pada relasi
urutan total setiap pasang elemen pasti terbanding, sedangkan pada relasi urutan
parsial tidak setiap pasang elemen terbanding.
Selain relasi-relasi yang disebutkan di atas, ada sebuah relasi khusus yang
penting yaitu fungsi. Relasi ini didefinisikan dari himpunan A ke himpunan B.
Definisi 2.2.6: Suatu fungsi dari himpunan A ke himpunan B, ditulis f : A → B,
adalah suatu relasi biner dari A ke B (yang berarti suatu himpunan
bagian dari B× ) yang memenuhi syarat-syarat sebagai berikut: A
19
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
1. Eksistensi: (∀x ∈ A) (∃y ∈ B) (x,y) ∈ f .
Artinya: setiap elemen dalam A berelasi dengan satu elemen
dalam B.
2. Keunikan: (∀( ), ( ) ∈ f ) = ⇒ = . 11 , yx 22 , yx 1x 2x 1y 2y
Artinya: setiap satu elemen dalam A hanya berelasi dengan
satu elemen dalam B.
Domain (daerah asal) dari fungsi f adalah himpunan semua komponen pertama
dari pasangan terurut (x,y) ∈ f. Elemen-elemen dalam domain disebut
prabayangan. Daerah asal suatu fungsi f dilambangkan dengan Dom f. Range
(daerah hasil) dari fungsi f adalah himpunan semua komponen kedua dari
pasangan terurut (x,y) ∈ f. Elemen-elemen dalam daerah hasil disebut bayangan.
Daerah hasil suatu fungsi f dilambangkan dengan Ran f. Pada pembahasan fungsi,
penulisan (x,y) ∈ f dapat diganti dengan f(x) = y, di mana x adalah prabayangan
dan y adalah bayangannya. Dengan menggunakan lambang ini fungsi dapat
didefinisikan sebagai berikut:
Definisi 2.2.7: Suatu fungsi dari A ke B, ditulis f : A → B, adalah suatu relasi biner
dari A ke B yang memenuhi syarat sebagai berikut:
1. Eksistensi: (∀x ∈ A) (∃y ∈ B) f(x) = y
2. Keunikan: (∀x,y ∈ A) x = y ⇒ f(x) = f(y)
20
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 2.2.8: Dua fungsi f dan fungsi g dikatakan sama bila dan hanya bila:
1. Dom f = Dom g
2. (∀x ∈ Dom f) f(x) = g(x)
Fungsi disebut juga pemetaan. Beberapa pemetaan khusus:
Definisi 2.2.9: Pemetaan Onto (Surjektif)
Suatu pemetaan f : A → B disebut pemetaan onto (surjektif) bila
dan hanya bila (∀y ∈ B) (∃x ∈ A) f(x) = y.
Definisi 2.2.10: Pemetaan Satu-satu (Injektif)
Suatu pemetaan f : A → B disebut pemetaan satu-satu (injektif)
bila dan hanya bila (∀ , ∈ A) f( ) = f( ) ⇒ = . 1x x x x x x2 1 2 1 2
Definisi 2.2.11: Pemetaan Bijektif
Suatu pemetaan f : A → B disebut pemetaan bijektif bila dan
hanya bila pemetaan ini adalah satu-satu dan onto sekaligus.
Definisi 2.2.12: Suatu pemetaan f : A → A yang didefinisikan dengan f(x) = x
disebut pemetaan identitas pada A.
Definisi 2.2.13: Andaikan R adalah relasi ekivalensi pada X dan
RX = { x ⏐x ∈ X}
21
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
dengan x adalah klas ekivalensi dengan wakil x.
Suatu pemetaan f : X → RX dengan f(x) = x disebut pemetaan
kanonis dari X ke RX .
Definisi 2.2.14: Suatu pemetaan f : A → B disebut pemetaan konstan bila dan
hanya bila (∃y ∈ B) (∀x ∈ A) f(x) = y.
Definisi 2.2.15: Suatu pemetaan f : B → {0,1} yang didefinisikan dengan
f(x) = ⎩⎨⎧
∈∉
BxBx
untuk1untuk0
disebut fungsi karakteristik dari B.
Jika fungsi f : A → B bijektif, maka untuk setiap y ∈ B ada paling sedikit
satu x ∈ A sedemikian hingga y = f(x) dan ada paling banyak satu x ∈ A
sedemikian hingga y = f(x). Oleh karena itu, jika f : A → B bijektif, maka (∀y ∈ B)
(∃!x ∈ A) y = f(x). Dikatakan bahwa ada korespondensi satu-satu antara elemen-
elemen dari A dan elemen-elemen dari B. Dalam hal ini A dan B dikatakan
ekipoten dan dilambangkan dengan A ~ B. Dari gambaran di atas dapatlah
didefinisikan fungsi invers yaitu:
22
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 2.2.16: Diberikan fungsi f : A → B yang bijektif.
Fungsi : B → A dengan (y) = x, di mana x adalah elemen
tunggal dalam A sedemikian hingga y = f(x), disebut
1−f 1−f
fungsi invers
dari f.
Teorema 2.2.5: Diberikan fungsi bijektif f : A → B. Fungsi invers dari suatu
fungsi bijektif adalah fungsi bijektif.
Bukti:
Diketahui f : A → B adalah fungsi bijektif. Akan ditunjukkan bahwa
: B → A adalah fungsi bijektif. Ambil sebarang x ∈ A. Harus ditemukan
y ∈ B sedemikian hingga (y) = x. Dipilih y = f(x) ∈ B. Menurut Definisi
2.2.16 berarti (y) = x, maka (∀x ∈ A) (∃y ∈ B) (y) = x, sehingga
: B → A adalah fungsi surjektif. Ambil sebarang , ∈ B,
sedemikian hingga ( ) = ( ). Andaikan ( ) = dan
( ) = , maka = , sehingga f( ) = f( ), karena f adalah
fungsi. Diketahui (y) = x ⇔ f(x) = y, sehingga f( ) = dan
f( ) = , maka = . Jadi berlaku (∀ , ∈ B) ( ) = ( )
⇒ = , sehingga : B → A adalah fungsi bijektif. Jadi : B → A
adalah fungsi bijektif.
1−
1−
1− 1−
1−
1− 1− 1−
1−
1−
1− 1−
1− 1−
f
f
f f
f 1y 2y
f 1y f 2y f 1y 1x
f 2y 2x 1x 2x 1x 2x
f 1x 1y
2x 2y 1y 2y 1y 2y f 1y f 2y
1y 2y f f
23
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 2.2.17: Diberikan fungsi f : A → B dan ⊆ A. 0A
Fungsi 0A
f : → B didefinisikan dengan 0A0A
f (x) = f(x)
disebut fungsi f yang terbatas pada . 0A
Teorema 2.2.6: Andaikan f : B → C dan g : A → B adalah fungsi-fungsi, maka
i. f o g dengan (f o g) (x) = f (g(x)) untuk setiap x ∈ A adalah
suatu fungsi dari A ke C.
ii. Ran (f o g) = { f(y)⏐y ∈ Ran g}
Bukti:
i. Akan ditunjukkan bahwa f o g memenuhi kondisi eksistensi dan
keunikan.
a. Eksistensi
Akan ditunjukkan (∀x ∈ A) (∃z ∈ C) (f o g)(x) = z. Ambil
sebarang x ∈ A. Karena g adalah fungsi dari A ke B, maka ada
suatu y ∈ B sedemikian hingga g(x) = y. Karena f adalah fungsi
dari B ke C, maka ada suatu z ∈ C sedemikian hingga f(y) = z,
sehingga f(g(x)) = z, maka (f o g) (x) = z.
b. Keunikan
24
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Akan ditunjukkan (∀ , ∈ A) = ⇒ (f 1x 2x 1x 2x o g) ( ) = (f 1x og)
( ). Andaikan dan sebarang elemen dalam A dengan
= . Karena g dan f adalah suatu fungsi, maka g( ) = g( )
dan f(g( )) = f(g( )), sehingga (f
2x 1x 2x
1x 2x 1x 2x
1x 2x o g) ( ) = (f 1x o g) ( ). 2x
Dari a dan b terbukti bahwa f o g memenuhi kondisi eksistensi dan
keunikan.
ii. Akan ditunjukkan Ran (f o g) = { f(y)⏐y ∈ Ran g}
(⇒) Ambil sebarang z ∈ Ran (f o g), maka ada x ∈ Dom (f o g),
sehingga (f o g) (x) = z, maka z = (f o g) (x) = f(g(x)) = f(y), di mana
y = g(x) ∈ Ran g, maka z ∈ {f(y)⏐y ∈ Ran g}.
Jadi Ran (f og) ⊆ {f(y)⏐y ∈ Ran g}. ...(1)
(⇐) Ambil sebarang z ∈ {f(y)⏐y ∈ Ran g}, sehingga z = f(y), dengan
y ∈ Ran g. Dengan demikian ada x ∈ Dom g, sehingga g(x) = y,
sehingga z = f(y) = f(g(x)) = (f o g) (x), maka z ∈ Ran (f o g).
Jadi {f(y)⏐y ∈ Ran g} ⊆ Ran (f o g) ...(2)
Dari (1) dan (2) terbukti Ran (f o g) = { f(y)⏐y ∈ Ran g}
25
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 2.2.18: Diberikan fungsi f : A → B dan g : B → C.
Fungsi g o f : A → C dengan (g o f )(x) = g(f(x)) untuk setiap
x ∈ A disebut fungsi komposit dari g dengan f.
Teorema 2.2.7: Komposisi fungsi bersifat asosiatif.
Andaikan f, g, dan h adalah fungsi-fungsi sedemikian hingga
dan terdefinisi, maka )( hgf hgf )(oo oo
hgf oo )( = )( hgf oo
Bukti:
Andaikan sebarang x ∈ Dom [ ], hgf oo )(
maka [ ] (x) = (h(x)) hgf oo )( )( gf o
= f(g(h(x)))
= f [ (x)] )( hg o
= [ ] (x) )( hgf oo
Terbukti (∀x ∈ Dom [ ]) [ ] (x) = [ ] (x). hgf oo )( hgf oo )( )( hgf oo
Terbukti bahwa komposisi fungsi bersifat asosiatif.
26
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Teorema 2.2.8: Diberikan fungsi bijektif f : A → B.
Fungsi komposit f o 1−f , adalah fungsi identitas pada himpunan
B, dan fungsi komposit 1−f o f, adalah fungsi identitas pada
himpunan A.
Bukti:
Andaikan dan adalah fungsi-sungsi identitas dari berturut-turut
himpunan A dan himpunan B, sehingga (∀x ∈ A) (x) = x dan (∀y ∈ B)
(y) = y. Akan ditunjukkan bahwa f
AI BI
AI
BI o 1−
1−
f = . Untuk setiap y ∈ B ada
tunggal x ∈ A sedemikian sehingga (y) = x, maka (f
BI
f o 1−
1−
f ) (y) =
f( (y)) = f(x) = y. Jadi f f o 1−f = . BI
Akan ditunjukkan bahwa 1−f o f = . Untuk setiap x ∈ A ada tunggal
y ∈ B sedemikian sehingga f(x) = y, sehingga (
AI
1−f o f ) (x) = ( f(x)) =
(y) = x. Jadi
1−
1− 1−
f
f f o f = . AI
3. Sistem Aljabar dan Homomorfisma
Telah diketahui bahwa fungsi adalah suatu relasi khusus antara dua
himpunan. Sekarang akan dibahas tentang suatu fungsi yang memetakan suatu
sistem tertentu ke sistem tertentu yang lain. Pembahasan ini diawali dengan
definisi operasi biner pada suatu himpunan dan definisi suatu sistem dalam
matematika sebagai berikut.
27
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 2.3.1: Suatu pemetaan dari SS × ke S disebut operasi biner pada
himpunan S. Operasi biner seringkali dilambangkan dengan ∗, dan
ditulis (∀(a,b) ∈ S) ∗(a,b) = a ∗ b.
Definisi 2.3.2: Pasangan terurut (S, ∗), yang terdiri dari himpunan S yang tidak
kosong dan suatu operasi biner ∗ yang didefinisikan pada S,
disebut sistem aljabar.
Homomorfisma adalah suatu fungsi yang memetakan suatu sistem aljabar
ke sistem aljabar yang lain, dan mengawetkan operasinya. Hal ini didefinisikan
sebagai berikut:
Definisi 2.3.3: Andaikan (S, ∗) dan (T, o) adalah sistem-sistem aljabar. Pemetaan
f : S → T disebut homomorfisma dari S ke T jika dan hanya jika
(∀ , ∈ S) f ( ∗ ) = f ( ) 1s s s s s2 1 2 1 o f ( ). 2s
Definisi 2.3.4: Suatu homomorfisma yang surjektif disebut epimorfisma.
Suatu homomorfisma yang injektif disebut monomorfisma.
Suatu homomorfisma bijektif disebut isomorfisma.
Suatu isomorfisma dari suatu himpunan ke himpunan itu sendiri
disebut automorfisma.
28
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 2.3.5: Sistem (S, ∗) dikatakan isomorfis dengan sistem (T, o) bila dan
hanya bila ada suatu isomorfisma f : S → T, dilambangkan dengan
S ≅ T.
Teorema 2.3.1: Jika f adalah suatu isomorfisma dari (S, ∗) ke (T, o), maka
adalah suatu isomorfisma dari (T,
1−f
o) ke (S, ∗).
Bukti:
Andaikan f : S → T suatu isomorfisma, maka f adalah suatu fungsi bijektif.
Telah dibuktikan dalam Teorema 2.2.5 bahwa : T → S adalah fungsi
bijektif. Sekarang tinggal membuktikan bahwa (
1−
1−
f
f 1t o ) = ( ) ∗
( ). Ambil sebarang dan ∈ T, maka ( ) = dan ( ) =
, dengan dan ∈ S, dan f( ) = dan f( ) = . Diketahui f adalah
suatu isomorfisma, maka f ( ∗ ) = f ( )
2t1−
1− 1− 1−
s s s
f 1t
f 2t 1t 2t f 1t 1s f 2t
2s 1s 2s 1s 1t 2s 2t
1 2 1 o f ( ), 2s
sehingga (1−f 1t o 2t ) = [ (f ( ) 1−f 1s o f ( )] 2s
= [ f ( ∗ )] 1−f 1s 2s
= ( 1−f o f ) ( ∗ ) 1s 2s
= ( ∗ ) (Teo. 2.2.8) sI 1s 2s
= ∗ (Def. 2.2.12) 1s 2s
29
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
= ( ) ∗ ( ). 1−f 1t1−f 2t
Terbukti bahwa invers dari suatu isomorfisma adalah suatu isomorfisma.
30
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
BAB III
HIMPUNAN TERCACAH
Pada Bab III ini dibahas himpunan tercacah dan sifat-sifat yang
menyertainya. Pembahasan ini dimulai dari himpunan hingga dan himpunan
takhingga. Kemudian ditinjau sifat-sifat himpunan tercacah dan beberapa contoh
himpunan tercacah. Akhirnya dibahas himpunan kuasa dan sifat-sifatnya, serta
keadaannya bila himpunan asalnya adalah himpunan tercacah.
1. Himpunan Hingga dan Himpunan Tak Hingga
Telah diketahui bahwa suatu himpunan dapat didefinisikan dengan
beberapa cara antara lain dengan menuliskan anggota-anggotanya dan dengan
menggunakan notasi pembentuk himpunan. Cara yang pertama biasa digunakan
apabila jumlah elemen dari himpunan dapat dibilang sampai elemen yang terakhir
secara jelas. Himpunan dengan elemen demikian disebut himpunan hingga yang
didefinisikan sebagai berikut:
Definisi 3.1.1: Suatu himpunan H dikatakan hingga bila dan hanya bila H adalah
himpunan kosong atau himpunan yang berkorespondensi satu-satu
dengan himpunan {1,2,3,...,k} untuk suatu k ∈ N, dengan N
himpunan semua bilangan asli.
Jika himpunan A = φ, maka A mempunyai 0 elemen dan dilambangkan oleh
n(A) = 0. Jika A berkorespondensi satu-satu dengan {1,2,3,...,k} maka A
mempunyai k elemen dan dilambangkan dengan n(A) = k.
31
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Cara yang kedua digunakan pada himpunan yang jumlah elemennya tidak
dapat dibilang sampai habis. Himpunan ini disebut himpunan takhingga yang
didefinisikan sebagai berikut:
Definisi 3.1.2: Himpunan H dikatakan takhingga bila dan hanya bila H
merupakan himpunan tidak kosong, yang tidak berkorespondensi
satu-satu dengan himpunan {1,2,3,...,k} untuk setiap k ∈ N.
Ada dua jenis himpunan takhingga yang berbeda dan konsep
korespondensi satu-satu kembali digunakan untuk menjelaskan perbedaan
tersebut.
2. Himpunan Tercacah dan Himpunan Terbilang
Definisi 3.2.1: Suatu himpunan takhingga yang berkorespondensi satu-satu
dengan N disebut himpunan tercacah.
Definisi 3.2.2: Himpunan hingga atau himpunan tercacah disebut himpunan
terbilang.
Definisi 3.2.3: Himpunan takhingga yang tidak berkorespondensi satu-satu
dengan N disebut himpunan taktercacah.
Untuk selanjutnya pembicaraan akan lebih pada himpunan tercacah dan
himpunan taktercacah.
Definisi 3.2.4: Diberikan sebarang himpunan A, dan R adalah relasi terurut parsial
pada A. Elemen a ∈ A adalah elemen terkecil bila dan hanya bila
(∀x ∈ A) aRx. Elemen a ∈ A adalah elemen terbesar bila dan
hanya bila (∀x ∈ A) xRa.
32
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Definisi 3.2.5: Diberikan sebarang himpunan A, dan R adalah relasi terurut total
pada A. Himpunan A dikatakan terurut wajar bila dan hanya bila
setiap himpunan bagian dari A memuat elemen terkecil.
Contoh himpunan tercacah adalah himpunan semua bilangan bulat Z dan
himpunan semua bilangan rasional Q, dan contoh himpunan taktercacah adalah
interval (0,1). Hal ini akan dibuktikan sesudah membahas beberapa sifat
himpunan tercacah sebagai berikut.
Teorema 3.2.1: Himpunan semua bilangan asli N terurut wajar oleh relasi ≤.
Bukti:
Akan ditunjukkan bahwa relasi ≤ adalah relasi urutan total pada N dengan
menunjukkan bahwa relasi ≤ memenuhi sifat relasi urutan total.
a. Refleksif
Ambil sebarang x ∈ N. Jelas bahwa x ≤ x, maka (∀x ∈ N) x ≤ x.
Jadi relasi ≤ memenuhi sifat refleksif.
b. Antisimetris
Ambil sebarang x,y ∈ N dengan x ≤ y dan y ≤ x, maka jelas bahwa x = y,
sehingga (∀x,y ∈ N) x ≤ y ∧ y ≤ x ⇒ x = y.
Jadi relasi ≤ memenuhi sifat antisimetris.
c. Transitif
Ambil sebarang x,y,z ∈ N dengan x ≤ y dan y ≤ z, maka jelas bahwa x
≤ z, sehingga (∀x,y,z ∈ N) x ≤ y ∧ y ≤ z ⇒ x = z.
Jadi relasi ≤ memenuhi sifat transitif.
33
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
d. Ambil sebarang x,y ∈ N, maka haruslah x ≤ y atau y ≤ x. Karena jika
x ≤ y dan y ≤ x, maka x = y, dan sifat ini sudah dipenuhi sebelumnya.
Dengan demikian relasi ≤ memenuhi sifat (∀x,y ∈ N) x ≤ y ∨ y ≤ x.
Berdasarkan a, b, c, dan d di atas, maka relasi ≤ adalah relasi urutan total,
sehingga setiap pasang elemen dalam N pasti terbanding. Dibentuk sebarang
himpunan P ⊆ N dan P ≠ φ, dengan P = {a}. Jelas bahwa a ≤ a, sehingga a
∈ P adalah elemen terkecil. Andaikan dibentuk sebarang himpuan T ⊆ N
dan T ≠ φ, dengan T = {a,d}, maka (∀x ∈ T) jika a ≤ x, maka a ∈ T adalah
elemen terkecil atau jika d ≤ x, maka d ∈ T adalah elemen terkecil. Dengan
demikian himpunan P dan T memuat elemen terkecil. Kembali dibentuk
sebarang himpunan D ⊆ N dan D ≠ φ, dengan D = {e,g,h,k,m,p,...}. Dengan
cara yang sama ditemukan bahwa himpunan D memuat elemen terkecil,
misalnya e, karena (∀x ∈ D) e ≤ x. Terlihat bahwa setiap himpunan bagian
tidak kosong dari N memuat elemen terkecil. Jadi himpunan semua bilangan
asli N terurut wajar oleh relasi ≤.
Teorema 3.2.2: Jika himpunan S adalah himpunan bilangan asli sedemikian
sehingga:
1. 1 ∈ S
2. (∀n ∈ S) (n ∈ S ⇒ n + 1 ∈ S),
maka S = N.
34
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Bukti:
S adalah himpunan bilangan asli sedemikian sehingga 1 ∈ S dan (∀n ∈ S)
(n ∈ S ⇒ n + 1 ∈ S). Andaikan A = N – S adalah himpunan yang tidak
kosong. Karena (N, ≤) terurut wajar, maka A memuat suatu elemen terkecil,
misalnya a. Jelas a ≠ 1, karena 1 ∈ S dan A = N – S, maka a – 1 ∈ N, dan
a – 1 ≤ a. Karena a adalah elemen terkecil dari A, maka a – 1 ∉ A, sehingga
a – 1 ∈ S. Karena a – 1 ∈ S, maka (a – 1) + 1 ∈ S, sehingga a ∈ S. Padahal
a ∈ A dan S = N – A, sehingga a ∉ S. Terjadi kontradiksi. Pengandaian
salah, maka A = φ. Jadi S = N – A = N – φ = N.
Teorema 3.2.3: Andaikan A adalah himpunan tercacah dan x ∉ A, maka A ∪ {x}
adalah himpunan tercacah.
Bukti:
A adalah himpunan tercacah dan x ∉ A, maka ada fungsi bijektif f : A → n.
Didefinisikan fungsi g : A ∪ {x} → N, dengan
g(y) = ⎩⎨⎧
∈+=
Ayyf xy
untuk1)(untuk 1
Harus ditunjukkan bahwa fungsi g bijektif. Andaikan n ∈ N. Jika n = 1,
maka n = g(x). Jika n ≠ 1, maka n = k + 1 untuk suatu k ∈ N. Tetapi k = f(y)
untuk suatu y ∈ A, sehingga n = k + 1 = f(y) + 1 = g(y) untuk suatu y ∈ A.
Karena untuk setiap n ∈ N dapat ditemukan y ∈ A ∪ {x} sedemikian hingga
n = g(y), maka fungsi g surjektif. Andaikan g(y) = g(z). Jika g(y) = 1, maka
y = z = x. Jika g(y) ≠ 1, maka f(y) + 1 = f(z) + 1. Karena fungsi f adalah
35
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
fungsi injektif, maka y = z. Karena untuk semua y, z ∈ A ∪ {x} berlaku jika
g(y) = g(z), maka y = z, sehingga fungsi g injektif. Terbukti bahwa fungsi g
bijektif. Jadi A ∪ {x} adalah himpunan tercacah.
Teorema 3.2.4: Gabungan himpunan tercacah dan himpunan hingga yang saling
asing adalah himpunan tercacah.
Bukti:
Diberikan himpunan tercacah A dan himpunan hingga B yang tidak kosong,
dengan A ∩ B = φ. Akan dibuktikan bahwa A ∪ B adalah himpunan
tercacah. Karena A himpunan tercacah, maka ada fungsi bijektif f : A → N
dan karena B adalah himpunan hingga, maka ada fungsi bijektif
g : B → {1,2,3,...,n} untuk suatu n ∈ N.
Didefinisikan fungsi h : A ∪ B → N dengan
h(y) = ⎩⎨⎧
∈Ν∈+∈
AykknByyg
untuk,untuk )(
Harus ditunjukkan bahwa fungsi h adalah fungsi bijektif.
Ambil sebarang t ∈ N. Jika t = k untuk suatu k ∈ {1,2,3,...,n}, maka dapat
ditemukan y ∈ B sedemikian hingga g(y) = k, karena fungsi g surjektif.
Dengan demikian h(y) = g(y) = k. Jika t = n + k, untuk suatu k ∈ n, maka
dapat ditemukan y ∈ A sedemikian hingga f(y) = t, karena fungsi f surjektif.
Dengan demikian h(y) = n + k = t. Oleh karena itu untuk semua t ∈ N dapat
ditemukan y ∈ A ∪ B sedemikian hingga t = h(y), maka fungsi h surjektif.
Ambil sebarang y, z ∈ A ∪ B sedemikian hingga h(y) = h(z). Tidak mungkin
terjadi h(y) = g(y) dan h(z) = n + k, k ∈ n, atau h(y) = n + k, k ∈ n, dan h(z)
36
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
= g(z). Jika h(y) = g(y) dan h(z) = g(z), maka jelas g(y) = g(z), sehingga y = z,
karena fungsi g injektif. Jika h(y) = n + k, k ∈ n, dan h(z) = n + k, k ∈ n,
maka untuk t = n + k, k ∈ n ada y ∈ A sedemikian hingga f(y) = t dan untuk
p = n + k, k ∈ n ada z ∈ A sedemikian hingga f(z) = p, karena fungsi f
surjektif, sehingga t = p = n + k, k ∈ n, maka f(y) = f(z). Karena fungsi f
injektif, maka y = z. Dengan demikian untuk semua y,z ∈ A ∪ B berlaku jika
h(y) = h(z), maka y = z. Jadi fungsi h injektif. Terbukti fungsi h bijektif. Jadi
A ∪ B adalah himpunan tercacah.
Teorema 3.2.5: Gabungan dua himpunan tercacah yang saling asing adalah
himpunan tercacah.
Bukti:
Diberikan himpunan tercacah A dan B, dengan A ∩ B = φ. Harus dibuktikan
bahwa A ∪ B himpunan tercacah. Himpunan A dan B masing-masing
berkorespondensi satu-satu dengan N, sehingga ada fungsi-fungsi bijektif
f : A → N dan g: B → N. Didefinisikan fungsi h : A ∪ B → N dengan
h(x) = ⎩⎨⎧
∈−∈
BxxgAxxf
untuk1)(2untuk )(2
Harus ditunjukkan bahwa h fungsi bijektif.
Ambil sebarang t ∈ N. Jika t genap, maka t = 2n untuk suatu n ∈ N.
Diketahui bahwa fungsi f surjektif, sehingga ∃x ∈ A sedemikian hingga
f(x) = n, maka h(x) = 2f(x) = 2n = t. Jika t ganjil, maka t = 2n – 1 untuk suatu
n ∈ N. Diketahui bahwa fungsi g surjektif, sehingga ∃x ∈ B sedemikian
hingga g(x) = n, sehingga h(x) = 2g(x) – 1 = 2n – 1 = t. Dengan demikian
37
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
(∀t ∈ N) (∃x ∈ A ∪ B) h(x) = t, sehingga h adalah fungsi surjektif. Ambil
sebarang t, p ∈ A ∪ B sedemikian hingga h(t) = h(p). Tidak mungkin terjadi
h(t) = 2f(t) dan h(p) = 2g(p) – 1 atau h(t) = 2g(t) – 1 dan h(p) = 2f(p), karena
2f(t) dan 2f(p) adalah bilangan genap, sedangkan 2g(t) – 1 dan 2g(p) – 1
adalah bilangan ganjil. Dengan demikian haruslah h(t) = 2f(t) dan h(p) =
2f(p) atau h(t) = 2g(t) – 1 dan h(p) = 2g(p) – 1, sehingga
2f(t) = 2f(p)
f(t) = f(p)
t = p karena fungsi f injektif
atau
2g(t) – 1 = 2g(p) – 1
2g(t) = 2g(p)
g(t) = g(p)
t = p karena fungsi g injektif
Dengan demikian berlaku (∀t, p ∈ A ∪ B) h(t) = h(p) ⇒ t = p, maka fungsi
h : A ∪ B → N adalah fungsi bijektif. Jadi A ∪ B himpunan tercacah.
Teorema 3.2.6: Himpunan A dengan A ⊆ N adalah himpunan terbilang.
Bukti:
Diberikan himpunan A dengan A ⊆ N. Harus ditunjukkan bahwa himpunan
A hingga atau tercacah. Jika himpunan A hingga, maka jelas bahwa
himpunan A terbilang. Andaikan himpunan A takhingga. Harus ditunjukkan
bahwa himpunan A tercacah, dengan membangun suatu fungsi f : N → A,
dan harus ditunjukkan bahwa fungsi f : N → A adalah fungsi bijektif. Telah
38
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
diketahui bahwa (N, ≤) terurut wajar, maka A mempunyai elemen terkecil.
Andaikan f(1) ∈ A adalah bayangan dari 1 ∈ N, dan merupakan elemen
terkecil dari A. Dibentuk himpunan AA =1 - { f(1)}, maka = { f(2), f(3),
f(4),...} dan ⊆ N, maka memuat elemen terkecil, yaitu f(2), dengan
f(2) adalah bayangan dari 2 ∈ N. Demikian seterusnya ∀n ∈ N dapat
dibentuk = A - { f(1), f(2), f(3),..., f(n)}, maka = { f(n+1), f(n+2),
f(n+3),...} dan ⊆ N, sehingga memuat elemen terkecil yaitu f(n+1),
dengan f(n+1) adalah bayangan dari n+1 ∈ N. Dengan demikian dapat
dibentuk suatu fungsi f : N → A dengan f(x) = y dan y berada di urutan ke-x
dalam daftar. Harus ditunjukkan bahwa fungsi f : N → A adalah fungsi
bijektif. Ambil sebarang y ∈ A dan y ∉ Ran f. Jika y – 1 = f(j) untuk suatu
j ∈ N, maka y = f (j+1), karena y adalah elemen terkecil dari . Padahal
y ∉ Ran f, sehingga terjadi kontradiksi, maka y – 1 ∉ Ran f, sehingga y – 2
∉ Ran f, dan seterusnya sedemikian hingga f(1) ∉ Ran f. Padahal f(1) adalah
elemen terkecil dari A. Kembali terjadi kontradiksi, sehingga y ∈ Ran f,
maka A ⊆ Ran f. Dengan demikian dapat ditemukan x ∈ N sedemikian
hingga y = f(x). Jadi fungsi f surjektif. Untuk setiap n ∈ N, f(1), f(2), f(3),...,
f(n) adalah daftar elemen pertama dari A yang juga terurut berdasarkan
urutan wajar (N, ≤). Ambil sebarang m,n ∈ N. Jika f(m) = f(n), maka dalam
daftar bilangan ke-m sama dengan bilangan ke-n, sehingga m = n. Jadi
fungsi f injektif, sehingga fungsi f bijektif, maka A himpunan tercacah. Jadi
terbukti A himpunan terbilang.
1A
1A 1A
nA nA
nA nA
jA
39
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Teorema 3.2.7: Diberikan himpunan tercacah A dan himpunan B dengan B ⊆ A,
maka himpunan B terbilang.
Bukti:
Diberikan himpunan tercacah A, maka ada fungsi bijektif f : A → N.
Diketahui himpunan B, dengan B ⊆ A. Karena B ⊆ A dan A ~ N, maka B ~
f(B) ⊆ N, sehingga B dapat dipandang sebagai subset dari N. Jadi
berdasarkan Teorema 3.2.6 himpunan B terbilang.
Teorema 3.2.8: Produk Kartesius N × N adalah himpunan tercacah.
Bukti:
Didefinisikan fungsi f : N × N → N dengan f((a,b)) = . Akan
ditunjukkan bahwa fungsi f bijektif. Ambil sebarang n ∈ N. Jika n ganjil,
dipilih a = 1 dan b =
)12(2 1 −− ba
21+n , sehingga f((1,
21+n )) = ((n+1) – 1) = n. Jika
n genap, dipilih a = 2 dan b =
02
42+n , sehingga f((2,
42+n )) = 2 (
22+n - 1)
= 2 (2n + 1 – 1) = n. Dapat ditemukan (a,b) ∈ N × N sedemikian hingga
f((a,b)) = n, sehingga (∀n ∈ N) (∃(a,b) ∈ N × N) f((a,b)) = n, maka fungsi f
surjektif. Ambil sebarang (a,b), (p,q) ∈ N × N dengan f((a,b)) = f((p,q)).
Harus ditunjukkan (a,b) = (p,q),
maka f((a,b)) = f((p,q))
= )12(2 1 −− ba )12(2 1 −− qp
= tiap ruas dikali 2 )12(2 −ba )12(2 −qp
40
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Tidak mungkin terjadi a2 = )12( −q dan p2 = )12( −b , karena dan
adalah bilangan genap, sedangkan
a2 p2
)12( −b dan )12( −q adalah bilangan
ganjil. Haruslah terjadi = dan a2 p2 12 −b = 12 −q , sehingga a = p dan
b = q, maka (a,b) = (p,q). Dengan demikian berlaku f((a,b)) = f((p,q)) ⇒
(a,b) = (p,q), sehingga (∀(a,b), (p,q) ∈ N × N) f((a,b)) = f((p,q)) ⇒ (a,b) =
(p,q). Terlihat bahwa fungsi f injektif, sehingga fungsi f bijektif.
Jadi N × N tercacah.
Teorema 3.2.9: Produk Kartesius dari dua himpunan tercacah adalah himpunan
tercacah.
Bukti:
Diberikan himpunan tercacah A dan B, maka himpunan A dan B masing-
masing berkorespondensi satu-satu dengan N, sehingga ada fungsi bijektif
f : A → N dan g : B → N. Akan ditunjukkan A × B adalah himpunan
tercacah. Diketahui A × B = {(a,b)⏐a ∈ A dan b ∈ B}. Didefinisikan fungsi
F : A B → N dengan F((a,b)) = (2g(b) – 1). Akan ditunjukkan
bahwa fungsi F : A B → N adalah fungsi bijektif. Ambil sebarang n ∈ N.
Jika n ganjil, maka dipilih a = (1) dan b = (
× 1)(2 −af
×
1−f 1−g2
1+n ), sehingga
F(( (1), (1−f 1−g2
1+n ))) = (2g( (1))1(( 1
2 −−ff 1−g2
1+n )) – 1)
= (2 (g 1)1)(( 1
2 −° −ff o 1−g ) (2
1+n ) – 1)
= (n + 1 – 1) 02
= n
41
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Jika n genap, maka dipilih a = (2) dan b = (1−f 1−g4
2+n ), sehingga
F(( (2), (1−f 1−g4
2+n ))) = (2g( (1))2(( 1
2 −−ff 1−g4
2+n ) – 1)
= (2 (g 1)2)(( 1
2 −° −ff o 1−g ) (4
2+n ) – 1)
= 2 (2n + 1 – 1)
= n
Dapat ditemukan (a,b) ∈ A × B sedemikian hingga F((a,b)) = n, sehingga
(∀n ∈ N) (∃(a,b) ∈ A × B) F((a,b)) = n. Terlihat bahwa fungsi F adalah
fungsi surjektif. Sekarang ambil sebarang (a,b), (p,q) ∈ A B dengan
F((a,b)) = F((p,q)). Harus ditunjukkan bahwa (a,b) = (p,q), sehingga
×
F((a,b)) = F((p,q))
1)(2 −af (2g(b) – 1) = (2g(q) – 1) 1)(2 −pf
)(2 af (2g(b) – 1) = (2g(q) – 1) tiap ruas dikali 2 )(2 pf
Tidak mungkin terjadi = (2g(q) – 1) dan = (2g(b) – 1), karena
dan adalah bilangan genap, sedangkan 2g(b) – 1 dan 2g(q) – 1
adalah bilangan ganjil. Dengan demikian haruslah = dan 2g(b) –
1 = 2g(q) – 1, sehingga f(a) = f(p) dan g(b) = g(q). Karena f : A → N dan g
: B → N adalah fungsi-fungsi injektif maka a = p dan b = q, sehingga (a,b) =
(p,q). Dengan demikian berlaku F((a,b)) = F((p,q)) ⇒ (a,b) = (p,q)
sedemikian hingga (∀(a,b), (p,q) ∈ A
)(2 af )(2 pf
)(2 af )(2 pf
)(2 af )(2 pf
× B) F((a,b)) = F((p,q)) ⇒ (a,b) =
(p,q). Terlihat bahwa fungsi F adalah fungsi injektif. Jadi fungsi
42
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
F : A × B → N adalah fungsi bijektif. Jadi Produk Kartesius dari dua
himpunan tercacah adalah himpunan tercacah.
Teorema 3.2.10: Himpunan semua bilangan bulat Z adalah himpunan tercacah.
Bukti:
Didefinisikan fungsi f : N → Z dengan f(x) = ⎪⎩
⎪⎨
⎧
=−
=−
genapbila 2
ganjilbila21
2xx
xx
.
Akan ditunjukkan bahwa fungsi f : N → Z bijektif. Dengan diagram
ditunjukkan sebagai berikut:
N 1 2 3 4 5 6 7 ...
↓ ↓ ↓ ↓ ↓ ↓ ↓
Z 0 - 1 1 - 2 2 - 3 3 ...
Akan ditunjukkan bahwa fungsi f surjektif. Ambil sebarang n ∈ Z.
a. Jika n < 0, maka x = - 2n ∈ N, dan f(x) = f(-2n) = - 21 (- 2n) = n
b. Jika n ≥ 0, maka x = 2n + 1 ∈ N, dan f(x) = f(2n + 1) = 21 (2n + 1) -
21
= n.
Berlaku (∀n ∈ Z) (∃x ∈ N) f(x) = n. Jadi fungsi f surjektif.
Sekarang akan ditunjukkan bahwa fungsi f injektif. Ambil sebarang x,y ∈
N dengan f(x) = f(y). Jika x ganjil dan y genap, maka f(x) = 21 x -
21 dan
f(y) = - 21 y , sehingga f(x) ≠ f(y). Jika x genap dan y ganjil, maka
43
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
f(x) = - 21 x dan f(y) =
21 y -
21 , sehingga f(x) ≠ f(y). Padahal diketahui
f(x) = f(y). Terjadi kontradiksi. Oleh karena itu tidak mungkin terjadi x ganjil
dan y genap atau x genap dan y ganjil. Haruslah x dan y genap atau x dan y
ganjil.
a. Jika x dan y ganjil, maka 21 x -
21 =
21 y -
21 , sehingga x = y.
b. Jika x dan y genap, maka - 21 x = -
21 y, sehingga x = y.
Berlaku (∀x,y ∈ N) f(x) = f(y) ⇒ x = y. Jadi fungsi f injektif.
Terlihat bahwa fungsi f : N → Z bijektif. Jadi himpunan semua bilangan
bulat Z adalah himpunan tercacah.
Sebelum menunjukkan bahwa himpunan semua bilangan rasional Q
tercacah, terlebih dahulu akan ditunjukkan bahwa himpunan semua bilangan
rasional positif tercacah. Hal ini dibuktikan dalam teorema sebagai berikut. +Q
Teorema 3.2.11: Himpunan semua bilangan rasional positif tercacah. +Q
Bukti:
Telah dibuktikan dalam Teorema 3.2.8 bahwa himpunan N × N tercacah.
Padahal setiap bilangan rasional positif berbentuk pecahan qp , dengan
p, q ∈ N. Dapat dikatakan bahwa elemen-elemen dari adalah pasangan
terurut (p,q) dengan p ∈ N dan q ∈ N, sehingga (p,q) ∈ N × N, maka kita
dapat memandang bahwa ⊆ N
+Q
+Q × N. Himpunan tak hingga, sehingga
dengan Teorema 3.2.7 terbukti himpunan tercacah.
+Q
+Q
44
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Teorema 3.2.12: Himpunan semua bilangan rasional Q tercacah.
Bukti:
Telah dibuktikan dalam Teorema 3.2.11 bahwa himpunan tercacah dan
dalam Teorema 3.2.10 bahwa himpunan semua bilangan bulat Z adalah
himpunan tercacah. Karena
+Q
−Z ⊆ Z dan himpunan −Z takhingga, maka
berdasarkan Teorema 3.2.7, −Z himpunan tercacah. Berdasarkan Teorema
3.2.9, maka −Z N adalah himpunan tercacah. Setiap bilangan rasional
negatif berbentuk pecahan
×
ba dengan a ∈ −Z dan b ∈ N, sehingga dapat
dikatakan bahwa elemen-elemen dari adalah pasangan terurut (a,b),
dengan a ∈
−Q
−Z dan b ∈ N, maka kita dapat memandang ⊆ −Q −Z N
dan himpunan takhingga. Kembali menggunakan Teorema 3.2.7 maka
himpunan adalah himpunan tercacah. Dengan demikian Q’ = ∪ ,
dengan ∩ = φ dan berdasarkan Teorema 3.2.5 adalah himpunan
tercacah. Telah dibuktikan dalam Teorema 3.2.4 bahwa gabungan himpunan
tercacah dan himpunan hingga yang saling asing adalah himpunan tercacah.
{0} adalah himpunan hingga dan Q’ ∩ {0} = φ, sehingga Q = Q’ ∪ {0}
adalah himpunan tercacah. Jadi terbukti himpunan semua bilangan rasional
Q tercacah.
×
−Q
−Q −Q +Q
−Q +Q
Teorema 3.2.13: Interval (0,1) adalah himpunan taktercacah.
Bukti:
45
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Andaikan interval I = (0,1) adalah himpunan tercacah, sehingga I = { , ,
,...} dengan setiap elemen dari I dapat dinyatakan sebagai berikut:
1x 2x
3x
= 0, 1x ...... 1131211 nkkkk
= 0, 2x ...... 2232221 nkkkk
= 0, 3x ...... 3333231 nkkkk
.
.
.
= 0, nx ......321 nnnnn kkkk
.
.
.
dengan ∈ {0,1,2,3,...,9} dan ≠ 0,000... ∀n ∈ N. Perhatikan y
= 0, dengan ∈ {0,1,2,3,...,9} dan ≠ , ≠ ,
≠ , ..., ≠ , ...., maka y ∈ I dan y ≠ , ∀n ∈ N. Jadi y ∉ I. Terjadi
kontradiksi. Jadi terbukti bahwa interval (0,1) adalah himpunan taktercacah.
ijk nx
......321 nbbbb ib 1b 11k 2b 22k 3b
33k nb nnk nx
Teorema 3.2.14: Himpunan semua bilangan real R taktercacah.
Bukti:
Didefinisikan fungsi f : (0,1) → R dengan f(x) = tg(πx - 2π ).
46
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Akan ditunjukkan bahwa fungsi f bijektif.
Ambil sebarang y ∈ R, dipilih x = π
π )(2
1 ytg −+ sedemikian hingga
f(x) = f (π
π )(2
1 ytg −+) = tg(π(
π
π )(2
1 ytg −+) -
2π )
= tg(2π + - )(1 ytg −
2π )
= tg( ) )(1 ytg −
= (tg o ) (y) 1−tg
= y
Dapat ditemukan x ∈ (0,1), sehingga f(x) = y. Dengan demikian berlaku
(∀y ∈ R) (∃x ∈ (0,1)) f(x) = y, sehingga fungsi f surjektif. Ambil sebarang
x,y ∈ (0,1) dengan f(x) = f(y), sehingga tg(πx - 2π ) = tg(πy -
2π ), maka
x = y, sehingga fungsi f injektif. Jadi fungsi f : (0,1) → R bijektif. Terlihat
himpunan semua bilangan real R berkorespondensi satu-satu dengan interval
terbuka (0,1). Telah dibuktikan dalam Teorema 3.2.13 bahwa interval
terbuka (0,1) adalah himpunan taktercacah. Jadi himpunan semua bilangan
real R adalah himpunan taktercacah.
3. Himpunan Kuasa
Telah diketahui bahwa elemen suatu himpunan dapat berupa himpunan.
Secara khusus dapat dibentuk suatu himpunan yang terdiri dari semua himpunan
bagian yang mungkin dari suatu himpunan V yang diberikan, dilambangkan
47
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
dengan ℘(V). Jumlah elemen dalam himpunan hingga V dilambangkan dengan
n (V).
Definisi 3.3.1: Himpunan ℘(V) = {A ⎢A ⊆ V} disebut himpunan kuasa dari V.
Lemma 3.3.1: Jika W himpunan hingga, a ∉ W dan V = W ∪ {a}, maka
n (℘(V)) = 2 n (℘(W)).
Bukti:
Diketahui a ∉ W dan V = W ∪ {a}, maka ℘(V) adalah gabungan semua
himpunan bagian dari W dan semua himpunan bagian dari W yang
digabungkan dengan himpunan {a}, dan kedua keluarga himpunan bagian
tersebut saling asing, sehingga ℘(V) = {A ⎢A ⊆ W} ∪ {A ∪ {a} ⎢A ⊆ W}
dan {A ⎢A ⊆ W} ∩ {A ∪ {a} ⎢A ⊆ W} = φ, maka:
n (℘(V)) = n ({A ⎢A ⊆ W} ∪ {A ∪ {a} ⎢A ⊆ W})
= n ({A ⎢A ⊆ W}) + n ({A ∪ {a} ⎢A ⊆ W})
= n ((℘(W)) + n ((℘(W)) karena n ((℘(W)) = n (℘(W ∪ {a}))
= 2 n ((℘(W))
Teorema 3.3.1: Jika n(V) = m, maka n(℘(V)) = m2 .
Bukti:
Teorema ini akan dibuktikan dengan menggunakan induksi matematika.
Misalkan pernyataan dalam teorema tersebut dilambangkan dengan Φ(n).
Jika V adalah himpunan kosong, maka ℘(V) = {φ}, sehingga n(℘(V)) = 1 =
, maka Φ(0) benar. ........(1) 02
48
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Andaikan Φ(k) benar, yaitu jika W memiliki k elemen maka ℘(W) memiliki
elemen. Andaikan V mempunyai k + 1 elemen. Ambil sebarang elemen
a ∈ V dan bentuk himpunan W = V – {a}, maka n(W) = k, sehingga n(℘(W))
= . Berdasarkan Lemma 3.3.1, maka n(℘(V)) = 2 n ((℘(W)) = 2.
, sehingga diperoleh (∀k ∈ N) [Φ(k) ⇒ Φ(k+ 1)] .....(2)
k2
k2 k2 =
12 +k
Dari (1) dan (2) terbukti bahwa (∀n ∈ N) Φ(n).
Untuk himpunan hingga V, ℘(V) mempunyai elemen yang lebih banyak
daripada V. Bagaimana jika V adalah himpunan takhingga? Untuk menjawab
pertanyaan seperti ini dibuktikan teorema berikut:
Teorema 3.3.2: 1. A ⊆ B ⇔ ℘(A) ⊆ ℘(B)
2. A = B ⇔ ℘(A) = ℘(B)
Bukti:
1. Jika A ⊆ B, maka (∀X) [X ⊆ A ⇒ X ⊆ B], maka (∀X) [X ∈℘(A) ⇒ X ∈
℘(B)], sehingga ℘(A) ⊆ ℘(B). Andaikan ℘(A) ⊆ ℘(B), maka (∀X) [X
∈℘(A) ⇒ X ∈ ℘(B)], yaitu (∀X) [X ⊆ A ⇒ X ⊆ B]. Ambil sebarang
t ∈ A, maka {t} ⊆ A. Jadi {t} ⊆ B, maka t ∈ B, sedemikian hingga
A ⊆ B.
2. Jika A = B bila dan hanya bila A ⊆ B dan B ⊆ A bila dan hanya bila
℘(A) ⊆ ℘(B) dan ℘(B) ⊆ ℘(A) bila dan hanya bila ℘(A) = ℘(B).
Teorema 3.3.3: Himpunan semua himpunan bagian dari suatu himpunan tercacah
adalah himpunan taktercacah.
Bukti:
49
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Diberikan A himpunan tercacah dan ℘(A) = {B ⎢B ⊆ A}. Akan ditunjukkan
bahwa ℘(A) adalah himpunan taktercacah. Andaikan ℘(A) tercacah, maka
ada fungsi f : A → ℘(A) yang bijektif. Didefinisikan T = {x ∈ A ⎢x ∉ f(x)},
maka T ⊆ A, sehingga T ∈ ℘(A). Karena fungsi f bijektif, maka ada y ∈ A
sedemikian hingga f(y) = T. Jika y ∈ T, maka berdasarkan definisi T,
y ∉ f(y). Karena f(y) = T, maka y ∉ T. Terjadi kontradiksi. Jika y ∉ T, maka
y ∉ f(y), karena T = f(y). Padahal berdasarkan definisi T, jika y ∉ f(y), maka
y ∈ T. Kembali terjadi kontradiksi. Karena dua kemungkinan yang ada
menimbulkan kontradiksi berarti pengandaian salah. Jadi ℘(A) himpunan
taktercacah.
Akibat 3.3.3: ℘(N) adalah himpunan taktercacah.
Bukti:
Karena N adalah himpunan tercacah, maka menurut Teorema 3.3.3 ℘(N)
adalah himpunan taktercacah.
Telah dibuktikan pada Teorema 3.2.14 bahwa himpunan semua bilangan
real R adalah himpunan taktercacah dan dari Akibat 3.3.3 di atas, terbukti bahwa
℘(N) adalah juga himpunan taktercacah. Sekarang akan ditunjukkan bahwa ada
korespondensi satu-satu antara himpunan semua bilangan real R dan ℘(N),
dengan terlebih dahulu menunjukkan bukti Teorema Schröder-Bernstein sebagai
berikut.
50
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Teorema 3.3.4: Diberikan himpunan A dan B. Jika fungsi f : A → B dan
g : B → A adalah fungsi-fungsi injektif, maka ada fungsi
F : A → B yang bijektif.
Bukti:
Diberikan himpunan A dan B. Diketahui fungsi f : A → B dan g : B → A
adalah fungsi-fungsi injektif. Harus ditunjukkan bahwa ada fungsi bijektif
F : A → B. Ambil sebarang ∈ B. Andaikan disusun suatu barisan , ,
, , , , ... yang merupakan elemen-elemen dari himpunan A dan B.
Perhatikan, mungkin ada atau tidak ada ∈ A sedemikian hingga
f( ) = . Jika ada, maka unik, karena fungsi f adalah fungsi injektif.
Dipilih sebagai invers dari , yang adalah bayangan dari
(berdasarkan fungsi f). Andaikan telah jelas bahwa ada, dipilih ∈ B
untuk menjadi elemen yang unik sedemikian hingga g( ) = . Kembali,
mungkin ada atau tidak ada ∈ B. Jika ada, maka unik, karena
fungsi g adalah fungsi injektif. Dengan cara yang sama, dipilih sebagai
invers dari , yang adalah bayangan dari (berdasarkan fungsi f), dan
seterusnya. Jika proses ini dilakukan terus menerus akan diperoleh tiga
kejadian yang mungkin sebagai berikut:
1b 1b 1a
2b 2a 3b 3a
1a
1a 1b 1a 1a
1a 1b 1a
1a 2b
2b 1a
2b 2b 2b
2a
2b 2a
1. Proses akan sampai pada ∈ A dan berhenti karena tidak ada ∈
B dengan g( ) = . Keadaan ini mungkin terjadi karena fungsi g
bukan fungsi surjektif.
na ∗b
∗b na
51
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
2. Proses akan sampai pada ∈ B dan berhenti karena tidak ada ∈
A dengan f( ) = . Keadaan ini mungkin terjadi karena fungsi f
bukan fungsi surjektif.
nb ∗a
∗a nb
3. Proses akan terus terjadi tanpa henti.
Demikian telah ditunjukkan bahwa untuk setiap b ∈ B akan terdefinisi
dalam proses ini, sehingga himpunan B dapat dibagi menjadi tiga himpunan
bagian yang saling asing. Andaikan
AB = { semua b ∈ B sedemikian hingga proses berakhir pada suatu } na
BB = { semua b ∈ B sedemikian hingga proses berakhir pada suatu } nb
dan = { semua b ∈ B sedemikian hingga proses tak pernah berakhir }. ∞B
Proses yang sama juga terjadi pada himpunan A, sehingga himpunan A juga
dibagi menjadi tiga himpunan bagian yang saling asing. Andaikan
AA = { semua a ∈ A sedemikian hingga proses berakhir pada suatu } na
BA = { semua a ∈ A sedemikian hingga proses berakhir pada suatu } nb
dan = { semua a ∈ A sedemikian hingga proses tak pernah berakhir }. ∞A
Sekarang akan ditunjukkan bahwa himpunan A berkorespondensi satu-satu
dengan himpunan B. Hal ini dilakukan dengan menunjukkan bahwa
berkorespondensi satu-satu dengan , berkorespondensi satu-satu
dengan , dan berkorespondensi satu-satu dengan . Fungsi f
dibatasi pada , sehingga fungsi f menjadi fungsi bijektif dari ke .
Hal ini akan dibuktikan melalui dua hal sebagai berikut:
AA
AB BA
BB ∞A ∞B
AA AA AB
52
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
1. Jika a ∈ maka f(a) ∈ , dan AA AB
2. (∀b ∈ ) (∃a ∈ ) f(a) = b AB AA
Akan dibuktikan (1) terlebih dahulu. Andaikan a ∈ , maka proses yang
diberikan pada a, berakhir pada himpunan A. Misalkan proses diberikan
pada f(a). Langkah pertama ini akan kembali pada a, dan akan dilanjutkan
dengan proses yang diberikan pada a dan diakhiri pada himpunan A,
sehingga f(a) ∈ . Sekarang akan dibuktikan (2). Andaikan b ∈ , maka
proses yang diberikan pada b, berakhir pada himpunan A, dan secara khusus
proses ini harus melalui proses pertama (atau proses ini akan berakhir pada
himpunan B dengan elemen b sendiri), sehingga, b = f(a) untuk suatu a ∈ A.
Tetapi proses yang diberikan pada a sama dengan proses lanjutan dari proses
yang diberikan pada b, sehingga proses ini berakhir pada himpunan A, maka
a ∈ . Jadi fungsi terbatas f : → adalah fungsi bijektif. Dengan
cara yang sama terbukti bahwa g : → adalah fungsi bijektif,
sehingga jelas bahwa : → adalah fungsi bijektif. Fungsi
f : → adalah fungsi bijektif, untuk fungsi f yang merupakan fungsi
injektif dan jika b ∈ , maka b = f(a) untuk suatu a ∈ A, karena proses
awal yang diberikan pada b, dan a ∈ . Hal ini terjadi karena proses yang
diawali dari a sama dengan proses yang diawali dari b, setelah langkah
pertama, dan proses ini tidak berakhir karena b ∈ .
AA
AB AB
AA AA AB
BB BA
1−g BA BB
∞A ∞B
∞B
∞A
∞B
Sekarang dapatlah didefinisikan fungsi F : A → B dengan
53
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
F(x) = ⎪⎩
⎪⎨
⎧
∈∈∈
−∞
B
A
AxxgAxxfAxxf
untuk)(untuk )(untuk )(
1
Akan ditunjukkan bahwa fungsi F : A → B adalah fungsi bijektif. Akan
ditunjukkan bahwa fungsi F adalah fungsi surjektif. Ambil sebarang y ∈ B.
Telah diketahui bahwa himpunan B dibagi menjadi tiga himpunan bagian
yang saling asing, yaitu , , dan . Demikian pula himpunan A,
dibagi menjadi tiga himpunan bagian yang saling asing, yaitu , , dan
. Selain itu telah dibuktikan bahwa fungsi f : → , f : →
, : → adalah fungsi-fungsi bijektif. Andaikan y ∈ , maka
y = f(x) untuk suatu x ∈ , andaikan y ∈ , maka y = (x) untuk suatu
x ∈ , dan andaikan y ∈ , maka y = f(x) untuk suatu x ∈ . Dengan
demikian selalu dapat ditemukan x ∈ A, dengan x merupakan salah satu
elemen dari , , atau , maka berlaku (∀y ∈ B ) (∃x ∈ A) y = F(x).
Terlihat bahwa fungsi F adalah fungsi surjektif. Sekarang akan ditunjukkan
bahwa fungsi F adalah fungsi injektif. Andaikan F(x) = F(y). Jika F(x) = f(x)
untuk x ∈ dan F(y) = f(y) untuk y ∈ , maka f(x) = f(y). Diketahui
f : → adalah fungsi bijektif. Jelas bahwa x = y untuk x, y ∈ .
Jika F(x) = (x) untuk suatu x ∈ dan F(y) = (y) untuk suatu y ∈
, maka (x) = (y). Diketahui : → adalah fungsi bijektif.
Jelas bahwa x = y untuk x, y ∈ , sehingga x = y untuk setiap x, y ∈ A,
dengan x, y merupakan salah satu elemen dari , , atau . Dengan
AB BB ∞B
AA BA
∞A AA AB ∞A
∞B 1−g BA BB AB
AA BB 1−g
BA ∞B ∞A
AA BA ∞A
AA AA
∞A ∞B ∞A
1−g BA 1−g
BA 1−g 1−g 1−g BA BB
BA
AA BA ∞A
54
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
demikian berlaku (∀x,y ∈ A) F(x) = F(y) ⇒ x = y. Terlihat bahwa fungsi F
adalah fungsi injektif. Jadi fungsi F : A → B adalah fungsi bijektif.
Teorema 3.3.5: Himpunan semua bilangan real R berkorespondensi satu-satu
dengan himpunan kuasa ℘(N).
Bukti:
Akan ditunjukkan bahwa interval terbuka I = (0,1) berkorespondensi satu-
satu dengan ℘(N), dan diketahui bahwa interval terbuka I = (0,1)
berkorespondensi satu-satu dengan himpunan semua bilangan real R. Harus
ditunjukkan bahwa ada fungsi-fungsi injektif f : (0,1) → ℘(N) dan
g : ℘(N) → (0,1). Didefinisikan fungsi f : (0,1) → ℘(N) sebagai berikut.
Diberikan X ⊆ N, dibangun suatu perluasan desimal 0, dengan ...210 aaa
⎩⎨⎧
∈∉
=XiXi
ai untuk 1untuk0
.
Andaikan f(X) = 0, . Jelas bahwa f adalah fungsi injektif, karena jika
f(X) = f(Y) = 0, ., maka i ∈ X ⇔ = 1 ⇔ i ∈ Y, sehingga X = Y,
maka ada fungsi injektif f : (0,1) → ℘(N). Sekarang didefinisikan fungsi
g : ℘(N) → (0,1), dan harus ditunjukkan bahwa fungsi g adalah fungsi
injektif. Perhatikan bahwa elemen-elemen dari (0,1) dapat dinyatakan secara
unik dalam bentuk desimal 0, ..., dengan 0 ≤ ≤ 9, sehingga bila
desimal diakhiri dengan 9 yang berulang, tidak diperbolehkan. Diberikan
x ∈ (0,1), ditulis x = 0, ... seperti di atas, dan g(x) = { ⎢k ∈ n}.
Andaikan g(x) = g(y), dengan x = 0, ... dan y = 0, ....
...210 aaa
...210 aaa ia
3210 nnnn kn
3210 nnnn kn k10
3210 mmmm 3210 nnnn
55
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Andaikan k ∈ n, maka ∈ g(x), sehingga ∈ g(y) juga.
Dengan demikian = untuk suatu i ∈ n. Karena dan
bilangan berdigit tunggal , pastilah k = i dan = , maka x = y, sehingga
fungsi g :℘(N) → (0,1) adalah fungsi injektif. Karena ada fungsi injektif
f : (0,1) → ℘(N) dan fungsi injektif g : ℘(N) → (0,1), dan berdasarkan
Teorema 3.3.4 maka ada korespondensi satu-satu antara himpunan semua
bilangan real R dengan himpunan kuasa ℘(N).
km k10 km k10
km k10 in i10 km in
km in
BAB IV
HIPOTESIS KONTINUUM
1. Bilangan Kardinal
56
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Bilangan asli biasanya mempunyai peran yang berbeda, yaitu sebagai tipe
urutan dalam urutan biasa dan sebagai ukuran dari suatu jumlah. Pada peranan
yang pertama disebut ordinal, yang tidak dibahas dalam tulisan ini, dan yang
kedua disebut kardinal. Pada himpunan hingga dua peranan tersebut secara umum
sama. Untuk himpunan takhingga barulah terlihat perbedaannya. Secara intuitif
bilangan kardinal dari himpunan A adalah suatu keadaan yang dimiliki oleh A dan
yang juga dimiliki oleh semua himpunan yang ekipoten dengan A. Bilangan
kardinal dari himpunan A dilambangkan dengan ⎢A ⎢, dan kemudian didefinisikan
sebagai berikut.
Definisi 4.1.1: Diberikan sebarang himpunan hingga A. Jika ada fungsi bijektif
f : {1,2,3,...,n} → A, maka bilangan kardinal himpunan A adalah n,
dan ditulis ⎢A ⎢ = n.
Jika A = φ, maka ⎢A ⎢ = 0.
Definisi 4.1.2: Bilangan kardinal pada himpunan hingga disebut kardinalitas
hingga, dan bilangan kardinal pada himpunan takhingga disebut
kardinalitas takhingga atau kardinalitas transfinit.
Definisi 4.1.3: Himpunan A dan himpunan B dikatakan mempunyai bilangan
kardinal (kardinalitas) yang sama bila dan hanya bila ada
korespondensi satu-satu dari A ke B.
Sifat bilangan kardinal pada sebarang himpunan dijelaskan dalam teorema sebagai
berikut.
57
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Teorema 4.1.1: Diberikan sebarang himpunan A. Maka bilangan kardinal
himpunan A lebih kecil daripada bilangan kardinal himpunan
kuasa ℘(A), ditulis ⎢A ⎢< ⎢℘(A) ⎢.
Bukti:
Diberikan sebarang himpunan A. Andaikan A = φ, maka ℘(A) = {φ}, ditulis
⎢A ⎢= 0 dan ⎢℘(A) ⎢= 1. Jadi untuk A = φ berlaku ⎢A ⎢< ⎢℘(A) ⎢. Andaikan
A ≠ φ. Didefinisikan fungsi g : A → ℘(A) dengan
g(x) = {x}, ∀x ∈ A.
Harus ditunjukkan bahwa fungsi g adalah fungsi injektif tetapi tidak bijektif.
Ambil sebarang Axx ∈21 , dengan g( ) = g( ). Diketahui bahwa
g( ) = { } dan g( ) = { }, sehingga { } = { }, maka = . Jadi
terbukti fungsi g adalah fungsi injektif. Andaikan fungsi g adalah fungsi
bijektif, maka untuk setiap x ∈ A ada g(x) ∈ ℘(A), sehingga g(x) ⊆ ℘(A).
Dengan demikian ada dua kemungkinan yaitu: x ∈ g(x) atau x ∉ g(x).
Didefinisikan himpunan
1x 2x
1x 1x 2x 2x 1x 2x 1x 2x
E = {x ∈ A ⎢x ∉ g(x)}.
Dengan demikian E ⊆ A, sehingga E ⊆ ℘(A). Karena fungsi g adalah fungsi
bijektif, maka fungsi g adalah fungsi surjektif, sehingga ada z ∈ A
sedemikian hingga g(z) = E. Menurut definisi himpunan E, z ∈ A bila dan
hanya bila z ∉ g(z). Padahal g(z) = E sehingga z ∈ E bila dan hanya bila
z ∉ E. Terjadi kontradiksi. Berarti pengadaian salah. Dengan demikian benar
58
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
bahwa fungsi g : A → ℘(A) adalah fungsi injektif tetapi tidak surjektif,
sehingga fungsi g : A → ℘(A) adalah fungsi yang tidak bijektif.
Jadi ⎢A ⎢< ⎢℘(A) ⎢.
Teorema 4.1.2: Jika A himpunan hingga dengan ⎢A ⎢ = m, maka ⎢℘(A) ⎢ = m2 .
Bukti:
Telah dibuktikan dalam Teorema 3.3.1 bahwa jika himpunan hingga A
memuat m elemen, maka himpunan kuasa ℘(A) memuat elemen.
Berdasarkan Definisi 4.1.3 maka ⎢℘(A) ⎢ = .
m2
m2
Bilangan kardinal pada himpunan takhingga sangat istimewa karena
mempunyai lambang-lambangnya sendiri. Adalah George Cantor yang
menentukan lambang dari bilangan kardinal takhingga. Ia menggunakan huruf
pertama dari abjad Hibrani yaitu ℵ (baca: ‘aleph’) dengan subskrip 0 untuk
melambangkan bilangan kardinal takhingga yang pertama, yang merupakan
kardinalitas dari himpunan semua bilangan asli N. Untuk melambangkan
kardinalitas himpunan semua bilangan real R digunakan huruf c. Hal ini
didefinisikan sebagai berikut.
Definisi 4.1.4: Bilangan kardinal dari N dilambangkan dengan (baca: ‘aleph
nol’). Bilangan kardinal dari R dilambangkan oleh c, dan disebut
0ℵ
kardinalitas kontinuum.
Teorema 4.1.3: Kardinalitas himpunan semua bilangan rasional Q adalah . 0ℵ
59
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Bukti:
Telah dibuktikan dalam Teorema 3.2.12 bahwa Q adalah himpunan
tercacah. Dengan demikian Q berkorespondensi satu-satu dengan N
sedemikian hingga ⎢Q ⎢= ⎢N ⎢= 0ℵ . Jadi terbukti bahwa kardinalitas semua
bilangan rasional Q adalah 0ℵ .
Teorema 4.1.4: Kardinalitas ℘(N) adalah c.
Bukti:
Telah dibuktikan dalam Teorema 3.3.5 bahwa ℘(N) berkorespondensi satu-
satu dengan R, sehingga ⎢℘(N) ⎢ = ⎢R ⎢ = c. Jadi terbukti bahwa
kardinalitas ℘(N) adalah c.
Telah dibuktikan bahwa kardinalitas himpunan kuasa himpunan hingga
yang memuat m elemen adalah . Pada sebarang himpunan, kardinalitas
himpunan kuasanya dijelaskan dalam teorema berikut ini.
m2
Teorema 4.1.5: Jika A sebarang himpunan, maka ⎢℘(A) ⎢ = A2 .
Berdasarkan Teorema 4.1.4 dan Teorema 4.1.5 di atas, dapat dibentuk
suatu hubungan antara dua bilangan kardinal takhingga, yaitu dan c sebagai
berikut.
0ℵ
Akibat 4.1.5: c = . 02ℵ
Bukti:
Berdasarkan Teorema 4.1.4 terbukti bahwa ⎢℘(N) ⎢= c, dan menurut
Definisi 4.1.4 ⎢N ⎢ = . Berdasarkan Teorema 4.1.5, ⎢℘(N) ⎢= . 0ℵ 02ℵ
Jadi c = . 02ℵ
60
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Dari setiap himpunan A dapat dibentuk himpunan kuasa ℘(A), dari setiap
himpunan ℘(A) dapat dibentuk himpunan kuasa ℘(℘(A)). Demikian seterusnya
selalu dapat dibentuk himpunan kuasa dari himpunan sebelumnya dan telah
dibuktikan bahwa ⎢A ⎢< ⎢℘(A) ⎢, maka berlaku ⎢A ⎢< ⎢℘(A) ⎢ < ⎢℘(℘(A)) ⎢ <
⎢℘(℘(℘(A))) ⎢ < .... Andaikan himpunan A hingga yang memuat n elemen,
maka ⎢A ⎢ = n dan ⎢℘(A) ⎢ = . Dengan demikian dapat dibentuk suatu barisan
bilangan kardinal hingga, yaitu n, , ..., dan berlaku n < < < ....
Andaikan himpunan A takhingga dan himpunan A berkorespondensi satu-satu
dengan N, maka ⎢A ⎢ = ⎢N ⎢ =
n2
n2 ,n22 n2
n22
0ℵ dan ⎢℘(A) ⎢ = . Oleh karena itu juga
dapat dibentuk suatu barisan bilangan kardinal takhingga, yaitu , , , ...,
dan berlaku pula < < < .... Menurut Definisi 4.1.3 dan Teorema
4.1.5, jika himpunan takhingga A berkorespondensi satu-satu dengan R, maka
⎢A ⎢ = ⎢R ⎢ = c atau dikatakan bahwa kardinalitas himpunan A adalah kardinalitas
kontinuum.
02ℵ
0ℵ 02ℵ 022ℵ
0ℵ 02ℵ 022ℵ
Beberapa contoh himpunan yang mempunyai kardinalitas kontinuum
adalah himpunan semua bilangan real, himpunan semua titik dalam interval
terbuka (0,1), dan himpunan semua bilangan irasional dalam interval terbuka
(0,1).
Berdasarkan hal-hal di atas, tumbuh sebuah dugaan yang kemudian
dinamakan Hipotesis Kontinuum, yang akan dibahas sebagai berikut.
2. Hipotesis Kontinuum
61
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Berawal dari suatu masalah yang diungkapkan oleh George Cantor pada
tahun 1874. Ia mendefinisikan kardinalitas dari N dan R, yang olehnya
dilambangkan dengan dan c, dan ia juga telah menunjukkan bahwa berlaku
sifat c = . Telah dibuktikan pula bahwa ℘(N) berkorespondensi satu-satu
dengan R dan ⎢N ⎢ < ⎢℘(N) ⎢, sehingga
0ℵ
02ℵ
0ℵ < c. Cantor menduga bahwa tidak ada
suatu bilangan kardinal x sedemikian hingga 0ℵ < x < c. Dugaan ini oleh Cantor
diberi nama Hipotesis Kontinuum.
Hipotesis ini pertama kali dimunculkan oleh Cantor pada tahun 1877,
setelah ia menemukan bahwa himpunan semua bilangan real R tidak dapat
dikorespondensikan satu-satu dengan himpunan semua bilangan asli N. Cantor
menduga bahwa kardinalitas himpunan semua bilangan real R merupakan
ketakhinggaan yang terletak satu tingkat di atas kardinalitas himpunan semua
bilangan asli N. adalah kardinalitas dari himpunan semua bilangan asli N atau
kardinalitas dari sebarang himpunan tercacah. Tingkat selanjutnya dari
ketakhinggaan adalah ,
0ℵ
1ℵ 2ℵ , 3ℵ , ... dan seterusnya. Telah diketahui bahwa
himpunan semua bilangan real R berkorespondensi satu-satu dengan semua titik
pada sebuah garis lurus, yaitu kontinuum, sehingga kardinalitas dari R oleh
Cantor dilambangkan sebagai c (dari continuum).
Pernyataan-pernyataan asli dari Cantor tentang Hipotesis Kontinuum atau
HK adalah sebagai berikut.
a. ⎢R ⎢ = 1ℵ
b. c = 1ℵ
62
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Cantor juga telah membuktikan bahwa ⎢℘(N) ⎢ = ⎢R ⎢, sehingga HK juga
dinyatakan sebagai berikut.
c. ⎢℘(N) ⎢ = 1ℵ
Untuk sebarang himpunan A yang diberikan, diketahui bahwa ⎢℘(A) ⎢ = A2 ,
sehingga ⎢℘(N) ⎢ = dan HK juga dinyatakan sebagai berikut. 02ℵ
d. = 02ℵ1ℵ
Pernyataan di atas disebut juga versi aritmatika dari HK.
Pada tahun 1908 Felix Hausdorff menyusun suatu bentuk umum dari HK
sebagai berikut.
Untuk sebarang bilangan kardinal αℵ berlaku αℵ2 = 1+ℵα .
Pernyataan di atas disebut Hipotesis Kontinuum Umum atau HKU.
Hipotesis Kontinuum Umum juga dinyatakan sebagai berikut:
{ ⎢N ⎢, ⎢℘(N) ⎢, ⎢℘(℘(N)) ⎢, ⎢℘(℘(℘(N))) ⎢, ...} = { 0ℵ , 1ℵ , , , ...}. 2ℵ 3ℵ
Bertahun-tahun lamanya Cantor dan para ahli matematika lain berusaha
untuk membuktikan HK, bahkan lewat negasinya juga, yaitu ¬HK. Sampai pada
akhirnya oleh Hilbert, Hipotesis Kontinuum diletakkan di tempat pertama dalam
daftar 23 masalah matematika yang penting untuk diselesaikan oleh para ahli
matematika abad ke-20.
Pada tahun 1938 Gödel membuat suatu perkembangan yang berarti dengan
membuktikan bahwa HK konsisten dengan ZFC (Teori Himpunan Zermelo-
Fraenkel dengan Aksioma Pilihan), dengan membentuk suatu model dari ZFC +
HK.
63
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Pada saat yang bersamaan Gödel juga membuktikan teoremanya yang
terkenal, yaitu Teorema Ketaklengkapan (Incompleteness Theorem) dan
menunjukkan bahwa ZFC adalah contoh dari suatu sistem yang tidak lengkap,
yang berarti bahwa ada pernyataan-pernyataan dalam teori himpunan itu yang
disebut pernyataan taktentu, yang tidak dapat dibuktikan kebenarannya ataupun
kesalahannya. Para ahli matematika menduga bahwa HK adalah suatu pernyataan
taktentu dalam ZFC. Tetapi hal ini tinggal hanya sebagai dugaan sampai tahun
1963.
Paul Cohen membangun suatu model dari ZFC + ¬HK, dan dengan model
Gödel yaitu ZFC + HK, menunjukkan bahwa HK adalah pernyataan yang bebas
dalam ZFC. Hal ini berarti bahwa baik HK atau ¬HK dapat ditambahkan sebagai
suatu teorema dari ZFC. Tetapi karena keduanya belum dapat dibuktikan
kesahihannya, para ahli matematika sampai saat ini masih berusaha membuktikan
teorema tersebut atau berusaha untuk menemukan teorema lain yang dengan tepat
dapat membantu proses pembuktian HK dengan lebih sempurna.
Sampai saat ini HK tinggal sebagai hipotesis yang unik dalam teori
himpunan, yaitu bahwa meskipun kesahihan pembuktian HK masih menjadi
perbincangan, HK dengan konsep kardinalitas dari kontinuumnya telah menjadi
inspirasi dalam pengembangan teori himpunan dan matematika pada umumnya.
BAB V
PENUTUP
64
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Himpunan, yang merupakan kumpulan dari obyek-obyek yang berbeda,
dinyatakan berdasarkan kesamaan sifat elemen-elemennya. Dua kelompok besar
himpunan adalah himpunan hingga dan himpunan takhingga. Himpunan A disebut
himpunan hingga jika A ≠ φ atau A berkorespondensi satu-satu dengan himpunan
{1,2,3,4,...., k} untuk suatu k ∈ N. Himpunan takhingga adalah himpunan tidak
kosong yang tidak berkorespondensi satu-satu dengan {1,2,3,4,...., k} untuk suatu
k ∈ N.
Himpunan tercacah dan himpunan taktercacah termasuk dalam himpunan
takhingga. Himpunan A disebut himpunan tercacah bila A berkorespondensi satu-
satu dengan himpunan semua bilangan asli N. Suatu himpunan apabila hingga
atau tercacah disebut himpunan terbilang.
Himpunan semua himpunan bagian dari himpunan A disebut himpunan
kuasa dari A. Dari setiap himpunan selalu dapat dibentuk himpunan kuasanya, dan
himpunan kuasa ℘(N) adalah himpunan taktercacah.
Himpunan A dikatakan mempunyai kardinalitas (bilangan kardinal) yang
sama dengan himpunan B, yaitu ⎢A ⎢= ⎢B ⎢, jika A berkorespondensi satu-satu
dengan B. Jika A adalah himpunan hingga dengan m elemen, yaitu ⎢A ⎢= m, maka
⎢℘(A) ⎢ = . Kardinalitas himpunan takhingga didasarkan pada sifat tercacah
atau taktercacahnya himpunan takhingga tersebut. Pada himpunan tercacah A, ⎢A ⎢
= ⎢N ⎢ = . Pada himpunan taktercacah B, ⎢B ⎢ = ⎢R ⎢ = c. Kardinalitas
himpunan taktercacah disebut kardinalitas kontinuum. Suatu hubungan antara c
m2
0ℵ
65
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
dan adalah c = . Timbul suatu dugaan bahwa tidak ada bilangan kardinal x
sedemikian hingga < x < c. Dugaan ini pertama kali dicetuskan oleh George
Cantor dan diberi nama Hipotesis Kontinuum. Pada Hipotesis Kontinuum Umum
dinyatakan bahwa berlaku
0ℵ 02ℵ
0ℵ
1+ℵα = atau selalu dapat ditemukan bilangan
kardinal yang lebih besar daripada bilangan kardinal sebelumnya.
αℵ2
DAFTAR PUSTAKA
66
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
Anglin, W.S.(1994). Mathematics: A Concise History and Philosophy. New York: Springer-Verlag.
Avelsgaard, Carol. (1990). Foundation for Advanced Mathematics. Illinois: Scott,
Foresman and Company.
Ciesielsky, Krzystof. (1997). Set Theory for The Working Mathematician. New York: Cambridge University Press.
Dunham, William. (1990). Journey Through Genius. New York: John Wiley & Sons, Inc.
Eccles, Peter. J. (1997). An Introduction to Mathematical Reasoning. New York: Cambridge University Press.
Fletcher, Peter. (1992). Foundation of Higher Mathematics. Massachussetts: PWS-Kent Publishing Company.
Gerstein, Larry J. (1996). Introduction to Mathematical Structure and Proofs. New York: Springer-Verlag.
Guillen, Michael. (1983). Bridges to Infinity. Los Angeles: Jeremy P. Tarcher, Inc.
Halmos, Paul R. (1960). Naive Set Theory. New York: Springer-Verlag.
Hamilton, A.G. (1982). Numbers, Sets, and Axioms. Cambridge: Cambridge University Press.
Hazewinkel, M. (1995). Encyclopaedia of Mathematics. Singapore: Toppan Company(s) Pte. Ltd.
Lipschutz, Seymour. (1989). Teori Himpunan. Jakarta: Penerbit Erlangga.
Lopez, Alex-Ortiz. (1998). The Continuum Hypothesis. http://daisy.uwaterloo.ca/~alopez.o/math-faq/ Lucas, John F. (1986). Introduction to Abstract Mathematics. California:
Wadsworth Publishing Company.
Maor Eli, (1991). To Infinity and Beyond. New Jersey: Princetown University Press.
McGough, Nancy. (1998). Infinite Ink: The Continuum Hypothesis.
67
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
http://www.ii.com/math/ch McGough, Nancy. (1998). The Continuum Hypothesis FAQ. http://www.ii.com/math/ch/faq Singh, Jagjit. (1972). Mathematical Ideas. London: Hutchison & Co (Publishers)
LTD.
Van Dalen, D. (1978). Sets: Naive, Axiomatic, and Applied. Oxford: Pergamon Press LTD.
68
PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI
top related