Himpunan terhitung

Himpunan matematis yang dapat dihitungTemplat:SHORTDESC:Himpunan matematis yang dapat dihitung

Dalam matematika, suatu himpunan dikatakan terhitung,^[1]^[2]^[3] tercacah,^[4] atau terbilang^[5] jika himpunannya berhingga atau dapat dibuat korespondensi satu-ke-satu dengan himpunan bilangan asli.^[6] Dengan kata lain, suatu himpunan disebut terhitung jika terdapat suatu fungsi injektif dari himpunan tersebut ke bilangan asli; ini artinya setiap elemen pada himpunan tersebut dapat dilabeli dengan tepat satu bilangan asli, atau elemen-elemen dari himpunannya dapat dihitung satu demi satu, walau mungkin saja proses perhitungannya mustahil selesai akibat jumlah elemen yang tak hingga banyaknya.

Dengan menggunakan istilah teknis, jika diasumsikan aksioma pemilihan terhitung, suatu himpunan disebut terhitung jika kardinalitasnya (banyaknya elemen pada himpunan tersebut) tidak lebih dari kardinalitas bilangan asli. Suatu himpunan terhitung yang bukan merupakan himpunan berhingga disebut terhitung tak terhingga.

Konsep ini diatribusikan kepada Georg Cantor, yang membuktikan keujudan dari himpunan-himpunan tak terhitung, yaitu himpunan-himpunan yang bukan merupakan himpunan terhitung; seperti contohnya himpunan semua bilangan riil.

Catatan penggunaan istilah

Walaupun artikel ini menggunakan istilah "terhitung" dan "terhitung tak terhingga" yang cukup umum digunakan, kedua istilah tersebut tidaklah universal.^[7] Beberapa referensi menggunakan istilah terhitung sebagai apa yang dimaksud disini sebagai terhitung tak terhingga, dan paling banyak terhitung sebagai apa yang dimaksud disini sebagai terhitung.^[8]^[9]

Istilah enumerable^[10] dan denumerable^[11]^[12]^[13] juga terkadang digunakan untuk berturut-turut menyatakan himpunan terhitung dan terhitung.^[14]

Definisi

Suatu himpunan H {\displaystyle H} $H$ dikatakan terhitung jika:

Himpunan H {\displaystyle H} $H$ adalah himpunan hingga atau terhitung tak berhingga.^[11]
Kardinalitasnya (dinotasikan dengan | H | {\displaystyle \left|H\right|} $\left|H\right|$ ) tidak lebih dari ℵ 0 {\displaystyle \aleph _{0}} $\aleph _{0}$ (alef nol), yaitu kardinalitas dari himpunan bilangan asli N {\displaystyle \mathbb {N} } $\mathbb {N}$ .^[15]
Terdapat suatu fungsi injektif dari H {\displaystyle H} $H$ ke N {\displaystyle \mathbb {N} } $\mathbb {N}$ .^[16]^[17]
Himpunan H {\displaystyle H} $H$ merupakan himpunan kosong atau terdapat suatu fungsi surjektif dari N {\displaystyle \mathbb {N} } $\mathbb {N}$ ke H {\displaystyle H} $H$ .^[17]
Terdapat suatu fungsi bijektif antara H {\displaystyle H} $H$ dan suatu himpunan bagian dari N {\displaystyle \mathbb {N} } $\mathbb {N}$ .^[18]

Semua definisi di atas ekuivalen satu sama lain.

Suatu himpunan H {\displaystyle H} $H$ dikatakan terhitung tak terhingga jika:

Kardinalitasnya (yaitu | H | {\displaystyle \left|H\right|} $\left|H\right|$ ) sama dengan ℵ 0 {\displaystyle \aleph _{0}} $\aleph _{0}$ .^[15]
Terdapat suatu pemetaan injektif dan surjektif antara H {\displaystyle H} $H$ dan N {\displaystyle \mathbb {N} } $\mathbb {N}$ .
Himpunan H {\displaystyle H} $H$ memiliki korespondensi satu-ke-satu dengan N {\displaystyle \mathbb {N} } $\mathbb {N}$ .^[19]
Elemen dari himpunan H {\displaystyle H} $H$ dapat disusun dalam suatu barisan tak terhingga a 0 , a 1 , a 2 , … {\displaystyle a_{0},\,a_{1},\,a_{2},\,\ldots } $a_{0},\,a_{1},\,a_{2},\,\ldots$ , dengan a i ≠ a j {\displaystyle a_{i}\neq a_{j}} $a_{i}\neq a_{j}$ ketika i ≠ j {\displaystyle i\neq j} $i\neq j$ , dan setiap elemen pada H {\displaystyle H} $H$ terdaftar.^[20]^[21]

Suatu himpunan disebut tak terhitung jika himpunannya tidak terhitung, atau dengan kata lain, kardinalitasnya lebih dari ℵ 0 {\displaystyle \aleph _{0}} $\aleph _{0}$ .^[15]

Sejarah

Pada tahun 1874, dalam artikel teori himpunan pertama miliknya, Cantor membuktikan bahwa himpunan bilangan riil merupakan himpunan tak terhitung, yang menunjukkan bahwa tidak semua himpunan tak terhingga merupakaan himpunan terhitung.^[22] Pada tahun tersebut, Cantor menggunakan korespondensi satu-ke-satu untuk mendefinisikan dan membandungkan kardinalitas.^[23] Pada tahun 1883, beliau memperluas bilangan asli dengan bilangan ordinal takhingga miliknya, dan menggunakan himpunan ordinal untuk membuat tak terhingga banyaknya himpunan yang memiliki kardinalitas yang beda-beda.^[24]

Pengantar

