Matematika Universitas — Tahun 1 · Bachelor Year 1

1Logika, Himpunan dan Pemetaan

Sampai sekarang, pembuktian dijalankan dengan gagasan yang informal namun jujur tentang apa arti “membuktikan”. Bab pertama matematika tingkat sarjana ini menyatakan aturan mainnya secara tegas: apa itu pernyataan matematis, bagaimana perangkai dan kuantor menggabungkan pernyataan, langkah mana yang sah di dalam sebuah bukti — lalu, di atas landasan itu, membangun dua bahasa universal matematika: himpunan dan pemetaan.

1.1 Pernyataan dan perangkai

Definisi 1.1 (Pernyataan, perangkai)

Sebuah pernyataan (atau proposisi) adalah kalimat yang bernilai benar (B) atau salah (S) — tepat satu di antara keduanya. Dari pernyataan $P$ dan $Q$ dibentuk:

negasi $\lnot P$ (“bukan $P$ ”), benar tepat ketika $P$ salah;
konjungsi $P \land Q$ (“ $P$ dan $Q$ ”), benar tepat ketika keduanya benar;
disjungsi $P \lor Q$ (“ $P$ atau $Q$ ”), benar tepat ketika sekurang-kurangnya satu benar (“atau” di sini bersifat inklusif);
implikasi $P \implies Q$ , salah tepat ketika $P$ benar dan $Q$ salah;
ekuivalensi $P \iff Q$ , benar tepat ketika $P$ dan $Q$ mempunyai nilai kebenaran yang sama.

Catatan 1.2

Tabel kebenaran $P \implies Q$ layak dihentikan sejenak: ketika $P$ salah, $P \implies Q$ bernilai benar, apa pun $Q$ -nya. “Jika $2 < 1$ maka $0 = 5$ ” adalah implikasi yang benar. Sebuah implikasi tidak mengatakan apa-apa tentang keadaan ketika hipotesisnya gagal.

Proposisi 1.3 (Kaidah perhitungan pernyataan)

Untuk setiap pernyataan $P$ , $Q$ , $R$ :

$\lnot(\lnot P) \iff P$ ;
hukum De Morgan: $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ dan $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
$(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , sehingga $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
kontraposisi: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
$(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ;
sifat distributif: $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$ dan $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ .

Bukti. Setiap ekuivalensi diperiksa dengan membandingkan tabel kebenaran: dua pernyataan majemuk yang dibangun dari $P$ , $Q$ , $R$ ekuivalen tepat ketika keduanya bernilai kebenaran sama pada masing-masing (empat atau delapan) kasus. Kita tuliskan satu tabel selengkapnya, untuk hukum De Morgan yang pertama:

$P$	$Q$	$P \land Q$	$\lnot(P \land Q)$	$\lnot P$	$\lnot Q$	$(\lnot P) \lor (\lnot Q)$
B	B	B	S	S	S	S
B	S	S	B	S	B	B
S	B	S	B	B	S	B
S	S	S	B	B	B	B

Kolom $4$ dan $7$ berimpit, dan itulah bukti hukum tersebut. Untuk kontraposisi ada jalan pintas lisan yang lebih cepat: $P \implies Q$ salah tepat pada kasus ( $P$ benar, $Q$ salah), sedangkan $(\lnot Q) \implies (\lnot P)$ salah tepat pada kasus ( $\lnot Q$ benar, $\lnot P$ salah), yaitu ( $Q$ salah, $P$ benar) — satu kasus yang persis sama, sehingga kedua implikasi itu bertabel sama. Kaidah selebihnya diperiksa dengan cara yang sama; perhatikan bahwa (3) menyusutkan setiap implikasi menjadi disjungsi, sehingga (2) secara mekanis melahirkan kaidah negasi $\lnot(P \implies Q) \iff P \land (\lnot Q)$ : untuk membantah sebuah implikasi kita harus menunjukkan satu kasus yang hipotesisnya berlaku dan kesimpulannya gagal. ∎

1.2 Kuantor

Definisi 1.4 (Kuantor)

Misalkan $P(x)$ sifat dari suatu unsur $x$ pada himpunan $E$ .

$\forall x \in E,\ P(x)$ (“untuk setiap $x$ di $E$ , $P(x)$ ”) benar bila setiap unsur $E$ memenuhi $P$ ;
$\exists x \in E,\ P(x)$ (“terdapat $x$ di $E$ sedemikian sehingga $P(x)$ ”) benar bila sekurang-kurangnya satu unsur $E$ memenuhi $P$ .

Kita tulis $\exists!$ untuk “terdapat dengan tunggal”.

Proposisi 1.5 (Negasi kuantor)

\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff \exists x \in E,\ \lnot P(x), \qquad \lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff \forall x \in E,\ \lnot P(x).

Bukti. Kita bahas ekuivalensi pertama dalam dua arah; yang kedua bersifat simetris. Jika $\forall x \in E,\ P(x)$ salah, maka tidak setiap unsur memenuhi $P$ : himpunan $A = \{x \in E : \lnot P(x)\}$ tidak mungkin kosong, dan unsur mana pun darinya menjadi saksi bagi $\exists x \in E,\ \lnot P(x)$ . Sebaliknya, jika ada $x_0 \in E$ yang memenuhi $\lnot P(x_0)$ , maka $x_0$ adalah contoh penyangkal dan pernyataan universal itu gugur. Untuk kaidah kedua: “tidak ada $x$ yang memenuhi $P$ ” berarti himpunan $\{x : P(x)\}$ kosong, yaitu setiap $x$ terletak di komplemennya $A$ . Diterapkan berantai pada rangkaian kuantor bersarang, kedua kaidah itu memberikan prosedur mekanis Contoh 1.8: negasi berjalan dari kiri ke kanan, membalik setiap $\forall$ menjadi $\exists$ dan setiap $\exists$ menjadi $\forall$ , lalu akhirnya menegasikan predikat yang terdalam. ∎

Contoh 1.6 (Menegasikan kalimat matematis sehari-hari)

Misalkan $f \colon \R \to \R$ . Kalimat “ $f$ naik” berbunyi

\forall x \in \R,\ \forall y \in \R,\quad x \leq y \implies f(x) \leq f(y) ,

dan negasinya, menurut Proposisi 1.5 beserta kaidah $\lnot(P \implies Q) \iff P \land \lnot Q$ :

\exists x \in \R,\ \exists y \in \R,\quad x \leq y \ \text{ dan }\ f(x) > f(y) :

satu pasang saksi sudah cukup. Demikian pula “ $f$ terbatas” berarti $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$ , dengan negasi

\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :

berapa pun batas yang diajukan, ada titik yang melampauinya. Inti gagasannya: negasi yang benar tidak pernah memuat “bukan” yang dikenakan pada blok berkuantor — ia adalah pernyataan positif yang baru, dengan peran yang bertukar: kini kita yang menghasilkan saksi, padahal tadinya kita yang menerimanya.

Contoh 1.7 (Urutan kuantor)

Urutan kuantor yang berlainan jenis itu penting:

\forall x \in \R,\ \exists y \in \R,\ y > x \quad\text{benar (ambil } y = x+1\text{),}

\exists y \in \R,\ \forall x \in \R,\ y > x \quad\text{salah (tak ada bilangan real yang melampaui semua bilangan real).}

Pada pernyataan pertama $y$ boleh bergantung pada $x$ ; pada yang kedua, satu $y$ harus berlaku untuk semua $x$ . Sebaliknya, dua kuantor yang sejenis selalu dapat dipertukarkan.

Contoh 1.8 (Membaca definisi dengan tiga kuantor)

Kalimat “barisan $(u_n)$ konvergen ke $\ell$ ” akan dituliskan pada Bab 11 sebagai

\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad \abs{u_n - \ell} \leq \varepsilon .

Negasinya, dengan Proposisi 1.5 yang diterapkan tiga kali, adalah

\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad \abs{u_n - \ell} > \varepsilon .

Kemampuan menegasikan kalimat semacam itu secara mekanis, tanpa memikirkan artinya, adalah keterampilan yang sesungguhnya: ia memisahkan kerja logika dari kerja matematika.

1.3 Teknik pembuktian

Metode 1.9 (Pola pembuktian yang baku)

Untuk membuktikan…

implikasi $P \implies Q$ secara langsung: andaikan $P$ , simpulkan $Q$ ;
dengan kontraposisi: andaikan $\lnot Q$ , simpulkan $\lnot P$ — sah menurut Proposisi 1.3 (4);
dengan kontradiksi: andaikan pernyataan itu salah, lalu turunkan sebuah kontradiksi;
sebuah ekuivalensi: buktikan kedua implikasinya secara terpisah (atau rangkaikan ekuivalensi yang sudah dikenal);
pernyataan “untuk setiap”: ambil $x$ yang sembarang di $E$ (“misalkan $x \in E$ ”) lalu buktikan $P(x)$ ;
pernyataan “terdapat”: tunjukkan sebuah saksi, atau buktikan keberadaannya secara tak langsung;
dengan induksi: lihat Teorema 1.12.

Ketika membuktikan pernyataan tentang sebuah unsur yang dipilih dengan cermat namun tetap sembarang, jangan sekali-kali memberi unsur itu sifat tambahan: “misalkan $x \in \R$ ” yang disusul “karena $x > 0$ …” tidak membuktikan apa pun untuk $x$ yang negatif.

Catatan 1.10 (Jebakan yang lazim dalam pembuktian)

Empat jebakan klasik, semuanya pantas disebut sekali.

Konvers, bukan kontraposisi. $Q \implies P$ tidak ekuivalen dengan $P \implies Q$ ; hanya $\lnot Q \implies \lnot P$ yang ekuivalen. “Jika hujan turun, jalan menjadi basah” tidak memberi hak untuk menyimpulkan hujan dari jalan yang basah.
Membuktikan ekuivalensi lewat satu implikasi saja. Klaim “jika dan hanya jika” adalah dua teorema; sebutkan arah mana yang sedang dibuktikan, lalu buktikan keduanya. Rangkaian $\iff$ hanya sah bila setiap mata rantainya benar-benar dapat dibalik — mengkuadratkan persamaan, misalnya, tidak.
Bukti yang berjalan mundur. Berangkat dari kesimpulan yang diinginkan lalu menurunkan pernyataan yang benar tidak membuktikan apa-apa (dari $-1 = 1$ orang menurunkan $1 = 1$ yang benar dengan mengkuadratkan). Sebuah perhitungan boleh ditemukan secara mundur, tetapi ia harus dituliskan maju, atau dengan ekuivalensi yang eksplisit.
Saksi tertentu lawan unsur sembarang. Untuk membuktikan $\exists x,\ P(x)$ , kita boleh menunjukkan satu $x$ yang dipilih dengan cerdik; untuk membuktikan $\forall x,\ P(x)$ , unsur $x$ yang dipilih harus tetap sembarang. Mencampur keduanya — memeriksa klaim universal pada sebuah contoh — adalah kesalahan yang paling sering muncul dalam pekerjaan pemula.

Contoh 1.11 (Kontraposisi dan kontradiksi dalam praktik)

Untuk $n \in \N$ : jika $n^2$ genap maka $n$ genap. Dengan kontraposisi: jika $n$ ganjil, $n = 2k+1$ , maka $n^2 = 4k^2 + 4k + 1$ ganjil.

$\sqrt 2$ irasional. Dengan kontradiksi: andaikan $\sqrt 2 = p/q$ dengan $p, q \in \N^*$ dan pecahan itu sudah paling sederhana. Maka $p^2 = 2q^2$ genap, sehingga $p$ genap (butir sebelumnya), $p = 2r$ ; lalu $q^2 = 2r^2$ genap, sehingga $q$ genap — bertentangan dengan bentuk paling sederhana tadi.

Teorema 1.12 (Induksi matematika)

Misalkan $P(n)$ sifat dari bilangan bulat $n$ . Jika

$P(0)$ benar, dan
untuk setiap $n \in \N$ berlaku $P(n) \implies P(n+1)$ ,

maka $P(n)$ benar untuk setiap $n \in \N$ .

Induksi kuat: kesimpulannya tidak berubah bila (2) diganti oleh: untuk setiap $n$ , $\bigl(P(0) \land \dots \land P(n)\bigr) \implies P(n+1)$ .

Bukti. Ini sifat $\N$ itu sendiri, yang setara dengan: setiap himpunan bagian tak kosong dari $\N$ mempunyai unsur terkecil (kita terima sebagai hal yang sudah diketahui). Memang, andaikan (1) dan (2) berlaku, lalu tulis $A = \{n \in \N : P(n) \text{ salah}\}$ . Jika $A \neq \emptyset$ , ia mempunyai unsur terkecil $m$ ; $m \neq 0$ menurut (1); lalu $m - 1 \notin A$ , sehingga $P(m-1)$ berlaku, dan (2) memberikan $P(m)$ — kontradiksi. Jadi $A = \emptyset$ . Untuk induksi kuat, terapkan argumen yang sama: $P(0), \dots, P(m-1)$ semuanya berlaku karena $m$ terkecil di $A$ . ∎

Contoh 1.13 (Membuktikan keberadaan yang tunggal)

Pernyataan $\exists!\,x,\ P(x)$ sesungguhnya dua pernyataan, yang dibuktikan terpisah: keberadaan (tunjukkan atau bangun suatu $x_0$ dengan $P(x_0)$ ) dan ketunggalan (andaikan $P(x)$ dan $P(x')$ , simpulkan $x = x'$ ). Contoh: ada tepat satu bilangan real $x$ dengan $x^3 + x = 2$ . Keberadaan: $x_0 = 1$ memenuhi, karena $1 + 1 = 2$ . Ketunggalan: jika $x^3 + x = x'^3 + x'$ , maka

0 = (x^3 - x'^3) + (x - x') = (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),

dan faktor keduanya bernilai positif (ia sama dengan $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$ ), sehingga $x = x'$ . Perhatikan pembagian tugasnya: keberadaan memakai tebakan yang beruntung, ketunggalan memakai aljabar yang berlaku untuk penyelesaian sembarang — tak satu pun di antara kedua argumen itu mengerjakan tugas yang lain, dan melupakan paruh kedua adalah godaan yang selalu hadir begitu sebuah penyelesaian ditemukan.

Contoh 1.14

Untuk setiap $n \in \N^*$ : $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$ . Basis $n = 1$ : kedua ruas sama dengan $1$ . Langkah: dengan mengandaikan rumus itu berlaku untuk $n$ ,

\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere

Contoh 1.15 (Induksi kuat dalam praktik)

Setiap bilangan bulat $n \geq 2$ merupakan hasil kali bilangan prima (bilangan prima adalah bilangan bulat $\geq 2$ yang pembaginya yang $\geq 1$ hanyalah $1$ dan dirinya sendiri; bilangan prima dipelajari tersendiri pada Bab 6). Induksi biasa tak berdaya di sini: mengetahui bahwa $95 = 5 \times 19$ terfaktorkan tidak mengatakan apa pun tentang $96$ . Induksi kuat justru pas. Basisnya: $2$ prima, jadi ia hasil kali bilangan prima dengan satu faktor. Langkah: ambil $n \geq 2$ dan andaikan setiap bilangan bulat $m$ dengan $2 \leq m \leq n$ merupakan hasil kali bilangan prima. Jika $n + 1$ prima, selesai. Jika tidak, $n + 1 = ab$ dengan $2 \leq a, b \leq n$ ; menurut hipotesis kuat, $a$ dan $b$ keduanya hasil kali bilangan prima, sehingga demikian pula $n + 1$ . Inti gagasannya: induksi kuat adalah alat yang tepat setiap kali “alasan” bagi $P(n+1)$ berada pada suatu peringkat sebelumnya yang tak terduga, bukan pada peringkat $n$ .

1.4 Himpunan

Definisi 1.16 (Operasi himpunan)

Gagasan himpunan dan relasi keanggotaan $x \in E$ kita terima sebagai gagasan primitif. Untuk himpunan $A, B$ di dalam himpunan semesta $E$ :

inklusi: $A \subseteq B$ bila $\forall x,\ x \in A \implies x \in B$ ; kesamaan $A = B$ bila $A \subseteq B$ dan $B \subseteq A$ ;
gabungan $A \cup B$ , irisan $A \cap B$ , selisih $A \setminus B = \{x \in A : x \notin B\}$ , komplemen $\overline{A} = E \setminus A$ ;
himpunan kosong $\emptyset$ , yang termuat dalam setiap himpunan;
himpunan kuasa $\mathcal{P}(E)$ : himpunan semua himpunan bagian dari $E$ ;
hasil kali $E \times F$ : himpunan pasangan terurut $(x, y)$ dengan $x \in E$ , $y \in F$ .

Contoh 1.17 (Membiasakan diri dengan himpunan kuasa)

Untuk $E = \{a, b\}$ :

\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\} \,\bigr\},

empat unsur — dan perhatikan disiplin tipenya: $a \in E$ tetapi $\{a\} \in \mathcal P(E)$ ; pernyataan $a \in \mathcal P(E)$ maupun $\{a\} \subseteq \mathcal P(E)$ keduanya salah sebagaimana tertulis (yang kedua menuntut $a$ menjadi himpunan bagian dari $E$ ). Diiterasikan dari ketiadaan: $\mathcal P(\emptyset) = \{\emptyset\}$ mempunyai satu unsur, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ mempunyai dua, berikutnya empat — himpunan yang anggotanya himpunan tetaplah himpunan biasa, dan Bab 2 akan membenarkan pola penggandaan itu: $\abs{\mathcal P(E)} = 2^{\abs E}$ . Menjaga agar tingkatannya ( $x$ , $\{x\}$ , $\{\{x\}\}$ ) tidak tertukar adalah separuh perjuangan dalam latihan seperti Latihan 1.11 dan 1.12.

Proposisi 1.18 (Aljabar himpunan)

Untuk himpunan bagian $A, B, C$ dari $E$ :

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ dan $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ dan $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ;
$A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

Bukti. Setiap kesamaan itu menerjemahkan satu kaidah Proposisi 1.3 lewat kamus ( $\in A$ atau bukan) $\leftrightarrow$ (pernyataan benar atau salah): misalnya $x \in \overline{A \cup B} \iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in \overline{A} \cap \overline{B}$ . Butir (3) adalah kontraposisi. Sebagai contoh kedua, hukum distributif yang pertama selengkapnya:

x \in A \cap (B \cup C) \iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr) \iff \bigl(x \in A \land x \in B\bigr) \lor \bigl(x \in A \land x \in C\bigr),

