--- title: "Logika, Himpunan dan Pemetaan" book: "Matematika Universitas — Tahun 1" subject: math language: id chapter: 1 exercises: 12 source: https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan --- # Bab 1 — Logika, 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](#def-b1-logic-statement) matematis, bagaimana perangkai dan kuantor menggabungkan [pernyataan](#def-b1-logic-statement), langkah mana yang sah di dalam sebuah bukti — lalu, di atas landasan itu, membangun dua bahasa universal matematika: [himpunan](#def-b1-logic-sets) dan [pemetaan](#def-b1-logic-map). ## 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](#def-b1-logic-statement) $P$, $Q$, $R$: 1. $\lnot(\lnot P) \iff P$ ; 2. hukum De Morgan: $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ dan $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ; 3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , sehingga $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ; 4. kontraposisi: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ; 5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ; 6. 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](#def-b1-logic-statement) 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](#def-b1-logic-sets) $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](#def-b1-logic-sets) $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](#def-b1-logic-statement) universal itu gugur. Untuk kaidah kedua: “tidak ada $x$ yang memenuhi $P$” berarti [himpunan](#def-b1-logic-sets) $\{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](#ex-b1-logic-limit): 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](#prop-b1-logic-negquant) 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](#def-b1-logic-statement) positif yang baru, dengan peran yang bertukar: kini kita yang menghasilkan saksi, padahal tadinya kita yang menerimanya. **Contoh 1.7 (Urutan kuantor).** [Urutan](#def-b1-logic-order) 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](#def-b1-logic-statement) 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](https://one-course.com/books/math/3/id/chapter/11-barisan#ch-b1-seq) sebagai $$ \forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad \abs{u_n - \ell} \leq \varepsilon . $$ Negasinya, dengan [Proposisi 1.5](#prop-b1-logic-negquant) 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… 1. *implikasi $P \implies Q$ secara langsung* : andaikan $P$ , simpulkan $Q$ ; 2. *dengan kontraposisi* : andaikan $\lnot Q$ , simpulkan $\lnot P$ — sah menurut [Proposisi 1.3](#prop-b1-logic-rules) (4); 3. *dengan kontradiksi* : andaikan [pernyataan](#def-b1-logic-statement) itu salah, lalu turunkan sebuah kontradiksi; 4. *sebuah ekuivalensi* : buktikan kedua implikasinya secara terpisah (atau rangkaikan ekuivalensi yang sudah dikenal); 5. *[pernyataan](#def-b1-logic-statement) “untuk setiap”* : ambil $x$ yang *sembarang* di $E$ (“misalkan $x \in E$ ”) lalu buktikan $P(x)$ ; 6. *[pernyataan](#def-b1-logic-statement) “terdapat”* : tunjukkan sebuah saksi, atau buktikan keberadaannya secara tak langsung; 7. *dengan induksi* : lihat [Teorema 1.12](#thm-b1-logic-induction) . Ketika membuktikan [pernyataan](#def-b1-logic-statement) 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. 1. *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. 2. *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. 3. *Bukti yang berjalan mundur.* Berangkat dari kesimpulan yang diinginkan lalu menurunkan [pernyataan](#def-b1-logic-statement) 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. 4. *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 1. $P(0)$ benar, dan 2. 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](#def-b1-logic-sets) 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](#def-b1-logic-statement) $\exists!\,x,\ P(x)$ sesungguhnya *dua* [pernyataan](#def-b1-logic-statement), 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](https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat#ch-b1-arith)). 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](#def-b1-logic-statement) $a \in \mathcal P(E)$ maupun $\{a\} \subseteq \mathcal P(E)$ keduanya salah sebagaimana tertulis (yang kedua menuntut $a$ menjadi *[himpunan](#def-b1-logic-sets) 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](#def-b1-logic-sets) yang anggotanya [himpunan](#def-b1-logic-sets) tetaplah [himpunan](#def-b1-logic-sets) biasa, dan [Bab 2](https://one-course.com/books/math/3/id/chapter/2-pencacahan#ch-b1-counting) 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](#exo-b1-logic-11) dan [1.12](#exo-b1-logic-12). **Proposisi 1.18 (Aljabar himpunan).** Untuk [himpunan](#def-b1-logic-sets) bagian $A, B, C$ dari $E$: 1. $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)$ ; 2. De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ dan $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ; 3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ . **Bukti.** Setiap kesamaan itu menerjemahkan satu kaidah [Proposisi 1.3](#prop-b1-logic-rules) lewat kamus ($\in A$ atau bukan) $\leftrightarrow$ ([pernyataan](#def-b1-logic-statement) 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](#prop-b1-logic-rules) (6), dan [pernyataan](#def-b1-logic-statement) terakhir itu terbaca $x \in (A \cap B) \cup (A \cap C)$. Setiap kesamaan [himpunan](#def-b1-logic-sets) 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.](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg) *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](#prop-b1-logic-setalgebra) 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](#def-b1-logic-sets) $E$ (*daerah asal*) dengan tepat satu unsur $f(x)$ pada [himpunan](#def-b1-logic-sets) $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](#def-b1-logic-map) invers: $f^{-1}(B)$ terdefinisi untuk setiap $f$. [Prapeta](#def-b1-logic-map) 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](#exo-b1-logic-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](#def-b1-logic-map) 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](#def-b1-logic-map) $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](#def-b1-logic-map) . **Teorema 1.24 (Pemetaan invers).** [Pemetaan](#def-b1-logic-map) $f \colon E \to F$ [bijektif](#def-b1-logic-inj) jika dan hanya jika ada [pemetaan](#def-b1-logic-map) $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](#def-b1-logic-inj) dengan $(f^{-1})^{-1} = f$. **Bukti.** ($\Rightarrow$) Jika $f$ [bijektif](#def-b1-logic-inj), setiap $y \in F$ mempunyai tepat satu [prapeta](#def-b1-logic-map); definisikan $g(y)$ sebagai [prapeta](#def-b1-logic-map) itu. Maka $f(g(y)) = y$ menurut konstruksinya, dan $g(f(x)) = x$ karena $x$ adalah *satu-satunya* [prapeta](#def-b1-logic-map) $f(x)$. ($\Leftarrow$) Andaikan $g$ semacam itu ada. Jika $f(x) = f(x')$, penerapan $g$ memberikan $x = x'$: jadi $f$ [injektif](#def-b1-logic-inj). Untuk $y \in F$, unsur $x = g(y)$ memenuhi $f(x) = y$: jadi $f$ [surjektif](#def-b1-logic-inj). 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](#def-b1-logic-inj) 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](#def-b1-logic-inj), 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](#thm-b1-logic-inverse). 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](#def-b1-logic-inj) ke $\R$). **Proposisi 1.26 (Komposisi dan ketiga sifat itu).** Misalkan $f \colon E \to F$ dan $g \colon F \to G$. 1. Jika $f$ dan $g$ [injektif](#def-b1-logic-inj) (masing-masing [surjektif](#def-b1-logic-inj) , [bijektif](#def-b1-logic-inj) ), maka demikian pula $g \circ f$ ; dan dalam kasus [bijektif](#def-b1-logic-inj) berlaku $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ . 2. Jika $g \circ f$ [injektif](#def-b1-logic-inj) , maka $f$ [injektif](#def-b1-logic-inj) . Jika $g \circ f$ [surjektif](#def-b1-logic-inj) , maka $g$ [surjektif](#def-b1-logic-inj) . **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](#def-b1-logic-inj) kita periksa langsung bahwa $f^{-1} \circ g^{-1}$ adalah invers dua sisi dari $g \circ f$, dan ketunggalan pada [Teorema 1.24](#thm-b1-logic-inverse) 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](#prop-b1-logic-comp) (2), kesimpulannya tidak dapat diperkuat: $g \circ f$ [bijektif](#def-b1-logic-inj) *tidak* memaksa $f$ [surjektif](#def-b1-logic-inj) atau $g$ [injektif](#def-b1-logic-inj). 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](#def-b1-logic-inj), namun $f$ melewatkan unsur $2$ dan $g$ meleburkan kedua unsurnya. Moralnya adalah aturan pembukuan yang tepat: informasi komposisi mengalir ke [pemetaan](#def-b1-logic-map) *dalam* untuk keinjektifan dan ke [pemetaan](#def-b1-logic-map) *luar* untuk kesurjektifan, tidak pernah sebaliknya. ([Latihan 1.9](#exo-b1-logic-9) membangun gejala yang sama dengan [himpunan](#def-b1-logic-sets) 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](#def-b1-logic-inj) ($f(-1) = f(1)$) dan tidak pula [surjektif](#def-b1-logic-inj) ($-1$ tak punya [prapeta](#def-b1-logic-map)). Dengan membatasi daerah asal dan daerah kawan, $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ [bijektif](#def-b1-logic-inj), dengan invers $y \mapsto \sqrt y$. Keinjektifan atau kesurjektifan sebuah [pemetaan](#def-b1-logic-map) 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](#def-b1-logic-sets) $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](#def-b1-logic-equiv), 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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) 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](#thm-b1-logic-partition) dari $E$ muncul dengan cara ini dari tepat satu [relasi ekuivalensi](#def-b1-logic-equiv) (“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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) 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](#def-b1-logic-equiv); kelas-kelasnya adalah $n$ [himpunan](#def-b1-logic-sets) bilangan bulat yang bersisa tertentu bila dibagi $n$. Contoh ini menjelma menjadi ring $\Z/n\Z$ pada [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures). **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](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/id/chapter/10-bilangan-real#ch-b1-reals). **Contoh 1.35 (Dua urutan pada kisi N2\N^2N2).** Pada pasangan bilangan cacah, bandingkan komponen demi komponen: $(a, b) \preceq (a', b')$ bila $a \leq a'$ *dan* $b \leq b'$ (*[urutan](#def-b1-logic-order) hasil kali*). Ini memang [urutan](#def-b1-logic-order) — setiap aksiomanya diwarisi koordinat demi koordinat — tetapi [urutan](#def-b1-logic-order) 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](#def-b1-logic-order) leksikografis*). Ketransitifannya menuntut pemeriksaan dua kasus tetapi tetap berlaku, dan kini setiap dua pasangan dapat dibandingkan: [urutannya](#def-b1-logic-order) total. Kedua [urutan](#def-b1-logic-order) itu memeringkat [himpunan](#def-b1-logic-sets) yang sama secara berbeda — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ padahal [urutan](#def-b1-logic-order) hasil kali tak berkata apa-apa — sebuah pengingat bahwa [urutan](#def-b1-logic-order) adalah struktur yang kita *pilih*, bukan sifat dari [himpunannya](#def-b1-logic-sets). 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](#def-b1-logic-sets) hingga hal ini menjelma menjadi kalkulus pencacahan pada [Bab 2](https://one-course.com/books/math/3/id/chapter/2-pencacahan#ch-b1-counting), tempat setiap rumus diam-diam merupakan sebuah bijeksi; untuk [himpunan](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/id/chapter/11-barisan#ch-b1-seq)) tidak lain adalah [pemetaan](#def-b1-logic-map) $\N \to \R$, sehingga [pernyataan](#def-b1-logic-statement) tentang barisan adalah [pernyataan](#def-b1-logic-statement) tentang sebuah [himpunan](#def-b1-logic-sets) [pemetaan](#def-b1-logic-map); 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](https://one-course.com/books/math/3/id/chapter/19-dimensi-hingga#ch-b1-findim)). Setiap kali sebuah “kesamaan” yang baru muncul — ekuipotensi, isomorfisma grup ([Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures)), isomorfisma linear — pola [Teorema 1.24](#thm-b1-logic-inverse) berulang: kesamaan adalah [pemetaan](#def-b1-logic-map) 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](#ex-b1-logic-limit) adalah santapan sehari-hari Bab [11](https://one-course.com/books/math/3/id/chapter/11-barisan#ch-b1-seq) dan [13](https://one-course.com/books/math/3/id/chapter/13-limit-dan-kekontinuan#ch-b1-continuity): setiap bukti limit adalah permainan melawan $\varepsilon$ yang sembarang. [Kelas ekuivalensi](#def-b1-logic-equiv) muncul kembali sebagai kelas kekongruenan $\Z/n\Z$ pada [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures), tempat [partisi](#thm-b1-logic-partition) [Teorema 1.31](#thm-b1-logic-partition) memperoleh struktur aljabar tersendiri. [Relasi urutan](#def-b1-logic-order), batas atas dan batas atas terkecil menjadi jantung aksiomatis $\R$ pada [Bab 10](https://one-course.com/books/math/3/id/chapter/10-bilangan-real#ch-b1-reals). Injeksi, surjeksi dan bijeksi kembali sebagai [pemetaan](#def-b1-logic-map) linear pada [Bab 20](https://one-course.com/books/math/3/id/chapter/20-pemetaan-linear#ch-b1-linmaps), 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](#def-b1-logic-sets) tak hingga*, yang kesimpulannya (keterbilangan $\Q$, ketakterbilangan $\R$) muncul lagi pada Bab [10](https://one-course.com/books/math/3/id/chapter/10-bilangan-real#ch-b1-reals) dan [12](https://one-course.com/books/math/3/id/chapter/12-topologi-garis-real#ch-b1-topology). ## 1.7 Latihan **Latihan 1.1 ★.** Tuliskan negasi setiap [pernyataan](#def-b1-logic-statement) berikut, tanpa memakai kata “bukan”: 1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ; 2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ; 3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (untuk sebuah [pemetaan](#def-b1-logic-map) tetap $f \colon \R \to \R$ ). Kemudian tentukan apakah [pernyataan](#def-b1-logic-statement) (1) dan (2) benar. **Solusi Latihan 1.1.** Negasi, dengan mendorong $\lnot$ melewati setiap kuantor ([Proposisi 1.5](#prop-b1-logic-negquant)) dan memakai $\lnot(P \implies Q) \iff P \land \lnot Q$: 1. $\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ; 2. $\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ; 3. $\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \R,\ \abs{x} \leq \delta \text{ dan } \abs{f(x)} > \varepsilon$ . [Pernyataan](#def-b1-logic-statement) (1) benar: diberikan $x$, ambil $y = -x + 1$; maka $x + y = 1 > 0$. [Pernyataan](#def-b1-logic-statement) (2) benar: $x = 0$ memenuhi $xy = 0$ untuk setiap $y$. **Latihan 1.2 ★.** Misalkan $P, Q$ [pernyataan](#def-b1-logic-statement). 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 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](#def-b1-logic-statement) yang salah, kebetulan saja: implikasi aslinya benar, lihat [Bab 14](https://one-course.com/books/math/3/id/chapter/14-pendiferensialan#ch-b1-derivative)). **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 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](#def-b1-logic-statement) 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$: 1. $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ; 2. $4^n + 5$ habis dibagi $3$ . **Solusi Latihan 1.4.** 1. 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 .$$ 2. 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](#def-b1-logic-sets) 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 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](#def-b1-logic-sets) bagian dari $E$. Buktikan: 1. $A \setminus B = A \cap \overline{B}$ ; 2. $(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ ; 3. $A \subseteq B \iff A \cup B = B \iff A \cap B = A$ . **Solusi Latihan 1.6.** 1. $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}$ . 2. Dengan memakai (1) dan sifat distributif ( [Proposisi 1.18](#prop-b1-logic-setalgebra) ): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ . 3. 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](#def-b1-logic-map) berikut, tentukan (dengan bukti) apakah ia [injektif](#def-b1-logic-inj), [surjektif](#def-b1-logic-inj), atau [bijektif](#def-b1-logic-inj): 1. $f \colon \N \to \N$ , $n \mapsto n + 1$ ; 2. $g \colon \Z \to \Z$ , $n \mapsto n + 1$ ; 3. $h \colon \R \setminus \{1\} \to \R$ , $x \mapsto \frac{x+1}{x-1}$ . Untuk $h$, sesuaikan daerah kawannya agar ia [bijektif](#def-b1-logic-inj), lalu hitung inversnya. **Solusi Latihan 1.7.** 1. $f$ [injektif](#def-b1-logic-inj) ( $n + 1 = m + 1 \implies n = m$ ) tetapi tidak [surjektif](#def-b1-logic-inj) : $0$ tak mempunyai [prapeta](#def-b1-logic-map) di $\N$ . 2. $g$ [bijektif](#def-b1-logic-inj) : $n \mapsto n - 1$ adalah invers dua sisi pada $\Z$ . 3. $h$ [injektif](#def-b1-logic-inj) : $\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](#def-b1-logic-inj) 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](#def-b1-logic-map) tunggal $x = \frac{y+1}{y-1}$ , sehingga $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ bersifat [bijektif](#def-b1-logic-inj) 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$. 1. Buktikan $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ dan $f(A \cup A') = f(A) \cup f(A')$ . 2. Buktikan $f(A \cap A') \subseteq f(A) \cap f(A')$ lalu berikan contoh yang inklusinya sejati. 3. Buktikan: $f$ [injektif](#def-b1-logic-inj) jika dan hanya jika $f(A \cap A') = f(A) \cap f(A')$ untuk setiap $A, A'$ . **Solusi Latihan 1.8.** 1. $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')$ . 2. 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\}$ . 3. ( $\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](#def-b1-logic-inj) . ( $\Rightarrow$ ) Misalkan $f$ [injektif](#def-b1-logic-inj) 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](#def-b1-logic-inj) dan $g$ [surjektif](#def-b1-logic-inj). Berikan contoh yang $f$ maupun $g$-nya tidak [bijektif](#def-b1-logic-inj). **Solusi Latihan 1.9.** $g \circ f = \mathrm{id}_E$ bersifat [injektif](#def-b1-logic-inj) sekaligus [surjektif](#def-b1-logic-inj), jadi menurut [Proposisi 1.26](#prop-b1-logic-comp) (2), $f$ [injektif](#def-b1-logic-inj) dan $g$ [surjektif](#def-b1-logic-inj). Contoh: $E = \N$, $F = \Z$, $f$ [pemetaan](#def-b1-logic-map) 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](#def-b1-logic-inj) dan $g$ tidak [injektif](#def-b1-logic-inj). **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](#def-b1-logic-equiv) lalu jelaskan kelas ekuivalensi setiap bilangan real $x$. Kelas mana yang beranggotakan tepat satu unsur? **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](#def-b1-logic-equiv) 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](#def-b1-logic-sets). 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 Latihan 1.11.** Misalkan $f \colon E \to \mathcal{P}(E)$ sebuah [pemetaan](#def-b1-logic-map) 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](#def-b1-logic-inj). (Khususnya tak ada [himpunan](#def-b1-logic-sets) yang berbijeksi dengan [himpunan kuasanya](#def-b1-logic-sets): ada “lebih banyak” [himpunan](#def-b1-logic-sets) bagian $\N$ daripada bilangan bulat.) **Latihan 1.12 ★★★.** Misalkan $f \colon E \to F$ sebuah [pemetaan](#def-b1-logic-map). Definisikan $\Phi \colon \mathcal{P}(F) \to \mathcal{P}(E)$ dengan $\Phi(B) = f^{-1}(B)$. 1. Buktikan bahwa $f$ [surjektif](#def-b1-logic-inj) jika dan hanya jika $\Phi$ [injektif](#def-b1-logic-inj) . 2. Buktikan bahwa $f$ [injektif](#def-b1-logic-inj) jika dan hanya jika $\Phi$ [surjektif](#def-b1-logic-inj) . **Solusi Latihan 1.12.** 1. ( $\Rightarrow$ ) Misalkan $f$ [surjektif](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Jika $f$ tidak [surjektif](#def-b1-logic-inj) , 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](#def-b1-logic-inj) . 2. ( $\Rightarrow$ ) Misalkan $f$ [injektif](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Jika $f$ tidak [injektif](#def-b1-logic-inj) , ambil $x \neq x'$ dengan $f(x) = f(x')$ . Setiap [himpunan](#def-b1-logic-sets) [prapeta](#def-b1-logic-map) $f^{-1}(B)$ memuat $x$ jika dan hanya jika ia memuat $x'$ ; jadi $\{x\}$ tidak berbentuk $\Phi(B)$ , dan $\Phi$ tidak [surjektif](#def-b1-logic-inj) . ## 1.8 Soal: Membandingkan ketakhinggaan **Soal 1.1.** Kapan dua [himpunan](#def-b1-logic-sets) dikatakan mempunyai “banyak unsur yang sama”? Jawaban Cantor — ketika ada bijeksi di antara keduanya — ternyata dapat dipakai bahkan untuk [himpunan](#def-b1-logic-sets) 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](#pb-b1-logic-1) itu ada, dan sangat banyak*, tanpa menunjukkan satu pun. Di sepanjang soal ini, untuk [himpunan](#def-b1-logic-sets) $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.** 1. Tunjukkan bahwa $\approx$ berperilaku seperti [relasi ekuivalensi](#def-b1-logic-equiv) : $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](#thm-b1-logic-inverse) dan [Proposisi 1.26](#prop-b1-logic-comp) .) 2. Tunjukkan bahwa $\preceq$ transitif, dan bahwa injeksi $f \colon E \to F$ selalu melahirkan $E \approx f(E)$ . 3. Misalkan $E \neq \emptyset$ . Tunjukkan bahwa $E \preceq F$ jika dan hanya jika ada surjeksi dari $F$ pada $E$ . 4. 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$. 5. Periksa bahwa $h$ terdefinisi dengan baik: jika $x \notin C$ maka $x \in g(F)$ , dan unsur $y$ dengan $g(y) = x$ bersifat tunggal. 6. Tunjukkan bahwa $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ . (Peta langsung berkomutasi dengan gabungan: [Latihan 1.8](#exo-b1-logic-8) .) 7. Tunjukkan bahwa $h$ [injektif](#def-b1-logic-inj) . (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$ .) 8. Tunjukkan bahwa $h$ [surjektif](#def-b1-logic-inj) : 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](#def-b1-logic-map) dari $y$ pada masing-masing kasus. 9. 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](#def-b1-logic-statement) ini tidak sepele. 10. 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](#thm-b1-logic-induction) ). Jadi $\N \times \N \approx \N$ : bidang titik bulat tidak lebih besar daripada garis. **Bagian III — [Himpunan terbilang](#pb-b1-logic-1).** Sebuah [himpunan](#def-b1-logic-sets) $E$ disebut *paling banyak terbilang* bila $E \preceq \N$, dan *terbilang* bila $E \approx \N$. 11. Tunjukkan bahwa setiap [himpunan](#def-b1-logic-sets) 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$ .) 12. Simpulkan bahwa sebuah [himpunan](#def-b1-logic-sets) 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. 13. Tunjukkan bahwa jika $E$ dan $F$ paling banyak terbilang, maka demikian pula $E \times F$ . Simpulkan bahwa $\Z \times \N^*$ terbilang. 14. 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](https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat#ch-b1-arith) ; lalu terapkan pertanyaan 12.) 15. Tunjukkan bahwa gabungan terbilang dari [himpunan](#def-b1-logic-sets) 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$ .) 16. Tunjukkan bahwa [himpunan](#def-b1-logic-sets) semua [himpunan](#def-b1-logic-sets) bagian *hingga* dari $\N$ bersifat terbilang. (Petakan [himpunan](#def-b1-logic-sets) bagian hingga $F$ ke $\sum_{i \in F} 2^i$ ; buktikan keinjektifannya dengan membandingkan unsur terbesar tempat kedua [himpunan](#def-b1-logic-sets) hingga itu berbeda, memakai $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ dari [Latihan 1.4](#exo-b1-logic-4) .) **Bagian IV — Diagonalisasi.** Misalkan $\{0,1\}^{\N}$ menyatakan [himpunan](#def-b1-logic-sets) semua [pemetaan](#def-b1-logic-map) $u \colon \N \to \{0, 1\}$, yakni [himpunan](#def-b1-logic-sets) barisan biner. 17. Konstruksikan bijeksi antara $\mathcal{P}(\N)$ dan $\{0,1\}^{\N}$ (fungsi indikator). 18. (Argumen diagonal) Misalkan $\Phi \colon \N \to \{0,1\}^{\N}$ sebuah [pemetaan](#def-b1-logic-map) 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](#exo-b1-logic-11) ) untuk $E = \N$ . 19. Terima — sebagaimana sudah dikenal sejak sekolah, dan ditegakkan secara ketat pada [Bab 10](https://one-course.com/books/math/3/id/chapter/10-bilangan-real#ch-b1-reals) — 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. 20. Simpulkan bahwa $\R$ tak terbilang, dan bahwa [himpunan](#def-b1-logic-sets) $\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](#pb-b1-logic-1) 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](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly) — bahwa polinomial tak nol berderajat $n$ mempunyai paling banyak $n$ akar real. 21. Tunjukkan bahwa setiap bilangan rasional bersifat aljabar, dan carilah polinomial berkoefisien bulat yang secara eksplisit menolkan $\sqrt 2$ dan $\sqrt 2 + \sqrt 3$ . 22. Untuk $n \in \N$ yang tetap, tunjukkan bahwa [himpunan](#def-b1-logic-sets) polinomial berderajat paling tinggi $n$ dengan koefisien bulat bersifat terbilang. (Injeksikan ia ke dalam $\Z^{n+1}$ lalu berinduksi pada $n$ dengan pertanyaan 13.) 23. Simpulkan bahwa [himpunan](#def-b1-logic-sets) *semua* polinomial berkoefisien bulat bersifat terbilang. 24. Buktikan *teorema Cantor tentang [bilangan aljabar](#pb-b1-logic-1)* : [himpunan](#def-b1-logic-sets) $\mathcal{A}$ berisi bilangan real aljabar bersifat terbilang. 25. Simpulkan: bilangan real transenden itu ada, dan [himpunan](#def-b1-logic-sets) [bilangan transenden](#pb-b1-logic-1) 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](#pb-b1-logic-1) tanpa menyebut satu pun. (Membuktikan sebuah bilangan *tertentu* seperti $\pi$ transenden jauh lebih sulit dan berada di luar jilid ini.) **Solusi Soal 1.1.** **1.** *Refleksif:* $\mathrm{id}_E$ adalah bijeksi $E$ pada dirinya sendiri. *Simetris:* jika $f \colon E \to F$ [bijektif](#def-b1-logic-inj), [Teorema 1.24](#thm-b1-logic-inverse) menyediakan $f^{-1} \colon F \to E$, yang juga [bijektif](#def-b1-logic-inj). *Transitif:* jika $f \colon E \to F$ dan $g \colon F \to G$ bijeksi, [Proposisi 1.26](#prop-b1-logic-comp) (1) mengatakan $g \circ f \colon E \to G$ bijeksi. (Ini hanya “seperti” [relasi ekuivalensi](#def-b1-logic-equiv): kumpulan semua [himpunan](#def-b1-logic-sets) terbukanlah [himpunan](#def-b1-logic-sets), karena paradoks yang disinggung [Latihan 1.11](#exo-b1-logic-11); ketiga sifat itulah yang penting.) **2.** Jika $f \colon E \to F$ dan $g \colon F \to G$ [injektif](#def-b1-logic-inj), maka $g \circ f$ [injektif](#def-b1-logic-inj) menurut [Proposisi 1.26](#prop-b1-logic-comp) (1): $E \preceq G$. Untuk butir kedua, batasi daerah kawan $f$ pada petanya: [pemetaan](#def-b1-logic-map) $\tilde f \colon E \to f(E)$, $x \mapsto f(x)$, [surjektif](#def-b1-logic-inj) menurut konstruksi $f(E)$ dan [injektif](#def-b1-logic-inj) karena $f$ [injektif](#def-b1-logic-inj), jadi [bijektif](#def-b1-logic-inj): $E \approx f(E)$. **3.** ($\Rightarrow$) Misalkan $f \colon E \to F$ [injektif](#def-b1-logic-inj) 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](#def-b1-logic-inj). ($\Leftarrow$) Misalkan $s \colon F \to E$ [surjektif](#def-b1-logic-inj). 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](#def-b1-logic-inj). **4.** $n \mapsto n + 1$ memetakan $\N$ ke dalam $\N^*$, bersifat [injektif](#def-b1-logic-inj) ($n + 1 = m + 1 \implies n = m$) dan [surjektif](#def-b1-logic-inj) (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](#exo-b1-logic-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](#def-b1-logic-inj). **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](#def-b1-logic-map). *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](#def-b1-logic-inj), jadi [bijektif](#def-b1-logic-inj). **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](#def-b1-logic-statement) itu tidak sepele karena kedua injeksi yang diberikan tak saling berkaitan — tak satu pun harus [surjektif](#def-b1-logic-inj), dan tak ada rumus naif yang mencampur $f$ dan $g$ yang mendefinisikan sebuah [pemetaan](#def-b1-logic-map): seluruh isinya adalah [partisi](#thm-b1-logic-partition) $E$ atas daerah $C$ (tempat kita menyalin $f$) dan komplemennya (tempat kita menjalankan $g$ secara terbalik). **10.** (a) [Pemetaan](#def-b1-logic-map) inklusi $\intoo01 \to \intcc01$ bersifat [injektif](#def-b1-logic-inj); dan $x \mapsto \frac{x + 1}3$ memetakan $\intcc01$ secara [injektif](#def-b1-logic-inj) 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](#thm-b1-logic-induction)) 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](#def-b1-logic-sets) 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](#def-b1-logic-sets) hingga dan [himpunan terbilang](#pb-b1-logic-1) 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](https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat#ch-b1-arith); untuk $r = 0$ ambil $0/1$). [Pemetaan](#def-b1-logic-map) $r \mapsto (p, q)$ lalu bersifat [injektif](#def-b1-logic-inj): 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](#exo-b1-logic-4). Jadi $\Psi(F) \neq \Psi(F')$: $\Psi$ [injektif](#def-b1-logic-inj) dan [himpunan](#def-b1-logic-sets) semua [himpunan](#def-b1-logic-sets) bagian hingga dari $\N$ paling banyak terbilang; ia tak hingga (ia memuat semua [himpunan](#def-b1-logic-sets) 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](#def-b1-logic-map) itu saling invers: $A_{\mathbf 1_A} = A$ dan $\mathbf 1_{A_u} = u$ (periksa nilainya pada setiap $n$). Menurut [Teorema 1.24](#thm-b1-logic-inverse), 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](#def-b1-logic-inj), dan menurut pertanyaan 3 tak ada pula injeksi $\{0,1\}^{\N} \to \N$: jadi $\{0,1\}^{\N}$ bukan [himpunan](#def-b1-logic-sets) yang paling banyak terbilang. Lewat kamus pertanyaan 17, sebuah [pemetaan](#def-b1-logic-map) $\Phi \colon \N \to \{0,1\}^{\N}$ adalah [pemetaan](#def-b1-logic-map) $f \colon \N \to \mathcal{P}(\N)$, dan $d$ berpadanan dengan [himpunan](#def-b1-logic-sets) $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](#exo-b1-logic-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](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1) 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](#def-b1-logic-map) ini [injektif](#def-b1-logic-inj), 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](#def-b1-logic-sets) polinomial bulat yang derajatnya terbatas bersifat paling banyak terbilang; ia tak hingga (ia memuat semua konstanta), jadi terbilang menurut pertanyaan 12. **23.** [Himpunan](#def-b1-logic-sets) semua polinomial bulat adalah $\bigcup_{n \in \N} \{P : \deg P \leq n,\ P \text{ berkoefisien bulat}\}$, sebuah gabungan terbilang dari [himpunan terbilang](#pb-b1-logic-1): paling banyak terbilang menurut pertanyaan 15, tak hingga, jadi terbilang. **24.** Untuk setiap polinomial bulat tak nol $P$, [himpunan](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1) itu ada dan bahkan membentuk [himpunan](#def-b1-logic-sets) tak terbilang, sedangkan [bilangan aljabar](#pb-b1-logic-1) — 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](#pb-b1-logic-1) mana pun, namun menunjukkan bahwa dalam pengertian ekuipotensi *hampir setiap* bilangan real bersifat transenden. Menyebut satu [bilangan transenden](#pb-b1-logic-1) tertentu — $\pi$ atau $\eu$ — menuntut matematika yang sama sekali lain dan puluhan tahun kerja tambahan.