1A1 — Teori himpunan — Fondasi Teori Ukuran

©date1996

Pada 111E-111F saya membahas secara ringkas himpunan ‘terhitung’. Pendekatan di sana mengikuti jalur yang tampaknya paling singkat menuju fakta-fakta yang segera diperlukan, dan mungkin sudah selayaknya saya menunjukkan di sini jalur yang lebih lazim. Saya memanfaatkan kesempatan ini untuk mencantumkan beberapa notasi yang menurut saya praktis, tetapi tidak digunakan secara universal.

1A1A Notasi kurung siku

Saya menggunakan kurung siku \([\) dan \(]\) dalam berbagai cara; saya berharap konteks selalu memperjelas penafsiran yang dimaksud.

1A1Aa (a)

Untuk \(a\), \(b\in\Bbb R\), saya menulis

\([a,b]=\{x:a\le x\le b\}\), \(\ooint{a,b}=\{x:a<x<b\}\),

\(\coint{a,b}=\{x:a\le x<b\}\), \(\ocint{a,b}=\{x:a<x\le b\}\).

Ketika rumus-rumus ini muncul, wajar jika kita langsung menyimpulkan bahwa \(a<b\); tetapi sesekali berguna untuk menafsirkannya ketika \(b\le a\), dan dalam hal itu saya mengikuti rumus-rumus di atas secara harfiah, sehingga

\([a,a]=\{a\}\), \(\ooint{a,a}=\coint{a,a}=\ocint{a,a}=\emptyset\),

\([a,b]=\ooint{a,b}=\coint{a,b}=\ocint{a,b}=\emptyset\) jika \(b<a\).

1A1Ab (b)

Kita dapat menafsirkan rumus-rumus tersebut dengan \(a\) atau \(b\) yang tak hingga; sebagai contoh,

\(\ooint{-\infty,b}=\{x:x<b\}\), \(\ooint{a,\infty}=\{x:a<x\}\), \(\ooint{-\infty,\infty}=\Bbb R\),

\(\coint{a,\infty}=\{x:x\ge a\}\), \(\ocint{-\infty,b}=\{x:x\le b\}\),

dan bahkan

\([0,\infty]=\{x:x\in\Bbb R,\,x\ge 0\}\cup\{\infty\}\), \([-\infty,\infty]=\Bbb R\cup\{-\infty,\infty\}\).

1A1Ac (c)

Dengan kehati-hatian tertentu — karena masih ada pilihan-pilihan yang harus dibuat, yang lebih aman dinyatakan secara eksplisit ketika diperlukan — kita dapat menggunakan rumus serupa untuk ‘interval’ dalam ruang multidimensi \(\BbbR^r\); lihat, misalnya, 115A atau 136D; dan bahkan dalam himpunan terurut parsial umum, walaupun himpunan-himpunan ini belum akan penting bagi kita sebelum Jilid 3.

1A1Ad (d)

Barangkali saya perlu menjelaskan pilihan saya untuk menggunakan \(\ooint{a,b}\), \(\coint{a,b}\) alih-alih \((a,b)\), \([a,b)\), yang keduanya lebih lazim dan lebih sedap dipandang. Alasan pertama hanyalah karena rumus

\((1,2)\in\ooint{0,2}\times\ooint{1,3}\)