Himpunan adalah sekumpulan elemen, dan dapat dinyatakan dengan berbagai cara, salah satunya ialah dengan mendaftar anggota-anggotanya; sebagai contoh, himpunan yang terdiri dari bilangan 3 {\displaystyle 3} $3$ , 5 {\displaystyle 5} $5$ , dan 12 {\displaystyle 12} $12$ dapat dituliskan sebagai { 3 , 5 , 12 } {\displaystyle \left\{3,\,5,\,12\right\}} $\left\{3,\,5,\,12\right\}$ , yang disebut sebagai bentuk roster.^[25] Akan tetapi, hal ini hanya efektif untuk himpunan yang kecil. Untuk himpunan yang besar, metode roster akan memakan waktu yang lama serta rawan terjadi galat. Daripada mendaftar setiap elemen satu per satu, terkadang tanda elipsis (" … {\displaystyle \ldots } $\ldots$ ") digunakan untuk mewakilkan banyak elemen di antara elemen awal dan akhir pada suatu himpunan, jika penulis yakin bahwa pembaca dapat menebak dengan mudah apa yang tanda elipsis wakilkan; sebagai contoh, { 1 , 2 , 3 , … , 99 , 100 } {\displaystyle \left\{1,\,2,\,3,\,\ldots ,\,99,\,100\right\}} $\left\{1,\,2,\,3,\,\ldots ,\,99,\,100\right\}$ mungkin saja menyatakan himpunan bilangan bulat dari 1 {\displaystyle 1} $1$ sampai dengan 100 {\displaystyle 100} $100$ . Dalam kasus ini, semua elemennya masih mungkin didaftarkan, sebab banyak elemennya berhingga. Jika setiap elemen dari himpunan 1 {\displaystyle 1} $1$ , 2 {\displaystyle 2} $2$ , dan seterusnya, sampai n {\displaystyle n} $n$ diberi label, maka hal ini menjadi definisi dari "himpunan berukuran n {\displaystyle n} $n$ ".

Beberapa himpunan merupakan himpunan tak terhingga; himpunan-himpunan ini memiliki lebih dari n {\displaystyle n} $n$ elemen, dengan n {\displaystyle n} $n$ adalah sembarang bilangan asli. Tidak peduli seberapa besar nilai n {\displaystyle n} $n$ nya (seperti n = 10 10 100 {\displaystyle n=10^{10^{100}}} $n=10^{10^{100}}$ ), himpunan tak terhingga memiliki lebih dari n {\displaystyle n} $n$ elemen. Misalnya, himpunan bilangan asli, yang dinyatakan sebagai { 1 , 2 , 3 , 4 , … } {\displaystyle \left\{1,\,2,\,3,\,4,\,\ldots \right\}} $\left\{1,\,2,\,3,\,4,\,\ldots \right\}$ ,^[6] memiliki tak hingga banyaknya elemen, sehingga ukuran himpunannya tidak dapat dinyatakan dengan bilangan asli apa pun. Salah satu hal yang wajar dilakukan ialah membagi himpunan-himpunan yang ada menjadi beberapa kelas: Satukan semua himpunan yang memiliki satu elemen; semua himpunan yang memiliki dua elemen; ...; dan terakhir, satukan semua himpunan tak hingga dan anggaplah mereka memiliki ukuran yang sama. Cara pandang ini dapat dilakukan untuk himpunan terhitung tak terhingga, dan menjadi asumsi yang berlaku sebelum penemuan Geog Cantor. Sebagai contoh, terdapat tak hingga banyaknya bilangan ganjil, tak hingga banyaknya bilangan genap, dan tak hingga banyaknya bilangan bulat secara keseluruhan. Semua himpunan tadi dapat dipandang memiliki ukuran yang sama, sebab setiap bilangan genap dapat dilabeli dengan tunggal menggunakan suatu bilangan bulat: n ⋮ − 2 ↦ − 4 − 1 ↦ − 2 0 ↦ 0 1 ↦ 2 2 ↦ 4 n ⋮ {\displaystyle {\begin{aligned}&{\phantom {n}}\vdots \\-2&\mapsto -4\\-1&\mapsto -2\\0&\mapsto 0\\1&\mapsto 2\\2&\mapsto 4\\&{\phantom {n}}\vdots \end{aligned}}} ${\begin{aligned}&{\phantom {n}}\vdots \\-2&\mapsto -4\\-1&\mapsto -2\\0&\mapsto 0\\1&\mapsto 2\\2&\mapsto 4\\&{\phantom {n}}\vdots \end{aligned}}$ dan secara umum, n ↦ 2 n {\displaystyle n\mapsto 2n} $n\mapsto 2n$ (lihat gambar di kanan). Proses yang baru saja terjadi ialah mengonstruksikan korespondensi satu-ke-satu (atau bijeksi), yaitu suatu fungsi yang menghubungkan dua himpunan dengan syarat setiap elemen pada masing-masing himpunan dikawankan dengan tepat satu elemen pada himpunan lainnya. Gagasan matematika dari "ukuran", kardinalitas, adalah dua himpunan memiliki ukuran yang sama jika dan hanya jika terdapat suatu fungsi bijektif yang menghubungkan keduanya. Semua himpunan yang memiliki korespondensi satu-ke-satu dengan bilangan bulat disebut sebagai himpunan terhitung tak terhingga dan kardinalitasnya dinotasikan dengan ℵ 0 {\displaystyle \aleph _{0}} $\aleph _{0}$ .

Georg Cantor menunjukkan bahwa tidak semua himpunan tak terhingga merupakan himpunan terhitung tak terhingga. Misalnya, himpunan bilangan riil tidak dapat dibuat korespondensi satu-ke-satu dengan bilangan asli. Himpunan bilangan riil memiliki kardinalitas yang lebih dari himpunan bilangan asli, dan disebut sebagai tak terhitung.

Kajian formal