menurut sifat distributif pada Proposisi 1.3 (6), dan pernyataan terakhir itu terbaca $x \in (A \cap B) \cup (A \cap C)$ . Setiap kesamaan himpunan semacam ini dapat dibuktikan lewat satu terjemahan mekanis ini — itulah sebabnya tak satu pun perlu dihafal. ∎

Metode 1.19 (Membuktikan kesamaan himpunan)

Untuk membuktikan $A = B$ , buktikan kedua inklusinya: ambil $x \in A$ , tunjukkan $x \in B$ ; lalu ambil $x \in B$ , tunjukkan $x \in A$ . Cara lain, rangkaikan ekuivalensi $x \in A \iff \dots \iff x \in B$ bila setiap langkahnya memang benar-benar sebuah ekuivalensi.

Hukum De Morgan dalam gambar: daerah yang diarsir di sebelah kiri adalah A ∪ B = A ∩ B (segala sesuatu di luar kedua cakram); di sebelah kanan, A ∩ B = A ∪ B (segala sesuatu kecuali daerah tumpang-tindih yang berbentuk lensa). Sebuah diagram bukanlah bukti, tetapi ia membuat bukti pengejaran unsur pada mustahil salah diingat. — Hukum De Morgan dalam gambar: daerah yang diarsir di sebelah kiri adalah $\overline{A \cup B} = \overline A \cap \overline B$ (segala sesuatu di luar kedua cakram); di sebelah kanan, $\overline{A \cap B} = \overline A \cup \overline B$ (segala sesuatu kecuali daerah tumpang-tindih yang berbentuk lensa). Sebuah diagram bukanlah bukti, tetapi ia membuat bukti pengejaran unsur pada Proposisi 1.18 mustahil salah diingat.

1.5 Pemetaan

Definisi 1.20 (Pemetaan, peta, prapeta)

Sebuah pemetaan (atau fungsi) $f \colon E \to F$ mengaitkan setiap unsur $x$ pada himpunan $E$ (daerah asal) dengan tepat satu unsur $f(x)$ pada himpunan $F$ (daerah kawan). Untuk $A \subseteq E$ dan $B \subseteq F$ :

f(A) = \{f(x) : x \in A\} \subseteq F, \qquad f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E