lebih mudah dipahami daripada bentuk padanannya. Secara umum, pilihan ini menghasilkan keseimbangan yang sedikit lebih baik antara banyaknya kemunculan \((\) dan \([\), bahkan dengan memperhitungkan penggunaan lebih lanjut dari \([\ldots]\) yang akan segera saya jelaskan.

1A1B Citra langsung dan citra balik

Sekarang saya menjelaskan penggunaan kurung siku yang sama sekali berbeda, yang termasuk dalam teori himpunan abstrak, bukan teori sistem bilangan real.

1A1Ba (a)

Jika \(f\) adalah suatu fungsi dan \(A\) suatu himpunan, saya menulis

\(f[A]=\{f(x):x\in A\cap\dom f\}\)

untuk citra langsung \(A\) oleh \(f\). Perhatikan bahwa walaupun \(A\) sering kali merupakan subhimpunan dari domain \(f\), hal ini tidak diasumsikan.

1A1Bb (b)

Jika \(f\) adalah suatu fungsi dan \(B\) suatu himpunan, saya menulis

\(f^{-1}[B]=\{x:x\in\dom f,\,f(x)\in B\}\)

untuk citra balik \(B\) oleh \(f\). Kali ini penting untuk memperhatikan bahwa tidak ada anggapan bahwa \(f\) injektif, atau bahwa \(f^{-1}\) merupakan suatu fungsi; rumus \(f^{-1}[\,\,]\) diberi makna yang tidak bergantung pada makna apa pun dari ungkapan \(f^{-1}\). Namun, mudah dilihat bahwa ketika \(f\) injektif, sehingga kita mempunyai fungsi invers sejati \(f^{-1}\) (yang didefinisikan pada himpunan nilai \(f\), yaitu \(f[\dom f]\)), maka \(f^{-1}[B]\), sebagaimana didefinisikan di sini, sama dengan penafsirannya menurut (a).

1A1Bc (c)

Sekarang andaikan bahwa \(R\) merupakan suatu relasi, yaitu suatu himpunan pasangan terurut, dan \(A\), \(B\) adalah himpunan. Maka saya menulis

\(R[A]=\{y:\,\exists\,x\in A\) sedemikian sehingga \((x,y)\in R\}\),

\(R^{-1}[B]=\{x:\,\exists\,y\in B\) sedemikian sehingga \((x,y)\in R\}\).

Jika kita menulis

\(R^{-1}=\{(y,x):(x,y)\in R\}\),

maka kita memperoleh penafsiran lain untuk \(R^{-1}[B]\) yang sama dengan penafsiran yang baru diberikan. Selain itu, jika \(R\) merupakan grafik suatu fungsi \(f\), yaitu jika untuk setiap \(x\) terdapat paling banyak satu \(y\) sedemikian sehingga \((x,y)\in R\), maka rumus-rumus di sini sama dengan rumus-rumus dalam (a)-(b) di atas.

1A1Bd (d)

(Bagian berikut ditujukan khusus kepada para pembaca yang telah diajari untuk membedakan kata ‘himpunan’ dan ‘kelas’.) Saya telah menggunakan kata ‘himpunan’ lebih dari sekali di atas. Namun, hal itu semata- mata demi keluwesan ungkapan. Rumus-rumus yang sama dapat digunakan dengan kelas-kelas sembarang, walaupun dalam beberapa teori himpunan ungkapan yang terlibat mungkin tidak diakui sebagai ‘suku’ dalam arti teknis.

1A1C Himpunan terhitung

Dalam 111Fa saya mendefinisikan ‘himpunan terhitung’ sebagai berikut: suatu himpunan \(K\) terhitung jika himpunan itu kosong atau terdapat suatu fungsi surjektif dari \(\Bbb N\) ke \(K\). Rumusan yang lebih lazim mengatakan bahwa suatu himpunan \(K\) terhitung jika dan hanya jika himpunan itu berhingga atau terdapat suatu bijeksi antara \(\Bbb N\) dan \(K\). Jadi, saya perlu segera memeriksa bahwa kedua rumusan ini setara.

1A1D Proposisi

Misalkan \(K\) suatu himpunan. Maka pernyataan- pernyataan berikut ekuivalen:

(i) \(K\) kosong atau terdapat suatu surjeksi dari \(\Bbb N\) ke \(K\);

(ii) \(K\) berhingga atau terdapat suatu bijeksi antara \(\Bbb N\) dan \(K\);

(iii) terdapat suatu injeksi dari \(K\) ke \(\Bbb N\).

Bukti

(a)(i)\(\Rightarrow\)(iii) Andaikan (i). Jika \(K\) kosong, maka fungsi kosong merupakan suatu injeksi dari \(K\) ke \(\Bbb N\). Jika tidak, terdapat suatu surjeksi \(\phi:\Bbb N\to K\). Sekarang, untuk setiap \(k\in K\), tetapkan

\(\psi(k)=\min\{n:n\in\Bbb N\), \(\phi(n)=k\}\);

nilai ini selalu terdefinisi dengan baik karena \(\phi\) surjektif, sehingga \(\{n:\phi(n)=k\}\) tidak pernah kosong dan mesti mempunyai anggota terkecil. Karena \(\phi\psi(k)=k\) untuk setiap \(k\), \(\psi\) mesti injektif, dan karena itu merupakan injeksi yang diperlukan dari \(K\) ke \(\Bbb N\).

(b)(iii)\(\Rightarrow\)(ii) Andaikan (iii); misalkan \(\psi:K\to\Bbb N\) suatu injeksi, dan tetapkan \(A=\psi[K]\subseteq\Bbb N\). Maka \(\psi\) merupakan suatu bijeksi antara \(K\) dan \(A\). Jika \(K\) berhingga, tentu saja (ii) terpenuhi. Jika tidak, \(A\) juga mesti tak hingga. Definisikan \(\phi:A\to\Bbb N\) dengan menetapkan

\(\phi(m)=\#(\{i:i\in A,\,i<m\})\),

yaitu banyaknya anggota \(A\) yang kurang dari \(m\), untuk setiap \(m\in A\); dengan demikian, \(\phi(m)\) adalah posisi \(m\) jika anggota-anggota \(A\) diurutkan dari yang terkecil, dimulai dengan \(0\) untuk anggota terkecil \(A\). Maka \(\phi:A\to\Bbb N\) merupakan suatu bijeksi, karena \(A\) tak hingga, dan \(\phi\psi:K\to\Bbb N\) merupakan suatu bijeksi.

(c)(ii)\(\Rightarrow\)(i) Jika \(K\) kosong, jelas himpunan itu memenuhi (i). Jika \(K\) berhingga dan tak kosong, daftarkan anggota-anggotanya sebagai \(k_0,\ldots,k_n\); sekarang tetapkan \(\phi(i)=k_i\) untuk \(i\le n\), dan \(k_0\) untuk \(i>n\), sehingga diperoleh suatu surjeksi \(\phi:\Bbb N\to K\). Jika \(K\) tak hingga, terdapat suatu bijeksi dari \(\Bbb N\) ke \(K\), yang tentu saja juga merupakan suatu surjeksi dari \(\Bbb N\) ke \(K\). Jadi, (i) benar dalam semua kasus.

Catatan Dalam bukti di atas saya menyebut ‘fungsi kosong’. Fungsi ini mempunyai domain \(\emptyset\); setelah hal itu dinyatakan, aturan apa pun, atau tanpa aturan sama sekali, untuk menghitung fungsi tersebut akan memberikan hasil yang sama karena aturan itu tidak akan pernah diterapkan. Dengan menelaah perasaan Anda terhadap konstruksi ini, Anda dapat mengetahui sesuatu tentang sikap dasar Anda terhadap matematika. Anda mungkin merasa bahwa konstruksi ini merupakan sesuatu yang dibuat-buat dan tidak relevan, atau Anda mungkin merasa bahwa konstruksi ini sama perlunya dengan bilangan \(0\). Kedua perasaan itu sepenuhnya sah, dan matematikawan yang matang akan berganti-ganti di antara keduanya; tetapi harus saya katakan bahwa saya sendiri lebih sering condong pada perasaan yang kedua daripada yang pertama, dan bahwa ketika saya mengatakan ‘fungsi’ dalam risalah ini, biasanya kemungkinan fungsi kosong tetap ada dalam benak saya.

1A1E Sifat-sifat himpunan terhitung

Izinkan saya merangkum kembali sifat-sifat dasar himpunan terhitung:

(a) Jika \(K\) terhitung dan \(\phi:K\to L\) merupakan suatu surjeksi, maka \(L\) terhitung. Bukti. Jika \(K\) kosong maka \(L\) juga kosong. Jika tidak, terdapat suatu surjeksi \(\psi:\Bbb N\to K\), sehingga \(\phi\psi\) merupakan suatu surjeksi dari \(\Bbb N\) ke \(L\), dan \(L\) terhitung. ∎

1A1Eb (b)

Jika \(K\) terhitung dan \(\phi:L\to K\) merupakan suatu injeksi, maka \(L\) terhitung. Bukti. Menurut 1A1D(iii), terdapat suatu injeksi \(\psi:K\to\Bbb N\); sekarang \(\psi\phi:L\to\Bbb N\) injektif, sehingga \(L\) terhitung. ∎

1A1Ec (c)

Khususnya, setiap subhimpunan dari suatu himpunan terhitung adalah terhitung (seperti dalam 111F(b-i)).

1A1Ed (d)

Hasil kali Kartesius dari sejumlah berhingga himpunan terhitung adalah terhitung (111Fb(iii)-(iv)).

1A1Ee (e)

\(\Bbb Z\) terhitung. Bukti. Pemetaan \((m,n)\mapsto m-n:\Bbb N\times\Bbb N\to\Bbb Z\) bersifat surjektif. ∎

1A1Ef (f)

\(\Bbb Q\) terhitung. Bukti. Pemetaan \((m,n)\mapsto \bover{m}{n+1}:\Bbb Z\times\Bbb N\to\Bbb Q\) bersifat surjektif. ∎

1A1F

Ada satu lagi sifat mendasar yang patut dibedakan dari sifat-sifat ini karena sifat tersebut bergantung pada argumen yang sedikit lebih mendalam.

Teorema Jika \(\Cal K\) merupakan suatu keluarga terhitung yang terdiri atas himpunan-himpunan terhitung, maka

\(\bigcup\Cal K=\{x:\,\exists\,K\in\Cal K,\, x\in K\}\)

terhitung.

Bukti

Tetapkan

\(\Cal K'=\Cal K\setminus\{\emptyset\} =\{K:K\in\Cal K,\,K\ne\emptyset\}\);

maka \(\Cal K'\subseteq\Cal K\), sehingga himpunan ini terhitung, dan \(\bigcup\Cal K'=\bigcup\Cal K\). Jika \(\Cal K'=\emptyset\), maka

\(\bigcup\Cal K=\bigcup\Cal K'=\emptyset\)

jelas terhitung. Jika tidak, misalkan \(m\mapsto K_m:\Bbb N\to\Cal K'\) suatu surjeksi. Untuk setiap \(m\in\Bbb N\), \(K_m\) merupakan suatu himpunan terhitung tak kosong, sehingga terdapat suatu surjeksi \(n\mapsto k_{mn}:\Bbb N\to K_m\). Sekarang \((m,n)\mapsto k_{mn}:\Bbb N\times\Bbb N\to\bigcup\Cal K\) merupakan suatu surjeksi (jika \(k\in\bigcup\Cal K\), terdapat \(K\in\Cal K'\) sedemikian sehingga \(k\in K\); terdapat \(m\in\Bbb N\) sedemikian sehingga \(K=K_m\); terdapat \(n\in\Bbb N\) sedemikian sehingga \(k=k_{mn}\)). Jadi, \(\bigcup\Cal K\) terhitung, sebagaimana diperlukan.

1A1G Catatan

Saya memisahkan hasil ini dari fakta-fakta ‘elementer’ dalam 1A1E, antara lain karena hasil ini menggunakan asas argumen yang berbeda dari semua asas yang diperlukan untuk pembahasan sebelumnya. Di tengah bukti saya menulis ‘sehingga terdapat suatu surjeksi \(n\mapsto k_{mn}:\Bbb N\to K_m\)’. Keberadaan suatu surjeksi dari \(\Bbb N\) ke \(K_m\) memang mengikuti pernyataan tepat sebelumnya, yaitu ‘\(K_m\) merupakan suatu himpunan terhitung tak kosong’. Langkah terselubungnya terletak pada pemberian nama secara langsung kepada surjeksi semacam itu sebagai ‘\(n\mapsto k_{mn}\)’. Tentu mungkin ada banyak surjeksi dari \(\Bbb N\) ke \(K_m\) — bahkan, pada umumnya, akan ada tak terhitung banyaknya — dan pada hakikatnya yang saya lakukan di sini ialah memilih salah satunya secara sembarang. Pilihan itu harus sembarang karena saya bekerja dalam konteks yang sepenuhnya abstrak, dan meskipun dalam setiap penerapan khusus teorema ini mungkin terdapat suatu surjeksi alami untuk digunakan, saya tidak mempunyai cara untuk meramalkan pendekatan apa, kalau pun ada, yang dapat menyediakan kriteria untuk menentukan satu fungsi tertentu di sini. Sejak setidaknya zaman Euklides, salah satu metode dasar argumen matematika ialah kesediaan kita untuk memberi nama kepada suatu objek, sebuah ‘titik umum’ atau ‘bilangan sembarang’, tanpa menentukan secara persis objek mana yang kita namai. Namun, di sini saya secara serentak memilih tak hingga banyak objek, masing-masing secara sembarang dari suatu himpunan tertentu. Ini merupakan penggunaan Aksioma Pilihan.

Saya tidak ingat pernah mendapati mahasiswa yang mengkritik argumen berbentuk seperti argumen dalam 1A1F dengan alasan bahwa argumen itu menggunakan suatu asas baru yang mungkin tidak sah; saya yakin tidak pernah terpikir oleh saya bahwa ada sesuatu yang patut dipersoalkan dalam kasus-kasus semacam ini sampai seseorang menunjukkannya. Jika Anda merasa bahwa pembahasan semacam ini tidak relevan dengan minat matematika Anda sendiri, Anda tentu dapat melewatinya, setidaknya sampai Anda mencapai Jilid 5. Sistem-sistem matematika yang di dalamnya aksioma pilihan tidak berlaku telah dipelajari; sistem-sistem itu sangat menarik, tetapi sejauh ini tetap berada di pinggiran bidang ini. Sistem-sistem yang di dalamnya aksioma pilihan gagal sedemikian rupa sehingga gabungan terhitung dari himpunan-himpunan terhitung kadang-kadang tidak terhitung mempunyai watak tersendiri, dan khususnya teori ukuran Lebesgue berubah secara mendasar; saya akan membahas kemungkinan ini dalam Bab 56 Jilid 5.

Untuk komentar singkat mengenai cara-cara lain menggunakan aksioma pilihan, lihat 134C.

1A1H Beberapa himpunan tak terhitung

Tentu saja tidak semua himpunan terhitung. Dalam 114G/115G saya menyatakan bahwa semua subhimpunan terhitung dari ruang Euklides terabaikan terhadap ukuran Lebesgue; akibatnya, setiap himpunan yang tidak terabaikan — misalnya setiap interval tak-sepele — mesti tak terhitung. Namun, barangkali akan membantu jika saya menyajikan di sini argumen elementer yang menunjukkan bahwa \(\Bbb R\) dan \(\Cal P\Bbb N\) tidak terhitung.

(a) Tidak ada surjeksi dari \(\Bbb N\) ke \(\Bbb R\). Bukti. Misalkan \(n\mapsto a_n:\Bbb N\to\Bbb R\) suatu fungsi sembarang. Untuk setiap \(n\in\Bbb N\), nyatakan \(a_n\) dalam bentuk desimal sebagai \(a_n=k_n + 0\cdot\epsilon_{n1}\epsilon_{n2}\ldots =k_n+\sum_{i=1}^{\infty}10^{-i}\epsilon_{ni}\), dengan \(k_n\in\Bbb Z\) bilangan bulat terbesar yang tidak melebihi \(a_n\), dan setiap \(\epsilon_{ni}\) suatu bilangan bulat antara \(0\) dan \(9\); sebagai konvensi, jika \(a_n\) kebetulan mempunyai bentuk desimal berhingga, gunakan ekspansi berhingga tersebut, sehingga \(\epsilon_{ni}\) akhirnya selalu \(0\), bukan akhirnya selalu \(9\). Sekarang definisikan \(\epsilon_i\), untuk \(i\ge 1\), dengan menetapkan bahwa \[\begin{aligned}\epsilon_i&=6\text{ jika }\epsilon_{ii}<6,\\ &=5\text{ jika }\epsilon_{ii}\ge 6.\\\end{aligned}\] Tinjau \(a=k_0+1+\sum_{i=1}^{\infty}10^{-i}\epsilon_i\), sehingga \(a=k_0+1+0\cdot\epsilon_1\epsilon_2\ldots\) dalam bentuk desimal. Saya menyatakan bahwa \(a\ne a_n\) untuk setiap \(n\). Tentu saja \(a\ne a_0\) karena \(a_0<k_0+1\le a\). Jika \(n\ge 1\), maka \(\epsilon_n\ne\epsilon_{nn}\); karena tidak ada \(\epsilon_i\) yang sama dengan \(0\) ataupun \(9\), tidak terdapat ekspansi desimal lain untuk \(a\), sehingga ekspansi \(a_n=k_n+0\cdot\epsilon_{n1}\epsilon_{n2}\ldots\) tidak dapat merepresentasikan \(a\), dan \(a\ne a_n\). Dengan demikian saya telah membangun suatu bilangan real yang tidak terdapat dalam daftar \(a_0,a_1,\ldots\). Karena \(\sequencen{a_n}\) sembarang, tidak ada surjeksi dari \(\Bbb N\) ke \(\Bbb R\). ∎

Jadi, \(\Bbb R\) tak terhitung.

1A1Hb (b)

Tidak ada surjeksi dari \(\Bbb N\) ke himpunan kuasanya \(\Cal P\Bbb N\). Bukti. Misalkan \(n\mapsto A_n:\Bbb N\to\Cal P\Bbb N\) suatu fungsi sembarang. Tetapkan \(A=\{n:n\in\Bbb N,\,n\notin A_n\}\). Jika \(n\in\Bbb N\), maka entah \(n\in A_n\), yang mengakibatkan \(n\notin A\), atau \(n\notin A_n\), yang mengakibatkan \(n\in A\). Jadi, dalam kedua kasus kita mempunyai \(n\in A\symmdiff A_n\), sehingga \(A\ne A_n\). Karena \(n\) sembarang, \(A\notin\{A_n:n\in\Bbb N\}\) dan \(n\mapsto A_n\) bukan suatu surjeksi. Karena \(\sequencen{A_n}\) sembarang, tidak ada surjeksi dari \(\Bbb N\) ke \(\Cal P\Bbb N\). ∎

Jadi, \(\Cal P\Bbb N\) juga tak terhitung.

1A1I Catatan

Sesungguhnya terdapat suatu bijeksi antara \(\Bbb R\) dan \(\Cal P\Bbb N\) (2A1Ha); dengan demikian, ketakterhitungan keduanya dapat dibuktikan hanya dengan salah satu dari argumen di atas.

1A1J Notasi

Untuk memperjelas, saya nyatakan di sini bahwa Saya akan mengatakan bahwa suatu keluarga himpunan \(\Cal A\) merupakan suatu partisi dari suatu himpunan \(X\) jika \(\Cal A\) merupakan penutup saling lepas dari \(X\), yaitu \(X=\bigcup\Cal A\) dan \(A\cap A'=\emptyset\) untuk semua \(A\), \(A'\in\Cal A\) yang berlainan; khususnya, himpunan kosong boleh termasuk atau tidak termasuk dalam \(\Cal A\). Demikian pula, suatu keluarga berindeks \(\familyiI{A_i}\) merupakan suatu partisi dari \(X\) jika \(\bigcup_{i\in I}A_i=X\) dan \(A_i\cap A_j=\emptyset\) untuk semua \(i\), \(j\in I\) yang berlainan; sekali lagi, satu atau beberapa \(A_i\) boleh kosong.

Latihan

1A1-notes Catatan penutup untuk Bagian 1A1

Gagasan-gagasan dalam 1A1C-1A1I pada dasarnya berasal dari G.F.Cantor. Konsep-konsep ini mendasar bagi teori himpunan modern, dan bahkan bagi bagian-bagian yang sangat luas dari matematika murni modern. Catatan-catatan di atas baru sedikit sekali menggambarkan kesuburan luar biasa dari gagasan-gagasan ini, yang memerlukan buku tersendiri agar dapat diuraikan secara semestinya; satu-satunya tujuan saya di sini ialah mencoba menjelaskan bagian-bagian kecil dari bidang ini yang diperlukan dalam jilid sekarang. Dalam jilid-jilid selanjutnya saya akan menyajikan hasil-hasil yang menggunakan gagasan-gagasan yang jauh lebih maju, yang akan saya bahas dalam lampiran-lampiran jilid tersebut.