Berdasarkan definisi, suatu himpunan H {\displaystyle H} $H$ disebut terhitung jika terdapat suatu fungsi bijektif dari H {\displaystyle H} $H$ ke himpunan bagian dari bilangan asli N = { 1 , 2 , 3 , 4 , … } {\displaystyle \mathbb {N} =\left\{1,\,2,\,3,\,4,\,\ldots \right\}} $\mathbb {N} =\left\{1,\,2,\,3,\,4,\,\ldots \right\}$ . Sebagai contoh, didefinisikan pemetaan a ↔ 1 b ↔ 2 c ↔ 3 {\displaystyle {\begin{aligned}a&\leftrightarrow 1\\b&\leftrightarrow 2\\c&\leftrightarrow 3\end{aligned}}} ${\begin{aligned}a&\leftrightarrow 1\\b&\leftrightarrow 2\\c&\leftrightarrow 3\end{aligned}}$ Oleh karena setiap elemen dari himpunan H = { a , b , c } {\displaystyle H=\left\{a,\,b,\,c\right\}} $H=\left\{a,\,b,\,c\right\}$ dikawankan dengan tepat satu elemen dari himpunan { 1 , 2 , 3 } {\displaystyle \left\{1,\,2,\,3\right\}} $\left\{1,\,2,\,3\right\}$ (dan begitu juga sebaliknya), maka pemetaannya bersifat bijektif, dan menjadi bukti bahwa H {\displaystyle H} $H$ adalah himpunan terhitung. Dengan cara serupa, maka dapat ditunjukkan bahwa setiap himpunan berhingga merupakan himpunan terhitung.

Pada kasus himpunan tak terhingga, suatu himpunan H {\displaystyle H} $H$ dikatakan terhitung tak terhingga jika terdapat suatu fungsi bijektif dari H {\displaystyle H} $H$ ke himpunan bilangan asli N {\displaystyle \mathbb {N} } $\mathbb {N}$ . Sebagai contoh, himpunan bilangan genap positif { 2 , 4 , 6 , 8 , … } {\displaystyle \left\{2,\,4,\,6,\,8,\,\ldots \right\}} $\left\{2,\,4,\,6,\,8,\,\ldots \right\}$ merupakan himpunan terhitung tak terhingga, sebab terdapat korespondensi satu-ke-satu n ↔ 2 n {\displaystyle n\leftrightarrow 2n} $n\leftrightarrow 2n$ sebagai berikut: 1 ↔ 2 2 ↔ 4 3 ↔ 6 4 ↔ 8 n ⋮ {\displaystyle {\begin{aligned}1&\leftrightarrow 2\\2&\leftrightarrow 4\\3&\leftrightarrow 6\\4&\leftrightarrow 8\\&{\phantom {n}}\vdots \end{aligned}}} ${\begin{aligned}1&\leftrightarrow 2\\2&\leftrightarrow 4\\3&\leftrightarrow 6\\4&\leftrightarrow 8\\&{\phantom {n}}\vdots \end{aligned}}$ Setiap himpunan bagian dari bilangan asli merupakan himpunan terhitung. Secara umum,

Teorema — Setiap himpunan bagian dari suatu himpunan terhitung merupakan himpunan terhitung.^[26]

Himpunan semua pasangan terurut (atau hasil-kali Kartesius) dari himpunan bilangan cacah W × W {\displaystyle \mathbb {W} \times \mathbb {W} } $\mathbb {W} \times \mathbb {W}$ merupakan himpunan terhitung tak terhingga. Hasil pemetaannya dapat dilihat pada gambar di bagian kanan dan dilakukan sebagai berikut 0 ↔ ( 0 , 0 ) 1 ↔ ( 1 , 0 ) 2 ↔ ( 0 , 1 ) 3 ↔ ( 2 , 0 ) 4 ↔ ( 1 , 1 ) 5 ↔ ( 0 , 2 ) 6 ↔ ( 3 , 0 ) {\displaystyle {\begin{aligned}0&\leftrightarrow \left(0,\,0\right)\\1&\leftrightarrow \left(1,\,0\right)\\2&\leftrightarrow \left(0,\,1\right)\\3&\leftrightarrow \left(2,\,0\right)\\4&\leftrightarrow \left(1,\,1\right)\\5&\leftrightarrow \left(0,\,2\right)\\6&\leftrightarrow \left(3,\,0\right)\end{aligned}}} ${\begin{aligned}0&\leftrightarrow \left(0,\,0\right)\\1&\leftrightarrow \left(1,\,0\right)\\2&\leftrightarrow \left(0,\,1\right)\\3&\leftrightarrow \left(2,\,0\right)\\4&\leftrightarrow \left(1,\,1\right)\\5&\leftrightarrow \left(0,\,2\right)\\6&\leftrightarrow \left(3,\,0\right)\end{aligned}}$ Pemetaan ini meliput seluruh pasangan terurut.

Bentuk pemetaan segitiga ini dapat diperumum secara rekursif menjadi bilangan asli rangkap- n {\displaystyle n} $n$ , yaitu ( a 1 , a 2 , a 3 , … , a n ) {\displaystyle \left(a_{1},\,a_{2},\,a_{3},\,\ldots ,\,a_{n}\right)} $\left(a_{1},\,a_{2},\,a_{3},\,\ldots ,\,a_{n}\right)$ dengan a k , n ∈ N {\displaystyle a_{k},\,n\in \mathbb {N} } $a_{k},\,n\in \mathbb {N}$ untuk setiap k ∈ { 1 , 2 , 3 , … , n } {\displaystyle k\in \left\{1,\,2,\,3,\,\ldots ,\,n\right\}} $k\in \left\{1,\,2,\,3,\,\ldots ,\,n\right\}$ , dengan cara memetakan secara berulang dua elemen pertama dari rangkap- n {\displaystyle n} $n$ nya ke suatu bilangan asli. Sebagai contoh, ( 0 , 2 , 3 ) {\displaystyle \left(0,\,2,\,3\right)} $\left(0,\,2,\,3\right)$ dapat ditulis sebagai ( ( 0 , 2 ) , 3 ) {\displaystyle \left(\left(0,\,2\right),\,3\right)} $\left(\left(0,\,2\right),\,3\right)$ . Perhatikan bahwa ( 0 , 2 ) {\displaystyle \left(0,\,2\right)} $\left(0,\,2\right)$ dipetakan ke 5 {\displaystyle 5} $5$ . Akibatnya, ( 0 , 2 , 3 ) {\displaystyle \left(0,\,2,\,3\right)} $\left(0,\,2,\,3\right)$ dipetakan ke ( 5 , 3 ) {\displaystyle \left(5,\,3\right)} $\left(5,\,3\right)$ , yang kemudian dipetakan ke 39 {\displaystyle 39} $39$ . Oleh karena rangkap- 2 {\displaystyle 2} $2$ yang berbeda, yaitu pasangan terurut seperti ( a , b ) {\displaystyle \left(a,\,b\right)} $\left(a,\,b\right)$ , dipetakan ke bilangan asli yng berbeda, maka perbedaan dua rangkap- n {\displaystyle n} $n$ pada setidaknya satu elemen saja sudah cukup untuk menjamin rangkap- n {\displaystyle n} $n$ nya dipetakan ke bilangan asli yang berbeda, sehingga terbukti bahwa terdapat suatu fungsi injektif dari himpunan rangkap- n {\displaystyle n} $n$ ke himpunan bilangan asli N {\displaystyle \mathbb {N} } $\mathbb {N}$ . Secara umum, maka