berturut-turut adalah peta langsung dari $A$ dan prapeta dari $B$ . Komposisi dari $f \colon E \to F$ dan $g \colon F \to G$ adalah $g \circ f \colon E \to G$ , $x \mapsto g(f(x))$ .

Catatan 1.21

Notasi $f^{-1}(B)$ tidak mengandaikan adanya pemetaan invers: $f^{-1}(B)$ terdefinisi untuk setiap $f$ . Prapeta berperilaku lebih baik daripada peta: $f^{-1}$ mengawetkan gabungan, irisan dan komplemen, sedangkan $f(A \cap A') \subseteq f(A) \cap f(A')$ dapat berupa inklusi sejati (Latihan 1.8).

Contoh 1.22 (Menghitung peta dan prapeta)

Misalkan $f \colon \R \to \R$ , $x \mapsto x^2$ . Maka:

f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad f^{-1}(\{-1\}) = \emptyset .

Untuk yang pertama: setiap $x \in \intcc{-1}2$ memenuhi $x^2 \in \intcc04$ , dan setiap $y \in \intcc04$ tercapai sebagai $y = (\sqrt y)^2$ dengan $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — perhatikan bahwa petanya bukan $\intcc14 = \{(-1)^2, 2^2\}$ : peta sebuah selang tidak dihitung dari titik ujungnya saja. Untuk yang kedua: $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$ , yang terpecah menjadi dua potong. Yang ketiga memperlihatkan bahwa prapeta boleh kosong — $f^{-1}(B)$ selalu bermakna, sekecil apa pun irisan $B$ dengan peta itu. Akhirnya perhatikan pada contoh ini gejala inklusi sejati dari catatan di atas: dengan $A = \intcc{-1}0$ dan $A' = \intcc01$ , kita peroleh $f(A \cap A') = f(\{0\}) = \{0\}$ , sedangkan $f(A) \cap f(A') = \intcc01$ .

Definisi 1.23 (Injektif, surjektif, bijektif)

Sebuah pemetaan $f \colon E \to F$ disebut:

injektif bila unsur yang berbeda mempunyai peta yang berbeda: $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ ;
surjektif bila setiap unsur $F$ tercapai: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
bijektif bila keduanya berlaku, yakni setiap $y \in F$ mempunyai tepat satu prapeta.

Teorema 1.24 (Pemetaan invers)

Pemetaan $f \colon E \to F$ bijektif jika dan hanya jika ada pemetaan $g \colon F \to E$ dengan $g \circ f = \mathrm{id}_E$ dan $f \circ g = \mathrm{id}_F$ . Dalam hal itu $g$ tunggal; ia ditulis $f^{-1}$ dan disebut invers dari $f$ , dan $f^{-1}$ sendiri bijektif dengan $(f^{-1})^{-1} = f$ .

Bukti. ( $\Rightarrow$ ) Jika $f$ bijektif, setiap $y \in F$ mempunyai tepat satu prapeta; definisikan $g(y)$ sebagai prapeta itu. Maka $f(g(y)) = y$ menurut konstruksinya, dan $g(f(x)) = x$ karena $x$ adalah satu-satunya prapeta $f(x)$ .

( $\Leftarrow$ ) Andaikan $g$ semacam itu ada. Jika $f(x) = f(x')$ , penerapan $g$ memberikan $x = x'$ : jadi $f$ injektif. Untuk $y \in F$ , unsur $x = g(y)$ memenuhi $f(x) = y$ : jadi $f$ surjektif.

Ketunggalan: jika $g$ dan $h$ sama-sama memenuhi, maka $g = g \circ \mathrm{id}_F = g \circ (f \circ h) = (g \circ f) \circ h = h$ . Akhirnya pasangan kesamaan itu simetris dalam $f$ dan $g$ , sehingga $g = f^{-1}$ bijektif dengan invers $f$ . ∎

Contoh 1.25 (Menghitung invers dalam praktik)

Misalkan $f \colon \R \to \intoo0{+\infty}$ , $f(x) = \eu^{2x+1}$ . Untuk membalikkannya, selesaikan $y = f(x)$ bagi $y > 0$ yang diberikan:

y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,

setiap langkahnya dapat dibalik pada daerah yang telah diumumkan. Perhitungan itu sekaligus menyerahkan segalanya: untuk setiap $y$ pada daerah kawan ada tepat satu penyelesaian $x$ , sehingga $f$ bijektif, dan

f^{-1} \colon \intoo0{+\infty} \to \R, \qquad f^{-1}(y) = \frac{\ln y - 1}2 .

Pemeriksaan cepat atas kedua komposisinya ( $f^{-1}(f(x)) = \frac{(2x+1) - 1}2 = x$ dan $f(f^{-1}(y)) = \eu^{\ln y} = y$ ) membenarkan kriteria Teorema 1.24. Inti gagasannya: “selesaikan untuk $x$ dan awasi ekuivalensinya” sekaligus merupakan bukti keberadaan, bukti ketunggalan, dan rumusnya — tetapi itu hanya berhasil bila daerah kawannya diumumkan dengan benar ( $f$ tidak surjektif ke $\R$ ).

Proposisi 1.26 (Komposisi dan ketiga sifat itu)

Misalkan $f \colon E \to F$ dan $g \colon F \to G$ .

Jika $f$ dan $g$ injektif (masing-masing surjektif, bijektif), maka demikian pula $g \circ f$ ; dan dalam kasus bijektif berlaku $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
Jika $g \circ f$ injektif, maka $f$ injektif. Jika $g \circ f$ surjektif, maka $g$ surjektif.

Bukti. (1) Jika $g(f(x)) = g(f(x'))$ , keinjektifan $g$ memberikan $f(x) = f(x')$ , lalu keinjektifan $f$ memberikan $x = x'$ . Jika $z \in G$ , kesurjektifan $g$ memberikan $y$ dengan $g(y) = z$ , lalu kesurjektifan $f$ memberikan $x$ dengan $f(x) = y$ , sehingga $g(f(x)) = z$ . Dalam kasus bijektif kita periksa langsung bahwa $f^{-1} \circ g^{-1}$ adalah invers dua sisi dari $g \circ f$ , dan ketunggalan pada Teorema 1.24 menutup buktinya.

(2) Jika $f(x) = f(x')$ maka $g(f(x)) = g(f(x'))$ , dan keinjektifan $g \circ f$ memberikan $x = x'$ . Jika $z \in G$ , kesurjektifan $g \circ f$ memberikan $x$ dengan $g(f(x)) = z$ : lalu $y = f(x)$ memenuhi $g(y) = z$ . ∎

Contoh 1.27 (Butir (2) sudah tajam)

Pada Proposisi 1.26 (2), kesimpulannya tidak dapat diperkuat: $g \circ f$ bijektif tidak memaksa $f$ surjektif atau $g$ injektif. Ambil $E = G = \{1\}$ , $F = \{1, 2\}$ , dengan $f(1) = 1$ dan $g(1) = g(2) = 1$ : maka $g \circ f = \mathrm{id}_E$ bijektif, namun $f$ melewatkan unsur $2$ dan $g$ meleburkan kedua unsurnya. Moralnya adalah aturan pembukuan yang tepat: informasi komposisi mengalir ke pemetaan dalam untuk keinjektifan dan ke pemetaan luar untuk kesurjektifan, tidak pernah sebaliknya. (Latihan 1.9 membangun gejala yang sama dengan himpunan tak hingga, tempat gejala itu menjadi mesin di balik invers sepihak.)

Contoh 1.28

$f \colon \R \to \R$ , $x \mapsto x^2$ tidak injektif ( $f(-1) = f(1)$ ) dan tidak pula surjektif ( $-1$ tak punya prapeta). Dengan membatasi daerah asal dan daerah kawan, $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ bijektif, dengan invers $y \mapsto \sqrt y$ . Keinjektifan atau kesurjektifan sebuah pemetaan bergantung pada daerah asal dan daerah kawan yang diumumkan, bukan hanya pada rumusnya.

1.6 Relasi

Definisi 1.29 (Relasi ekuivalensi)

Sebuah relasi biner $\mathcal{R}$ pada himpunan $E$ disebut relasi ekuivalensi bila ia bersifat refleksif ( $x \mathbin{\mathcal{R}} x$ untuk setiap $x$ ), simetris ( $x \mathbin{\mathcal{R}} y \implies y \mathbin{\mathcal{R}} x$ ) dan transitif ( $x \mathbin{\mathcal{R}} y$ dan $y \mathbin{\mathcal{R}} z$ mengakibatkan $x \mathbin{\mathcal{R}} z$ ). Kelas ekuivalensi dari $x$ adalah $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$ .

Contoh 1.30 (Memeriksa ketiga aksioma)

Pada $\R$ , tetapkan $x \mathbin{\mathcal{R}} y$ bila $x - y \in \Z$ . Refleksif: $x - x = 0 \in \Z$ . Simetris: jika $x - y \in \Z$ maka $y - x = -(x - y) \in \Z$ . Transitif: jika $x - y \in \Z$ dan $y - z \in \Z$ , maka $x - z = (x - y) + (y - z) \in \Z$ (jumlah dua bilangan bulat). Jadi $\mathcal R$ adalah relasi ekuivalensi, dan $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$ : setiap kelas memuat tepat satu wakil di $\intco01$ , yaitu bagian pecahan-nya. Sebaliknya, relasi “ $\abs{x - y} \leq 1$ ” pada $\R$ bersifat refleksif dan simetris tetapi tidak transitif ( $0 \mathbin{\mathcal R} 1$ dan $1 \mathbin{\mathcal R} 2$ , padahal $\abs{0 - 2} > 1$ ): kedekatan tidak menular, dan tidak ada partisi ke dalam kelas — contoh penyangkal yang berguna untuk diingat ketika pemeriksaan aksioma mulai terasa rutin.

Teorema 1.31 (Kelas-kelasnya membentuk partisi)

Misalkan $\mathcal{R}$ relasi ekuivalensi pada $E$ . Maka kelas-kelas ekuivalensinya tak kosong, saling lepas atau sama, dan gabungannya adalah $E$ : kelas-kelas itu membentuk partisi dari $E$ . Sebaliknya, setiap partisi dari $E$ muncul dengan cara ini dari tepat satu relasi ekuivalensi (“berada pada potongan yang sama”).

Bukti. $x \in \mathrm{cl}(x)$ menurut kerefleksifan, jadi setiap kelas tak kosong dan gabungannya $E$ . Andaikan $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$ , katakanlah $z$ terletak di keduanya. Maka $x \mathbin{\mathcal{R}} z$ dan $y \mathbin{\mathcal{R}} z$ , sehingga menurut kesimetrisan dan ketransitifan $x \mathbin{\mathcal{R}} y$ . Selanjutnya untuk sebarang $t \in \mathrm{cl}(y)$ , ketransitifan memberikan $t \in \mathrm{cl}(x)$ , dan begitu pula sebaliknya: kedua kelas itu sama. Untuk arah sebaliknya, misalkan $(E_i)_{i \in I}$ sebuah partisi dari $E$ dan definisikan $x \mathbin{\mathcal S} y$ sebagai “ada potongan yang memuat $x$ dan $y$ sekaligus”. Refleksif: $x$ terletak pada suatu potongan, yang lalu memuat $x$ dua kali. Simetris: syarat pendefinisinya simetris dalam $x$ dan $y$ . Transitif: jika $x, y \in E_i$ dan $y, z \in E_j$ , maka $y \in E_i \cap E_j$ , sehingga $E_i = E_j$ (potongan yang berbeda saling lepas) dan $x, z$ berbagi satu potongan. Kelas- $\mathcal S$ dari $x$ tepat sama dengan potongan yang memuat $x$ , jadi kelas-kelasnya adalah potongan yang diberikan itu. Akhirnya relasinya ditentukan oleh kelas-kelasnya: dua relasi ekuivalensi dengan kelas yang sama merelasikan pasangan yang sama, karena masing-masing merelasikan $x$ dan $y$ tepat ketika $y$ termasuk dalam kelas $x$ — dari sanalah klaim ketunggalannya. ∎

Contoh 1.32

Pada $\Z$ , kekongruenan modulo $n$ ( $x \equiv y \pmod n$ bila $n$ membagi $x - y$ ) adalah relasi ekuivalensi; kelas-kelasnya adalah $n$ himpunan bilangan bulat yang bersisa tertentu bila dibagi $n$ . Contoh ini menjelma menjadi ring $\Z/n\Z$ pada Bab 7.

Definisi 1.33 (Relasi urutan)

Relasi $\preceq$ pada $E$ disebut urutan bila ia refleksif, antisimetris ( $x \preceq y$ dan $y \preceq x$ mengakibatkan $x = y$ ) serta transitif. Urutan itu total bila setiap dua unsur dapat dibandingkan, dan parsial bila tidak. Unsur $M \in A \subseteq E$ disebut unsur terbesar dari $A$ bila $a \preceq M$ untuk setiap $a \in A$ ; unsur terbesar (dan terkecil) bersifat tunggal bila ada.

Contoh 1.34

$(\R, \leq)$ terurut total. $(\mathcal{P}(E), \subseteq)$ terurut parsial begitu $E$ mempunyai dua unsur: $\{a\}$ dan $\{b\}$ tak dapat dibandingkan. Himpunan bagian $A = \{\{a\}, \{b\}\}$ dari $\mathcal{P}(\{a,b\})$ tak mempunyai unsur terbesar, namun mempunyai batas atas $\{a, b\}$ : pembedaan antara unsur terbesar dan batas atas muncul kembali, untuk $\R$ , pada Bab 10.

Contoh 1.35 (Dua urutan pada kisi $\N^2$ )

Pada pasangan bilangan cacah, bandingkan komponen demi komponen: $(a, b) \preceq (a', b')$ bila $a \leq a'$ dan $b \leq b'$ (urutan hasil kali). Ini memang urutan — setiap aksiomanya diwarisi koordinat demi koordinat — tetapi urutan parsial: $(1, 3)$ dan $(2, 0)$ tak terbandingkan. Kini bandingkan seperti kamus: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ bila $a < a'$ , atau $a = a'$ dan $b \leq b'$ (urutan leksikografis). Ketransitifannya menuntut pemeriksaan dua kasus tetapi tetap berlaku, dan kini setiap dua pasangan dapat dibandingkan: urutannya total. Kedua urutan itu memeringkat himpunan yang sama secara berbeda — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ padahal urutan hasil kali tak berkata apa-apa — sebuah pengingat bahwa urutan adalah struktur yang kita pilih, bukan sifat dari himpunannya. Perbandingan leksikografis juga merupakan kiat baku untuk melebur beberapa kriteria pengurutan menjadi satu.

Catatan 1.36 (Selingan: ukuran sebagai bijeksi)

Sebuah tema yang mengalir diam-diam sepanjang bab ini pantas disorot: bijeksi adalah gagasan matematikawan tentang “ukuran yang sama”. Untuk himpunan hingga hal ini menjelma menjadi kalkulus pencacahan pada Bab 2, tempat setiap rumus diam-diam merupakan sebuah bijeksi; untuk himpunan tak hingga hal itu menjelma menjadi soal akhir pekan di bawah, tempat $\N$ , $\Q$ dan $\R$ ternyata mempunyai ukuran yang sungguh-sungguh berbeda. Kamus yang sama muncul dua kali lagi dalam jilid ini dalam bentuk yang lebih halus: barisan (Bab 11) tidak lain adalah pemetaan $\N \to \R$ , sehingga pernyataan tentang barisan adalah pernyataan tentang sebuah himpunan pemetaan; dan aljabar linear akan mengukur ruang vektor bukan dengan bijeksi melainkan dengan bijeksi linear, yang keberadaannya dikendalikan oleh satu bilangan tunggal, yaitu dimensi (Bab 19). Setiap kali sebuah “kesamaan” yang baru muncul — ekuipotensi, isomorfisma grup (Bab 7), isomorfisma linear — pola Teorema 1.24 berulang: kesamaan adalah pemetaan yang punya invers dan menghormati struktur.

Catatan 1.37 (Di mana bab ini dipakai)

Di mana-mana — tetapi beberapa tempat pantas ditandai. Senam tiga kuantor pada Contoh 1.8 adalah santapan sehari-hari Bab 11 dan 13: setiap bukti limit adalah permainan melawan $\varepsilon$ yang sembarang. Kelas ekuivalensi muncul kembali sebagai kelas kekongruenan $\Z/n\Z$ pada Bab 7, tempat partisi Teorema 1.31 memperoleh struktur aljabar tersendiri. Relasi urutan, batas atas dan batas atas terkecil menjadi jantung aksiomatis $\R$ pada Bab 10. Injeksi, surjeksi dan bijeksi kembali sebagai pemetaan linear pada Bab 20, tempat keinjektifan dapat diuji pada satu vektor saja (kernelnya); dan soal akhir pekan di bawah mengubah gagasan bijeksi yang telanjang menjadi teori tentang ukuran himpunan tak hingga, yang kesimpulannya (keterbilangan $\Q$ , ketakterbilangan $\R$ ) muncul lagi pada Bab 10 dan 12.

1.7 Latihan

Latihan 1.1 ★

Tuliskan negasi setiap pernyataan berikut, tanpa memakai kata “bukan”:

$\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
$\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (untuk sebuah pemetaan tetap $f \colon \R \to \R$ ).

Kemudian tentukan apakah pernyataan (1) dan (2) benar.

Solusi

Solusi Latihan 1.1.

Negasi, dengan mendorong $\lnot$ melewati setiap kuantor (Proposisi 1.5) dan memakai $\lnot(P \implies Q) \iff P \land \lnot Q$ :

$\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
$\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
$\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \R,\ \abs{x} \leq \delta \text{ dan } \abs{f(x)} > \varepsilon$ .

Pernyataan (1) benar: diberikan $x$ , ambil $y = -x + 1$ ; maka $x + y = 1 > 0$ . Pernyataan (2) benar: $x = 0$ memenuhi $xy = 0$ untuk setiap $y$ .

Latihan 1.2 ★

Misalkan $P, Q$ pernyataan. Dengan tabel kebenaran, buktikan bahwa $\lnot(P \implies Q) \iff P \land (\lnot Q)$ , lalu simpulkan negasi dari: “jika sebuah fungsi dapat diturunkan maka ia kontinu”.

Solusi

Solusi Latihan 1.2.

Tabel kebenaran, dengan menulis B/S untuk keempat kasus $(P, Q)$ :

$P$	$Q$	$P \implies Q$	$\lnot(P \implies Q)$	$\lnot Q$	$P \land \lnot Q$
B	B	B	S	S	S
B	S	S	B	B	B
S	B	B	S	S	S
S	S	B	S	B	S

Kolom $4$ dan $6$ berimpit, dan itu membuktikan ekuivalensinya. Negasi dari “jika sebuah fungsi dapat diturunkan maka ia kontinu” karena itu berbunyi: “ada fungsi yang dapat diturunkan dan tidak kontinu” (sebuah pernyataan yang salah, kebetulan saja: implikasi aslinya benar, lihat Bab 14).

Latihan 1.3 ★

Buktikan dengan kontraposisi: untuk $x \in \R$ , jika $x^3 + x \geq 2$ maka $x \geq 1$ . Kemudian buktikan dengan kontradiksi: tidak ada bilangan real positif tegas yang terkecil.

Solusi

Solusi Latihan 1.3.

Kontraposisi. Andaikan $x < 1$ . Maka $x^3 < 1$ (fungsi pangkat tiga naik) dan $x < 1$ , sehingga $x^3 + x < 2$ . Ini membuktikan kontraposisinya, jadi juga pernyataan itu sendiri.

Kontradiksi. Andaikan $a > 0$ bilangan real positif tegas yang terkecil. Maka $a/2$ positif tegas dan $a/2 < a$ (karena $a > 0$ ), bertentangan dengan keminimalannya. Jadi $a$ semacam itu tidak ada.

Latihan 1.4 ★

Buktikan dengan induksi bahwa untuk setiap $n \in \N$ :

$\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
$4^n + 5$ habis dibagi $3$ .

Solusi

Solusi Latihan 1.4.

Basis $n = 0$ : $2^0 = 1 = 2^1 - 1$ . Langkah: dengan mengandaikan kesamaan itu berlaku untuk $n$ ,

$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$
Basis $n = 0$ : $4^0 + 5 = 6 = 3 \times 2$ . Langkah: jika $4^n + 5 = 3m$ , maka

$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$

yang habis dibagi $3$ .

Latihan 1.5 ★

Temukan cacat pada “bukti” berikut bahwa semua pensil berwarna sama. Misalkan $P(n)$ : “pada setiap himpunan berisi $n$ pensil, semua pensil berwarna sama”. $P(1)$ jelas. Andaikan $P(n)$ lalu ambil $n+1$ pensil; dengan membuang yang terakhir, $n$ pensil pertama sewarna; dengan membuang yang pertama, $n$ pensil terakhir sewarna; jadi semua $n+1$ pensil sewarna.

Solusi

Solusi Latihan 1.5.

Langkah induksinya diam-diam mengandaikan bahwa kedua kelompok (“ $n$ pertama” dan “ $n$ terakhir”) saling tumpang-tindih, sehingga pensil bersamanya membawa warna dari kelompok yang satu ke kelompok yang lain. Untuk $n + 1 = 2$ kedua kelompok itu adalah $\{$ pensil pertama $\}$ dan $\{$ pensil kedua $\}$ : keduanya saling lepas, dan argumennya runtuh. Jadi $P(1) \implies P(2)$ tidak pernah dibuktikan, dan induksinya ambruk — walaupun $P(n) \implies P(n+1)$ sah untuk setiap $n \geq 2$ .

Latihan 1.6 ★

Misalkan $A, B, C$ himpunan bagian dari $E$ . Buktikan:

$A \setminus B = A \cap \overline{B}$ ;
$(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ ;
$A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

Solusi

Solusi Latihan 1.6.

$x \in A \setminus B \iff x \in A \land x \notin B \iff x \in A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
Dengan memakai (1) dan sifat distributif (Proposisi 1.18): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ .
Andaikan $A \subseteq B$ . Maka $A \cup B \subseteq B$ (kedua potongannya terletak di $B$ ) dan $B \subseteq A \cup B$ selalu berlaku, sehingga $A \cup B = B$ . Andaikan $A \cup B = B$ : maka $A \cap B \subseteq A$ selalu berlaku, dan $A \subseteq A \cup B = B$ memberikan $A \subseteq A \cap B$ , sehingga $A \cap B = A$ . Andaikan $A \cap B = A$ : maka $A = A \cap B \subseteq B$ . Jadi ketiga syarat itu ekuivalen (kita membuktikan satu daur implikasi).

Latihan 1.7 ★★

Untuk setiap pemetaan berikut, tentukan (dengan bukti) apakah ia injektif, surjektif, atau bijektif:

$f \colon \N \to \N$ , $n \mapsto n + 1$ ;
$g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
$h \colon \R \setminus \{1\} \to \R$ , $x \mapsto \frac{x+1}{x-1}$ .

Untuk $h$ , sesuaikan daerah kawannya agar ia bijektif, lalu hitung inversnya.

Solusi

Solusi Latihan 1.7.

$f$ injektif ( $n + 1 = m + 1 \implies n = m$ ) tetapi tidak surjektif: $0$ tak mempunyai prapeta di $\N$ .
$g$ bijektif: $n \mapsto n - 1$ adalah invers dua sisi pada $\Z$ .
$h$ injektif: $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ memberikan $(x+1)(x'-1) = (x'+1)(x-1)$ , yaitu $xx' - x + x' - 1 = xx' - x' + x - 1$ , sehingga $2x' = 2x$ . Ia tidak surjektif pada $\R$ : menyelesaikan $y = \frac{x+1}{x-1}$ memberikan $x(y - 1) = y + 1$ , yang tak punya penyelesaian bila $y = 1$ (persamaannya menjadi $0 = 2$ ). Dengan daerah kawan $\R \setminus \{1\}$ , perhitungan yang sama memberikan prapeta tunggal $x = \frac{y+1}{y-1}$ , sehingga $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ bersifat bijektif dan $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ adalah inversnya sendiri.

Latihan 1.8 ★★

Misalkan $f \colon E \to F$ , dan misalkan $A, A' \subseteq E$ serta $B, B' \subseteq F$ .

Buktikan $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ dan $f(A \cup A') = f(A) \cup f(A')$ .
Buktikan $f(A \cap A') \subseteq f(A) \cap f(A')$ lalu berikan contoh yang inklusinya sejati.
Buktikan: $f$ injektif jika dan hanya jika $f(A \cap A') = f(A) \cap f(A')$ untuk setiap $A, A'$ .

Solusi

Solusi Latihan 1.8.

$x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in B \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ . Untuk peta: $y \in f(A \cup A')$ berlaku persis bila $y = f(x)$ untuk suatu $x$ di $A$ atau di $A'$ , yakni bila $y \in f(A)$ atau $y \in f(A')$ .
Jika $y \in f(A \cap A')$ , maka $y = f(x)$ dengan $x \in A$ dan $x \in A'$ , sehingga $y \in f(A)$ dan $y \in f(A')$ . Kesejatiannya: ambil $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : maka $f(A \cap A') = f(\emptyset) = \emptyset$ tetapi $f(A) \cap f(A') = \{1\}$ .
( $\Leftarrow$ ) Dengan $A = \{x\}$ , $A' = \{x'\}$ untuk $x \neq x'$ : jika $f(x) = f(x')$ , maka $f(A) \cap f(A') = \{f(x)\}$ sedangkan $f(A \cap A') = \emptyset$ , bertentangan dengan kesamaan yang diandaikan; jadi $f$ injektif. ( $\Rightarrow$ ) Misalkan $f$ injektif dan $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ dengan $x \in A$ , $x' \in A'$ ; keinjektifan memberikan $x = x' \in A \cap A'$ , sehingga $y \in f(A \cap A')$ . Bersama (2), kesamaannya berlaku.

Latihan 1.9 ★★

Misalkan $f \colon E \to F$ dan $g \colon F \to E$ memenuhi $g \circ f = \mathrm{id}_E$ . Buktikan bahwa $f$ injektif dan $g$ surjektif. Berikan contoh yang $f$ maupun $g$ -nya tidak bijektif.

Solusi

Solusi Latihan 1.9.

$g \circ f = \mathrm{id}_E$ bersifat injektif sekaligus surjektif, jadi menurut Proposisi 1.26 (2), $f$ injektif dan $g$ surjektif. Contoh: $E = \N$ , $F = \Z$ , $f$ pemetaan inklusi $n \mapsto n$ , dan $g \colon \Z \to \N$ , $g(n) = n$ untuk $n \geq 0$ dan $g(n) = 0$ untuk $n < 0$ . Maka $g(f(n)) = n$ untuk setiap $n \in \N$ , tetapi $f$ tidak surjektif dan $g$ tidak injektif.

Latihan 1.10 ★★

Pada $\R$ , definisikan $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ . Buktikan bahwa $\mathcal{R}$ adalah relasi ekuivalensi lalu jelaskan kelas ekuivalensi setiap bilangan real $x$ . Kelas mana yang beranggotakan tepat satu unsur?

Solusi

Solusi Latihan 1.10.

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1) = 0 \iff y = x$ atau $y = 1 - x$ . Refleksif: $y = x$ memenuhi. Simetris: syarat “ $y = x$ atau $y = 1 - x$ ” bersifat simetris dalam $x$ dan $y$ (jika $y = 1 - x$ maka $x = 1 - y$ ). Transitif: andaikan $x \mathbin{\mathcal{R}} y$ dan $y \mathbin{\mathcal{R}} z$ ; dengan menelusuri keempat kasusnya, $z$ selalu sama dengan $x$ atau $1 - x$ (misalnya $y = 1 - x$ dan $z = 1 - y$ memberikan $z = x$ ). Jadi $\mathcal{R}$ adalah relasi ekuivalensi dan $\mathrm{cl}(x) = \{x,\, 1 - x\}$ . Kelas ini beranggotakan satu unsur tepat ketika $x = 1 - x$ , yaitu untuk $x = \frac12$ .

Latihan 1.11 ★★★

(Cantor) Misalkan $E$ sebuah himpunan. Buktikan bahwa tidak ada surjeksi dari $E$ pada $\mathcal{P}(E)$ . Petunjuk: diberikan $f \colon E \to \mathcal{P}(E)$ , tinjau $D = \{x \in E : x \notin f(x)\}$ .

Solusi

Solusi Latihan 1.11.

Misalkan $f \colon E \to \mathcal{P}(E)$ sebuah pemetaan sembarang lalu tulis $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$ . Andaikan $D = f(a)$ untuk suatu $a \in E$ . Jika $a \in D$ , maka menurut definisi $D$ , $a \notin f(a) = D$ : kontradiksi. Jika $a \notin D$ , maka $a \notin f(a)$ , sehingga menurut definisi $D$ , $a \in D$ : kontradiksi. Jadi $D$ tidak berada pada peta $f$ , dan $f$ tidak surjektif. (Khususnya tak ada himpunan yang berbijeksi dengan himpunan kuasanya: ada “lebih banyak” himpunan bagian $\N$ daripada bilangan bulat.)

Latihan 1.12 ★★★

Misalkan $f \colon E \to F$ sebuah pemetaan. Definisikan $\Phi \colon \mathcal{P}(F) \to \mathcal{P}(E)$ dengan $\Phi(B) = f^{-1}(B)$ .

Buktikan bahwa $f$ surjektif jika dan hanya jika $\Phi$ injektif.
Buktikan bahwa $f$ injektif jika dan hanya jika $\Phi$ surjektif.

Solusi

Solusi Latihan 1.12.

( $\Rightarrow$ ) Misalkan $f$ surjektif dan $\Phi(B) = \Phi(B')$ . Untuk $y \in B$ , pilih $x$ dengan $f(x) = y$ ; maka $x \in f^{-1}(B) = f^{-1}(B')$ , sehingga $y = f(x) \in B'$ . Jadi $B \subseteq B'$ , dan secara simetris $B' \subseteq B$ : $\Phi$ injektif. ( $\Leftarrow$ ) Jika $f$ tidak surjektif, pilih $y_0 \in F$ di luar petanya; maka $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ padahal $\{y_0\} \neq \emptyset$ , sehingga $\Phi$ tidak injektif.
( $\Rightarrow$ ) Misalkan $f$ injektif dan $A \subseteq E$ . Tulis $B = f(A)$ ; maka $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , dan keinjektifan memberikan $f(x) \in f(A) \iff x \in A$ , sehingga $\Phi(B) = A$ : jadi $\Phi$ surjektif. ( $\Leftarrow$ ) Jika $f$ tidak injektif, ambil $x \neq x'$ dengan $f(x) = f(x')$ . Setiap himpunan prapeta $f^{-1}(B)$ memuat $x$ jika dan hanya jika ia memuat $x'$ ; jadi $\{x\}$ tidak berbentuk $\Phi(B)$ , dan $\Phi$ tidak surjektif.

1.8 Soal: Membandingkan ketakhinggaan

Soal 1.1

Kapan dua himpunan dikatakan mempunyai “banyak unsur yang sama”? Jawaban Cantor — ketika ada bijeksi di antara keduanya — ternyata dapat dipakai bahkan untuk himpunan tak hingga, dan jawaban itu memecah ketakhinggaan menjadi ukuran yang sungguh berbeda. Soal ini membangun seluruh perkakasnya dari definisi telanjang bab ini: teorema Cantor–Schröder–Bernstein (dua injeksi memproduksi sebuah bijeksi), keterbilangan $\Q$ , ketakterbilangan $\R$ lewat argumen diagonal, dan kesimpulan Cantor tahun 1874 yang mencengangkan: bilangan transenden itu ada, dan sangat banyak, tanpa menunjukkan satu pun. Di sepanjang soal ini, untuk himpunan $E$ dan $F$ , tulis $E \preceq F$ bila ada injeksi dari $E$ ke dalam $F$ , dan $E \approx F$ (“ $E$ dan $F$ ekuipoten”) bila ada bijeksi dari $E$ pada $F$ .

Bagian I — Kosakata perbandingan.

Tunjukkan bahwa $\approx$ berperilaku seperti relasi ekuivalensi: $E \approx E$ ; jika $E \approx F$ maka $F \approx E$ ; jika $E \approx F$ dan $F \approx G$ maka $E \approx G$ . (Kutip secara persis Teorema 1.24 dan Proposisi 1.26.)
Tunjukkan bahwa $\preceq$ transitif, dan bahwa injeksi $f \colon E \to F$ selalu melahirkan $E \approx f(E)$ .
Misalkan $E \neq \emptyset$ . Tunjukkan bahwa $E \preceq F$ jika dan hanya jika ada surjeksi dari $F$ pada $E$ .
Periksa bahwa $n \mapsto n + 1$ adalah bijeksi dari $\N$ pada $\N^* = \N \setminus \{0\}$ , dan bahwa

$\sigma(n) = \frac n2 \ \ (n \text{ genap}), \qquad \sigma(n) = -\frac{n+1}2 \ \ (n \text{ ganjil})$

adalah bijeksi dari $\N$ pada $\Z$ . Jadi membuang satu titik, atau melipatgandakan ke arah negatif, tidak mengubah ukuran $\N$ .

Bagian II — Teorema Cantor–Schröder–Bernstein. Misalkan $f \colon E \to F$ dan $g \colon F \to E$ dua injeksi. Definisikan

C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr) \ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,

lalu misalkan $h \colon E \to F$ memetakan $x \in C$ ke $f(x)$ , dan $x \notin C$ ke satu-satunya $y \in F$ dengan $g(y) = x$ .

Periksa bahwa $h$ terdefinisi dengan baik: jika $x \notin C$ maka $x \in g(F)$ , dan unsur $y$ dengan $g(y) = x$ bersifat tunggal.
Tunjukkan bahwa $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ . (Peta langsung berkomutasi dengan gabungan: Latihan 1.8.)
Tunjukkan bahwa $h$ injektif. (Tiga kasus; pada kasus campuran $x \in C$ , $x' \notin C$ , tunjukkan bahwa $h(x) = h(x')$ akan memaksa $x' \in g(f(C)) \subseteq C$ .)
Tunjukkan bahwa $h$ surjektif: diberikan $y \in F$ , bedakan kasus $g(y) \notin C$ dan $g(y) \in C_n$ untuk suatu $n \geq 1$ (mengapa $g(y) \in C_0$ mustahil?), lalu tunjukkan sebuah prapeta dari $y$ pada masing-masing kasus.
Simpulkan dengan teorema Cantor–Schröder–Bernstein: jika $E \preceq F$ dan $F \preceq E$ , maka $E \approx F$ . Berikan satu kalimat komentar tentang apa yang membuat pernyataan ini tidak sepele.
Dua penerapan. (a) Tunjukkan $\intcc01 \approx \intoo01$ . (b) Tunjukkan bahwa $\varphi(p, q) = 2^p(2q + 1) - 1$ mendefinisikan bijeksi dari $\N \times \N$ pada $\N$ — keinjektifan lewat argumen paritas, kesurjektifan lewat induksi kuat (Teorema 1.12). Jadi $\N \times \N \approx \N$ : bidang titik bulat tidak lebih besar daripada garis.

Bagian III — Himpunan terbilang. Sebuah himpunan $E$ disebut paling banyak terbilang bila $E \preceq \N$ , dan terbilang bila $E \approx \N$ .

Tunjukkan bahwa setiap himpunan bagian tak hingga $A \subseteq \N$ bersifat terbilang. (Definisikan $\varphi(n)$ secara rekursif sebagai unsur terkecil dari $A \setminus \{\varphi(0), \dots, \varphi(n-1)\}$ ; tunjukkan bahwa $\varphi$ naik tegas, memenuhi $\varphi(n) \geq n$ , dan mencapai setiap unsur $A$ .)
Simpulkan bahwa sebuah himpunan paling banyak terbilang jika dan hanya jika ia hingga atau terbilang, lalu amati bahwa pertanyaan 9 memberi jalan pintas: jika $E \preceq \N$ dan $\N \preceq E$ , maka $E$ terbilang.
Tunjukkan bahwa jika $E$ dan $F$ paling banyak terbilang, maka demikian pula $E \times F$ . Simpulkan bahwa $\Z \times \N^*$ terbilang.
Tunjukkan bahwa $\Q$ terbilang. (Injeksikan $\Q$ ke dalam $\Z \times \N^*$ dengan menuliskan setiap bilangan rasional dalam bentuk paling sederhana berpenyebut positif — ketunggalan penyajian itu dibuktikan pada Bab 6; lalu terapkan pertanyaan 12.)
Tunjukkan bahwa gabungan terbilang dari himpunan yang paling banyak terbilang tetap paling banyak terbilang: jika setiap $E_n$ ( $n \in \N$ ) paling banyak terbilang, maka demikian pula $\bigcup_{n \in \N} E_n$ . (Kirim $x$ ke pasangan $(n, f_n(x))$ dengan $n$ indeks terkecil yang memenuhi $x \in E_n$ .)
Tunjukkan bahwa himpunan semua himpunan bagian hingga dari $\N$ bersifat terbilang. (Petakan himpunan bagian hingga $F$ ke $\sum_{i \in F} 2^i$ ; buktikan keinjektifannya dengan membandingkan unsur terbesar tempat kedua himpunan hingga itu berbeda, memakai $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ dari Latihan 1.4.)

Bagian IV — Diagonalisasi. Misalkan $\{0,1\}^{\N}$ menyatakan himpunan semua pemetaan $u \colon \N \to \{0, 1\}$ , yakni himpunan barisan biner.

Konstruksikan bijeksi antara $\mathcal{P}(\N)$ dan $\{0,1\}^{\N}$ (fungsi indikator).
(Argumen diagonal) Misalkan $\Phi \colon \N \to \{0,1\}^{\N}$ sebuah pemetaan sembarang. Tinjau barisan $d$ yang didefinisikan oleh $d(n) = 1 - \Phi(n)(n)$ . Tunjukkan bahwa $d$ tidak berada pada peta $\Phi$ , lalu simpulkan bahwa $\{0,1\}^{\N}$ tidak paling banyak terbilang. Jelaskan dalam satu kalimat mengapa, lewat pertanyaan 17, hal ini tepat merupakan teorema Cantor (Latihan 1.11) untuk $E = \N$ .
Terima — sebagaimana sudah dikenal sejak sekolah, dan ditegakkan secara ketat pada Bab 10 — bahwa setiap $x \in \intco01$ mempunyai satu ekspansi desimal sejati yang tunggal $x = 0.d_1 d_2 d_3\dots$ (yaitu yang tidak berakhir dengan untaian tak hingga angka $9$ ). Diberikan sebarang barisan $(x_n)_{n \geq 1}$ unsur $\intco01$ , konstruksikan $x \in \intco01$ dengan $x \neq x_n$ untuk setiap $n$ : pilih angka ke- $n$ -nya sama dengan $5$ bila angka ke- $n$ dari $x_n$ berbeda dari $5$ , dan $6$ bila tidak. Berikan alasan cermat bahwa $x$ sejati dan menghindari setiap $x_n$ , lalu simpulkan bahwa $\intco01$ tidak paling banyak terbilang.
Simpulkan bahwa $\R$ tak terbilang, dan bahwa himpunan $\R \setminus \Q$ berisi bilangan irasional juga tak terbilang. Dalam pengertian apa persisnya “kebanyakan” bilangan real bersifat irasional?

Bagian V — Teorema Cantor tahun 1874: bilangan transenden itu ada. Bilangan real $x$ disebut aljabar bila $P(x) = 0$ untuk suatu polinomial tak nol $P$ berkoefisien bulat, dan transenden bila tidak. Terima untuk bagian ini — hal ini dibuktikan pada Bab 8 — bahwa polinomial tak nol berderajat $n$ mempunyai paling banyak $n$ akar real.

Tunjukkan bahwa setiap bilangan rasional bersifat aljabar, dan carilah polinomial berkoefisien bulat yang secara eksplisit menolkan $\sqrt 2$ dan $\sqrt 2 + \sqrt 3$ .
Untuk $n \in \N$ yang tetap, tunjukkan bahwa himpunan polinomial berderajat paling tinggi $n$ dengan koefisien bulat bersifat terbilang. (Injeksikan ia ke dalam $\Z^{n+1}$ lalu berinduksi pada $n$ dengan pertanyaan 13.)
Simpulkan bahwa himpunan semua polinomial berkoefisien bulat bersifat terbilang.
Buktikan teorema Cantor tentang bilangan aljabar: himpunan $\mathcal{A}$ berisi bilangan real aljabar bersifat terbilang.
Simpulkan: bilangan real transenden itu ada, dan himpunan bilangan transenden tak terbilang. Lalu tariklah kesimpulan atas seluruh soal ini dalam beberapa kalimat: rantai $\N \approx \Z \approx \Q \approx \mathcal{A}$ , lompatan tegas ke $\R \approx$ (pada dasarnya) $\mathcal{P}(\N)$ , tempat setiap perkakas (Cantor–Schröder–Bernstein, gabungan terbilang, argumen diagonal) menjadi penentu — dan pukulan filosofis dari pembuktian bahwa ada tak terbilang banyaknya bilangan transenden tanpa menyebut satu pun. (Membuktikan sebuah bilangan tertentu seperti $\pi$ transenden jauh lebih sulit dan berada di luar jilid ini.)

Solusi

Solusi Soal 1.1.

1. Refleksif: $\mathrm{id}_E$ adalah bijeksi $E$ pada dirinya sendiri. Simetris: jika $f \colon E \to F$ bijektif, Teorema 1.24 menyediakan $f^{-1} \colon F \to E$ , yang juga bijektif. Transitif: jika $f \colon E \to F$ dan $g \colon F \to G$ bijeksi, Proposisi 1.26 (1) mengatakan $g \circ f \colon E \to G$ bijeksi. (Ini hanya “seperti” relasi ekuivalensi: kumpulan semua himpunan terbukanlah himpunan, karena paradoks yang disinggung Latihan 1.11; ketiga sifat itulah yang penting.)

2. Jika $f \colon E \to F$ dan $g \colon F \to G$ injektif, maka $g \circ f$ injektif menurut Proposisi 1.26 (1): $E \preceq G$ . Untuk butir kedua, batasi daerah kawan $f$ pada petanya: pemetaan $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , surjektif menurut konstruksi $f(E)$ dan injektif karena $f$ injektif, jadi bijektif: $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Misalkan $f \colon E \to F$ injektif dan tetapkan $a \in E$ ( $E \neq \emptyset$ ). Definisikan $s \colon F \to E$ oleh: $s(y)$ adalah satu-satunya $x$ dengan $f(x) = y$ bila $y \in f(E)$ (ketunggalannya menurut keinjektifan), dan $s(y) = a$ bila tidak. Untuk setiap $x \in E$ , $s(f(x)) = x$ , jadi setiap $x$ tercapai: $s$ surjektif. ( $\Leftarrow$ ) Misalkan $s \colon F \to E$ surjektif. Untuk masing-masing $x \in E$ pilih satu $y_x \in F$ dengan $s(y_x) = x$ , lalu tulis $u(x) = y_x$ . Jika $u(x) = u(x')$ maka $x = s(u(x)) = s(u(x')) = x'$ : jadi $u \colon E \to F$ injektif.

4. $n \mapsto n + 1$ memetakan $\N$ ke dalam $\N^*$ , bersifat injektif ( $n + 1 = m + 1 \implies n = m$ ) dan surjektif (setiap $m \geq 1$ sama dengan $(m - 1) + 1$ dengan $m - 1 \in \N$ ). Untuk $\sigma$ : ia memetakan bilangan genap $0, 2, 4, \dots$ ke $0, 1, 2, \dots$ dan bilangan ganjil $1, 3, 5, \dots$ ke $-1, -2, -3, \dots$ Keinjektifan: masukan genap mendarat di $\N$ ( $\sigma(n) = n/2 \geq 0$ ) dan masukan ganjil mendarat di bilangan bulat negatif tegas ( $\sigma(n) = -(n+1)/2 \leq -1$ ), jadi tabrakan hanya mungkin terjadi di dalam satu kelas paritas, tempat $\sigma$ monoton tegas ( $n/2 = m/2$ atau $(n+1)/2 = (m+1)/2$ memaksa $n = m$ ). Kesurjektifan: $k \geq 0$ sama dengan $\sigma(2k)$ ; $k \leq -1$ sama dengan $\sigma(-2k - 1)$ dengan $-2k - 1 \geq 1$ ganjil. Jadi $\N \approx \N^*$ dan $\N \approx \Z$ .

5. $C_0 = E \setminus g(F) \subseteq C$ , jadi $x \notin C$ mengakibatkan $x \notin C_0$ , yaitu $x \in g(F)$ : ada $y \in F$ yang memenuhi $g(y) = x$ . Jika juga $g(y') = x$ , keinjektifan $g$ memberikan $y' = y$ . Jadi klausa kedua pada definisi $h$ memilih satu unsur $g^{-1}(x)$ yang tunggal dan terdefinisi dengan baik.

6. Peta langsung berkomutasi dengan gabungan (Latihan 1.8 (1), diterapkan pada $f$ lalu pada $g$ ):

g\bigl(f(C)\bigr) = g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr) = \bigcup_{n \in \N} g\bigl(f(C_n)\bigr) = \bigcup_{n \in \N} C_{n+1} = \bigcup_{n \geq 1} C_n \subseteq C .

7. Ambil $x \neq x'$ di $E$ . Jika keduanya terletak di $C$ , maka $h(x) = f(x) \neq f(x') = h(x')$ menurut keinjektifan $f$ . Jika keduanya tidak terletak di $C$ , maka $g(h(x)) = x \neq x' = g(h(x'))$ , sehingga $h(x) \neq h(x')$ . Jika $x \in C$ dan $x' \notin C$ (kasus campuran, sampai penukaran nama): andaikan $h(x) = h(x')$ , yaitu $f(x) = g^{-1}(x')$ . Dengan menerapkan $g$ : $x' = g(f(x)) \in g(f(C))$ , dan pertanyaan 6 memberikan $x' \in C$ — kontradiksi. Jadi $h(x) \neq h(x')$ pada semua kasus: $h$ injektif.

8. Ambil $y \in F$ . Kasus 1: $g(y) \notin C$ . Maka $h(g(y)) = g^{-1}(g(y)) = y$ : unsur $g(y)$ adalah sebuah prapeta. Kasus 2: $g(y) \in C$ , katakanlah $g(y) \in C_n$ . Karena $g(y) \in g(F)$ , kita punya $g(y) \notin C_0 = E \setminus g(F)$ , jadi $n \geq 1$ dan $g(y) \in C_n = g(f(C_{n-1}))$ : ada $x \in C_{n-1}$ dengan $g(y) = g(f(x))$ . Keinjektifan $g$ memberikan $y = f(x)$ , dan $x \in C_{n-1} \subseteq C$ , sehingga $h(x) = f(x) = y$ . Pada kedua kasus $y$ tercapai: $h$ surjektif, jadi bijektif.

9. Jika $E \preceq F$ dan $F \preceq E$ , pilih injeksi $f \colon E \to F$ dan $g \colon F \to E$ ; pertanyaan 5–8 membangun sebuah bijeksi $h \colon E \to F$ , sehingga $E \approx F$ . Pernyataan itu tidak sepele karena kedua injeksi yang diberikan tak saling berkaitan — tak satu pun harus surjektif, dan tak ada rumus naif yang mencampur $f$ dan $g$ yang mendefinisikan sebuah pemetaan: seluruh isinya adalah partisi $E$ atas daerah $C$ (tempat kita menyalin $f$ ) dan komplemennya (tempat kita menjalankan $g$ secara terbalik).

10. (a) Pemetaan inklusi $\intoo01 \to \intcc01$ bersifat injektif; dan $x \mapsto \frac{x + 1}3$ memetakan $\intcc01$ secara injektif ke dalam $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (ia afin dengan kemiringan tak nol). Menurut pertanyaan 9, $\intcc01 \approx \intoo01$ — sebuah bijeksi yang cukup menjengkelkan untuk dituliskan secara eksplisit. (b) Keinjektifan. Andaikan $2^p(2q + 1) = 2^{p'}(2q' + 1)$ dengan, katakanlah, $p \leq p'$ . Dengan membagi $2^p$ : $2q + 1 = 2^{p' - p}(2q' + 1)$ . Jika $p' > p$ ruas kanan genap dan ruas kiri ganjil — mustahil; jadi $p = p'$ , lalu $2q + 1 = 2q' + 1$ dan $q = q'$ . Kesurjektifan. Kita tunjukkan dengan induksi kuat bahwa setiap bilangan bulat $m \geq 1$ berbentuk $2^p(2q + 1)$ . Untuk $m = 1$ : $p = q = 0$ . Ambil $m \geq 1$ dan andaikan klaim itu berlaku untuk semua bilangan bulat di $\intint1m$ . Jika $m + 1$ ganjil, $m + 1 = 2q + 1$ dengan $p = 0$ . Jika $m + 1$ genap, $m + 1 = 2m'$ dengan $1 \leq m' \leq m$ ; menurut hipotesis $m' = 2^p(2q + 1)$ , sehingga $m + 1 = 2^{p+1}(2q + 1)$ . Jadi $\varphi(p, q) = 2^p(2q + 1) - 1$ mengenai setiap $n \in \N$ , dan $\varphi$ adalah bijeksi $\N \times \N \to \N$ .

11. Karena $A$ tak hingga, $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ tak pernah kosong, dan sifat unsur terkecil pada $\N$ (yang dipakai untuk membuktikan Teorema 1.12) membuat definisi rekursif itu sah. Naik tegas: $\varphi(n + 1)$ termasuk $A \setminus \{\varphi(0), \dots, \varphi(n)\} \subseteq A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ , yang minimumnya adalah $\varphi(n)$ ; jadi $\varphi(n + 1) \geq \varphi(n)$ , dan kesamaan tersingkir, sehingga $\varphi(n+1) > \varphi(n)$ . $\varphi(n) \geq n$ : dengan induksi, $\varphi(0) \geq 0$ , dan $\varphi(n + 1) \geq \varphi(n) + 1 \geq n + 1$ . Keinjektifan menyusul dari kemonotonan tegas. Kesurjektifan pada $A$ : andaikan ada $a \in A$ yang tak pernah tercapai. Karena $\varphi(a + 1) \geq a + 1 > a$ , himpunan semua $n$ dengan $\varphi(n) > a$ tak kosong; misalkan $n$ unsur terkecilnya. Untuk setiap $k < n$ berlaku $\varphi(k) \leq a$ , jadi $\varphi(k) < a$ ( $a$ tidak tercapai). Maka $a$ terletak di $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ dan $a < \varphi(n)$ , bertentangan dengan keminimalan yang mendefinisikan $\varphi(n)$ . Jadi $\varphi$ adalah bijeksi $\N \to A$ , dan $A$ terbilang.

12. Misalkan $E \preceq \N$ lewat injeksi $f$ ; maka $E \approx f(E)$ (pertanyaan 2). Jika $f(E)$ hingga, $E$ hingga; jika $f(E)$ tak hingga, pertanyaan 11 memberikan $f(E) \approx \N$ , sehingga $E \approx \N$ menurut ketransitifan (pertanyaan 1). Sebaliknya himpunan hingga dan himpunan terbilang jelas terinjeksi ke dalam $\N$ . Jalan pintasnya: $E \preceq \N$ dan $\N \preceq E$ memberikan $E \approx \N$ secara langsung menurut Cantor–Schröder–Bernstein — tanpa perlu argumen pencacahan.

13. Misalkan $f \colon E \to \N$ dan $g \colon F \to \N$ dua injeksi. Maka $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ adalah injeksi $E \times F \to \N$ : jika petanya berimpit, keinjektifan $\varphi$ (pertanyaan 10) memberikan $f(x) = f(x')$ dan $g(y) = g(y')$ , lalu $x = x'$ , $y = y'$ . Untuk $\Z \times \N^*$ : kedua faktornya terbilang (pertanyaan 4), jadi $\Z \times \N^* \preceq \N$ ; ia tak hingga (ia memuat $\{0\} \times \N^*$ ), sehingga terbilang menurut pertanyaan 12.

14. Setiap bilangan rasional $r$ mempunyai penyajian tunggal $r = p/q$ dengan $p \in \Z$ , $q \in \N^*$ dan pecahan itu paling sederhana (ketunggalannya dibuktikan pada Bab 6; untuk $r = 0$ ambil $0/1$ ). Pemetaan $r \mapsto (p, q)$ lalu bersifat injektif: pasangan itu menentukan $r = p/q$ . Jadi $\Q \preceq \Z \times \N^* \preceq \N$ menurut pertanyaan 13. Karena $\N \subseteq \Q$ memberikan $\N \preceq \Q$ , pertanyaan 12 (atau langsung Cantor–Schröder–Bernstein) menunjukkan $\Q \approx \N$ : bilangan rasional bersifat terbilang.

15. Untuk masing-masing $n$ tetapkan injeksi $f_n \colon E_n \to \N$ . Untuk $x \in \bigcup_n E_n$ , misalkan $n(x)$ indeks $n$ terkecil yang memenuhi $x \in E_n$ , lalu tulis $u(x) = \varphi\bigl(n(x), f_{n(x)}(x)\bigr) \in \N$ . Jika $u(x) = u(x')$ , keinjektifan $\varphi$ memberikan $n(x) = n(x') = n$ dan $f_n(x) = f_n(x')$ , sehingga $x = x'$ menurut keinjektifan $f_n$ . Jadi gabungan itu terinjeksi ke dalam $\N$ : ia paling banyak terbilang.

16. Tulis $\Psi(F) = \sum_{i \in F} 2^i$ untuk $F \subseteq \N$ yang hingga ( $\Psi(\emptyset) = 0$ ). Andaikan $F \neq F'$ dan misalkan $m$ unsur terbesar tempat keduanya berbeda, katakanlah $m \in F \setminus F'$ (tukar namanya jika perlu). Unsur yang $> m$ termasuk keduanya atau tak termasuk keduanya, jadi sumbangannya sama pada kedua jumlah itu; dengan membandingkan sumbangan unsur yang $\leq m$ :

\sum_{i \in F,\, i \leq m} 2^i \geq 2^m > 2^m - 1 = \sum_{k=0}^{m-1} 2^k \geq \sum_{i \in F',\, i \leq m} 2^i ,

memakai jumlah geometri Latihan 1.4. Jadi $\Psi(F) \neq \Psi(F')$ : $\Psi$ injektif dan himpunan semua himpunan bagian hingga dari $\N$ paling banyak terbilang; ia tak hingga (ia memuat semua himpunan beranggota tunggal), jadi terbilang.

17. Kirim $A \subseteq \N$ ke fungsi indikatornya $\mathbf 1_A \colon \N \to \{0,1\}$ , $\mathbf 1_A(n) = 1$ bila $n \in A$ dan $0$ bila tidak; kirim $u \in \{0,1\}^{\N}$ ke $A_u = \{n \in \N : u(n) = 1\}$ . Kedua pemetaan itu saling invers: $A_{\mathbf 1_A} = A$ dan $\mathbf 1_{A_u} = u$ (periksa nilainya pada setiap $n$ ). Menurut Teorema 1.24, masing-masing adalah bijeksi: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$ .

18. Untuk setiap $n$ , $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$ , jadi barisan $d$ dan $\Phi(n)$ berbeda pada indeks $n$ : $d \neq \Phi(n)$ . Jadi tak ada $\Phi$ yang surjektif, dan menurut pertanyaan 3 tak ada pula injeksi $\{0,1\}^{\N} \to \N$ : jadi $\{0,1\}^{\N}$ bukan himpunan yang paling banyak terbilang. Lewat kamus pertanyaan 17, sebuah pemetaan $\Phi \colon \N \to \{0,1\}^{\N}$ adalah pemetaan $f \colon \N \to \mathcal{P}(\N)$ , dan $d$ berpadanan dengan himpunan $D = \{n : n \notin f(n)\}$ (memang $d(n) = 1 \iff \Phi(n)(n) = 0 \iff n \notin f(n)$ ): argumen diagonal itu adalah bukti Cantor untuk Latihan 1.11 dengan $E = \N$ .

19. Tulis $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ dalam bentuk sejati lalu definisikan $\delta_n = 5$ bila $d_n(n) \neq 5$ , $\delta_n = 6$ bila $d_n(n) = 5$ , lalu $x = 0.\delta_1\delta_2\delta_3\dots$ Ekspansi ini hanya memakai angka $5$ dan $6$ , jadi ia tidak berakhir dengan angka $9$ semua: ia ekspansi sejati dari suatu bilangan real $x \in \intco01$ . Untuk setiap $n$ , angka ke- $n$ dari $x$ dan $x_n$ berbeda ( $\delta_n \neq d_n(n)$ menurut konstruksinya); karena ekspansi sejati bersifat tunggal, $x \neq x_n$ . Jadi tak ada barisan yang menghabiskan $\intco01$ : menurut pertanyaan 3 lagi, $\intco01$ bukan himpunan yang paling banyak terbilang.

20. $\intco01 \subseteq \R$ , jadi injeksi $\R \to \N$ akan terbatasi menjadi injeksi pada $\intco01$ , bertentangan dengan pertanyaan 19: $\R$ tak terbilang. Jika $\R \setminus \Q$ paling banyak terbilang, maka $\R = \Q \cup (\R \setminus \Q)$ akan menjadi gabungan dua himpunan yang paling banyak terbilang, jadi paling banyak terbilang menurut pertanyaan 15 (ambil $E_0 = \Q$ , $E_n = \R \setminus \Q$ untuk $n \geq 1$ ) — kontradiksi. Jadi bilangan irasional tak terbilang. Persisnya: di dalam $\R$ , bilangan rasional membentuk himpunan terbilang sedangkan komplemennya tak terbilang; tak ada bijeksi yang dapat memasangkan $\R \setminus \Q$ dengan $\Q$ — bilangan irasional secara tegas “lebih banyak” daripada bilangan rasional, meskipun keduanya tak hingga dan keduanya padat.

21. $p/q$ (dengan $q \neq 0$ ) adalah akar $qX - p$ , sebuah polinomial tak nol berkoefisien bulat. $\sqrt 2$ adalah akar $X^2 - 2$ . Untuk $x = \sqrt 2 + \sqrt 3$ : $x^2 = 5 + 2\sqrt 6$ , sehingga $x^2 - 5 = 2\sqrt 6$ dan $(x^2 - 5)^2 = 24$ , yaitu

x^4 - 10x^2 + 1 = 0 :

$\sqrt 2 + \sqrt 3$ adalah akar $X^4 - 10X^2 + 1$ .

22. Petakan $P = a_0 + a_1X + \dots + a_nX^n$ (berderajat $\leq n$ , berkoefisien bulat) ke $(a_0, \dots, a_n) \in \Z^{n+1}$ : pemetaan ini injektif, karena polinomial ditentukan oleh koefisiennya. Dengan induksi pada $n$ : $\Z^1 = \Z$ terbilang (pertanyaan 4), dan $\Z^{n+2} \approx \Z^{n+1} \times \Z$ paling banyak terbilang menurut pertanyaan 13. Jadi setiap himpunan polinomial bulat yang derajatnya terbatas bersifat paling banyak terbilang; ia tak hingga (ia memuat semua konstanta), jadi terbilang menurut pertanyaan 12.

23. Himpunan semua polinomial bulat adalah $\bigcup_{n \in \N} \{P : \deg P \leq n,\ P \text{ berkoefisien bulat}\}$ , sebuah gabungan terbilang dari himpunan terbilang: paling banyak terbilang menurut pertanyaan 15, tak hingga, jadi terbilang.

24. Untuk setiap polinomial bulat tak nol $P$ , himpunan akarnya $R_P = \{x \in \R : P(x) = 0\}$ bersifat hingga (paling banyak $\deg P$ unsur, diterima tanpa bukti). Menurut pertanyaan 23 polinomial bulat tak nol dapat dicacah $P_0, P_1, P_2, \dots$ ; maka $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ adalah gabungan terbilang dari himpunan hingga (jadi paling banyak terbilang): paling banyak terbilang menurut pertanyaan 15. Ia memuat $\Q$ (pertanyaan 21), jadi ia tak hingga: $\mathcal{A}$ terbilang.

25. Jika $\R \setminus \mathcal{A}$ paling banyak terbilang, $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ akan paling banyak terbilang (pertanyaan 15), bertentangan dengan pertanyaan 20. Jadi bilangan transenden itu ada dan bahkan membentuk himpunan tak terbilang, sedangkan bilangan aljabar — yang mencakup setiap bilangan yang dibangun dari bilangan bulat lewat penarikan akar — hanya membentuk kerangka terbilang di dalam $\R$ . Ringkasan arsitekturnya: pertanyaan 1–3 menyiapkan bahasa perbandingannya; Cantor–Schröder–Bernstein (pertanyaan 5–9) memungkinkan kita membuktikan ekuipotensi lewat dua injeksi mudah, bukan lewat satu bijeksi cerdik, dan dipakai untuk $\intcc01 \approx \intoo01$ , untuk $\Q$ dan di sepanjang Bagian V; bijeksi pemasangan (pertanyaan 10) menggerakkan hasil kali dan gabungan terbilang (pertanyaan 13, 15), yang pada gilirannya menggerakkan $\Q$ , polinomial bulat dan $\mathcal{A}$ ; argumen diagonal (pertanyaan 18–19) menyediakan satu-satunya ketaksamaan tegas $\N \prec \R$ yang membuat seluruh kisah ini tidak sepele. Kesimpulan Cantor mencengangkan secara filosofis: buktinya sama sekali tidak menunjukkan bilangan transenden mana pun, namun menunjukkan bahwa dalam pengertian ekuipotensi hampir setiap bilangan real bersifat transenden. Menyebut satu bilangan transenden tertentu — $\pi$ atau $\eu$ — menuntut matematika yang sama sekali lain dan puluhan tahun kerja tambahan.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium