Proposisi B.7.
Jika \(X\) merupakan himpunan hingga tak kosong, terdapat bilangan bulat positif tunggal \(n\) sedemikian sehingga terdapat bijeksi \(f:[n]\bijection X\text{.}\)
Subbab B.5 Himpunan Hingga
Suatu himpunan \(X\) disebut hingga jika salah satu dari kondisi berikut berlaku: (1) \(X=\emptyset\text{;}\) atau (2) terdapat bilangan bulat positif \(n\) dan bijeksi \(f:[n]\bijection X\text{.}\) Jika \(X\) bukan himpunan hingga, himpunan itu disebut tak hingga. Sebagai contoh, \(\{a,\emptyset,(3,2),\posints\}\) dan \(\posints\times\emptyset\) merupakan himpunan hingga. Sebaliknya, \(\posints\times \{\emptyset\}\) merupakan himpunan tak hingga. Tentu saja, \([n]\) dan \(\bfn\) merupakan himpunan hingga untuk setiap \(n\in\posints\text{.}\)
Dalam beberapa kasus, menentukan apakah suatu himpunan hingga atau tak hingga memerlukan usaha. Berikut adalah hasil yang benar-benar klasik.
Proposisi B.8.
Himpunan bilangan prima \(P\) bersifat tak hingga.
Bukti.
Andaikan himpunan bilangan prima \(P\) hingga. Himpunan ini tidak kosong karena \(2\in P\text{.}\) Misalkan \(n\) merupakan bilangan bulat positif tunggal sedemikian sehingga terdapat bijeksi \(f:[n]\rightarrow P\text{.}\) Selanjutnya, tetapkan
\begin{equation*}
p=1+f(1)\times f(2)\times f(3)\times \dots\times f(n)
\end{equation*}
Bilangan \(p\) tidak habis dibagi oleh satu pun bilangan prima dalam \(P\text{,}\) tetapi lebih besar daripada setiap unsur \(P\text{.}\) Jadi, \(p\) merupakan bilangan prima atau mempunyai faktor prima yang tidak termasuk dalam \(P\text{.}\) Kontradiksi ini menyelesaikan bukti.
Berikut adalah contoh terkenal suatu himpunan yang belum diketahui hingga atau tak hingga.
Konjektur B.9.
Diduga bahwa himpunan berikut bersifat tak hingga:
\begin{equation*}
T=\{n\in\posints:n \text{ dan } n+2 \text{ keduanya
prima } \}.
\end{equation*}
Konjektur ini dikenal sebagai Konjektur Prima Kembar. Nilai \(\text{A} ++\) dijamin bagi mahasiswa mana pun yang berhasil menuntaskannya!
Proposisi B.10.
Misalkan \(X\) dan \(Y\) merupakan himpunan hingga. Jika terdapat injeksi \(f:X\injection Y\) dan injeksi \(g:Y \injection X\text{,}\) maka terdapat bijeksi \(h:X \bijection Y\text{.}\)
Jika \(X\) merupakan himpunan hingga tak kosong, kardinalitas dari \(X\text{,}\) yang dinotasikan dengan \(|X|\) , adalah bilangan bulat positif tunggal \(n\) sedemikian sehingga terdapat bijeksi \(f:[n]\bijection X\text{.}\) Secara intuitif, \(|X|\) adalah banyaknya unsur dalam \(X\text{.}\) Sebagai contoh,
\begin{equation*}
|\{(6,2), (8,(4,\emptyset)), \{3,\{5\}\}\}|=3.
\end{equation*}
Berdasarkan konvensi, kardinalitas himpunan kosong ditetapkan sama dengan nol, dan kita menulis \(|\emptyset|=0\text{.}\)
Proposisi B.11.
Jika \(X\) dan \(Y\) merupakan himpunan hingga tak kosong, maka \(|X\times Y| =|X|\times |Y|\text{.}\)
Perhatikan bahwa pernyataan dalam Proposisi B.11 merupakan contoh “pembebanan berlebih pada operator”, suatu teknik yang tersedia dalam beberapa bahasa pemrograman. Secara khusus, tanda kali \(\times\) digunakan dua kali, tetapi mempunyai arti yang berbeda. Dalam \(X\times Y\text{,}\) tanda itu menyatakan produk Kartesius, sedangkan dalam \(|X|\times |Y|\text{,}\) tanda itu menyatakan perkalian biasa bilangan bulat positif. Bahasa pemrograman dapat melacak tipe data variabel dan menerapkan penafsiran yang tepat bagi operator seperti \(\times\) berdasarkan variabel yang dikenainya.
Kita juga mempunyai bentuk umum Proposisi B.11 berikut:
\begin{equation*}
|X_1\times X_2\times\dots\times X_n|=
|X_1|\times |X_2|\times\dots\times |X_n|
\end{equation*}
Teorema B.12.
-
Terdapat bijeksi di antara sebarang dua dari himpunan-himpunan tak hingga berikut: \(\posints\text{,}\) \(\ints\text{,}\) dan \(\rats\text{.}\)
-
Terdapat injeksi dari \(\rats\) ke \(\reals\text{.}\)
-
Tidak terdapat fungsi surjektif dari \(\rats\) ke \(\reals\text{.}\)