Teorema — Hasil-kali Kartesius dari berhingga banyaknya himpunan terhitung merupakan himpunan terhitung.^[27]

Bukti —

Perhatikan bahwa N × N {\displaystyle \mathbb {N} \times \mathbb {N} } $\mathbb {N} \times \mathbb {N}$ merupakan himpunan terhitung, sebab terdapat fungsi injektif^[28] f : N × N → N {\displaystyle f\,\colon \,\mathbb {N} \times \mathbb {N} \to \mathbb {N} } $f\,\colon \,\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ dengan f ( x , y ) = 2 x ⋅ 3 y {\displaystyle f\!\left(x,\,y\right)=2^{x}\cdot 3^{y}} $f\!\left(x,\,y\right)=2^{x}\cdot 3^{y}$ Jika A {\displaystyle A} $A$ dan B {\displaystyle B} $B$ merupakan himpunan terhitung, maka terdapat fungsi surjektif g : N → A dan h : N → B {\displaystyle g\,\colon \,\mathbb {N} \to A\qquad {\text{dan}}\qquad h\,\colon \,\mathbb {N} \to B} $g\,\colon \,\mathbb {N} \to A\qquad {\text{dan}}\qquad h\,\colon \,\mathbb {N} \to B$ Berdasarkan informasi tersebut, fungsi g × h : N × N → A × B {\displaystyle g\times h\,\colon \,\mathbb {N} \times \mathbb {N} \to A\times B} $g\times h\,\colon \,\mathbb {N} \times \mathbb {N} \to A\times B$ bersifat surjektif, sehingga A × B {\displaystyle A\times B} $A\times B$ merupakan himpunan terhitung. Hasil ini dapat diperumum menjadi hasil-kali Kartesius dari berhingga banyaknya himpunan terhitung dengan menggunakan induksi matematika.

Himpunan semua bilangan bulat Z {\displaystyle \mathbb {Z} } $\mathbb {Z}$ dan himpunan semua bilangan rasional Q {\displaystyle \mathbb {Q} } $\mathbb {Q}$ secara intuitif terlihat lebih besar dari N {\displaystyle \mathbb {N} } $\mathbb {N}$ , namun penampilan bisa menipu. Jika pasangan terurut N × N {\displaystyle \mathbb {N} \times \mathbb {N} } $\mathbb {N} \times \mathbb {N}$ dipandang sebagai pembilang dan penyebut dari suatu pecahan biasa,^[29] maka setiap pecahan bernilai positif dapat dikawankan dengan suatu bilangan asli yang berbeda satu sama lain. Representasi ini juga memuat bilangan asli, sebab setiap bilangan asli n {\displaystyle n} $n$ dapat dinyatakan sebagai pecahan n 1 {\displaystyle {\dfrac {n}{1}}} ${\dfrac {n}{1}}$ , sehingga dapat disimpulkan bahwa jumlah bilangan rasional positif sama banyaknya dengan bilangan bulat positif. Hal ini juga berlaku untuk seluruh bilangan rasional, seperti pada pernyataan berikut.

Teorema — Himpunan semua bilangan bulat Z {\displaystyle \mathbb {Z} } $\mathbb {Z}$ , himpunan semua bilangan rasional Q {\displaystyle \mathbb {Q} } $\mathbb {Q}$ , dan himpunan semua bilangan aljabar A {\displaystyle \mathbb {A} } $\mathbb {A}$ merupakan himpunan terhitung.

Bukti —

Himpunan Z {\displaystyle \mathbb {Z} } $\mathbb {Z}$ merupakan himpunan terhitung, sebab terdapat fungsi injektif f : Z → N {\displaystyle f\,\colon \,\mathbb {Z} \to \mathbb {N} } $f\,\colon \,\mathbb {Z} \to \mathbb {N}$ dengan f ( n ) = { 2 n n ≥ 0 3 − n n < 0 {\displaystyle f(n)={\begin{cases}2^{n}&n\geq 0\\3^{-n}&n<0\end{cases}}} $f(n)={\begin{cases}2^{n}&n\geq 0\\3^{-n}&n<0\end{cases}}$
Himpunan Q {\displaystyle \mathbb {Q} } $\mathbb {Q}$ merupakan himpunan terhitung, sebab terdapat suatu fungsi surjektif g : Z × N → Q {\displaystyle g\,\colon \,\mathbb {Z} \times \mathbb {N} \to \mathbb {Q} } $g\,\colon \,\mathbb {Z} \times \mathbb {N} \to \mathbb {Q}$ dengan g ( m , n ) = m n + 1 {\displaystyle g\!\left(m,\,n\right)={\dfrac {m}{n+1}}} $g\!\left(m,\,n\right)={\dfrac {m}{n+1}}$
Berdasarkan definisi, setiap bilangan aljabar (termasuk bilangan kompleks merupakan akar persamaan dari suatu polinomial dengan koefisien bilangan bulat. Diberikan sembarang a ∈ A {\displaystyle a\in \mathbb {A} } $a\in \mathbb {A}$ , dan misalkan c 0 + c 1 x + c 2 x 2 + c 3 x 3 + … + c k x k {\displaystyle c_{0}+c_{1}x+c_{2}x^{2}+c_{3}x^{3}+\ldots +c_{k}x^{k}} $c_{0}+c_{1}x+c_{2}x^{2}+c_{3}x^{3}+\ldots +c_{k}x^{k}$ adalah suatu polinomial dengan koefisien bilangan bulat sedemikian sehingga a {\displaystyle a} $a$ adalah akar ke- n {\displaystyle n} $n$ dari polinomial tersebut, dengan akar-akarnya diurutkan berdasarkan nilai mutlaknya dari kecil ke besar, lalu argumennya diurutkan dari kecil ke besar. Himpunan A {\displaystyle \mathbb {A} } $\mathbb {A}$ merupakan himpunan terhitung, sebab terdapat suatu fungsi injektif h : A → N {\displaystyle h\,\colon \,\mathbb {A} \to \mathbb {N} } $h\,\colon \,\mathbb {A} \to \mathbb {N}$ dengan h ( a ) = 2 n ⋅ 3 c 0 ⋅ 5 c 1 ⋅ 7 c 2 ⋅ … ⋅ p k + 2 c k {\displaystyle h\!\left(a\right)=2^{n}\cdot 3^{c_{0}}\cdot 5^{c_{1}}\cdot 7^{c_{2}}\cdot \ldots \cdot {p_{k+2}}^{c_{k}}} $h\!\left(a\right)=2^{n}\cdot 3^{c_{0}}\cdot 5^{c_{1}}\cdot 7^{c_{2}}\cdot \ldots \cdot {p_{k+2}}^{c_{k}}$ dimana p i {\displaystyle p_{i}} $p_{i}$ menyatakan bilangan prima ke- i {\displaystyle i} $i$ .

Dalam beberapa kasus, penggunaan lebih dari satu pemetaan adalah hal yang membantu. Misalkan akan dibuktikan bahwa suatu himpunan A {\displaystyle A} $A$ merupakan himpunan terhitung dan A {\displaystyle A} $A$ bersifat injektif ke himpunan lain (katakanlah) B {\displaystyle B} $B$ , maka himpunan A {\displaystyle A} $A$ terbukti merupakan himpunan terhitung jika B {\displaystyle B} $B$ bersifat injektif ke himpunan bilangan asli. Sebagai contoh, terdapat suatu fungsi injektif dari himpunan semua bilangan rasional positif ke pasangan (rangkap- 2 {\displaystyle 2} $2$ ) bilangan asli, salah satunya ialah p q ↔ ( p , q ) {\displaystyle {\dfrac {p}{q}}\leftrightarrow \left(p,\,q\right)} ${\dfrac {p}{q}}\leftrightarrow \left(p,\,q\right)$ (dengan syarat FPB ( p , q ) = 1 {\displaystyle \operatorname {FPB} \!\left(p,\,q\right)=1} $\operatorname {FPB} \!\left(p,\,q\right)=1$ ). Oleh karena N × N {\displaystyle \mathbb {N} \times \mathbb {N} } $\mathbb {N} \times \mathbb {N}$ memiliki korespondensi satu-ke-satu dengan N {\displaystyle \mathbb {N} } $\mathbb {N}$ (seperti yang telah ditunjukkan sebelumnya), maka himpunan bilangan rasional positif terbukti merupakan himpunan terhitung.

Teorema — Setiap gabungan berhingga dari himpunan-himpunan terhitung juga merupakan himpunan terhitung.^[30]^[31]

Bukti —

Misalkan n ∈ N {\displaystyle n\in \mathbb {N} } $n\in \mathbb {N}$ dan N := { 1 , 2 , 3 , … , n } {\displaystyle N:=\left\{1,\,2,\,3,\,\ldots ,\,n\right\}} $N:=\left\{1,\,2,\,3,\,\ldots ,\,n\right\}$ . Jika A k {\displaystyle A_{k}} $A_{k}$ adalah himpunan terhitung untuk setiap k ∈ N {\displaystyle k\in N} $k\in N$ , maka terdapat fungsi-fungsi f k : N → A k {\displaystyle f_{k}\,\colon \,\mathbb {N} \to A_{k}} $f_{k}\,\colon \,\mathbb {N} \to A_{k}$ yang bersifat surjektif. Akibatnya, fungsi F : N × N → ⋃ k = 1 n A k {\displaystyle F\,\colon \,N\times \mathbb {N} \to \bigcup _{k\,=\,1}^{n}A_{k}} $F\,\colon \,N\times \mathbb {N} \to \bigcup _{k\,=\,1}^{n}A_{k}$ juga bersifat surjektif, dengan F ( k , x ) = f k ( x ) {\displaystyle F\!\left(k,\,x\right)=f_{k}\!\left(x\right)} $F\!\left(k,\,x\right)=f_{k}\!\left(x\right)$ . Oleh karena himpunan N × N {\displaystyle N\times \mathbb {N} } $N\times \mathbb {N}$ merupakan himpunan terhitung, maka ⋃ k = 1 n A k {\displaystyle \displaystyle \bigcup _{k\,=\,1}^{n}A_{k}} $\displaystyle \bigcup _{k\,=\,1}^{n}A_{k}$ juga merupakan himpunan terhitung.

Dengan pengetahuan bahwa terdapat himpunan tak terhitung, maka terlintas pikiran untuk mendorong lebih jauh hasil terakhir ini, dan jawabannya adalah "iya" dan "tidak"; Hasil ini dapat diperluas, namun perlu diasumsikan suatu aksioma tambahan sebagai berikut.

Teorema — Dengan mengasumsikan aksioma pemilihan terhitung, maka setiap gabungan terhitung dari himpunan-himpunan terhitung juga merupakan himpunan terhitung.

Bukti —

Misalkan n ∈ N {\displaystyle n\in \mathbb {N} } $n\in \mathbb {N}$ . Jika A k {\displaystyle A_{k}} $A_{k}$ adalah himpunan terhitung untuk setiap k ∈ N {\displaystyle k\in \mathbb {N} } $k\in \mathbb {N}$ , maka berdasarkan aksioma pemilihan terhitung, terdapat fungsi-fungsi f k : N → A k {\displaystyle f_{k}\,\colon \,\mathbb {N} \to A_{k}} $f_{k}\,\colon \,\mathbb {N} \to A_{k}$ yang bersifat surjektif.^[32] Oleh karena fungsi F : N × N → ⋃ k = 1 n A i {\displaystyle F\,\colon \,\mathbb {N} \times \mathbb {N} \to \bigcup _{k\,=\,1}^{n}A_{i}} $F\,\colon \,\mathbb {N} \times \mathbb {N} \to \bigcup _{k\,=\,1}^{n}A_{i}$ bersifat surjektif, dan bukan injektif, maka tidak ada syarat bahwa himpunannya harus bersifat saling asing.

Sebagai contoh, diberikan himpunan terhitung A {\displaystyle A} $A$ , B {\displaystyle B} $B$ , C {\displaystyle C} $C$ , dan seterusnya. Pertama, setiap elemen dari masing-masing himpunan akan dilabeli oleh suatu rangkap, lalu setiap rangkap akan dilabeli dengan suatu indeks menggunakan varian pemetaan segitiga kelak-kelok yang telah ditunjukkan sebelumnya: Indeks Rangkap Elemen 0 ( 0 , 0 ) a 0 1 ( 0 , 1 ) a 1 2 ( 1 , 0 ) b 0 3 ( 0 , 2 ) a 2 4 ( 1 , 1 ) b 1 5 ( 2 , 0 ) c 0 6 ( 0 , 3 ) a 3 7 ( 1 , 2 ) b 2 8 ( 2 , 1 ) c 1 9 ( 3 , 0 ) d 0 10 ( 0 , 4 ) a 4 ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{c|c|c}{\text{Indeks}}&{\text{Rangkap}}&{\text{Elemen}}\\\hline 0&\left(0,\,0\right)&a_{0}\\1&\left(0,\,1\right)&a_{1}\\2&\left(1,\,0\right)&b_{0}\\3&\left(0,\,2\right)&a_{2}\\4&\left(1,\,1\right)&b_{1}\\5&\left(2,\,0\right)&c_{0}\\6&\left(0,\,3\right)&a_{3}\\7&\left(1,\,2\right)&b_{2}\\8&\left(2,\,1\right)&c_{1}\\9&\left(3,\,0\right)&d_{0}\\10&\left(0,\,4\right)&a_{4}\\\vdots &\vdots &\vdots \end{array}}} ${\begin{array}{c|c|c}{\text{Indeks}}&{\text{Rangkap}}&{\text{Elemen}}\\\hline 0&\left(0,\,0\right)&a_{0}\\1&\left(0,\,1\right)&a_{1}\\2&\left(1,\,0\right)&b_{0}\\3&\left(0,\,2\right)&a_{2}\\4&\left(1,\,1\right)&b_{1}\\5&\left(2,\,0\right)&c_{0}\\6&\left(0,\,3\right)&a_{3}\\7&\left(1,\,2\right)&b_{2}\\8&\left(2,\,1\right)&c_{1}\\9&\left(3,\,0\right)&d_{0}\\10&\left(0,\,4\right)&a_{4}\\\vdots &\vdots &\vdots \end{array}}$

Aksioma pemilihan terhitung diperlukan untuk memberikan indeks kepada semua himpunan A {\displaystyle A} $A$ , B {\displaystyle B} $B$ , C {\displaystyle C} $C$ , … {\displaystyle \ldots } $\ldots$ , secara bersamaan.

Teorema — Misalkan A {\displaystyle A} $A$ dan B {\displaystyle B} $B$ adalah himpunan.

Jika fungsi f : A → B {\displaystyle f\,\colon \,A\to B} $f\,\colon \,A\to B$ bersifat injektif dan B {\displaystyle B} $B$ adalah himpunan terhitung, maka A {\displaystyle A} $A$ juga merupakan himpunan terhitung.
Jika fungsi g : A → B {\displaystyle g\,\colon \,A\to B} $g\,\colon \,A\to B$ bersifat surjektif dan A {\displaystyle A} $A$ adalah himpunan terhitung, maka B {\displaystyle B} $B$ juga merupakan himpunan terhitung.

Bukti —

Kedua hal ini merupakan akibat dari definisi himpunan terhitung sebagai fungsi injektif / surjektif.

Jika B {\displaystyle B} $B$ adalah himpunan terhitung, maka terdapat fungsi injektif h : B → N {\displaystyle h\,\colon \,B\to \mathbb {N} } $h\,\colon \,B\to \mathbb {N}$ . Oleh karena fungsi f {\displaystyle f} $f$ bersifat injektif, maka fungsi komposisi h ∘ f : A → N {\displaystyle h\circ f\,\colon \,A\to \mathbb {N} } $h\circ f\,\colon \,A\to \mathbb {N}$ juga bersifat injektif, sehingga terbukti bahwa A {\displaystyle A} $A$ merupakan himpunan terhitung.
Jika A {\displaystyle A} $A$ adalah himpunan terhitung, maka terdapat fungsi surjektif h : N → A {\displaystyle h\,\colon \,\mathbb {N} \to A} $h\,\colon \,\mathbb {N} \to A$ . Oleh karena fungsi g {\displaystyle g} $g$ bersifat surjektif, maka terdapat dua kasus yang mungkin terjadi: himpunan A {\displaystyle A} $A$ dan B {\displaystyle B} $B$ sama-sama merupakan himpunan kosong, atau fungsi komposisi g ∘ h : N → B {\displaystyle g\circ h\,\colon \,\mathbb {N} \to B} $g\circ h\,\colon \,\mathbb {N} \to B$ juga bersifat surjektif. Berdasarkan kedua kasus yang diperoleh, terbukti bahwa B {\displaystyle B} $B$ merupakan himpunan terhitung.

Teorema Cantor menyatakan bahwa jika X {\displaystyle X} $X$ adalah suatu himpunan dan P ( X ) {\displaystyle {\mathcal {P}}\!\left(X\right)} ${\mathcal {P}}\!\left(X\right)$ adalah himpunan kuasa dari X {\displaystyle X} $X$ (yaitu himpunan seluruh himpunan bagian dari X {\displaystyle X} $X$ ), maka tidak ada fungsi surjektif dari X {\displaystyle X} $X$ ke P ( X ) {\displaystyle {\mathcal {P}}\!\left(X\right)} ${\mathcal {P}}\!\left(X\right)$ . Pembuktian dari pernyataan ini dapat dilihat pada artikel teorema Cantor. Salah satu akibat dari teorema ini ialah

Teorema — Himpunan P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} ${\mathcal {P}}\!\left(\mathbb {N} \right)$ bukan merupakan himpunan terhitung; atau dengan kata lain, himpunannya tak terhitung.

Lihat juga

Rujukan

↑ Warsito (2021). Pengantar Matematika (BMP). Tanggerang Selatan: Universitas Terbuka.{{cite book}}: Pemeliharaan CS1: Status URL (link)
↑ Setiadji (2009). Himpunan & logika samar serta aplikasinya. Yogyakarta: Graha Ilmu.{{cite book}}: Pemeliharaan CS1: Status URL (link)
↑ Fatihah, Nurul; Haripamyu, Haripamyu; Ekariani, Shelvi (2020-06-29). "Ukuran Luar Lebesgue di R n {\displaystyle \mathbb {R} ^{n}} $\mathbb {R} ^{n}$ ". Jurnal Matematika UNAND. 9 (2): 76–83. doi:10.25077/jmu.9.2.76-83.2020. ISSN 2721-9410.
↑ "Daftar Istilah". Pasti (Padanan Istilah). Badan Pengembangan dan Pembinaan Bahasa. Diakses tanggal 21 Oktober 2024.
↑ Umam, Ahmad Khairul. "ANALISIS REAL 1" (PDF). Repositori Universitas Billfath. hlm. 2. Diakses tanggal 21 Oktober 2024.
1 2 Oleh karena terdapat bijeksi antara bilangan asli { 1 , 2 , 3 , 4 , … } {\displaystyle \left\{1,\,2,\,3,\,4,\,\ldots \right\}} $\left\{1,\,2,\,3,\,4,\,\ldots \right\}$ dan bilangan cacah { 0 , 1 , 2 , 3 , 4 , … } {\displaystyle \left\{0,\,1,\,2,\,3,\,4,\,\ldots \right\}} $\left\{0,\,1,\,2,\,3,\,4,\,\ldots \right\}$ , maka tidak masalah apabila bilangan 0 {\displaystyle 0} $0$ dianggap sebagai bilangan asli atau bukan. Mengesampingkan hal tersebut, artikel ini mengikuti ISO 31-11 dan konvensi standar dalam logika matematika, yang menyatakan bahwa 0 {\displaystyle 0} $0$ adalah bilangan asli.
↑ Manetti, Marco (19 Juni 2015). Topology [Topologi] (dalam bahasa Inggris). Springer. hlm. 26. ISBN 978-3-319-16958-3.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Rudin 1976, Chapter 2
↑ Tao 2016, hlm. 181
↑ Kamke 1950, hlm. 2
1 2 Lang 1993, §2 of Chapter I
↑ Apostol 1969, hlm. 23, Chapter 1.14
↑ noorma_yulia. "Himpunan Terhitung". Menara Ilmu Analisis Real. Universitas Gajah Mada. Diakses tanggal 22 Oktober 2024.
↑ Thierry, Vialar (4 April 2017). Handbook of Mathematics (dalam bahasa Inggris). BoD - Books on Demand. hlm. 24. ISBN 978-2-9551990-1-5.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
1 2 3 Yaqub, Aladdin M. (24 Oktober 2014). An Introduction to Metalogic [Pengantar Metalogika] (dalam bahasa Inggris). Broadview Press. ISBN 978-1-4604-0244-3.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Singh, Tej Bahadur (17 Mei 2019). Introduction to Topology [Pengantar Topologi] (dalam bahasa Inggris). Springer. hlm. 422. ISBN 978-981-13-6954-4.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
1 2 Katzourakis, Nikolaos; Varvaruca, Eugen (2 Januari 2018). An Illustrative Introduction to Modern Analysis [Pengantar Ilustratif Analisis Modern] (dalam bahasa Inggris). CRC Press. ISBN 978-1-351-76532-9.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Halmos 1960, p. 91
↑ Kamke 1950, p. 2
↑ Dlab, Vlastimil; Williams, Kenneth S. (9 Juni 2020). Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics (dalam bahasa Inggris). World Scientific. hlm. 8. ISBN 978-981-12-1999-3.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Tao 2016, hlm. 182
↑ Stillwell, John C. (2010), Roads to Infinity: The Mathematics of Truth and Proof [Jalan Menuju Tak Hingga: Matematika dari Kebenaran dan Bukti] (dalam bahasa Inggris), CRC Press, hlm. 10, ISBN 9781439865507, Penemuan himpunan tak terhitung oleh Cantor pada 1874 merupakan salah satu kejadian yang paling tidak terduga dalam sejarah matematika. Sebelum tahun 1874, tak terhingga bahkan tidak dianggap sebagai topik matematika yang sah oleh banyak orang, sehingga keperluan untuk membedakan antara himpunan terhitung tak terhingga dan himpunan tak terhitung tak terhingga tidak dapat dibayangkan.
↑ Cantor 1878, p. 242.
↑ Ferreirós 2007, pp. 268, 272–273.
↑ "What Are Sets and Roster Form?" [Apa Itu Himpunan dan Bentuk Roster?]. expii. 2021-05-09. Diarsipkan dari versi aslinya tanggal 2020-09-18.
↑ Halmos 1960, hlm. 91
↑ Halmos 1960, hlm. 92
↑ Avelsgaard 1990, hlm. 182
↑ Pecahan dalam bentuk a b {\displaystyle {\dfrac {a}{b}}} ${\dfrac {a}{b}}$ , dengan a {\displaystyle a} $a$ dan b ≠ 0 {\displaystyle b\neq 0} $b\neq 0$ adalah suatu bilangan bulat
↑ Avelsgaard 1990, hlm. 180
↑ Fletcher & Patty 1988, hlm. 187
↑ Hrbacek, Karel; Jech, Thomas (22 Juni 1999). Introduction to Set Theory, Third Edition, Revised and Expanded (dalam bahasa Inggris). CRC Press. hlm. 141. ISBN 978-0-8247-7915-3.{{cite book}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)

Referensi

(Inggris)Apostol, Tom M. (Juni 1969), Multi-Variable Calculus and Linear Algebra with Applications, Calculus, vol. 2 (Edisi 2nd), New York: John Wiley + Sons, ISBN 978-0-471-00007-5{{citation}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
(Inggris)Avelsgaard, Carol (1990), Foundations for Advanced Mathematics, Scott, Foresman and Company, ISBN 0-673-38152-8
(Inggris)Cantor, Georg (1878), "Ein Beitrag zur Mannigfaltigkeitslehre", Journal für die Reine und Angewandte Mathematik, 1878 (84): 242–248, doi:10.1515/crelle-1878-18788413, S2CID 123695365
(Inggris)Ferreirós, José (2007), Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (Edisi 2nd revised), Birkhäuser, ISBN 978-3-7643-8349-7
(Inggris)Fletcher, Peter; Patty, C. Wayne (1988), Foundations of Higher Mathematics, Boston: PWS-KENT Publishing Company, ISBN 0-87150-164-3
(Inggris)Halmos, Paul R. (1960), Naive Set Theory [Teori Himpunan Naif], D. Van Nostrand Company, Inc Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).
(Inggris)Kamke, Erich (1950), Theory of Sets, Dover series in mathematics and physics, New York: Dover, ISBN 978-0486601410{{citation}}: Ketidakcocokan ISBN / tanggal
(Inggris)Lang, Serge (1993), Real and Functional Analysis, Berlin, New York: Springer-Verlag, ISBN 0-387-94001-4
(Inggris)Rudin, Walter (1976), Principles of Mathematical Analysis, New York: McGraw-Hill, ISBN 0-07-054235-X
(Inggris)Tao, Terence (2016). "Infinite sets". Analysis I. Texts and Readings in Mathematics. Vol. 37 (Edisi 3). Singapore: Springer. hlm. 181–210. doi:10.1007/978-981-10-1789-6_8. ISBN 978-981-10-1789-6.

Portal:

l b s Sistem bilangan
Set dihitung	Bilangan asli (ℕ) Bilangan bulat (ℤ) Bilangan rasional (ℚ) Bilangan Constructible Bilangan aljabar (𝔸) Periode Jumlah dihitung Bilangan real didefinisikan Bilangan aritmetik Bilangan bulat Gaussian
Aljabar divisi	Bilangan riil (ℝ) Bilangan kompleks (ℂ) Kuaternion (ℍ) Oktonion (𝕆)
Perpecahan Aljabar komposisi	over ℝ: Bilangan berkompleks perpecahan Berkuaternion perpecahan Beroktonion perpecahan over ℂ: Bilangan bikompleks Bikuaternion Bioktonion
Hiperkompleks lainnya	Nomor ganda Kuaternion ganda Kuaternion hiperbolik Sedenion (𝕊) Berbioktonion perpecahan Bilangan multikompleks
Jenis lainnya	Bilangan kardinal Bilangan irasional Bilangan Hyperreal Lapangan Levi-Civita Bilangan surealis Bilangan Transenden Bilangan ordinal Bilangan p-adic Bilangan supranatural Bilangan Superreal
Klasifikasi Daftar

l b s Logika matematika
Umum	Bahasa formal Aturan formasi Sistem formal Sistem deduktif Pembuktian formal Formal semantik Formula bentukan Himpunan Elemen Kelas Logika klasik Aksioma Deduksi alami Aturan inferensi Relasi Teorema Konsekuensi logis Sistem aksiomatis Teori tipe Simbol Sintaks Teori
Logika tradisional	Proposisi Inferensi Argumen Validitas Meyakinkan Silogisme Sisi berlawanan Diagram Venn
Kalkulus proposisional Logika boolean	Fungsi Boolean Kalkulus proposisional Formula proposisional Hubungan logis Tabel kebenaran
Logika predikat	Orde-pertama Pembilang Predikat Orde-dua Kalkulus predikat Monadic
Teori himpunan	Himpunan Himpunan kosong Enumerasi Ekstensionalitas Himpunan terbatas Fungsi Subhimpunan Himpinan perpangkatan Himpunan terhitung Himpunan rekursif Domain Rentang Pasangan berurut Himputan tak terhitung
Teori model	Model Interpretasi Model nonstandar Teori model terbatas Nilai kebenaran Validitas
Teori pembuktian	Pembuktian formal Sistem deduktif Sistem formal Teorema Konsekuensi logis Aturan inferensi Sintaks
Teori komputabilitas	Rekursi Himpunan rekursif Himpunan rekursif terhitung Permasalahan keputusan Tesis Church–Turing Fungsi terhitung Fungsi rekursif primitif
Kategori

l b s Teori himpunan
Umum	Himpunan (matematika)
Aksioma	Adjungsi Batas ukuran Determinasi Gabungan Himpunan kuasa Keberaturan Kebisadibangunan (V=L) Perluasan Pasangan Pemilihan tercacah terikat global Takhingga Aksioma Martin Skema aksioma penggantian spesifikasi
Operasi	Gabungan Gabungan lepas Himpunan kuasa Hukum De Morgan Irisan Komplemen Produk Kartesius Selisih himpunan Beda setangkup
Konsep Metode	Argumen diagonal Bilangan kardinal (besar) Bilangan ordinal Diagram Venn Elemen pasangan terurut rangkap Hipotesis kontinum Induksi lintas-hingga Kardinalitas Kelas Keluarga Korespondensi satu-ke-satu Pemaksaan Semesta yang bisa dibangun
Jenis himpunan	Himpunan bagian · Superhimpunan Berhingga (turun-temurun) Takhingga (takhingga Dedekind) Kabur Kosong Rekursif Semesta Tercacah Tak tercacah Transitif
Teori	Aksiomatik Alternatif Naif Teorema Cantor Zermelo Umum Principia Mathematica New Foundations (NF, NFU) Zermelo–Fraenkel (ZFC) von Neumann–Bernays–Gödel (NBG) Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoks Masalah	Paradoks Russell Masalah Suslin Paradoks Burali-Forti
Teoretisi himpunan	Abraham Fraenkel Bertrand Russell Ernst Zermelo Georg Cantor John von Neumann Kurt Gödel Paul Bernays Paul Cohen Richard Dedekind Thomas Jech Thoralf Skolem Willard Quine