Bab 3: Teori Himpunan Aksiomatik dan Aljabar Himpunan

Bab ini menjawab dua pertanyaan yang menyertai pemakaian himpunan dalam analisis: bagaimana keberadaan suatu himpunan dijamin, dan bagaimana kesamaan dua himpunan dibuktikan. Bahasa kuantifikator dari Bab 2 akan dipakai untuk keduanya. Kita mulai dengan aksioma dasar dan pembentukan himpunan bagian, lalu mengembangkan operasi biner. Setelah itu, gabungan dan irisan diperluas ke keluarga berindeks sembarang. Hukum De Morgan dan contoh interval memperlihatkan mengapa indeks kosong, ujung interval, dan perbedaan urutan kuantifikator harus ditangani secara eksplisit.

3.1 Aksioma Dasar Teori Himpunan

Bab 2 memakai himpunan secara bebas. Kita menulis "himpunan semua $x$ di $U$ yang memenuhi sifat tertentu", membentuk gabungan dan irisan keluarga berindeks, dan menyatakan bahwa dua himpunan dengan anggota yang sama adalah himpunan yang sama. Pemakaian itu sah sebagai bahasa kerja. Namun ada satu pertanyaan yang ditunda: kapan sebuah ungkapan "himpunan semua $x$ yang …" benar-benar menunjuk sebuah objek?

Jawaban yang paling sederhana adalah bahwa setiap sifat menentukan sebuah himpunan. Unit ini menunjukkan bahwa jawaban itu salah, dan kesalahannya bukan soal teknis kecil. Jawaban itu menghasilkan kontradiksi dalam logika murni. Karena itu, teori himpunan aksiomatik memisahkan dua hal yang dalam pemakaian sehari-hari sering dicampur.

1. Kesamaan. Kapan dua himpunan dianggap sama? Jawabannya diberikan oleh ekstensionalitas.
2. Keberadaan. Himpunan mana yang dijamin ada? Jawabannya diberikan oleh aksioma keberadaan: himpunan kosong, separasi, dan kemudian pasangan, gabungan, dan himpunan kuasa.

Setiap konstruksi dalam bab ini akan disertai jaminan keberadaan yang eksplisit. Setiap kesamaan akan dibuktikan dari anggota-anggotanya.

Bahasa: keanggotaan dan kesamaan

Teori yang kita pakai adalah ZF (Zermelo–Fraenkel), yang dirumuskan dalam bahasa orde pertama satu-sortir. Hanya ada satu jenis objek, yaitu himpunan. Selain simbol logika dari Bab 1–2, bahasa ini hanya memiliki satu simbol nonlogis, yaitu relasi biner $\in$. Kesamaan $=$ adalah simbol logika. Jadi formula atom hanya berbentuk

$$x \in y \qquad\text{atau}\qquad x = y,$$

dan semua formula lain dibangun dari formula atom dengan konektif dan kuantifikator. Konvensi ini mengikuti penyajian standar; lihat [R3-1] dan [R3-3].

Konsekuensinya penting. Simbol-simbol yang segera kita perkenalkan, seperti $\subseteq$, $\emptyset$, dan $\{x \in a : \varphi\}$, bukan bagian dari bahasa dasar. Notasi relasi seperti $\subseteq$ menyingkat formula, sedangkan $\emptyset$ dan notasi set-builder menamai objek yang telah dijamin ada dan tunggal. Pernyataan yang memakai notasi tambahan ini dapat dijabarkan kembali dalam bahasa dasar $\in$ dan $=$. Menambah singkatan tidak menambah objek. Sebuah nama untuk objek, misalnya $\emptyset$, baru boleh dipakai setelah kita membuktikan bahwa objek yang dimaksud ada dan tunggal.

Ketika contoh memakai angka seperti $1, 2, 3$ atau bilangan real, angka itu diperlakukan sebagai objek yang telah dikenal pembaca. Kita tidak berpura-pura bahwa konstruksi bilangan dari himpunan sudah selesai. Yang dipakai dari angka-angka itu hanyalah bahwa angka yang berbeda adalah objek yang berbeda, beserta sifat-sifat yang akan disebut setiap kali digunakan.

Sesuai Bab 2, semesta setiap struktur tidak kosong. Kesamaan tunduk pada aturan logika substitusi: jika $a = b$, maka setiap formula yang benar untuk $a$ juga benar untuk $b$. Khususnya,

$$a = b \;\rightarrow\; \forall x\,(x \in a \leftrightarrow x \in b).$$

Arah ini adalah logika. Arah sebaliknya, yaitu bahwa kesamaan anggota memaksa kesamaan himpunan, tidak dapat diturunkan dari logika. Arah sebaliknya itu adalah aksioma pertama kita.

Definisi 3.1.1 (Inklusi). Untuk himpunan $X$ dan $A$,

$$X \subseteq A \;:\!\!\leftrightarrow\; \forall x\,(x \in X \rightarrow x \in A).$$

Kita membaca $X \subseteq A$ sebagai "$X$ himpunan bagian dari $A$". Kita menulis $X \subsetneq A$ untuk $X \subseteq A \land X \neq A$, dan $X \not\subseteq A$ untuk $\neg(X \subseteq A)$.

Perhatikan perbedaan bentuknya. $x \in A$ adalah formula atom, sedangkan $X \subseteq A$ adalah formula universal. Negasi inklusi, menurut aturan negasi kuantifikator di Bab 2, adalah eksistensial:

$$X \not\subseteq A \;\leftrightarrow\; \exists x\,(x \in X \land x \notin A).$$

Jadi untuk membantah inklusi, kita cukup menunjukkan satu saksi. Untuk membuktikan inklusi, kita harus menangani anggota $X$ yang sembarang.

Aksioma 3.1.2 (Ekstensionalitas).

$$\forall a\,\forall b\,\bigl(\forall x\,(x \in a \leftrightarrow x \in b) \rightarrow a = b\bigr).$$

Aksioma ini menyatakan bahwa sebuah himpunan ditentukan sepenuhnya oleh anggotanya. Urutan penyebutan, pengulangan, dan cara mendeskripsikan sebuah himpunan tidak berpengaruh. Yang menentukan hanyalah jawaban atas pertanyaan "apakah $x$ anggota?" untuk setiap $x$.

Ada dua hal yang tidak dikatakan oleh ekstensionalitas.

• Ekstensionalitas tidak menyatakan bahwa sebuah himpunan ada. Bentuknya adalah universal atas sebuah implikasi. Dalam struktur dengan satu objek dan relasi $\in$ yang kosong, aksioma ini benar, dan struktur tersebut hanya memiliki satu himpunan. Dari ekstensionalitas saja kita tidak dapat menurunkan keberadaan himpunan apa pun selain yang sudah dijamin oleh logika.
• Ekstensionalitas tidak membuktikan bahwa ZF konsisten. Ekstensionalitas hanya membatasi berapa banyak himpunan yang boleh memiliki anggota yang sama, yaitu paling banyak satu.

Dengan Definisi 3.1.1, premis aksioma ini dapat dipecah menjadi dua inklusi. Pemecahan itu adalah strategi standar untuk membuktikan kesamaan himpunan di seluruh bab ini.

Proposisi 3.1.3 (Sifat dasar inklusi). Untuk setiap himpunan $A$, $B$, dan $C$:

1. (Refleksif) $A \subseteq A$.
2. (Antisimetris, dua inklusi) $A = B \leftrightarrow (A \subseteq B \land B \subseteq A)$.
3. (Transitif) Jika $A \subseteq B$ dan $B \subseteq C$, maka $A \subseteq C$.

Bukti.

(1) Ambil $x$ sembarang. Implikasi $x \in A \rightarrow x \in A$ berbentuk $P \rightarrow P$, sehingga benar untuk setiap nilai kebenaran $P$. Karena $x$ sembarang, $\forall x\,(x \in A \rightarrow x \in A)$, yaitu $A \subseteq A$.

(2) $(\Leftarrow)$ Andaikan $A \subseteq B$ dan $B \subseteq A$. Ambil $x$ sembarang. Inklusi pertama memberi $x \in A \rightarrow x \in B$, dan inklusi kedua memberi $x \in B \rightarrow x \in A$. Gabungan keduanya adalah $x \in A \leftrightarrow x \in B$. Karena $x$ sembarang, premis Aksioma 3.1.2 terpenuhi, sehingga $A = B$.

$(\Rightarrow)$ Andaikan $A = B$. Menurut (1), $A \subseteq A$. Substitusi kesamaan pada kemunculan kedua memberi $A \subseteq B$, dan substitusi pada kemunculan pertama memberi $B \subseteq A$. Arah ini hanya memakai logika kesamaan, bukan ekstensionalitas.

(3) Andaikan $A \subseteq B$ dan $B \subseteq C$. Ambil $x$ sembarang dan andaikan $x \in A$. Instansiasi inklusi pertama pada $x$ memberi $x \in B$. Instansiasi inklusi kedua pada $x$ yang sama memberi $x \in C$. Jadi $x \in A \rightarrow x \in C$. Variabel $x$ tidak bebas dalam asumsi $A \subseteq B$ maupun $B \subseteq C$, karena di sana $x$ terikat oleh kuantifikatornya sendiri. Karena itu generalisasi sah, dan kita peroleh $A \subseteq C$. ∎

Perlu dicatat bahwa $\subsetneq$ tidak refleksif, karena $A \subsetneq A$ menuntut $A \neq A$. Bab 4 akan memberi nama pada kombinasi sifat (1)–(3). Di sini sifat-sifat itu dipakai hanya sebagai alat bukti.

Contoh 3.1.4 (Apa yang diputuskan ekstensionalitas sebelum ada himpunan). Kita belum memiliki aksioma yang menjamin adanya himpunan yang anggotanya tepat $a$ dan $b$. Aksioma itu adalah pasangan (Aksioma 3.1.16). Meskipun demikian, ekstensionalitas sudah dapat memutuskan keunikan dalam bentuk bersyarat.

Misalkan $a$ dan $b$ himpunan, dan misalkan $c$, $c'$, dan $d$ adalah himpunan yang memenuhi

$$\forall x\,\bigl(x \in c \leftrightarrow (x = a \lor x = b)\bigr), \quad \forall x\,\bigl(x \in c' \leftrightarrow (x = a \lor x = b)\bigr), \quad \forall x\,\bigl(x \in d \leftrightarrow (x = b \lor x = a \lor x = a)\bigr).$$

Untuk setiap $x$, ketiga ruas kanan ekuivalen secara logis, karena $\lor$ komutatif dan $P \lor P \leftrightarrow P$ (Bab 1). Jadi $c$, $c'$, dan $d$ memiliki anggota yang sama, dan menurut Aksioma 3.1.2, $c = c' = d$. Inilah alasan mengapa nanti kita boleh menulis $\{a, b\} = \{b, a\} = \{a, b, a\}$. Urutan dan pengulangan memang tidak menentukan anggota. Namun semua ini bersyarat. Jika tidak ada himpunan yang memenuhi syarat itu, kalimat di atas benar secara vakum, dan ekstensionalitas tidak dapat mengubah keadaan tersebut.

Kasus $a = b$ perlu diperhatikan. Syarat $x = a \lor x = a$ setara dengan $x = a$. Jadi sebuah himpunan $s$ yang memenuhi

$$\forall x\,(x \in s \leftrightarrow x = a)$$

juga tunggal bila ada. Himpunan itulah yang nanti disebut singleton $\{a\}$. Sebelum pasangan tersedia, kita hanya boleh mengatakan hal-hal berikut tentang $s$ yang diandaikan ada.

• $a \in s$, karena $a = a$. Ini pernyataan keanggotaan.
• Untuk setiap himpunan $A$, $s \subseteq A$ benar tepat ketika $a \in A$. Arah pertama didapat dengan menginstansiasi inklusi pada $a$. Arah kedua berlaku karena setiap anggota $s$ sama dengan $a$. Ini pernyataan inklusi tentang $s$, dan bentuknya berbeda dari pernyataan keanggotaan tentang $a$.

Dengan demikian, "$a$ anggota $A$" dan "$s$ himpunan bagian $A$" adalah dua formula yang berbeda. Keduanya kebetulan ekuivalen, dan ekuivalensi itu memerlukan bukti. Proposisi 3.1.20 akan menyatakannya kembali setelah keberadaan $\{a\}$ dijamin.

Keberadaan pertama: himpunan kosong

Aksioma 3.1.5 (Himpunan kosong).

$$\exists e\,\forall x\,(x \notin e).$$

Aksioma ini adalah pernyataan keberadaan pertama dalam daftar kita. Aksioma ini menjamin bahwa sekurang-kurangnya satu himpunan tidak memiliki anggota.

Catatan 3.1.6 (Keberadaan dan keunikan dipasok oleh aksioma yang berbeda). Pernyataan "ada tepat satu $e$ dengan $\forall x\,(x \notin e)$" adalah konjungsi dari dua pernyataan.

• Keberadaan: $\exists e\,\forall x\,(x \notin e)$. Ini dijamin oleh Aksioma 3.1.5.
• Paling banyak satu: $\forall e\,\forall e'\,\bigl(\forall x\,(x \notin e) \land \forall x\,(x \notin e') \rightarrow e = e'\bigr)$. Ini akan dijamin oleh ekstensionalitas.

Kedua bagian ini memang independen. Pertimbangkan struktur dengan dua objek berbeda $u$ dan $v$, dan relasi $\in$ yang kosong. Dalam struktur ini Aksioma 3.1.5 benar, bahkan dengan dua saksi. Namun ekstensionalitas salah, karena $u$ dan $v$ memiliki anggota yang sama (tidak ada) tetapi $u \neq v$. Sebaliknya, struktur satu objek $w$ dengan $w \in w$ memenuhi ekstensionalitas tetapi tidak memiliki himpunan kosong. Jadi tidak satu pun dari kedua aksioma ini yang dapat menggantikan yang lain.

Teorema 3.1.7 (Keunikan himpunan kosong). Jika $e$ dan $e'$ adalah himpunan tanpa anggota, maka $e = e'$. Akibatnya, ada tepat satu himpunan tanpa anggota. Himpunan ini ditulis $\emptyset$. Lebih lanjut, setiap himpunan $Y$ dengan $\forall x\,(x \notin Y)$ memenuhi $Y = \emptyset$.

Bukti. Ambil $x$ sembarang. Menurut hipotesis, $x \in e$ salah dan $x \in e'$ salah. Biimplikasi antara dua pernyataan yang sama-sama salah adalah benar, sehingga $x \in e \leftrightarrow x \in e'$. Karena $x$ sembarang, Aksioma 3.1.2 memberi $e = e'$.

Aksioma 3.1.5 memberi sekurang-kurangnya satu himpunan tanpa anggota, dan bagian pertama memberi paling banyak satu. Jadi ada tepat satu, dan nama $\emptyset$ menunjuk objek yang jelas. Kalimat terakhir teorema adalah bagian pertama dengan $e := Y$ dan $e' := \emptyset$. ∎

Kalimat terakhir inilah yang paling sering dipakai. Untuk membuktikan bahwa sebuah himpunan yang dibentuk dengan cara tertentu sama dengan $\emptyset$, kita cukup menunjukkan bahwa himpunan itu tidak memiliki anggota.

Proposisi 3.1.8 (Himpunan kosong adalah himpunan bagian setiap himpunan). Untuk setiap himpunan $A$, berlaku $\emptyset \subseteq A$. Selain itu, untuk setiap $X$, $X \subseteq \emptyset$ mengimplikasikan $X = \emptyset$.

Bukti. Kita harus menunjukkan $\forall x\,(x \in \emptyset \rightarrow x \in A)$. Ambil $x$ sembarang. Anteseden $x \in \emptyset$ salah, sehingga implikasinya benar, apa pun nilai $x \in A$. Karena $x$ sembarang, $\emptyset \subseteq A$. Bukti ini sama sekali tidak memeriksa isi $A$.

Untuk bagian kedua, andaikan $X \subseteq \emptyset$. Bagian pertama dengan $A := X$ memberi $\emptyset \subseteq X$. Proposisi 3.1.3(2) lalu memberi $X = \emptyset$. ∎

Ini adalah versi himpunan dari pembatas kosong di Bab 2: universal yang dibatasi oleh $\emptyset$ selalu benar. Namun $\emptyset \subseteq A$ tidak berarti $\emptyset \in A$. Untuk $A = \emptyset$ kita punya

$$\emptyset \subseteq \emptyset \quad\text{benar}, \qquad \emptyset \in \emptyset \quad\text{salah}.$$

Objeknya sama, relasinya berbeda, dan nilai kebenarannya berbeda. Inklusi adalah universal yang dapat benar secara vakum. Keanggotaan adalah pernyataan atom yang kebenarannya ditentukan oleh apakah objek yang disebut memang anggota himpunan tersebut.

Pembentukan himpunan bagian: skema separasi

Sejauh ini satu-satunya himpunan yang dijamin ada adalah $\emptyset$. Bab 2 sering memakai bentuk "himpunan semua $x$ di $U$ yang memenuhi $\varphi$". Aksioma berikut menjamin bentuk itu, asalkan ada himpunan $U$ yang disaring. Karena satu aksioma diberikan untuk setiap formula $\varphi$, aksioma ini sebenarnya adalah skema, yaitu daftar tak hingga aksioma yang dibentuk menurut satu pola.

Aksioma 3.1.9 (Skema separasi). Untuk setiap formula $\varphi(x, p_1, \dots, p_n)$ dalam bahasa ZF yang tidak memuat $b$ sebagai variabel bebas,

$$\forall p_1 \cdots \forall p_n\,\forall a\,\exists b\,\forall x\,\bigl(x \in b \leftrightarrow (x \in a \land \varphi(x, p_1, \dots, p_n))\bigr).$$

Peran masing-masing variabel adalah sebagai berikut.

• $a$ adalah himpunan yang disaring. Himpunan ini sudah harus tersedia.
• $x$ adalah variabel penyaring yang berjalan atas anggota $a$.
• $p_1, \dots, p_n$ adalah parameter, yaitu himpunan tetap yang boleh dirujuk oleh syarat penyaring. Himpunan $a$ sendiri boleh menjadi salah satu parameter.
• $b$ adalah himpunan baru yang keberadaannya dijamin. Variabel $b$ tidak boleh bebas dalam $\varphi$. Kemunculan terikat tidak menjadi masalah, karena dapat diganti nama.

Proposisi 3.1.10 (Notasi set-builder terbatas). Untuk setiap $a$ dan nilai parameter $p_1, \dots, p_n$, himpunan $b$ dalam Aksioma 3.1.9 tunggal. Himpunan itu ditulis

$$\{x \in a : \varphi(x, p_1, \dots, p_n)\},$$

dan memenuhi $\{x \in a : \varphi(x, p_1, \dots, p_n)\} \subseteq a$.

Bukti. Jika $b$ dan $b'$ sama-sama memenuhi syarat, maka untuk setiap $x$, $x \in b$ dan $x \in b'$ keduanya ekuivalen dengan $x \in a \land \varphi(x, p_1, \dots, p_n)$. Jadi $x \in b \leftrightarrow x \in b'$, dan Aksioma 3.1.2 memberi $b = b'$. Untuk inklusi, ambil $x \in b$. Syarat keanggotaan memberi $x \in a \land \varphi(\dots)$, dan khususnya $x \in a$. ∎

Separasi hanya dapat mengecilkan himpunan yang sudah ada. Separasi tidak pernah menghasilkan anggota yang tidak berasal dari $a$.

Parameter. Misalkan semesta kerja $U = \{1, 2, 3, 4, 5\}$ telah tersedia. Keberadaannya akan dijamin oleh pasangan dan gabungan, dengan angka sebagai objek yang dikenal. Formula $\varphi(x, p) := x \neq p$ memuat satu parameter $p$. Untuk $p = 3$,

$$\{x \in U : x \neq 3\} = \{1, 2, 4, 5\},$$

dan untuk $p = 7$, yang bukan anggota $U$, tidak ada anggota yang tersaring keluar, sehingga

$$\{x \in U : x \neq 7\} = U.$$

Satu formula dengan parameter yang berbeda menghasilkan himpunan yang berbeda. Separasi tetap sah ketika parameternya berada di luar $a$. Pola yang sama, dengan parameter berupa himpunan lain, akan memberi irisan dan selisih pada Contoh 3.1.13.

Mengapa $b$ tidak boleh bebas dalam $\varphi$. Syarat ini bukan formalitas. Andaikan kita mengizinkan $\varphi(x) := x \notin b$. Instans yang dihasilkan adalah

$$\forall a\,\exists b\,\forall x\,\bigl(x \in b \leftrightarrow (x \in a \land x \notin b)\bigr).$$

Ambil himpunan $a$ yang memiliki anggota $x_0$. Pasangan akan segera memberi contoh seperti itu, misalnya $\{\emptyset\}$. Instansiasi pada $x := x_0$ memberi $x_0 \in b \leftrightarrow x_0 \notin b$, sebuah kontradiksi. Jadi "instans" ini akan membantah keberadaan setiap himpunan tak kosong. Syarat penyaring tidak boleh merujuk himpunan yang sedang didefinisikan olehnya.

Catatan: himpunan kosong dapat diturunkan. Dalam semantik Bab 2, semesta tidak kosong. Karena itu $\exists a\,(a = a)$ adalah validitas logika, sehingga sekurang-kurangnya ada satu himpunan $a$. Terapkan separasi pada $a$ dengan formula yang selalu salah, misalnya $\varphi(x) := x \neq x$:

$$b = \{x \in a : x \neq x\}.$$

Untuk setiap $x$ berlaku $x = x$, sehingga ruas kanan $x \in a \land x \neq x$ salah, dan $b$ tidak memiliki anggota. Jadi Aksioma 3.1.5 adalah teorema dari separasi ditambah logika dengan semesta tak kosong. Kita tetap menyatakannya sebagai aksioma karena alasan pedagogis: keberadaan himpunan pertama menjadi prinsip yang terlihat, bukan efek samping yang tersembunyi dalam konvensi semantik. Teorema 3.1.7 tidak terpengaruh, karena keunikan selalu berasal dari ekstensionalitas.

Komprehensi tak terbatas dan paradoks Russell

Bandingkan separasi dengan prinsip yang lebih "murah hati". Komprehensi tak terbatas menyatakan bahwa untuk setiap formula $\varphi(x)$ yang tidak memuat $b$ sebagai variabel bebas,

$$\exists b\,\forall x\,\bigl(x \in b \leftrightarrow \varphi(x)\bigr).$$

Jika prinsip ini berlaku, setiap ungkapan $\{x : \varphi(x)\}$ otomatis menunjuk sebuah himpunan, tanpa perlu himpunan penyaring. Satu-satunya perbedaan dari separasi adalah hilangnya konjung $x \in a$. Perbedaan kecil ini fatal.

Proposisi 3.1.11 (Paradoks Russell). Instans komprehensi tak terbatas untuk $\varphi(x) := x \notin x$ dapat dibantah dalam logika murni:

$$\neg\,\exists b\,\forall x\,(x \in b \leftrightarrow x \notin x).$$

Bukti. Andaikan ada $b$ dengan $\forall x\,(x \in b \leftrightarrow x \notin x)$. Instansiasi universal pada $x := b$ memberi

$$b \in b \leftrightarrow b \notin b.$$

Formula berbentuk $P \leftrightarrow \neg P$ salah untuk setiap nilai kebenaran $P$ (Bab 1). Kontradiksi ini membuktikan negasi pengandaian. ∎

Bukti ini tidak memakai satu pun aksioma ZF. Akibatnya, setiap teori yang memuat komprehensi tak terbatas untuk formula ini tidak konsisten. Pelajarannya tepat: tidak setiap sifat menentukan sebuah himpunan. Russell tidak melarang bentuk notasi set-builder tertentu; ia menolak prinsip komprehensi tak terbatas. Notasi $\{x:\varphi(x)\}$ boleh dipakai bila keberadaan himpunan yang dimaksud sudah dijamin, misalnya ketika $\varphi(x)$ berbentuk $x\in a\land\psi(x)$ dan separasi berlaku. Jika syarat yang sama diterapkan di dalam himpunan $a$ melalui separasi, kontradiksinya hilang dan berubah menjadi informasi tentang $a$.

Teorema 3.1.12 (Russell di dalam ZF). Untuk setiap himpunan $a$, misalkan

$$r_a := \{x \in a : x \notin x\},$$

yang ada dan tunggal menurut separasi dengan $\varphi(x) := x \notin x$ tanpa parameter. Maka $r_a \notin a$. Akibatnya, tidak ada himpunan $V$ yang memenuhi $\forall x\,(x \in V)$.

Bukti. Formula $\varphi(x) := x \notin x$ tidak memuat $r_a$ ataupun $b$ sebagai variabel bebas, sehingga Aksioma 3.1.9 dan Proposisi 3.1.10 memang berlaku. Menurut definisinya, untuk setiap $x$:

$$x \in r_a \leftrightarrow (x \in a \land x \notin x).$$

Andaikan $r_a \in a$. Instansiasi pada $x := r_a$ memberi

$$r_a \in r_a \leftrightarrow (r_a \in a \land r_a \notin r_a).$$

Konjung pertama di ruas kanan benar menurut pengandaian, sehingga ruas kanan ekuivalen dengan $r_a \notin r_a$. Kita peroleh $r_a \in r_a \leftrightarrow r_a \notin r_a$, sebuah kontradiksi. Jadi $r_a \notin a$.

Untuk bagian kedua, andaikan ada $V$ dengan $\forall x\,(x \in V)$. Bentuk $r_V = \{x \in V : x \notin x\}$ dengan separasi. Instansiasi universal pada $x := r_V$ memberi $r_V \in V$, sedangkan bagian pertama dengan $a := V$ memberi $r_V \notin V$. Kontradiksi. Jadi himpunan $V$ seperti itu tidak ada. ∎

Bukti ini tidak memakai aksioma fondasi dan tidak bergantung pada pertanyaan apakah ada himpunan yang memuat dirinya sendiri. Bahkan $r_a \notin r_a$ juga berlaku, karena $r_a \subseteq a$ dan $r_a \notin a$. Argumen Russell, yang dibatasi oleh separasi, berubah dari paradoks menjadi teorema: dalam ZF tidak ada himpunan semesta mutlak. Itulah sebabnya setiap $U$ dalam buku ini adalah semesta kerja tertentu, misalnya $\{1, \dots, 5\}$ atau $\mathbb{R}$. $U$ tidak pernah berarti "semua himpunan".

Contoh 3.1.13 (Irisan dan selisih sebagai separasi). Untuk himpunan $A$ dan $B$, separasi memberi

$$A \cap B := \{x \in A : x \in B\}, \qquad A \setminus B := \{x \in A : x \notin B\}.$$

Di sini $B$ berperan sebagai parameter. Jadi irisan dan selisih tidak memerlukan aksioma baru. Operasi-operasi ini dikembangkan di 3.2. Yang penting di sini adalah keberadaannya sudah terjamin.

Proposisi 3.1.14 (Irisan keluarga tak kosong). Misalkan $\mathcal{F}$ himpunan dan $\mathcal{F} \neq \emptyset$. Ada tepat satu himpunan $\bigcap \mathcal{F}$ yang memenuhi

$$\forall x\,\bigl(x \in \textstyle\bigcap \mathcal{F} \leftrightarrow \forall C\,(C \in \mathcal{F} \rightarrow x \in C)\bigr).$$

Bukti. Keberadaan. Karena $\mathcal{F} \neq \emptyset$, ada $A_0 \in \mathcal{F}$. Bentuk

$$D := \{x \in A_0 : \forall C\,(C \in \mathcal{F} \rightarrow x \in C)\}$$

dengan separasi, memakai parameter $\mathcal{F}$. Kita periksa bahwa $D$ memenuhi syarat keanggotaan.

• Jika $x \in D$, maka menurut definisinya $\forall C \in \mathcal{F}\,(x \in C)$.
• Sebaliknya, jika $\forall C \in \mathcal{F}\,(x \in C)$, maka khususnya $x \in A_0$ karena $A_0 \in \mathcal{F}$. Jadi $x \in D$.

Keunikan. Dua himpunan yang memenuhi syarat ini memiliki anggota yang sama, sehingga keduanya sama menurut ekstensionalitas. Khususnya, $D$ tidak bergantung pada pilihan $A_0$. ∎

Untuk $\mathcal{F} = \emptyset$, syarat $\forall C\,(C \in \emptyset \rightarrow x \in C)$ benar secara vakum untuk setiap $x$. Himpunan yang memenuhinya akan memuat semua himpunan, dan Teorema 3.1.12 melarang hal itu. Karena itu, konvensi Bab 2 dipertahankan dengan batas eksplisit. Untuk $\mathcal{F}$ yang anggotanya himpunan bagian dari $U$,

$$\textstyle\bigcap^U \mathcal{F} := \{x \in U : \forall C\,(C \in \mathcal{F} \rightarrow x \in C)\},$$

sehingga $\bigcap^U \emptyset = U$. Untuk $\mathcal{F} \neq \emptyset$, berlaku $\bigcap^U \mathcal{F} = \bigcap \mathcal{F}$, karena syarat $x \in U$ sudah terpenuhi oleh $x \in A_0 \subseteq U$.

Contoh 3.1.15 (Filter pada semesta berhingga). Ini adalah model kecil, bukan laporan implementasi. Misalkan $U = \{1, 2, 3, 4, 5, 6\}$ adalah nomor peserta, dengan tabel nilai berikut.

Sifat "nilai $\geq 70$" memberi $\{x \in U : \text{nilai}(x) \geq 70\} = \{1, 3, 4, 6\}$. Peserta 3 dan 6 berada tepat di ambang batas dan ikut terpilih, karena syaratnya $\geq$, bukan $>$.

Sifat "nilai $\geq 95$" memberi $\{x \in U : \text{nilai}(x) \geq 95\} = \emptyset$. Hasil kosong adalah keluaran filter yang sah, bukan galat. Separasi memang menjamin bahwa himpunan tersebut ada.

Ada dua catatan kejujuran untuk contoh ini.

1. "Nilai" adalah tabel, dan konsep fungsi baru dikembangkan di Bab 5. Karena $U$ berhingga, sifat pertama dapat ditulis tanpa fungsi sebagai disjungsi $x = 1 \lor x = 3 \lor x = 4 \lor x = 6$.
2. Filter selalu bekerja di dalam $U$. Ungkapan "semua bilangan genap" menunjuk sebuah himpunan setelah keberadaannya dijamin secara sah, misalnya sebagai $\{x\in\mathbb N : x \text{ genap}\}$ melalui separasi. Keberadaan $\mathbb{N}$ sendiri memerlukan aksioma tak hingga (lihat peta ZF di bawah).

Pasangan, gabungan, dan himpunan kuasa

Separasi hanya mengecilkan himpunan. Kita belum dapat membuat himpunan yang anggotanya berasal dari dua himpunan berbeda. Kita juga belum dapat membentuk satu himpunan pun yang memiliki anggota. Tiga aksioma berikut mengisi kekurangan itu, dan kita hanya akan memakainya secukupnya untuk Bab 3.

Aksioma 3.1.16 (Pasangan). $\forall a\,\forall b\,\exists c\,\forall x\,\bigl(x \in c \leftrightarrow (x = a \lor x = b)\bigr)$.

Himpunan $c$ tunggal menurut ekstensionalitas dan ditulis $\{a, b\}$. Kasus $a = b$ memberi singleton $\{a\} := \{a, a\}$, dengan $x \in \{a\} \leftrightarrow x = a$.

Aksioma 3.1.17 (Gabungan). $\forall \mathcal{F}\,\exists u\,\forall x\,\bigl(x \in u \leftrightarrow \exists C\,(C \in \mathcal{F} \land x \in C)\bigr)$.

Himpunan $u$ tunggal dan ditulis $\bigcup \mathcal{F}$. Untuk dua himpunan, definisikan $A \cup B := \bigcup\{A, B\}$. Dengan definisi ini, $x \in A \cup B \leftrightarrow (x \in A \lor x \in B)$, karena $C \in \{A, B\}$ berarti $C = A$ atau $C = B$.

Perbandingan antara keduanya juga patut dicatat. Kuantifikator dalam syarat gabungan adalah eksistensial, sedangkan kuantifikator dalam syarat irisan adalah universal. Perbedaan ini akan menjadi inti De Morgan tak hingga di 3.4.

Proposisi 3.1.18. $\bigcup \emptyset = \emptyset$.

Bukti. $x \in \bigcup \emptyset$ berarti ada $C$ dengan $C \in \emptyset$ dan $x \in C$. Tidak ada $C$ yang memenuhi $C \in \emptyset$, sehingga eksistensial ini salah untuk setiap $x$. Jadi $\bigcup \emptyset$ tidak memiliki anggota, dan Teorema 3.1.7 memberi $\bigcup \emptyset = \emptyset$. ∎

Hasil ini sesuai dengan konvensi "gabungan kosong $= \emptyset$" di Bab 2. Bedanya, kini konvensi itu menjadi teorema, dan tidak diperlukan semesta $U$ seperti pada kasus irisan.

Aksioma 3.1.19 (Himpunan kuasa). $\forall a\,\exists p\,\forall x\,(x \in p \leftrightarrow x \subseteq a)$.

Himpunan $p$ tunggal dan ditulis $\mathcal{P}(a)$. Kombinasi separasi dan himpunan kuasa adalah cara resmi untuk "mengumpulkan himpunan bagian $U$ yang memenuhi sifat tertentu", yaitu $\{X \in \mathcal{P}(U) : \psi(X)\}$.

Catatan lingkup. Bab 2 menulis gabungan berindeks $\bigcup_{i \in I} A_i$. Agar notasi itu menunjuk sebuah himpunan, koleksi nilai keluarga harus telah dijamin sebagai himpunan. Misalkan $I$ dan $U$ adalah himpunan, dan formula $\psi(i, X)$, dengan parameter tetap, menentukan tepat satu $X \subseteq U$ untuk setiap $i \in I$; nilai itu kita tulis $A_i$. Separasi pada $\mathcal{P}(U)$, dengan parameter $I$ dan parameter-parameter dalam $\psi$, memberi

$$\mathcal F=\{X\in\mathcal P(U):\exists i\,(i\in I\land\psi(i,X))\},$$

yaitu koleksi semua nilai $A_i$. Aksioma 3.1.17 kemudian memberi $\bigcup \mathcal{F}$, dan $x \in \bigcup \mathcal{F}$ tepat ketika ada $i \in I$ dengan $x \in A_i$. Demikian pula, $\bigcap^U \mathcal{F}$ memuat tepat semua $x \in U$ dengan $x \in A_i$ untuk setiap $i \in I$; untuk $I = \emptyset$ kita peroleh $\mathcal{F} = \emptyset$, sehingga gabungannya $\emptyset$ dan irisan relatifnya $U$, sesuai konvensi Bab 2. Bila keluarga sudah diberikan sebagai himpunan, langkah pengumpulan ini tidak diperlukan. Untuk penugasan yang terdefinisi oleh formula tetapi tanpa batas bersama $U$ yang tersedia, skema penggantian menjamin himpunan nilainya; skema itu dirumuskan dengan formula dalam bahasa $\in$ dan $=$ sendiri, sedangkan konsep fungsi akan dikembangkan di Bab 5. Unit 3.3 bekerja dengan keluarga yang nilainya himpunan bagian dari semesta kerja $U$ dan diberikan oleh formula seperti di atas, atau sudah diberikan sebagai himpunan, sehingga penggantian tidak diperlukan.

Anggota, himpunan bagian, dan keluarga

Dalam ZF, setiap objek adalah himpunan. Akibatnya, kata "keluarga himpunan" tidak menunjuk jenis objek baru. Kata itu adalah penekanan cara membaca: kita menyebut $\mathcal{F}$ keluarga ketika yang kita perhatikan adalah anggota-anggotanya sebagai himpunan, yaitu anggota dari anggotanya. Ada tiga hubungan yang harus dipisahkan dengan tegas.

• $x \in A$: $x$ adalah anggota $A$. Ini formula atom.
• $X \subseteq A$: setiap anggota $X$ adalah anggota $A$. Ini formula universal.
• $X \in \mathcal{P}(A)$: $X$ adalah anggota keluarga semua himpunan bagian $A$. Menurut Aksioma 3.1.19, pernyataan ini setara dengan $X \subseteq A$. Jadi pada satu tingkat, inklusi diterjemahkan menjadi keanggotaan pada tingkat berikutnya.

Proposisi 3.1.20. Untuk setiap $a$ dan $A$, berlaku $\{a\} \subseteq A \leftrightarrow a \in A$.

Bukti. $(\Rightarrow)$ Karena $a \in \{a\}$, inklusi memberi $a \in A$. $(\Leftarrow)$ Jika $x \in \{a\}$, maka $x = a$, sehingga $x \in A$ menurut substitusi kesamaan. ∎

Relasi $\subseteq$ transitif (Proposisi 3.1.3). Sebaliknya, $\in$ tidak transitif, seperti ditunjukkan contoh bertingkat berikut.

Contoh 3.1.21 (Tingkat-tingkat himpunan murni). Pasangan dan himpunan kosong memberi himpunan-himpunan berikut:

$$\emptyset, \qquad \{\emptyset\}, \qquad \{\{\emptyset\}\}, \qquad \{\emptyset, \{\emptyset\}\}.$$

(a) $\emptyset \neq \{\emptyset\}$. Kita punya $\emptyset \in \{\emptyset\}$ tetapi $\emptyset \notin \emptyset$. Kedua himpunan berbeda keanggotaan pada $x = \emptyset$, sehingga keduanya tidak sama. Himpunan kosong dan himpunan yang anggotanya hanya himpunan kosong adalah dua objek yang berbeda.

(b) $\{\emptyset\} \neq \{\{\emptyset\}\}$. Anggota tunggal $\{\{\emptyset\}\}$ adalah $\{\emptyset\}$, dan $\{\emptyset\} \neq \emptyset$ menurut (a). Jadi $\emptyset \notin \{\{\emptyset\}\}$, sedangkan $\emptyset \in \{\emptyset\}$.

(c) $\in$ tidak transitif. Kita punya $\emptyset \in \{\emptyset\}$ dan $\{\emptyset\} \in \{\{\emptyset\}\}$. Namun, menurut (b), $\emptyset \notin \{\{\emptyset\}\}$.

(d) Inklusi versus keanggotaan. Untuk $A = \{\emptyset, \{\emptyset\}\}$, keempat pernyataan berikut benar: $\emptyset \in A$, $\emptyset \subseteq A$, $\{\emptyset\} \in A$, dan $\{\emptyset\} \subseteq A$. Pernyataan terakhir benar menurut Proposisi 3.1.20, karena $\emptyset \in A$. Sementara itu, untuk $B = \{\{\emptyset\}\}$, berlaku $\{\emptyset\} \in B$ tetapi $\{\emptyset\} \not\subseteq B$, karena $\emptyset \notin B$.

Contoh 3.1.22 (Himpunan kuasa bertingkat).

$\mathcal{P}(\emptyset) = \{\emptyset\}$. Jika $X \subseteq \emptyset$, maka $X$ tidak memiliki anggota, sebab setiap anggota $X$ harus menjadi anggota $\emptyset$. Jadi $X = \emptyset$. Sebaliknya, $\emptyset \subseteq \emptyset$. Jadi $X \in \mathcal{P}(\emptyset) \leftrightarrow X = \emptyset$. Perhatikan bahwa $\mathcal{P}(\emptyset)$ tidak kosong, karena ia memiliki tepat satu anggota.

$\mathcal{P}(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\}$. Misalkan $X \subseteq \{\emptyset\}$. Ada dua kasus. Jika $\emptyset \in X$, maka $X$ dan $\{\emptyset\}$ memiliki anggota yang sama, sehingga $X = \{\emptyset\}$. Jika $\emptyset \notin X$, maka $X$ tidak memiliki anggota, sehingga $X = \emptyset$. Kedua calon memang himpunan bagian dari $\{\emptyset\}$.

$\mathcal{P}(\{a, b\})$ dengan $a = \emptyset$ dan $b = \{\emptyset\}$. Di sini $a \neq b$ menurut Contoh 3.1.21(a). Misalkan $X \subseteq \{a, b\}$. Setiap anggota $X$ adalah $a$ atau $b$, sehingga $X$ ditentukan sepenuhnya oleh jawaban atas dua pertanyaan: apakah $a \in X$, dan apakah $b \in X$. Empat kombinasi jawaban menghasilkan

$$X \in \{\emptyset, \{a\}, \{b\}, \{a, b\}\}.$$

Keempat himpunan ini saling berbeda, karena setiap dua di antaranya berbeda keanggotaan pada $a$ atau pada $b$. Dalam himpunan murni,

$$\mathcal{P}(\mathcal{P}(\{\emptyset\})) = \bigl\{\emptyset,\ \{\emptyset\},\ \{\{\emptyset\}\},\ \{\emptyset, \{\emptyset\}\}\bigr\}.$$

Ketiga perhitungan ini menghasilkan himpunan kuasa dengan 1, 2, dan 4 anggota. Rumus umum "$n$ anggota menghasilkan $2^n$ himpunan bagian" tidak dibuktikan di sini. Pembuktiannya memerlukan induksi dan konsep bijeksi untuk menghitung, dan keduanya belum tersedia. Yang telah kita lakukan hanyalah memeriksa ketiga kasus ini secara langsung.

Gabungan pada tingkat yang sama. $\bigcup\{\emptyset\} = \emptyset$, karena satu-satunya $C$ yang tersedia adalah $\emptyset$, dan $\emptyset$ tidak memiliki anggota. Selanjutnya, $\bigcup\{\emptyset, \{\emptyset\}\} = \emptyset \cup \{\emptyset\} = \{\emptyset\}$. Operasi $\bigcup$ "turun satu tingkat", sedangkan $\mathcal{P}$ "naik satu tingkat". Latihan 3.1.27 memeriksa sejauh mana kedua operasi ini saling membatalkan.

Peta jujur: ZF dan ZFC

Aksioma-aksioma di atas hanyalah bagian awal ZF. Berikut adalah daftar lengkap ZF dalam bentuk peta. Daftar ini tidak dibuktikan dan tidak dipakai melebihi apa yang dinyatakan.

ZFC adalah ZF ditambah aksioma pilihan (AC), yang secara informal menyatakan bahwa dari setiap keluarga himpunan tak kosong dapat dipilih satu anggota dari tiap himpunan sekaligus melalui sebuah fungsi pilihan. AC adalah tambahan terhadap ZF, bukan bagian dari ZF. Seluruh hasil Bab 3 adalah teorema ZF. Lebih tepatnya, hasil-hasil itu hanya memakai enam aksioma pertama dalam tabel, ditambah $\mathbb{N}$ dan $\mathbb{R}$ yang dipinjam pada contoh. Pada contoh interval di 3.4, peminjaman bilangan real mencakup sifat urutan dan sifat Archimedes; sifat-sifat ini akan dinyatakan saat digunakan dan dibuktikan pada bab selanjutnya, bukan disimpulkan dari aljabar himpunan. Bila kelak sebuah argumen memerlukan AC, pemakaiannya akan dinyatakan.

Peta ini sengaja tidak mencakup pertanyaan tentang konsistensi ZF atau tentang independensi AC terhadap ZF. Kedua pertanyaan itu berada di luar lingkup bab ini dan tidak akan dipakai.

Latihan

Latihan 3.1.23. Tentukan kebenaran $\emptyset \in A$ dan $\emptyset \subseteq A$ untuk $A = \emptyset$, $A = \{\emptyset\}$, dan $A = \{\{\emptyset\}\}$.

Pembahasan. Pernyataan $\emptyset \subseteq A$ benar untuk ketiganya menurut Proposisi 3.1.8. Bukti itu tidak memeriksa isi $A$ sama sekali. Sebaliknya, $\emptyset \in A$ harus diperiksa anggota demi anggota.

• $A = \emptyset$: salah, karena $A$ tidak memiliki anggota.
• $A = \{\emptyset\}$: benar.
• $A = \{\{\emptyset\}\}$: salah, karena satu-satunya anggota $A$ adalah $\{\emptyset\}$, dan $\{\emptyset\} \neq \emptyset$ (Contoh 3.1.21(a)).

Strategi umumnya: inklusi adalah universal dan dapat benar secara vakum, sedangkan keanggotaan adalah pernyataan atom yang harus diperiksa terhadap anggota-anggota himpunan tersebut.

Latihan 3.1.24. Buktikan bahwa jika $\{a, b\} = \{c, d\}$, maka $(a = c \land b = d) \lor (a = d \land b = c)$.

Pembahasan. Strateginya adalah membagi kasus menurut keanggotaan, dengan perhatian khusus pada kasus batas ketika dua nama menunjuk objek yang sama.

Karena $a \in \{a, b\} = \{c, d\}$, kita punya $a = c$ atau $a = d$.

Kasus $a = c$. Karena $b \in \{c, d\}$, kita punya $b = c$ atau $b = d$.

• Jika $b = d$, selesai.
• Jika $b = c$, maka $b = a$, sehingga $\{a, b\} = \{a\}$. Karena $d \in \{c, d\} = \{a\}$, kita peroleh $d = a$. Jadi $a = c$ dan $b = a = d$, dan disjungsi pertama berlaku.

Kasus $a = d$. Kita punya $b = c$ atau $b = d$.

• Jika $b = c$, disjungsi kedua berlaku.
• Jika $b = d$, maka $b = a$. Dengan argumen yang sama, $c \in \{a\}$, sehingga $c = a$. Jadi $a = c$ dan $b = d$.

Kasus batas $a = b$ tidak boleh dilewati, sebab di situlah "dua anggota" runtuh menjadi satu anggota. Hasil ini adalah langkah pertama menuju pasangan terurut di Bab 4. Pasangan terurut tidak didefinisikan di sini.

Latihan 3.1.25. Tunjukkan bahwa tidak ada himpunan $S$ yang memuat $\{x\}$ untuk setiap himpunan $x$.

Pembahasan. Andaikan $S$ seperti itu ada. Untuk sembarang $x$, kita punya $\{x\} \in S$ dan $x \in \{x\}$, sehingga $x \in \bigcup S$ menurut Aksioma 3.1.17. Jadi $\bigcup S$ memuat semua himpunan, dan ini bertentangan dengan Teorema 3.1.12.

Strategi umumnya: untuk menunjukkan bahwa sebuah kumpulan "terlalu besar", turunkan dari kumpulan itu sebuah himpunan semesta dengan memakai aksioma yang sah, lalu terapkan Russell.

Latihan 3.1.26. Buktikan bahwa $A \subseteq B \leftrightarrow \mathcal{P}(A) \subseteq \mathcal{P}(B)$.

Pembahasan.

• $(\Rightarrow)$ Jika $X \in \mathcal{P}(A)$, maka $X \subseteq A \subseteq B$. Transitivitas inklusi (Proposisi 3.1.3) memberi $X \subseteq B$, sehingga $X \in \mathcal{P}(B)$.
• $(\Leftarrow)$ Karena $A \subseteq A$, kita punya $A \in \mathcal{P}(A) \subseteq \mathcal{P}(B)$, sehingga $A \in \mathcal{P}(B)$, yaitu $A \subseteq B$.

Arah kedua menginstansiasi inklusi universal $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ pada $X := A$. Ini adalah instansiasi yang paling hemat.

Latihan 3.1.27. Buktikan bahwa $\bigcup \mathcal{P}(A) = A$. Kemudian tunjukkan bahwa $\mathcal{P}(\bigcup \mathcal{F}) = \mathcal{F}$ tidak selalu berlaku.

Pembahasan. Untuk bagian pertama, kita buktikan dua inklusi.

• $(\subseteq)$ Jika $x \in \bigcup \mathcal{P}(A)$, maka ada $C$ dengan $C \subseteq A$ dan $x \in C$. Akibatnya $x \in A$.
• $(\supseteq)$ Jika $x \in A$, maka $\{x\} \subseteq A$ menurut Proposisi 3.1.20. Jadi $\{x\} \in \mathcal{P}(A)$, dan karena $x \in \{x\}$, kita peroleh $x \in \bigcup \mathcal{P}(A)$. Saksi eksistensialnya adalah $C := \{x\}$, yang keberadaannya dijamin oleh pasangan.

Untuk bagian kedua, kita selalu punya $\mathcal{F} \subseteq \mathcal{P}(\bigcup \mathcal{F})$, karena setiap $C \in \mathcal{F}$ memenuhi $C \subseteq \bigcup \mathcal{F}$. Namun kesamaan dapat gagal. Ambil $\mathcal{F} = \{\{\emptyset\}\}$. Maka $\bigcup \mathcal{F} = \{\emptyset\}$ dan $\mathcal{P}(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\} \neq \mathcal{F}$, karena $\emptyset \notin \mathcal{F}$.

Latihan 3.1.28. Untuk sembarang $A$, mana dari pernyataan berikut yang selalu benar: $\emptyset \in \mathcal{P}(A)$, $A \in \mathcal{P}(A)$, $\{\emptyset\} \subseteq \mathcal{P}(A)$, $A \subseteq \mathcal{P}(A)$?

Pembahasan.

• Tiga pernyataan pertama selalu benar. Dua yang pertama berlaku karena $\emptyset \subseteq A$ dan $A \subseteq A$. Yang ketiga berlaku menurut Proposisi 3.1.20, karena $\emptyset \in \mathcal{P}(A)$.
• Pernyataan keempat berarti "setiap anggota $A$ adalah himpunan bagian dari $A$". Pernyataan ini tidak selalu benar. Untuk $A = \{\{\emptyset\}\}$, anggota $\{\emptyset\}$ bukan himpunan bagian dari $A$, karena $\emptyset \notin A$. Sebaliknya, untuk $A = \{\emptyset, \{\emptyset\}\}$, pernyataan itu benar.

Pelajarannya: sebelum menyatakan sebuah inklusi, periksa apakah yang dibandingkan adalah anggota atau himpunan bagian.

Latihan 3.1.29. Pada Contoh 3.1.15, tentukan $\{x \in U : \text{nilai}(x) > 70\}$ dan $\bigcap^U \mathcal{F}$ untuk $\mathcal{F} = \{\{1, 3, 4, 6\}, \{3, 4, 5\}\}$ dan untuk $\mathcal{F} = \emptyset$.

Pembahasan.

• Dengan ketaksamaan ketat, peserta 3 dan 6, yang nilainya tepat 70, keluar dari hasil. Jadi hasilnya $\{1, 4\}$.
• Untuk $\mathcal{F}$ tak kosong, $x$ harus berada di kedua himpunan, sehingga $\bigcap^U \mathcal{F} = \{3, 4\}$. Hasil ini sama dengan $\bigcap \mathcal{F}$ menurut Proposisi 3.1.14.
• Untuk $\mathcal{F} = \emptyset$, syaratnya vakum, sehingga $\bigcap^U \emptyset = U = \{1, \dots, 6\}$. Tanpa batas $U$, irisan ini tidak terdefinisi.

Ketiga perhitungan menunjukkan bahwa ambang batas dan keluarga kosong adalah tempat kesalahan paling mungkin terjadi.

Menuju 3.2

Kini kita memiliki jaminan keberadaan untuk $\emptyset$, $\{a, b\}$, $A \cup B$, $A \cap B$, $A \setminus B$, dan $\mathcal{P}(A)$, serta satu alat untuk membuktikan kesamaan, yaitu dua inklusi. Unit 3.2 memakai jaminan ini untuk mengembangkan aljabar operasi biner (gabungan, irisan, komplemen relatif terhadap semesta kerja $U$, dan selisih simetris) beserta hukum-hukumnya.

3.2 Operasi Biner dan Hukum Aljabar Himpunan

Unit 3.1 memberi kriteria kesamaan dan beberapa cara sah untuk memperoleh himpunan baru. Dari sana, cara mendefinisikan operasi pada himpunan menjadi jelas. Menurut ekstensionalitas, sebuah himpunan ditentukan sepenuhnya oleh anggotanya. Karena itu, mendefinisikan himpunan baru berarti melakukan dua hal:

1. Syarat keanggotaan. Kita menyatakan dengan tepat objek mana yang menjadi anggota.
2. Keberadaan. Kita menunjukkan bahwa aksioma yang tersedia menjamin adanya himpunan dengan anggota tepat seperti itu.

Ketunggalan tidak perlu dibuktikan tersendiri, karena dua himpunan dengan syarat keanggotaan yang sama adalah sama menurut ekstensionalitas. Pola ini juga menentukan cara membuktikan hukum aljabar himpunan. Untuk membuktikan dua ungkapan himpunan sama, kita menunjukkan bahwa untuk setiap $x$, keanggotaan $x$ di ruas kiri ekuivalen dengan keanggotaannya di ruas kanan.

Pada unit ini $A,B,C$ menyatakan himpunan sembarang. Bila komplemen dipakai, ada semesta kerja $U$ yang dinyatakan secara eksplisit dan $A,B,C\subseteq U$. Semesta $U$ adalah himpunan tertentu, bukan himpunan semua himpunan.

Gabungan, irisan, dan selisih

Definisi 3.2.1 (Gabungan). Untuk himpunan $A$ dan $B$, gabungan $A\cup B$ didefinisikan sebagai $\bigcup\{A,B\}$.

Proposisi 3.2.2. Untuk setiap $x$,

$$x\in A\cup B \iff (x\in A \lor x\in B).$$

Selain itu, $A\cup B$ adalah satu-satunya himpunan yang memiliki sifat ini.

Bukti. Aksioma pasangan memberi himpunan $\{A,B\}$ dengan $Y\in\{A,B\}\iff (Y=A\lor Y=B)$. Aksioma gabungan (Unit 3.1) bersama separasi memberi himpunan $\bigcup\{A,B\}$ yang memenuhi

$$x\in\bigcup\{A,B\}\iff \exists Y\,\bigl(Y\in\{A,B\}\land x\in Y\bigr).$$

Ruas kanan ekuivalen dengan $\exists Y\,\bigl((Y=A\lor Y=B)\land x\in Y\bigr)$. Dengan mendistribusikan konjungsi atas disjungsi dan memisahkan kuantifikator eksistensial atas disjungsi, ruas ini ekuivalen dengan

$$\exists Y\,(Y=A\land x\in Y)\ \lor\ \exists Y\,(Y=B\land x\in Y).$$

Bagian pertama ekuivalen dengan $x\in A$: saksi $Y=A$ memberi arah ke kiri, dan kesamaan $Y=A$ memungkinkan substitusi untuk arah ke kanan. Bagian kedua serupa. Jadi $x\in\bigcup\{A,B\}\iff(x\in A\lor x\in B)$.

Untuk ketunggalan, misalkan $S$ juga memenuhi $x\in S\iff(x\in A\lor x\in B)$ untuk setiap $x$. Maka $x\in S\iff x\in A\cup B$ untuk setiap $x$, sehingga $S=A\cup B$ menurut ekstensionalitas. $\blacksquare$

Gabungan membutuhkan aksiomanya sendiri karena $A\cup B$ pada umumnya lebih besar daripada $A$ maupun $B$. Separasi hanya dapat memotong himpunan yang sudah ada, tidak dapat memperbesarnya. Irisan dan selisih berbeda: keduanya selalu termuat di $A$, sehingga separasi sudah cukup.

Definisi 3.2.3 (Irisan dan selisih). Untuk himpunan $A$ dan $B$,

$$A\cap B=\{x\in A : x\in B\},\qquad A\setminus B=\{x\in A : x\notin B\}.$$

Kedua himpunan ada menurut separasi dengan parameter $B$. Formula yang dipakai berturut-turut adalah $\varphi(x,B)\colon x\in B$ dan $\psi(x,B)\colon \neg(x\in B)$. Jika $A\cap B=\varnothing$, kita katakan $A$ dan $B$ saling lepas. (Bandingkan definisi irisan dan selisih dalam [R3-1] dan [R3-2].)

Proposisi 3.2.4. Untuk setiap $x$,

$$x\in A\cap B\iff(x\in A\land x\in B),\qquad x\in A\setminus B\iff(x\in A\land x\notin B).$$

Bukti. Ini langsung dari bentuk separasi: $x\in\{x\in A:\varphi(x,B)\}\iff(x\in A\land\varphi(x,B))$. $\blacksquare$

Catatan 3.2.5. Definisi irisan tampak berat sebelah, karena $A$ berperan sebagai pembatas dan $B$ sebagai parameter. Namun $\{x\in B: x\in A\}$ memiliki syarat keanggotaan $x\in B\land x\in A$, yang ekuivalen dengan $x\in A\land x\in B$. Menurut ekstensionalitas, kedua himpunan itu sama. Pilihan pembatas hanya alat untuk menjamin keberadaan, bukan bagian dari makna irisan. Selisih tidak simetris dengan cara yang sama, dan hal ini akan terlihat pada contoh di bawah. Selisih $A\setminus B$ juga tidak mensyaratkan $B\subseteq A$. Anggota $B$ yang tidak berada di $A$ tidak berpengaruh apa pun.

Definisi 3.2.6 (Komplemen relatif). Misalkan $U$ semesta kerja yang ditetapkan dan $A\subseteq U$. Komplemen $A$ (relatif $U$) adalah

$$A^{c}=U\setminus A.$$

Jadi $x\in A^c\iff(x\in U\land x\notin A)$.

Notasi $A^c$ menyembunyikan $U$. Notasi ini hanya dipakai bila $U$ sudah jelas dari konteks. Bila ada dua semesta yang mungkin, kita menulis $U\setminus A$. Sebagai contoh, komplemen $\{1\}$ relatif $\{1,2\}$ adalah $\{2\}$, sedangkan relatif $\{1,2,3\}$ adalah $\{2,3\}$.

Komplemen tanpa semesta, yaitu "semua objek yang bukan anggota $A$", tidak tersedia. Andaikan untuk $A=\varnothing$ ada himpunan $V$ yang memuat semua objek yang bukan anggota $\varnothing$. Maka $V$ memuat setiap himpunan. Separasi pada $V$ dengan formula $x\notin x$ lalu menghasilkan himpunan Russell, dan menurut Unit 3.1 hal itu mustahil. Inilah alasan semua komplemen dalam buku ini relatif terhadap $U$ yang dinyatakan.

Kasus batas. Langsung dari syarat keanggotaan diperoleh:

$$A\setminus\varnothing=A,\quad \varnothing\setminus A=\varnothing,\quad A\setminus A=\varnothing,\quad \varnothing^c=U,\quad U^c=\varnothing.$$

Sebagai contoh, $x\in A\setminus A\iff(x\in A\land x\notin A)$. Syarat ini tidak dipenuhi oleh objek apa pun, sehingga $A\setminus A$ adalah himpunan kosong yang tunggal.

Contoh wajib dihitung tuntas

Ambil $U=\{1,2,3,4,5\}$, $A=\{1,2,3\}$, dan $B=\{2,3,4\}$. Lambang $1,\dots,5$ dipinjam sebagai objek yang sudah dikenal dan berbeda satu sama lain. Kita tidak mengaku telah mengonstruksi bilangan.

Karena semua himpunan yang terlibat termuat di $U$, objek di luar $U$ tidak menjadi anggota satu pun di antaranya. Jadi untuk menentukan himpunan-himpunan ini cukup memeriksa kelima anggota $U$. Tabel berikut mencatat keanggotaan. Simbol ✓ berarti anggota dan – berarti bukan. Kolom $A\triangle B$ didefinisikan pada subbagian Selisih simetris (Definisi 3.2.13) dan dicantumkan di sini agar perhitungannya lengkap.

Hasilnya:

$$A\cup B=\{1,2,3,4\},\quad A\cap B=\{2,3\},\quad A\setminus B=\{1\},\quad B\setminus A=\{4\},$$$$A^c=\{4,5\},\quad B^c=\{1,5\},\quad A\triangle B=\{1,4\}.$$

Setiap entri tabel adalah penerapan langsung Proposisi 3.2.2 dan 3.2.4. Contohnya, $5\notin A\cup B$ karena $5\notin A$ dan $5\notin B$. Contoh lain, $4\in A^c$ karena $4\in U$ dan $4\notin A$. Perhatikan juga bahwa $A\setminus B=\{1\}\neq\{4\}=B\setminus A$, sehingga selisih tidak komutatif.

Beberapa identitas yang akan dibuktikan pada subbagian Hukum aljabar himpunan dapat diperiksa pada contoh ini:

• $(A\cup B)^c=\{5\}$ dan $A^c\cap B^c=\{4,5\}\cap\{1,5\}=\{5\}$.
• $(A\cap B)^c=\{1,4,5\}$ dan $A^c\cup B^c=\{4,5\}\cup\{1,5\}=\{1,4,5\}$.
• $A\cap B^c=\{1,2,3\}\cap\{1,5\}=\{1\}=A\setminus B$.

Kecocokan ini hanya menunjukkan bahwa identitas berlaku untuk himpunan-himpunan ini. Kecocokan pada satu contoh bukan bukti untuk semua $A,B\subseteq U$. Sebaliknya, satu contoh yang tidak cocok sudah cukup untuk membantah sebuah identitas (lihat subbagian Kontracontoh).

Hukum aljabar himpunan

Hukum-hukum berikut dikelompokkan menurut apakah semesta diperlukan atau tidak.

Teorema 3.2.7 (Hukum tanpa semesta). Untuk semua himpunan $A,B,C$:

1. (Komutatif) $A\cup B=B\cup A$ dan $A\cap B=B\cap A$.
2. (Asosiatif) $(A\cup B)\cup C=A\cup(B\cup C)$ dan $(A\cap B)\cap C=A\cap(B\cap C)$.
3. (Idempoten) $A\cup A=A$ dan $A\cap A=A$.
4. (Himpunan kosong) $A\cup\varnothing=A$ dan $A\cap\varnothing=\varnothing$.
5. (Absorpsi) $A\cup(A\cap B)=A$ dan $A\cap(A\cup B)=A$.
6. (Distributif) $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)$.
7. (Monotonitas dasar) $A\cap B\subseteq A\subseteq A\cup B$.

Ada dua cara yang sah untuk membuktikan kesamaan $X=Y$:

• Dua inklusi. Tunjukkan $X\subseteq Y$ dan $Y\subseteq X$, lalu terapkan ekstensionalitas. Pada tiap arah kita hanya memerlukan implikasi, dan analisis kasus dapat dilakukan dengan leluasa.
• Rantai ekuivalensi. Tuliskan syarat keanggotaan kedua ruas sebagai formula, lalu hubungkan keduanya dengan langkah-langkah yang masing-masing merupakan ekuivalensi yang berlaku untuk setiap $x$, baik karena ekuivalensi logis (Bab 1) maupun karena hipotesis yang dinyatakan, seperti $A\subseteq U$. Setiap langkah harus berupa ekuivalensi, bukan sekadar implikasi. Kesalahan yang umum adalah menyisipkan satu langkah yang hanya berlaku satu arah.

Kita mulai dengan butir-butir yang langsung mengikuti dari ekuivalensi logis sederhana. Setelah itu kita menyajikan butir distributif pertama dan absorpsi dengan dua inklusi, lalu distributif kedua dan asosiatif dengan rantai ekuivalensi.

Tulis $a,b,c$ untuk pernyataan $x\in A$, $x\in B$, $x\in C$. Tulis pula $\bot$ untuk pernyataan yang selalu salah (misalnya $x\in\varnothing$) dan $\top$ untuk pernyataan yang selalu benar.

Bukti (1), (3), (4), (7). Masing-masing mengikuti dari ekuivalensi dan implikasi logis berikut:

• (1) komutativitas $\lor$ dan $\land$;
• (3) $a\lor a\iff a$ dan $a\land a\iff a$;
• (4) $a\lor\bot\iff a$ dan $a\land\bot\iff\bot$, karena $x\in\varnothing$ selalu salah;
• (7) $a\land b\Rightarrow a$ dan $a\Rightarrow a\lor b$. $\blacksquare$

Bukti (6), bagian pertama, dengan dua inklusi.

($\subseteq$) Ambil $x\in A\cap(B\cup C)$. Maka $x\in A$ dan $x\in B\cup C$, sehingga $x\in B$ atau $x\in C$.

• Jika $x\in B$, maka $x\in A\cap B$, sehingga $x\in(A\cap B)\cup(A\cap C)$.
• Jika $x\in C$, maka $x\in A\cap C$, dan kesimpulannya sama.

($\supseteq$) Ambil $x\in(A\cap B)\cup(A\cap C)$.

• Jika $x\in A\cap B$, maka $x\in A$ dan $x\in B\subseteq B\cup C$, sehingga $x\in A\cap(B\cup C)$.
• Jika $x\in A\cap C$, argumennya serupa dengan $C$ menggantikan $B$.

Menurut ekstensionalitas, kedua ruas sama. $\blacksquare$

Bukti (6), bagian kedua, dengan ekuivalensi.

$$x\in A\cup(B\cap C)\iff a\lor(b\land c)\iff(a\lor b)\land(a\lor c)\iff x\in(A\cup B)\cap(A\cup C).$$

Ekuivalensi di tengah adalah hukum distributif disjungsi atas konjungsi. Bila diperlukan, hukum ini dapat diperiksa dengan tabel kebenaran delapan baris. Karena rantai ini berlaku untuk setiap $x$, ekstensionalitas memberi kesamaan yang dimaksud. $\blacksquare$

Bukti (5). Untuk $A\cup(A\cap B)=A$:

• ($\supseteq$) Setiap himpunan termuat dalam gabungannya dengan himpunan lain.
• ($\subseteq$) Jika $x\in A\cup(A\cap B)$, maka $x\in A$, atau $x\in A$ dan $x\in B$. Dalam kedua kasus $x\in A$.

Untuk $A\cap(A\cup B)=A$:

• ($\subseteq$) Ini adalah butir (7), yang sudah dibuktikan di atas.
• ($\supseteq$) Jika $x\in A$, maka $x\in A\cup B$, sehingga $x\in A\cap(A\cup B)$. $\blacksquare$

Bukti (2). Untuk gabungan, $x\in(A\cup B)\cup C\iff(a\lor b)\lor c\iff a\lor(b\lor c)\iff x\in A\cup(B\cup C)$, memakai asosiativitas disjungsi. Untuk irisan, argumennya sama dengan konjungsi. $\blacksquare$

Berkat asosiativitas, kita boleh menulis $A\cup B\cup C$ dan $A\cap B\cap C$ tanpa tanda kurung. Penulisan ini hanya untuk banyaknya himpunan yang ditulis secara eksplisit. Keluarga himpunan yang lebih umum dibahas di Unit 3.3.

Teorema 3.2.8 (Hukum relatif semesta). Misalkan $A,B\subseteq U$, dan komplemen diambil relatif $U$. Maka:

1. $A\cup A^c=U$ dan $A\cap A^c=\varnothing$.
2. $(A^c)^c=A$.
3. $A\cup U=U$ dan $A\cap U=A$.
4. (De Morgan) $(A\cup B)^c=A^c\cap B^c$ dan $(A\cap B)^c=A^c\cup B^c$.
5. $A\setminus B=A\cap B^c$.
6. $A\subseteq B\iff B^c\subseteq A^c$.

Bukti.

(1) Untuk $x\in U$, tepat salah satu dari $x\in A$ dan $x\notin A$ berlaku. Jadi $A\cup A^c\supseteq U$. Inklusi $A\cup A^c\subseteq U$ berlaku karena $A\subseteq U$ dan $A^c\subseteq U$. Bagian $A\cap A^c=\varnothing$ berlaku karena $x\in A\land x\notin A$ mustahil.

(2) Kita hitung:

$$x\in U\setminus(U\setminus A)\iff x\in U\land\neg(x\in U\land x\notin A)\iff x\in U\land(x\notin U\lor x\in A)\iff x\in U\land x\in A.$$

Langkah terakhir benar karena $x\in U\land x\notin U$ mustahil. Karena $A\subseteq U$, pernyataan $x\in U\land x\in A$ ekuivalen dengan $x\in A$. Hipotesis $A\subseteq U$ benar-benar dipakai pada langkah ini. Untuk himpunan sembarang $A$, perhitungan yang sama hanya memberi $U\setminus(U\setminus A)=U\cap A$.

(3) Untuk $A\cup U=U$: arah $\supseteq$ jelas, dan arah $\subseteq$ berlaku karena $A\subseteq U$. Untuk $A\cap U=A$: arah $\subseteq$ jelas, dan arah $\supseteq$ berlaku karena setiap $x\in A$ juga anggota $U$.

(4) Untuk bagian pertama:

$$x\in(A\cup B)^c\iff x\in U\land\neg(x\in A\lor x\in B)\iff x\in U\land x\notin A\land x\notin B$$$$\iff(x\in U\land x\notin A)\land(x\in U\land x\notin B)\iff x\in A^c\cap B^c.$$

Langkah kedua adalah De Morgan proposisional dari Bab 1. Langkah ketiga menduplikasi konjung $x\in U$, yang sah menurut idempotensi.

Bagian kedua diturunkan dari bagian pertama dengan dualitas. Terapkan bagian pertama pada $A^c,B^c\subseteq U$, lalu pakai (2):

$$(A^c\cup B^c)^c=(A^c)^c\cap(B^c)^c=A\cap B.$$

Ambil komplemen kedua ruas. Ini sah karena $X=Y$ mengakibatkan $X^c=Y^c$. Dengan (2) sekali lagi, karena $A^c\cup B^c\subseteq U$, diperoleh $A^c\cup B^c=(A\cap B)^c$.

(5) Kita bandingkan syarat keanggotaan kedua ruas: $x\in A\setminus B\iff x\in A\land x\notin B$, sedangkan $x\in A\cap B^c\iff x\in A\land x\in U\land x\notin B$. Karena $x\in A$ mengakibatkan $x\in U$, konjung $x\in U$ dapat dihilangkan, sehingga keduanya ekuivalen.

(6) Misalkan $A\subseteq B$ dan ambil $x\in B^c$, yaitu $x\in U$ dan $x\notin B$. Jika $x\in A$, maka $x\in B$, sebuah kontradiksi. Jadi $x\notin A$, sehingga $x\in A^c$. Untuk arah sebaliknya, terapkan arah yang baru dibuktikan pada $B^c\subseteq A^c$ untuk memperoleh $(A^c)^c\subseteq(B^c)^c$. Menurut (2), ini berarti $A\subseteq B$. $\blacksquare$

Proposisi 3.2.9 (Inklusi dinyatakan dengan operasi). Untuk himpunan $A,B$, keempat pernyataan berikut ekuivalen:

$$\text{(i) } A\subseteq B,\quad \text{(ii) } A\cup B=B,\quad \text{(iii) } A\cap B=A,\quad \text{(iv) } A\setminus B=\varnothing.$$

Bukti.

• (i)⇒(ii): $B\subseteq A\cup B$ selalu berlaku. Sebaliknya, jika $x\in A\cup B$, maka $x\in B$, atau $x\in A$ dan karena itu juga $x\in B$.
• (ii)⇒(iii): $A\cap B=A\cap(A\cup B)=A$ menurut absorpsi.
• (iii)⇒(iv): $A\setminus B=(A\cap B)\setminus B$. Himpunan ini kosong karena tidak ada $x$ yang memenuhi $x\in B\land x\notin B$.
• (iv)⇒(i): Jika $x\in A$ dan $x\notin B$, maka $x\in A\setminus B=\varnothing$, dan hal itu mustahil. Jadi setiap $x\in A$ adalah anggota $B$. $\blacksquare$

Kontracontoh: pembatalan dan identitas palsu

Dalam aritmetika yang sudah dikenal, $a+b=a+c$ mengakibatkan $b=c$. Untuk gabungan dan irisan, sifat semacam ini tidak berlaku.

Proposisi 3.2.10 (Pembatalan gagal).

1. Ada himpunan $A,B,C$ dengan $A\cup B=A\cup C$ tetapi $B\neq C$.
2. Ada himpunan $A,B,C$ dengan $A\cap B=A\cap C$ tetapi $B\neq C$.

Bukti.

1. Ambil $A=B=\{1\}$ dan $C=\varnothing$. Maka $A\cup B=\{1\}=A\cup C$, tetapi $1\in B\setminus C$.
2. Ambil $A=\varnothing$, $B=\{1\}$, dan $C=\{2\}$. Maka $A\cap B=\varnothing=A\cap C$, tetapi $B\neq C$. $\blacksquare$

Penyebabnya terlihat dari syarat keanggotaan. Gabungan dengan $A$ menghapus informasi tentang bagian $B$ yang berada di dalam $A$. Irisan dengan $A$ menghapus informasi tentang bagian $B$ yang berada di luar $A$. Bila kedua informasi digabungkan, tidak ada yang hilang:

Teorema 3.2.11. Jika $A\cup B=A\cup C$ dan $A\cap B=A\cap C$, maka $B=C$.

Bukti. Ambil $x\in B$.

• Jika $x\in A$, maka $x\in A\cap B=A\cap C$, sehingga $x\in C$.
• Jika $x\notin A$, maka dari $x\in A\cup B=A\cup C$ dan $x\notin A$ diperoleh $x\in C$.

Jadi $B\subseteq C$. Hipotesisnya simetris dalam $B$ dan $C$, sehingga $C\subseteq B$ juga berlaku. $\blacksquare$

Bukti aljabar juga tersedia:

$$C=(A\cup C)\cap C=(A\cup B)\cap C=(A\cap C)\cup(B\cap C)=(A\cap B)\cup(B\cap C)=B\cap(A\cup C)=B\cap(A\cup B)=B.$$

Ruas ini memakai absorpsi, hipotesis, distributivitas, hipotesis, distributivitas, hipotesis, dan absorpsi, dalam urutan itu, bersama komutativitas di langkah absorpsi dan distributif.

Identitas palsu yang sering muncul. Untuk masing-masing identitas berikut, kita beri kontracontoh dan rumus yang benar.

1. $(A\cup B)\setminus B=A$. Pernyataan ini salah: untuk $A=B=\{1\}$, ruas kiri $\varnothing$ dan ruas kanan $\{1\}$. Rumus yang benar adalah

$$x\in(A\cup B)\setminus B\iff(a\lor b)\land\neg b\iff a\land\neg b,$$

sehingga $(A\cup B)\setminus B=A\setminus B$. Himpunan ini sama dengan $A$ tepat ketika $A\cap B=\varnothing$. Sebab, jika $A\setminus B=A$ dan $x\in A\cap B$, maka $x\in A=A\setminus B$, sehingga $x\notin B$, sebuah kontradiksi. Sebaliknya, jika $A\cap B=\varnothing$, setiap $x\in A$ memenuhi $x\notin B$, sehingga $A\subseteq A\setminus B\subseteq A$.

2. $A\setminus(B\setminus C)=(A\setminus B)\setminus C$. Pernyataan ini salah: untuk $A=B=C=\{1\}$, ruas kiri $\{1\}\setminus\varnothing=\{1\}$ dan ruas kanan $\varnothing\setminus\{1\}=\varnothing$. Jadi selisih tidak asosiatif. Rumus yang benar untuk ruas kiri:

$$x\in A\setminus(B\setminus C)\iff a\land\neg(b\land\neg c)\iff a\land(\neg b\lor c)\iff(a\land\neg b)\lor(a\land c),$$

sehingga $A\setminus(B\setminus C)=(A\setminus B)\cup(A\cap C)$. Untuk ruas kanan, $(A\setminus B)\setminus C$ mempunyai syarat $a\land\neg b\land\neg c$, sehingga sama dengan $A\setminus(B\cup C)$.

3. $A\cup(B\setminus C)=(A\cup B)\setminus C$. Pernyataan ini salah: untuk $A=C=\{1\}$ dan $B=\varnothing$, ruas kiri $\{1\}$ dan ruas kanan $\varnothing$. Rumus yang benar untuk ruas kanan diperoleh dari

$$x\in(A\cup B)\setminus C\iff(a\lor b)\land\neg c\iff(a\land\neg c)\lor(b\land\neg c),$$

sehingga $(A\cup B)\setminus C=(A\setminus C)\cup(B\setminus C)$. Ruas kiri yang semula, $A\cup(B\setminus C)$, bersyarat $a\lor(b\land\neg c)$. Kedua formula bernilai sama kecuali bila $a$ dan $c$ keduanya benar; pada keadaan itu ruas kiri benar dan ruas kanan salah. Jadi keduanya sama tepat ketika $A\cap C=\varnothing$.

Cara menemukan kontracontoh. Tuliskan syarat keanggotaan kedua ruas sebagai formula dalam $a,b,c$. Kemudian cari satu penilaian kebenaran yang membuat kedua formula berbeda nilai. Pada butir 2, penilaian itu adalah $a,b,c$ semuanya benar. Penilaian tersebut lalu diwujudkan dengan satu objek, dalam hal ini $1$, yang dimasukkan tepat ke himpunan-himpunan yang penilaiannya benar. Lema 3.2.12 pada subbagian berikut menjelaskan mengapa cara ini selalu berhasil.

Diagram Venn dan bukti universal

Diagram Venn menggambar $A$, $B$, $C$ sebagai daerah yang saling tumpang tindih. Diagram membantu menebak sebuah identitas dan mengingatnya. Namun satu gambar menyajikan satu konfigurasi, sedangkan hukum aljabar himpunan menyatakan sesuatu tentang semua himpunan, yakni sebuah klaim universal. Ada beberapa bahaya konkret:

• Daerah kosong tidak terlihat. Gambar baku untuk $A$ dan $B$ memperlihatkan $A\cap B$ dan $A\setminus B$ sebagai daerah yang tampak berisi. Pembaca mudah mengira $A\cap B\neq\varnothing$ atau $A\setminus B\neq\varnothing$ selalu berlaku. Kedua klaim itu salah: untuk $A=\{1\}$, $B=\{2\}$ berlaku $A\cap B=\varnothing$, dan bila $A=B$ berlaku $A\setminus B=\varnothing$.
• Inklusi tidak tergambar. Bila $A\subseteq B$, diagram baku masih menampilkan daerah $A\setminus B$. Kesimpulan yang mengandaikan daerah itu berisi menjadi keliru.
• Tidak ada kuantifikator. Gambar tidak menyatakan "untuk setiap $x$". Langkah dari gambar ke kesamaan himpunan justru memerlukan ekstensionalitas yang diterapkan pada setiap $x$.

Walaupun begitu, gagasan "periksa setiap daerah" dapat dijadikan argumen yang sah, asalkan dinyatakan dan dibuktikan dengan tepat.

Lema 3.2.12 (Prinsip pola keanggotaan). Misalkan $E(A,B,C)$ dan $F(A,B,C)$ adalah ungkapan yang dibentuk dari lambang $A,B,C$ dengan langkah berhingga memakai $\cup,\cap,\setminus$. Masing-masing memiliki formula proposisional $e(a,b,c)$ dan $f(a,b,c)$ yang memenuhi $x\in E\iff e(x\in A,\,x\in B,\,x\in C)$ untuk setiap $x$, dan hal yang sama untuk $F$. Maka:

(a) Jika $e$ dan $f$ ekuivalen secara logis, yaitu sama nilainya pada kedelapan baris tabel kebenaran, maka $E(A,B,C)=F(A,B,C)$ dapat dibuktikan untuk semua himpunan $A,B,C$.

(b) Jika $e$ dan $f$ tidak ekuivalen secara logis, ada himpunan konkret $A,B,C\in\{\varnothing,\{\varnothing\}\}$ dengan $E(A,B,C)\neq F(A,B,C)$.

Bukti. Keberadaan $e$ diperoleh dengan induksi pada pembentukan ungkapan. Induksi ini dilakukan di tingkat meta, atas langkah pembentukan yang berhingga. Untuk lambang dasar, ungkapan $A$ memberi formula $a$, dan seterusnya. Pada langkah pembentukan, $\cup,\cap,\setminus$ memberi $\lor$, $\land$, dan $\cdot\land\neg\cdot$ menurut Proposisi 3.2.2 dan 3.2.4.

(a) Untuk setiap $x$, keanggotaan $x$ di $E$ dan di $F$ ekuivalen, sehingga $E=F$ menurut ekstensionalitas.

(b) Misalkan pada baris $(v_1,v_2,v_3)$ formula $e$ dan $f$ berbeda nilai. Ambil objek $\varnothing$, lalu definisikan $A=\{\varnothing\}$ bila $v_1$ benar dan $A=\varnothing$ bila $v_1$ salah. Definisikan $B$ dan $C$ dengan cara serupa. Himpunan $\{\varnothing\}$ ada menurut aksioma pasangan. Untuk $x=\varnothing$, pola keanggotaannya tepat $(v_1,v_2,v_3)$. Akibatnya $\varnothing$ menjadi anggota tepat satu di antara $E$ dan $F$, sehingga $E\neq F$. $\blacksquare$

Kedua butir lema berada pada tingkat yang berbeda. Butir (a) menghasilkan bukti di dalam teori himpunan dari fakta tentang tabel kebenaran. Butir (b) menghasilkan kontracontoh konkret. Bersama-sama keduanya menyatakan bahwa, untuk ungkapan semacam ini, sebuah identitas berlaku umum tepat ketika formula keanggotaannya ekuivalen secara logis.

Untuk ungkapan yang memuat komplemen relatif $U$, tambahkan $U$ sebagai lambang keempat dan tulis $X^c$ sebagai $U\setminus X$. Baris yang konsisten dengan $A,B,C\subseteq U$ ialah delapan baris dengan $x\in U$ benar, ditambah baris dengan semua nilai salah. Pada baris terakhir setiap ungkapan yang dibangun dengan $\cup,\cap,\setminus$ bernilai salah, sehingga baris itu tidak pernah membedakan $E$ dan $F$. Karena itu cukup memeriksa delapan baris pertama, dan pada butir (b) kita ambil $U=\{\varnothing\}$.

Jadi diagram Venn tiga himpunan yang diperiksa daerah demi daerah, dengan delapan daerah yang sesuai dengan delapan baris tabel, dapat dijadikan bukti. Namun status buktinya berasal dari Lema 3.2.12(a), bukan dari gambarnya. Butir (b) juga menjamin bahwa setiap identitas palsu dalam bentuk ini memiliki kontracontoh dengan satu objek, seperti pada subbagian Kontracontoh.

Lema ini hanya berlaku untuk banyaknya himpunan yang ditentukan dan ungkapan yang dibentuk dalam langkah berhingga. Untuk keluarga dengan indeks berhingga yang sudah ditetapkan, kuantifikator masih dapat diuraikan menjadi kombinasi berhingga. Namun satu tabel keanggotaan berhingga tidak cukup untuk membuktikan identitas bagi keluarga berindeks sembarang, termasuk indeks tak hingga, seperti pada Unit 3.3-3.4. Bukti umum memakai aturan kuantifikator; hukum De Morgan tak hingga khususnya memakai negasi kuantifikator.

Selisih simetris

Definisi 3.2.13 (Selisih simetris). $A\triangle B=(A\setminus B)\cup(B\setminus A)$.

Keberadaannya dijamin oleh Definisi 3.2.1 dan 3.2.3. Untuk penulisan ringkas, tulis $p\oplus q$ untuk formula $(p\land\neg q)\lor(\neg p\land q)$, yaitu "tepat satu dari $p,q$".

Proposisi 3.2.14. Untuk setiap $x$,

$$x\in A\triangle B\iff(x\in A)\oplus(x\in B)\iff\neg(x\in A\leftrightarrow x\in B).$$

Selain itu, $A\triangle B=(A\cup B)\setminus(A\cap B)$.

Bukti. Ekuivalensi pertama adalah gabungan dari Proposisi 3.2.2 dan 3.2.4. Untuk ekuivalensi kedua, $a\leftrightarrow b$ benar tepat ketika $a,b$ keduanya benar atau keduanya salah, yaitu tepat ketika $a\oplus b$ salah. Untuk bentuk terakhir:

$$(a\lor b)\land\neg(a\land b)\iff(a\lor b)\land(\neg a\lor\neg b)\iff(a\land\neg b)\lor(b\land\neg a).$$

Ekuivalensi terakhir diperoleh dengan menguraikan konjungsi. Dua suku yang muncul, yaitu $a\land\neg a$ dan $b\land\neg b$, selalu salah sehingga dapat dihapus. $\blacksquare$

Jadi $A\triangle B$ memuat objek yang tepat satu kali menjadi anggota $A$ atau $B$. Pada contoh wajib, $A\triangle B=\{1\}\cup\{4\}=\{1,4\}$. Dengan rumus kedua, $\{1,2,3,4\}\setminus\{2,3\}=\{1,4\}$, dan hasilnya sama.

Proposisi 3.2.15. Untuk semua himpunan $A,B$:

1. $A\triangle B=B\triangle A$.
2. $A\triangle\varnothing=A$.
3. $A\triangle A=\varnothing$.
4. $A\triangle B=\varnothing\iff A=B$.

Bila $A\subseteq U$, berlaku juga: 5. $A\triangle U=A^c$. 6. $A\triangle A^c=U$.

Bukti.

1. $\oplus$ simetris dalam kedua argumennya.
2. $a\oplus\bot\iff a$.
3. $a\oplus a$ selalu salah.
4. $A\triangle B=\varnothing$ berarti tidak ada $x$ dengan $\neg(x\in A\leftrightarrow x\in B)$. Ini berarti $x\in A\leftrightarrow x\in B$ untuk setiap $x$, yaitu $A=B$ menurut ekstensionalitas.
5. Karena $A\subseteq U$, objek yang menjadi anggota tepat satu di antara $A$ dan $U$ adalah objek di $U$ yang bukan anggota $A$.
6. Setiap $x\in U$ adalah anggota tepat satu di antara $A$ dan $A^c$. Objek di luar $U$ tidak menjadi anggota keduanya. $\blacksquare$

Teorema 3.2.16 (Asosiativitas selisih simetris). $(A\triangle B)\triangle C=A\triangle(B\triangle C)$.

Bukti. Tulis $a,b,c$ untuk $x\in A,\ x\in B,\ x\in C$. Menurut Proposisi 3.2.14, keanggotaan $x$ di ruas kiri ekuivalen dengan $(a\oplus b)\oplus c$, dan di ruas kanan dengan $a\oplus(b\oplus c)$. Pertama kita catat dua fakta dari definisi $\oplus$:

$$p\oplus\bot\iff p,\qquad p\oplus\top\iff\neg p.$$

Klaim. $(a\oplus b)\oplus c$ benar jika dan hanya jika banyaknya pernyataan benar di antara $a,b,c$ ganjil, yaitu satu atau tiga.

Kita buktikan klaim dengan dua kasus pada $c$:

• Jika $c$ salah, maka $(a\oplus b)\oplus c\iff a\oplus b$. Ini benar tepat ketika tepat satu dari $a,b$ benar. Karena $c$ tidak menambah hitungan, kondisi itu sama dengan "banyaknya yang benar di antara $a,b,c$ adalah satu", dan satu adalah satu-satunya bilangan ganjil yang mungkin ketika $c$ salah.
• Jika $c$ benar, maka $(a\oplus b)\oplus c\iff\neg(a\oplus b)$. Ini benar tepat ketika banyaknya yang benar di antara $a,b$ adalah nol atau dua. Ditambah $c$, banyaknya yang benar di antara $a,b,c$ menjadi satu atau tiga, yaitu ganjil. Sebaliknya, bila banyaknya yang benar di antara $a,b,c$ ganjil dan $c$ benar, maka banyaknya yang benar di antara $a,b$ genap.

Selanjutnya, $a\oplus(b\oplus c)\iff(b\oplus c)\oplus a$ karena $\oplus$ komutatif. Menurut klaim yang diterapkan pada urutan $(b,c,a)$, pernyataan ini benar tepat ketika banyaknya pernyataan benar di antara $b,c,a$ ganjil. Kondisi "banyaknya yang benar ganjil" tidak bergantung pada urutan ketiga pernyataan. Jadi kedua ruas memiliki syarat keanggotaan yang ekuivalen untuk setiap $x$, dan ekstensionalitas menyelesaikan bukti. $\blacksquare$

Sebagai pemeriksaan silang, berikut tabel lengkapnya. Simbol 1 berarti benar dan 0 berarti salah. Pemeriksaan ini sah menurut Lema 3.2.12(a) setelah $\triangle$ diuraikan menurut Definisi 3.2.13.

Dengan asosiativitas, kita boleh menulis $A\triangle B\triangle C$. Menurut klaim di atas, $x\in A\triangle B\triangle C$ jika dan hanya jika $x$ menjadi anggota sejumlah ganjil di antara $A,B,C$. Sifat ini tidak sama dengan "anggota tepat satu himpunan". Kedua syarat berbeda pada objek yang menjadi anggota ketiga himpunan sekaligus.

Akibat 3.2.17 (Pembatalan untuk $\triangle$). Jika $A\triangle B=A\triangle C$, maka $B=C$.

Bukti. Memakai Proposisi 3.2.15 dan Teorema 3.2.16:

$$B=\varnothing\triangle B=(A\triangle A)\triangle B=A\triangle(A\triangle B)=A\triangle(A\triangle C)=(A\triangle A)\triangle C=C.\qquad\blacksquare$$

Bandingkan hasil ini dengan Proposisi 3.2.10. Pembatalan berlaku untuk $\triangle$ karena setiap himpunan merupakan "invers" bagi dirinya sendiri terhadap $\triangle$, yaitu $A\triangle A=\varnothing$. Gabungan dan irisan tidak memiliki invers semacam itu.

Proposisi 3.2.18. $A\cap(B\triangle C)=(A\cap B)\triangle(A\cap C)$. Sebaliknya, gabungan tidak distributif atas $\triangle$.

Bukti. Ruas kiri mempunyai syarat $a\land(b\oplus c)$, dan ruas kanan $(a\land b)\oplus(a\land c)$.

• Jika $a$ salah, kedua formula salah.
• Jika $a$ benar, kedua formula ekuivalen dengan $b\oplus c$.

Untuk bagian kedua, ambil $A=B=C=\{1\}$. Maka $A\cup(B\triangle C)=\{1\}\cup\varnothing=\{1\}$, sedangkan $(A\cup B)\triangle(A\cup C)=\{1\}\triangle\{1\}=\varnothing$. $\blacksquare$

Contoh tiga himpunan. Di semesta $U=\{1,2,3,4,5\}$, ambil $A=\{1,2,3\}$, $B=\{2,3,4\}$, dan $C=\{3,4,5\}$.

Dengan pengelompokan kiri:

$$A\triangle B=\{1,4\},\qquad(A\triangle B)\triangle C=\{1,4\}\triangle\{3,4,5\}=\{1\}\cup\{3,5\}=\{1,3,5\}.$$

Dengan pengelompokan kanan:

$$B\triangle C=\{2\}\cup\{5\}=\{2,5\},\qquad A\triangle(B\triangle C)=\{1,2,3\}\triangle\{2,5\}=\{1,3\}\cup\{5\}=\{1,3,5\}.$$

Kita periksa melalui paritas:

Jadi $A\triangle B\triangle C=\{1,3,5\}$. Himpunan objek yang menjadi anggota tepat satu himpunan adalah $\{1,5\}$. Selisih di antara keduanya adalah objek $3$, yang berada di ketiga himpunan.

Penerapan: filter pada data

Kita memodelkan penyaringan data sebagai operasi himpunan. Data berikut adalah ilustrasi rekaan untuk perhitungan dan tidak berasal dari sistem atau eksperimen nyata.

Misalkan $U=\{1,2,\dots,8\}$ adalah himpunan nomor identitas rekaman pelanggan. Dalam model ini setiap filter diwakili oleh himpunan hasilnya, suatu subset $U$ yang diberikan dengan mendaftar anggotanya. Ambil dua himpunan hasil filter:

• $L=\{1,2,4,6,8\}$: rekaman yang berlangganan buletin;
• $T=\{2,3,4,7,8\}$: rekaman yang bertransaksi bulan ini.

Komplemennya adalah $L^c=\{3,5,7\}$ dan $T^c=\{1,5,6\}$. Setiap kueri berikut dihitung dari syarat keanggotaan.

Baris ketiga dan keempat sama sesuai De Morgan (Teorema 3.2.8). Jadi kueri "bukan (P atau Q)" dapat ditulis ulang sebagai "bukan P dan bukan Q" tanpa mengubah hasilnya. Baris terakhir cocok dengan $(L\cup T)\setminus(L\cap T)=\{1,2,3,4,6,7,8\}\setminus\{2,4,8\}=\{1,3,6,7\}$.

Perubahan antar-cuplikan. Misalkan daftar pelanggan buletin kemarin adalah $L_0=L=\{1,2,4,6,8\}$, sedangkan hari ini $L_1=\{1,4,5,6\}$. Himpunan rekaman yang berubah status adalah

$$D=L_0\triangle L_1=\{2,8\}\cup\{5\}=\{2,5,8\}.$$

Di dalamnya, $L_0\setminus L_1=\{2,8\}$ adalah rekaman yang berhenti berlangganan, dan $L_1\setminus L_0=\{5\}$ adalah rekaman yang baru berlangganan.

Karena $L_0\triangle D=L_0\triangle(L_0\triangle L_1)=(L_0\triangle L_0)\triangle L_1=L_1$, menurut Teorema 3.2.16 dan Proposisi 3.2.15, cuplikan hari ini dapat dipulihkan dari cuplikan kemarin dan himpunan perubahan $D$. Kita periksa langsung: $\{1,2,4,6,8\}\triangle\{2,5,8\}=\{1,4,6\}\cup\{5\}=\{1,4,5,6\}=L_1$.

Tiga filter dan jebakan paritas. Tambahkan himpunan hasil filter $P=\{3,4,5,8\}$ untuk rekaman yang mengajukan pengaduan. Maka

$$L\triangle T\triangle P=\{1,3,6,7\}\triangle\{3,4,5,8\}=\{1,6,7\}\cup\{4,5,8\}=\{1,4,5,6,7,8\}.$$

Hasil ini dapat diperiksa per rekaman:

• Rekaman 4 dan 8 memenuhi ketiga filter, jadi berjumlah ganjil.
• Rekaman 2 ($L,T$) dan 3 ($T,P$) memenuhi dua filter, jadi genap.
• Rekaman 1 dan 6 ($L$), 5 ($P$), dan 7 ($T$) memenuhi tepat satu filter.

Kueri "memenuhi tepat satu filter" menghasilkan $\{1,5,6,7\}$. Seandainya kueri itu ditulis sebagai rangkaian selisih simetris, rekaman 4 dan 8 akan ikut terpilih secara keliru. Kesalahan ini tidak tampak pada kasus dua filter dan baru muncul ketika ada tiga filter. Latihan 10 menetapkan kapan kedua kueri memberi hasil yang sama.

Pembatas kosong. Bila sebuah filter tidak dipenuhi rekaman mana pun, hasilnya $\varnothing$, dan rumus-rumus tetap berlaku tanpa pengecualian: $L\cap\varnothing=\varnothing$, $L\cup\varnothing=L$, $L\triangle\varnothing=L$, dan $\varnothing^c=U$. Bila basis datanya sendiri kosong, yaitu $U=\varnothing$, setiap filter menghasilkan $\varnothing$ dan $\varnothing^c=U=\varnothing$. Semua hukum di Teorema 3.2.8 tetap berlaku, karena buktinya tidak pernah mengandaikan $U$ berisi.

Latihan

1. Untuk contoh wajib $U=\{1,2,3,4,5\}$, $A=\{1,2,3\}$, $B=\{2,3,4\}$, hitung $(A\triangle B)^c$, $A^c\triangle B^c$, $A\setminus(A\setminus B)$, dan $(A\cup B)\setminus(A\triangle B)$. Identitas umum apa yang diisyaratkan oleh hasilnya?
2. Buktikan, tanpa semesta, bahwa $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$ dan $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$. Tunjukkan bahwa De Morgan pada Teorema 3.2.8 adalah kasus khusus untuk $A=U$.
3. Buktikan $A\setminus(A\setminus B)=A\cap B$ untuk semua himpunan $A,B$.
4. Apakah $(A\setminus B)\cup B=A$ berlaku untuk semua $A,B$? Tentukan syarat perlu dan cukupnya.
5. Untuk $A,B\subseteq U$, buktikan $A^c\triangle B^c=A\triangle B$.
6. Tunjukkan bahwa $A\setminus B=A\setminus C$ tidak mengakibatkan $B=C$. Kemudian buktikan $A\setminus B=A\setminus C\iff A\cap B=A\cap C$.
7. Buktikan $(A\cup B)\triangle(A\cup C)=(B\triangle C)\setminus A$. Simpulkan $(A\cup B)\triangle(A\cup C)\subseteq A\cup(B\triangle C)$, lalu tentukan dengan tepat kapan kesamaan berlaku.
8. (Pembatas kosong.) Misalkan $U=\varnothing$. Tentukan semua $A\subseteq U$, hitung $A^c$, lalu periksa $A\cup A^c=U$, $A\cap A^c=\varnothing$, dan kedua hukum De Morgan. Kemudian, untuk $U$ sembarang, hitung $\varnothing\triangle B$ dan $(\varnothing^c)^c$.
9. Pada data subbagian Penerapan: filter pada data dengan himpunan $L,T,P$, hitung himpunan rekaman yang memenuhi paling sedikit dua filter, tepat dua filter, dan tepat satu filter.
10. Buktikan bahwa himpunan objek yang menjadi anggota tepat satu di antara $A,B,C$ sama dengan $A\triangle B\triangle C$ jika dan hanya jika $A\cap B\cap C=\varnothing$.

Pembahasan

1. Strategi: pakai tabel keanggotaan pada subbagian Contoh wajib dihitung tuntas.

• $(A\triangle B)^c=U\setminus\{1,4\}=\{2,3,5\}$.
• $A^c\triangle B^c=\{4,5\}\triangle\{1,5\}=\{4\}\cup\{1\}=\{1,4\}$, sama dengan $A\triangle B$.
• $A\setminus(A\setminus B)=\{1,2,3\}\setminus\{1\}=\{2,3\}$, sama dengan $A\cap B$.
• $(A\cup B)\setminus(A\triangle B)=\{1,2,3,4\}\setminus\{1,4\}=\{2,3\}$, juga sama dengan $A\cap B$.

Hasil ini mengisyaratkan tiga identitas: $A^c\triangle B^c=A\triangle B$ (Latihan 5), $A\setminus(A\setminus B)=A\cap B$ (Latihan 3), dan $(A\cup B)\setminus(A\triangle B)=A\cap B$. Untuk identitas terakhir, syaratnya $(a\lor b)\land\neg(a\oplus b)$. Bila $a,b$ keduanya salah, $a\lor b$ salah. Bila tepat satu benar, $a\oplus b$ benar. Jadi syarat ini benar tepat ketika $a,b$ keduanya benar, yaitu $a\land b$. Perhitungan pada satu contoh hanya mengisyaratkan identitas. Pembuktiannya diberikan secara terpisah.

2. Strategi: ikuti rantai ekuivalensi pada bukti Teorema 3.2.8(4), dengan $A$ menggantikan $U$. Untuk identitas pertama:

$$x\in A\setminus(B\cup C)\iff a\land\neg(b\lor c)\iff a\land\neg b\land\neg c\iff(a\land\neg b)\land(a\land\neg c).$$

Untuk identitas kedua:

$$x\in A\setminus(B\cap C)\iff a\land(\neg b\lor\neg c)\iff(a\land\neg b)\lor(a\land\neg c).$$

Untuk $A=U$ dan $B,C\subseteq U$, ruas-ruas ini menjadi $(B\cup C)^c=B^c\cap C^c$ dan $(B\cap C)^c=B^c\cup C^c$. Versi tanpa semesta ini menunjukkan bahwa De Morgan pada dasarnya adalah hukum tentang selisih. Semesta hanya memberi nama "komplemen" pada selisih terhadap $U$.

3. Strategi: rantai ekuivalensi pada syarat keanggotaan. Syarat keanggotaannya adalah $a\land\neg(a\land\neg b)\iff a\land(\neg a\lor b)\iff(a\land\neg a)\lor(a\land b)\iff a\land b$. Hasil ini adalah kasus khusus dari rumus yang benar pada identitas palsu nomor 2 di subbagian Kontracontoh, dengan $B$ diganti $A$ dan $C$ diganti $B$: $A\setminus(A\setminus B)=(A\setminus A)\cup(A\cap B)=A\cap B$.

4. Strategi: uji dulu dengan pembatas kosong untuk mencari kontracontoh, lalu sederhanakan syarat keanggotaan ruas kiri dan cocokkan dengan Proposisi 3.2.9. Identitas ini tidak berlaku umum. Ambil $A=\varnothing$ dan $B=\{1\}$: ruas kiri $\{1\}$, ruas kanan $\varnothing$. Dalam kasus umum, $(a\land\neg b)\lor b\iff(a\lor b)\land(\neg b\lor b)\iff a\lor b$, sehingga $(A\setminus B)\cup B=A\cup B$. Menurut Proposisi 3.2.9 (dengan peran $A$ dan $B$ ditukar), $A\cup B=A$ jika dan hanya jika $B\subseteq A$. Jadi syarat perlu dan cukupnya adalah $B\subseteq A$.

5. Strategi: pisahkan $x\notin U$ dan $x\in U$. Untuk $x\notin U$, $x$ tidak menjadi anggota kedua ruas, karena kedua ruas termuat di $U$. Untuk $x\in U$, $x\in A^c\iff\neg a$ dan $x\in B^c\iff\neg b$. Jadi syarat keanggotaan ruas kiri adalah $(\neg a)\oplus(\neg b)$. Formula ini benar tepat ketika tepat satu dari $\neg a,\neg b$ benar, yaitu tepat ketika tepat satu dari $a,b$ benar. Dengan demikian $(\neg a)\oplus(\neg b)\iff a\oplus b$. Ruas kanan termuat di $U$ karena $A,B\subseteq U$, sehingga untuk $x\in U$ keanggotaan kedua ruas ekuivalen. Menurut ekstensionalitas, kedua ruas sama.

Bukti alternatif secara aljabar. $A^c\triangle B^c=(U\triangle A)\triangle(U\triangle B)=(U\triangle U)\triangle(A\triangle B)=A\triangle B$. Ruas ini memakai Proposisi 3.2.15(5), asosiativitas dan komutativitas $\triangle$, serta $U\triangle U=\varnothing$.

6. Kontracontoh: $A=\varnothing$, $B=\{1\}$, $C=\{2\}$. Maka $A\setminus B=\varnothing=A\setminus C$, tetapi $B\neq C$.

Ekuivalensi. Strategi: $A\setminus B$ hanya bergantung pada bagian $B$ yang berada di dalam $A$, yaitu $A\setminus B=A\setminus(A\cap B)$. Identitas ini benar karena $x\in A\land\neg(x\in A\land x\in B)\iff x\in A\land x\notin B$.

(⇒) Misalkan $A\setminus B=A\setminus C$. Menurut Latihan 3,

$$A\cap B=A\setminus(A\setminus B)=A\setminus(A\setminus C)=A\cap C.$$

(⇐) Misalkan $A\cap B=A\cap C$. Maka

$$A\setminus B=A\setminus(A\cap B)=A\setminus(A\cap C)=A\setminus C.$$

Pelajarannya: $A\setminus B$ hanya "melihat" bagian $B$ yang berada di dalam $A$.

7. Strategi: analisis kasus pada $a$.

• Jika $a$ benar, maka $a\lor b$ dan $a\lor c$ keduanya benar, sehingga $(a\lor b)\oplus(a\lor c)$ salah. Ruas kanan $(b\oplus c)\land\neg a$ juga salah.
• Jika $a$ salah, ruas kiri menjadi $b\oplus c$ dan ruas kanan juga $b\oplus c$.

Jadi kedua ruas sama. Inklusinya mengikuti dari $(B\triangle C)\setminus A\subseteq B\triangle C\subseteq A\cup(B\triangle C)$.

Kesamaan. Jika $A\neq\varnothing$, ambil $x\in A$. Maka $x\in A\cup(B\triangle C)$, tetapi $x\notin(B\triangle C)\setminus A$. Jadi kesamaan gagal. Jika $A=\varnothing$, kedua ruas sama dengan $B\triangle C$. Kesimpulannya, kesamaan berlaku jika dan hanya jika $A=\varnothing$, untuk $B,C$ apa pun. Hal ini memperkuat kontracontoh pada Proposisi 3.2.18: kegagalan distributivitas terjadi pada setiap $A$ yang tidak kosong, bukan hanya pada contoh khusus.

8. Strategi: tentukan dulu semua subset dari $\varnothing$ dengan ekstensionalitas, lalu periksa hukum-hukumnya dengan perhitungan langsung. Jika $U=\varnothing$, satu-satunya subset adalah $\varnothing$. Sebab jika $A\subseteq\varnothing$ dan $x\in A$, maka $x\in\varnothing$, dan hal itu mustahil. Jadi $A=\varnothing$ menurut ekstensionalitas. Dari sini $\varnothing^c=\varnothing\setminus\varnothing=\varnothing$. Pemeriksaan hukum-hukumnya:

• $A\cup A^c=\varnothing=U$ dan $A\cap A^c=\varnothing$;
• $(A\cup B)^c=\varnothing=A^c\cap B^c$, dan bagian kedua De Morgan serupa.

Semua hukum berlaku karena tidak ada $x\in U$ yang perlu diperiksa. Pernyataan "untuk setiap $x\in U$" benar secara hampa. Untuk $U$ sembarang, $\varnothing\triangle B=B$ menurut Proposisi 3.2.15(2) dan komutativitas. Selain itu $\varnothing^c=U$ dan $U^c=\varnothing$, sehingga $(\varnothing^c)^c=\varnothing$, sesuai dengan Teorema 3.2.8(2).

Soal ini menegaskan bahwa semesta kerja boleh kosong. Larangan dalam teori ini hanya mengenai semesta mutlak, bukan semesta yang kosong.

9. Strategi: "paling sedikit dua" berarti termuat dalam paling sedikit satu irisan berpasangan. Kita hitung:

$$L\cap T=\{2,4,8\},\quad L\cap P=\{4,8\},\quad T\cap P=\{3,4,8\}.$$

Maka:

• Paling sedikit dua: $(L\cap T)\cup(L\cap P)\cup(T\cap P)=\{2,3,4,8\}$.
• Ketiganya: $L\cap T\cap P=\{4,8\}$.
• Tepat dua: $\{2,3,4,8\}\setminus\{4,8\}=\{2,3\}$.
• Paling sedikit satu: $L\cup T\cup P=\{1,2,3,4,5,6,7,8\}=U$.
• Tepat satu: $(L\cup T\cup P)\setminus\{2,3,4,8\}=U\setminus\{2,3,4,8\}=\{1,5,6,7\}$.

Pemeriksaan silang. Jumlah ganjil berarti tepat satu atau ketiganya, yaitu $\{1,5,6,7\}\cup\{4,8\}=\{1,4,5,6,7,8\}=L\triangle T\triangle P$. Hasil ini cocok dengan perhitungan pada subbagian Penerapan: filter pada data.

10. Strategi: pisahkan objek menurut banyaknya keanggotaan di antara $A,B,C$: satu, dua, atau tiga. Misalkan $E$ adalah himpunan objek yang menjadi anggota tepat satu di antara $A,B,C$. Himpunan $E$ ada, misalnya sebagai $\{x\in A\cup B\cup C:\ \text{tepat satu dari }a,b,c\}$ melalui separasi. Menurut Teorema 3.2.16, $x\in A\triangle B\triangle C$ jika dan hanya jika banyaknya keanggotaan $x$ di antara $A,B,C$ adalah satu atau tiga. Jadi

$$A\triangle B\triangle C=E\cup(A\cap B\cap C),$$

dan kedua suku di ruas kanan saling lepas.

(⇐) Jika $A\cap B\cap C=\varnothing$, maka $A\triangle B\triangle C=E\cup\varnothing=E$.

(⇒) Jika $x\in A\cap B\cap C$, maka $x\in A\triangle B\triangle C$ tetapi $x\notin E$. Jadi kedua himpunan berbeda.

Pada contoh tiga himpunan di subbagian Selisih simetris, $A\cap B\cap C=\{3\}$. Itulah sebabnya hasilnya $\{1,3,5\}$, sedangkan $E=\{1,5\}$. Pada data filter, $L\cap T\cap P=\{4,8\}$, yaitu tepat rekaman yang terpilih secara keliru.

Menuju Unit 3.3

Semua operasi pada unit ini melibatkan dua atau tiga himpunan yang disebut satu per satu. Syarat keanggotaannya adalah kombinasi berhingga dari $\lor$, $\land$, dan $\neg$. Karena itu Lema 3.2.12 dapat mereduksi setiap identitas menjadi pemeriksaan sejumlah berhingga pola keanggotaan.

Unit 3.3 mengganti himpunan yang disebut satu per satu dengan keluarga $(A_i)_{i\in I}$ yang nilainya subset $U$. Disjungsi "$x\in A$ atau $x\in B$" diganti oleh "ada $i\in I$ dengan $x\in A_i$". Konjungsi diganti oleh "$x\in U$ dan untuk semua $i\in I$, $x\in A_i$", sesuai konvensi Bab 2. Untuk indeks tak hingga, satu tabel keanggotaan berhingga tidak mencakup seluruh anggota keluarga. Pembuktian yang berlaku bagi indeks sembarang menggunakan aturan kuantifikator dan negasinya; kasus indeks kosong memperjelas mengapa irisan harus diambil relatif $U$.

3.3 Keluarga Himpunan Berindeks

Unit 3.2 membahas gabungan dan irisan dua himpunan. Analisis jarang berhenti di situ. Kita sering bekerja dengan barisan interval, dengan himpunan titik yang memenuhi pertidaksamaan ke-$n$ untuk setiap $n$, atau dengan sekumpulan kriteria penyaringan. Tulisan seperti $A_1\cup A_2\cup A_3\cup\cdots$ tampak wajar, tetapi titik-titik itu tidak mendefinisikan apa pun. Operasi biner hanya dapat diulang berhingga kali, dan tidak ada "langkah terakhir" yang menghasilkan gabungan tak hingga.

Karena itu dibutuhkan dua hal. Pertama, cara yang sah untuk menyebut banyak himpunan menurut labelnya. Kedua, definisi gabungan dan irisan yang langsung memakai kuantifikator, tanpa melalui pengulangan operasi biner. Bab 2 telah menyiapkan kuantifikatornya. Unit ini menyiapkan bahasa keluarganya dan memeriksa jebakan yang menyertainya. Indeks tidak sama dengan anggota. Label berbeda boleh menunjuk himpunan yang sama. Himpunan indeks boleh kosong. Urutan "untuk setiap" dan "ada" tidak boleh ditukar sembarangan.

Sepanjang unit ini $U$ adalah semesta kerja tertentu, yaitu suatu himpunan yang telah ditetapkan, bukan himpunan semua himpunan. Seperti di Bab 2, $\mathbb N=\{0,1,2,\dots\}$. Untuk $k\in\mathbb N$ kita menulis $\mathbb N_{\ge k}=\{n\in\mathbb N: n\ge k\}$. Bilangan, label, dan sifat aritmetika elementer dalam contoh dipinjam sebagai objek dan fakta yang telah dikenal. Sifat yang dipinjam itu mencakup urutan pada $\mathbb N$, maksimum dua bilangan asli, dan prinsip induksi. Kita tidak mengaku telah mengonstruksinya.

Indeks, suku, dan anggota

Definisi 3.3.1 (Keluarga berindeks). Misalkan $U$ dan $I$ himpunan, dan $\psi(i,X)$ formula bahasa teori himpunan yang boleh memuat parameter. Misalkan pula untuk setiap $i\in I$ terdapat tepat satu $X$ dengan $X\subseteq U$ dan $\psi(i,X)$. Secara eksplisit:

$$\forall i\in I\;\exists X\,\Bigl(X\subseteq U\wedge \psi(i,X)\wedge \forall Y\,\bigl[(Y\subseteq U\wedge\psi(i,Y))\to Y=X\bigr]\Bigr). \tag{K}$$

Untuk $i\in I$, himpunan tunggal tersebut dinamai $A_i$. Kita katakan bahwa $\psi$ menetapkan keluarga himpunan bagian $U$ berindeks $I$, dan menuliskannya $(A_i)_{i\in I}$. Istilah yang dipakai:

• $I$ adalah himpunan indeks, dan unsurnya disebut indeks;
• $A_i$ adalah suku keluarga yang berindeks $i$;
• unsur $A_i$ disebut anggota suku itu.

Dua keluarga $(A_i)_{i\in I}$ dan $(B_i)_{i\in I}$ dengan himpunan indeks yang sama dianggap sama sebagai keluarga jika $A_i=B_i$ untuk setiap $i\in I$, meskipun formula penetapnya ditulis berbeda.

Lambang $A_i$ bukan suku formal dalam bahasa $\in$ dan $=$. Ia singkatan yang aman karena (K) menjamin keberadaan dan ketunggalan. Lema berikut memastikan bahwa singkatan itu dapat diuraikan dengan dua cara yang setara.

Lema 3.3.2 (Dua bacaan untuk "$x\in A_i$"). Misalkan (K) berlaku dan $i\in I$. Untuk setiap $x$, kedua pernyataan berikut ekuivalen:

1. $\exists X\,(X\subseteq U\wedge\psi(i,X)\wedge x\in X)$;
2. $\forall X\,\bigl((X\subseteq U\wedge\psi(i,X))\to x\in X\bigr)$.

Kita menulis $x\in A_i$ untuk salah satunya.

Bukti. (1 ⇒ 2) Misalkan $X_0\subseteq U$, $\psi(i,X_0)$, dan $x\in X_0$. Ambil sembarang $X$ dengan $X\subseteq U$ dan $\psi(i,X)$. Menurut bagian ketunggalan (K), $X=X_0$, sehingga $x\in X$.

(2 ⇒ 1) Karena $i\in I$, (K) memberi suatu $X_0$ dengan $X_0\subseteq U$ dan $\psi(i,X_0)$. Pernyataan 2 yang diterapkan pada $X_0$ memberi $x\in X_0$. Jadi $X_0$ menjadi saksi bagi pernyataan 1. ∎

Bacaan pertama bersifat eksistensial dan cocok untuk gabungan. Bacaan kedua bersifat universal dan cocok untuk irisan. Keduanya setara karena $i\in I$. Untuk $i\notin I$, (K) tidak menjamin apa pun. Jika tidak ada $X\subseteq U$ dengan $\psi(i,X)$, pernyataan 1 salah untuk setiap $x$, sedangkan pernyataan 2 benar secara hampa.

Catatan 3.3.3 (Tiga tingkat keanggotaan). Dalam sebuah keluarga terdapat tiga relasi keanggotaan yang berbeda peran:

$$i\in I,\qquad A_i\in\mathcal P(U)\ \ (\text{yaitu } A_i\subseteq U),\qquad x\in A_i\ \ (\text{sehingga } x\in U).$$

Tidak ada syarat yang menghubungkan $I$ dengan $U$. Himpunan indeks boleh saling lepas dengan semesta, misalnya label $I=\{\mathsf a,\mathsf b\}$ dengan $U=\mathbb N$. Keduanya juga boleh beririsan. Pernyataan $i\in A_i$ tidak diwajibkan dan tidak dilarang. Kalau berlaku, itu kebetulan isi keluarga tertentu, bukan sifat struktur keluarga.

Dalam ungkapan "$x\in A_i$", baik $x$ maupun $i$ adalah variabel bebas. Pada gabungan dan irisan di bawah, $i$ diikat oleh kuantifikator. Akibatnya $\bigcup_{i\in I}A_i$ dan $\bigcup_{k\in I}A_k$ menyatakan himpunan yang sama, sejalan dengan penggantian nama variabel terikat di Bab 2.

Proposisi 3.3.4 (Koleksi suku). Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$ yang ditetapkan oleh $\psi$. Terdapat tepat satu himpunan $\mathcal F$ yang memenuhi

$$X\in\mathcal F \iff \bigl(X\subseteq U\wedge \exists i\in I\;\psi(i,X)\bigr),$$

dan untuk setiap $X$ berlaku $X\in\mathcal F\iff \exists i\in I\,(X=A_i)$. Kita menulis $\mathcal F=\{A_i: i\in I\}$.

Bukti. Himpunan kuasa $\mathcal P(U)$ ada menurut 3.1. Separasi pada $\mathcal P(U)$ dengan formula $\exists i\in I\,\psi(i,X)$, berparameter $I$ dan parameter $\psi$, menghasilkan

$$\mathcal F=\{X\in\mathcal P(U):\exists i\in I\;\psi(i,X)\}$$

(bandingkan [R3-1] untuk separasi dan [R3-3] untuk himpunan kuasa). Ketunggalannya mengikuti ekstensionalitas.

Untuk bagian kedua, misalkan $X\subseteq U$ dan $\psi(i,X)$ untuk suatu $i\in I$. Menurut ketunggalan dalam (K), $X$ adalah suku $A_i$. Sebaliknya, $A_i\subseteq U$ dan $\psi(i,A_i)$ berlaku menurut definisi $A_i$. ∎

Jika keluarga sudah diberikan sebagai himpunan, keberadaannya tidak perlu dianggap kembali. Proposisi di atas hanya diperlukan ketika keluarga diberikan melalui aturan $\psi$.

Contoh 3.3.5 (Repetisi indeks). Ambil $U=\{1,2,3\}$ dan $I=\{1,2,3,4\}$, dengan

$$A_1=\{1,2\},\quad A_2=\{2,3\},\quad A_3=\{1,2\},\quad A_4=\{1,2\}.$$

Formula penetapnya dapat ditulis sebagai disjungsi $(i=1\wedge X=\{1,2\})\vee(i=2\wedge X=\{2,3\})\vee(i=3\wedge X=\{1,2\})\vee(i=4\wedge X=\{1,2\})$. Untuk setiap $i\in I$ tepat satu disjung berlaku, sehingga (K) terpenuhi.

Keluarga ini punya empat indeks, tetapi koleksi sukunya hanya

$$\mathcal F=\{A_i:i\in I\}=\bigl\{\{1,2\},\{2,3\}\bigr\},$$

yang beranggota dua himpunan. Tiga indeks berbeda, yaitu 1, 3, dan 4, menunjuk suku yang sama. Hal ini sah, karena (K) menuntut ketunggalan suku untuk tiap indeks, bukan ketunggalan indeks untuk tiap suku.

Contoh ini juga memperlihatkan perbedaan tingkat keanggotaan. Kita punya $3\in I$ tetapi $3\notin A_3$. Kita punya $1\in A_1$ dan $A_1\in\mathcal F$, tetapi $1\notin\mathcal F$. Alasannya, untuk label yang kita pinjam, $1\ne\{1,2\}$ dan $1\ne\{2,3\}$. Jadi relasi $\in$ tidak transitif secara umum.

Keluarga $(B_i)_{i\in I}$ dengan $B_1=\{2,3\}$ dan $B_2=B_3=B_4=\{1,2\}$ memiliki koleksi suku yang sama, $\{B_i:i\in I\}=\mathcal F$. Namun keluarga ini berbeda dari $(A_i)_{i\in I}$ karena $A_1\ne B_1$. Keluarga menyimpan informasi tentang suku mana yang terletak pada indeks mana. Koleksi suku tidak menyimpan informasi itu.

Catatan 3.3.6 (Keluarga turunan, pembatasan, dan kaitan dengan Bab 5).

(a) Keluarga turunan. Misalkan $(A_i)_{i\in I}$ ditetapkan oleh $\psi$ dan $B\subseteq U$. Didefinisikan

$$\chi(i,Y)\;:\equiv\;\exists X\,\bigl(X\subseteq U\wedge\psi(i,X)\wedge Y=B\cap X\bigr).$$

Untuk $i\in I$, himpunan $Y=B\cap A_i$ memenuhi $\chi$ dan $Y\subseteq U$. Misalkan $Y$ dan $Y'$ sama-sama memenuhi $\chi(i,\cdot)$ dengan saksi $X$ dan $X'$. Menurut (K), $X=X'$, sehingga $Y=B\cap X=Y'$. Jadi $\chi$ menetapkan keluarga $(B\cap A_i)_{i\in I}$.

Dengan cara yang sama diperoleh keluarga $(B\cup A_i)_{i\in I}$ dan $(U\setminus A_i)_{i\in I}$. Ketiganya adalah keluarga himpunan bagian $U$ karena $B\cup A_i\subseteq U$ dan $U\setminus A_i\subseteq U$. Selanjutnya keluarga turunan semacam ini dipakai tanpa mengulang argumennya.

(b) Pembatasan. Jika $J\subseteq I$, formula $\psi$ yang sama memenuhi (K) dengan $J$ menggantikan $I$, sebab "untuk setiap $i\in I$" mencakup setiap $i\in J$. Hasilnya adalah keluarga $(A_j)_{j\in J}$, yaitu pembatasan keluarga semula pada $J$.

(c) Kaitan dengan Bab 5. Pembaca yang telah mengenal fungsi akan melihat penetapan $i\mapsto A_i$ sebagai fungsi dari $I$ ke $\mathcal P(U)$, dan $\mathcal F$ sebagai daerah hasilnya. Pandangan itu benar, tetapi sengaja belum dipakai di sini. Yang kita perlukan hanyalah (K). Domain, kodomain, daerah hasil, serta peta maju dan peta balik dibahas di Bab 5. Apabila suatu keluarga kelak telah tersedia sebagai himpunan, misalnya sebagai fungsi, formula penetapnya cukup merujuk himpunan itu sebagai parameter. Tidak ada aksioma keberadaan baru yang dibutuhkan.

Gabungan dan irisan keluarga

Definisi 3.3.7. Untuk keluarga $(A_i)_{i\in I}$ himpunan bagian $U$ didefinisikan

$$\bigcup_{i\in I}A_i=\{x\in U:\exists i\in I\;(x\in A_i)\},\qquad \bigcap^{U}_{i\in I}A_i=\{x\in U:\forall i\in I\;(x\in A_i)\}.$$

Himpunan pertama disebut gabungan keluarga. Himpunan kedua disebut irisan keluarga relatif $U$. Definisi ini sejalan dengan konvensi Bab 2 dan dengan penyajian keluarga berindeks dalam [R3-2]. Buku ini memakai irisan relatif $U$, bukan relatif "semesta semua objek".

Keberadaan dan ketunggalan. Ungkapan $x\in A_i$ di atas adalah singkatan dari Lema 3.3.2. Pada gabungan dipakai bacaan eksistensial, dan pada irisan dipakai bacaan universal. Dengan demikian kedua ruas kanan berbentuk separasi pada $U$. Formula pemisahnya berpeubah $x$ dan berparameter $I$, $U$, serta parameter $\psi$. Variabel yang menamai himpunan baru dipilih tidak bebas dalam formula itu. Variabel terikat $i$ dan $X$ dipilih agar tidak bentrok dengan variabel $\psi$. Separasi menjamin keberadaan kedua himpunan, dan ekstensionalitas menjamin ketunggalannya. Kita tidak memerlukan aksioma lain dan tidak memerlukan komprehensi tak terbatas.

Karena setiap $A_i\subseteq U$, syarat "$x\in U$" pada gabungan tidak menambah apa pun: jika $x\in A_i$ untuk suatu $i$, maka sudah tentu $x\in U$. Pada irisan, syarat itu bekerja tepat ketika $I=\varnothing$, seperti terlihat berikut ini.

Proposisi 3.3.8 (Indeks kosong dan ketakbergantungan pada $U$). Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$.

1. Jika $I=\varnothing$, maka $\bigcup_{i\in I}A_i=\varnothing$ dan $\bigcap^{U}_{i\in I}A_i=U$.
2. Misalkan $U\subseteq V$. Dengan formula $X\subseteq U\wedge\psi(i,X)$, keluarga yang sama adalah keluarga himpunan bagian $V$. Gabungannya, dihitung relatif $U$ maupun relatif $V$, menghasilkan himpunan yang sama.
3. Jika $I\neq\varnothing$, maka untuk setiap $x$ berlaku $x\in\bigcap^{U}_{i\in I}A_i\iff\forall i\in I\,(x\in A_i)$. Akibatnya, dalam situasi butir 2, $\bigcap^{U}_{i\in I}A_i=\bigcap^{V}_{i\in I}A_i$.
4. Jika $I=\varnothing$ dan $U\subsetneq V$, maka $\bigcap^{U}_{i\in I}A_i\neq\bigcap^{V}_{i\in I}A_i$.

Bukti. (1) Untuk $I=\varnothing$, pernyataan $\exists i\in I\,(x\in A_i)$, yaitu $\exists i\,(i\in\varnothing\wedge x\in A_i)$, salah untuk setiap $x$. Jadi gabungannya tidak beranggota, dan menurut ketunggalan himpunan kosong (3.1) gabungan itu sama dengan $\varnothing$. Pernyataan $\forall i\in I\,(x\in A_i)$, yaitu $\forall i\,(i\in\varnothing\to x\in A_i)$, benar secara hampa untuk setiap $x$. Jadi irisannya beranggota tepat semua $x\in U$, dan menurut ekstensionalitas irisan itu sama dengan $U$.

(2) Formula $X\subseteq U\wedge\psi(i,X)$ memenuhi (K) dengan $V$ menggantikan $U$. Penyebabnya: setiap $X$ yang memenuhinya juga memenuhi $X\subseteq V$, dan ketunggalannya diwarisi dari ketunggalan relatif $U$. Suku-suku yang dihasilkan sama. Untuk sembarang $x$, jika $\exists i\in I\,(x\in A_i)$, maka $x\in U$ dan juga $x\in V$. Jadi syarat "$x\in U\wedge\exists i$" dan "$x\in V\wedge\exists i$" ekuivalen, dan ekstensionalitas memberi kesamaan kedua gabungan.

Formula yang dimodifikasi memang diperlukan. Sebagai contoh, ambil $I=\{0\}$, $U=\{1\}$, $V=\{1,2\}$, dan $\psi(i,X):\equiv X=\{1\}\vee X=\{2\}$. Relatif $U$, untuk $i=0$ hanya $X=\{1\}$ yang memenuhi, sehingga sukunya tunggal. Relatif $V$, baik $\{1\}$ maupun $\{2\}$ memenuhi, sehingga ketunggalan gagal.

(3) Arah (⇒) langsung dari definisi. Untuk arah (⇐), karena $I\ne\varnothing$, ambil $i_0\in I$. Dari $x\in A_{i_0}\subseteq U$ diperoleh $x\in U$, sehingga $x$ memenuhi kedua syarat dalam definisi irisan. Karena ruas kanan tidak menyebut $U$, alasan yang sama berlaku relatif $V$, dan ekstensionalitas memberi kesamaan.

(4) Menurut butir 1, kedua irisan itu adalah $U$ dan $V$. Keduanya berbeda karena $U\subsetneq V$. ∎

Jadi menulis $\bigcap_{i\in I}A_i$ tanpa menyebut semesta aman tepat ketika $I\neq\varnothing$. Bila himpunan indeks mungkin kosong, $U$ harus disebut. Gabungan tidak pernah memerlukan penyebutan itu.

Proposisi 3.3.9 (Kasus dua indeks). Misalkan $I=\{a,b\}$, yang diperoleh dari aksioma pasangan, dan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$. Maka

$$\bigcup_{i\in I}A_i=A_a\cup A_b,\qquad \bigcap^{U}_{i\in I}A_i=A_a\cap A_b.$$

Kesamaan ini berlaku juga ketika $a=b$. Dalam hal itu kedua ruas sama dengan $A_a$.

Bukti. Menurut aksioma pasangan, $i\in\{a,b\}\iff(i=a\vee i=b)$. Oleh karena itu

$$\exists i\in I\,(x\in A_i)\iff (x\in A_a\vee x\in A_b) \qquad\text{dan}\qquad \forall i\in I\,(x\in A_i)\iff (x\in A_a\wedge x\in A_b).$$

Ruas kiri yang pertama setara dengan $x\in A_a\cup A_b$. Untuk irisan, syarat "$x\in U$" berlebih karena $A_a\subseteq U$, sehingga ruas kiri yang kedua setara dengan $x\in A_a\cap A_b$. Ekstensionalitas menutup bukti. Jika $a=b$, maka $A_a\cup A_a=A_a\cap A_a=A_a$. ∎

Untuk $p\le q$ dalam $\mathbb N_{\ge1}$, tulis $J_{p,q}=\{i\in\mathbb N:p\le i\le q\}$. Misalkan $(A_i)_{i\in J_{1,r}}$ keluarga himpunan bagian $U$ dengan $r\ge1$, dan ambil $1\le p\le q\le r$. Suatu ekspresi gabungan atas $A_p,\ldots,A_q$ dibentuk dari suku-suku itu menurut urutannya, dengan operasi $\cup$ biner dan suatu pengurungan. Setiap ekspresi tersebut sama dengan $\bigcup_{i\in J_{p,q}}A_i$.

Bukti. Kita memakai induksi kuat atas $q-p$, sebagai bagian dari perangkat aritmetika yang dipinjam; prinsip induksi dikembangkan pada Bab 7. Jika $q=p$, satu-satunya ekspresi adalah $A_p$, dan $\bigcup_{i\in\{p\}}A_i=A_p$ langsung dari syarat keanggotaan. Jika $q>p$, operasi terluar membagi ekspresi menjadi $E_1\cup E_2$, dengan $E_1$ memakai $A_p,\ldots,A_s$ dan $E_2$ memakai $A_{s+1},\ldots,A_q$ untuk suatu $p\le s<q$. Kedua rentang lebih pendek, sehingga hipotesis induksi mengidentifikasi $E_1$ dan $E_2$ dengan gabungan keluarga pada rentang masing-masing. Untuk setiap $x$,

$$\begin{aligned} x\in E_1\cup E_2 &\iff (\exists i\in J_{p,s}\;x\in A_i)\lor(\exists i\in J_{s+1,q}\;x\in A_i)\\ &\iff \exists i\in J_{p,q}\;x\in A_i. \end{aligned}$$

Langkah terakhir memakai pemisahan $J_{p,q}=J_{p,s}\cup J_{s+1,q}$. Ekstensionalitas membuktikan klaim.

Untuk ekspresi irisan, basisnya juga $A_p=\bigcap^U_{i\in\{p\}}A_i$, karena $A_p\subseteq U$. Pada langkah induksi, operasi terluarnya $E_1\cap E_2$. Hipotesis induksi memberi, untuk setiap $x$,

$$\begin{aligned} x\in E_1\cap E_2 &\iff x\in U\ \land\ (\forall i\in J_{p,s}\;x\in A_i)\ \land\ (\forall i\in J_{s+1,q}\;x\in A_i)\\ &\iff x\in U\ \land\ \forall i\in J_{p,q}\;x\in A_i. \end{aligned}$$

Ekstensionalitas kembali memberi hasil. Semua rentang pada pembuktian ini tak kosong. Kedua induksi hanya menjangkau himpunan indeks berhingga; keduanya tidak membuktikan klaim tentang gabungan atau irisan atas seluruh $\mathbb N_{\ge1}$. Karena itu Definisi 3.3.7 dirumuskan langsung dengan kuantifikator. $\square$

Proposisi 3.3.10 (Gabungan dan irisan hanya bergantung pada koleksi suku). Misalkan $\mathcal F=\{A_i:i\in I\}$. Maka

$$\bigcup_{i\in I}A_i=\bigcup\mathcal F,\qquad \bigcap^{U}_{i\in I}A_i=\{x\in U:\forall X\in\mathcal F\;(x\in X)\}.$$

Akibatnya, dua keluarga himpunan bagian $U$ dengan koleksi suku yang sama memiliki gabungan yang sama dan irisan relatif $U$ yang sama, walaupun himpunan indeksnya berbeda.

Bukti. Himpunan $\bigcup\mathcal F$ ada menurut aksioma gabungan (3.1; bandingkan [R3-1]). Menurut Proposisi 3.3.4,

$$x\in\textstyle\bigcup\mathcal F\iff\exists X\,(X\in\mathcal F\wedge x\in X)\iff \exists X\,\exists i\in I\,(X=A_i\wedge x\in X)\iff\exists i\in I\,(x\in A_i).$$

Langkah terakhir menukar dua kuantifikator eksistensial yang bertetangga, lalu menghapus $X$ dengan mensubstitusi $X=A_i$. Ruas paling kanan setara dengan keanggotaan pada $\bigcup_{i\in I}A_i$, karena syarat $x\in U$ berlebih.

Untuk irisan, $\forall X\,(X\in\mathcal F\to x\in X)$ setara dengan $\forall X\,\forall i\in I\,(X=A_i\to x\in X)$, yang setara dengan $\forall i\in I\,(x\in A_i)$. Ekstensionalitas menutup bukti. ∎

Pada Contoh 3.3.5, empat indeks memberi gabungan $\{1,2\}\cup\{2,3\}=\{1,2,3\}$ dan irisan $\{1,2\}\cap\{2,3\}=\{2\}$. Repetisi $A_1=A_3=A_4$ tidak mengubah hasil itu.

Proposisi 3.3.11 (Batas atas dan batas bawah). Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$.

1. Untuk setiap $k\in I$: $A_k\subseteq\bigcup_{i\in I}A_i$ dan $\bigcap^{U}_{i\in I}A_i\subseteq A_k$.
2. Jika $C$ himpunan dan $A_i\subseteq C$ untuk setiap $i\in I$, maka $\bigcup_{i\in I}A_i\subseteq C$.
3. Jika $C\subseteq U$ dan $C\subseteq A_i$ untuk setiap $i\in I$, maka $C\subseteq\bigcap^{U}_{i\in I}A_i$.

Bukti. (1) Jika $x\in A_k$, maka $k$ adalah saksi bagi $\exists i\in I\,(x\in A_i)$. Jika $x$ anggota irisan, maka sifat "untuk setiap $i$" khususnya berlaku untuk $i=k$.

(2) Misalkan $x\in\bigcup_{i\in I}A_i$. Ada $k\in I$ dengan $x\in A_k$, dan $A_k\subseteq C$ memberi $x\in C$.

(3) Misalkan $x\in C$. Maka $x\in U$ karena $C\subseteq U$. Untuk sembarang $i\in I$ berlaku $x\in A_i$ karena $C\subseteq A_i$. Jadi $x$ anggota irisan. ∎

Butir 1 dan 2 mengatakan bahwa gabungan adalah himpunan terkecil yang memuat semua suku. Butir 1 dan 3 mengatakan bahwa irisan relatif $U$ adalah himpunan bagian $U$ terbesar yang termuat dalam semua suku.

Hipotesis $C\subseteq U$ pada butir 3 tidak dapat dihapus bila $I=\varnothing$. Misalnya, ambil $U=\{1\}$, $C=\{2\}$, dan $I=\varnothing$. Syarat "$C\subseteq A_i$ untuk setiap $i$" benar secara hampa, tetapi $C\not\subseteq U=\bigcap^{U}_{i\in\varnothing}A_i$. Bila $I\ne\varnothing$, hipotesis itu otomatis terpenuhi karena $C\subseteq A_{i_0}\subseteq U$.

Contoh 3.3.12 (Kelipatan). Ambil $U=\{1,2,\dots,10\}$ dan $I=\{2,3,5\}$. Untuk $i\in I$, definisikan

$$A_i=\{x\in U:\exists k\in\mathbb N\;(x=ik)\},$$

yaitu kelipatan $i$ di dalam $U$. Formula penetapnya adalah $\psi(i,X):\equiv X=\{x\in U:\exists k\in\mathbb N\,(x=ik)\}$. Untuk tiap $i$, separasi pada $U$ memberi tepat satu himpunan seperti itu. Dengan menghitung langsung:

$$A_2=\{2,4,6,8,10\},\qquad A_3=\{3,6,9\},\qquad A_5=\{5,10\}.$$

Gabungan. Sebuah $x\in U$ masuk gabungan jika dan hanya jika $x$ termuat dalam sedikitnya satu suku. Bilangan $1$ dan $7$ tidak termuat di suku mana pun, sedangkan setiap unsur $U$ lainnya termuat di salah satunya. Jadi

$$\bigcup_{i\in I}A_i=\{2,3,4,5,6,8,9,10\}.$$

Irisan. Sudah $A_3\cap A_5=\varnothing$, karena tidak ada unsur yang sekaligus termuat dalam $\{3,6,9\}$ dan $\{5,10\}$. Menurut Proposisi 3.3.11(1), irisan seluruh keluarga termuat dalam $A_3$ dan juga dalam $A_5$, sehingga termuat dalam $A_3\cap A_5=\varnothing$. Jadi

$$\bigcap^{U}_{i\in I}A_i=\varnothing.$$

Untuk pembatasan pada beberapa $J\subseteq I$ diperoleh tabel berikut. Hasil-hasil ini dipakai lagi di Contoh 3.3.16 dan 3.3.18.

Baris $J=\{2\}$ memakai Proposisi 3.3.9 dengan $a=b$. Baris $J=\varnothing$ memakai Proposisi 3.3.8(1).

Contoh 3.3.13 (Model penyaringan data). Contoh berikut adalah model himpunan bagi penyaringan data, bukan laporan tentang suatu implementasi. Misalkan semesta kerja terdiri atas enam rekaman, $U=\{r_1,\dots,r_6\}$, dengan atribut berikut:

Setiap kriteria penyaringan dimodelkan sebagai himpunan rekaman yang lolos. Ambil $I=\{1,2,3\}$, dengan

• $F_1=\{r\in U: r\text{ aktif}\}=\{r_1,r_2,r_4,r_6\}$,
• $F_2=\{r\in U: r\text{ di wilayah Barat}\}=\{r_1,r_3,r_4\}$,
• $F_3=\{r\in U: \text{nilai } r\ge 50\}=\{r_1,r_3,r_5,r_6\}$.

"Lolos semua kriteria" adalah irisan, dan "lolos sedikitnya satu kriteria" adalah gabungan:

$$\bigcap^{U}_{i\in I}F_i=\{r_1\},\qquad \bigcup_{i\in I}F_i=U.$$

Irisan dihitung bertahap: $F_1\cap F_2=\{r_1,r_4\}$, lalu $\{r_1,r_4\}\cap F_3=\{r_1\}$. Untuk gabungan, $F_1\cup F_2=\{r_1,r_2,r_3,r_4,r_6\}$, dan satu-satunya rekaman yang tersisa, $r_5$, termuat dalam $F_3$.

Jika hanya kriteria $J=\{1,3\}$ yang diaktifkan, maka $\bigcap^{U}_{j\in J}F_j=F_1\cap F_3=\{r_1,r_6\}$. Hasil ini lebih besar daripada $\{r_1\}$. Menambah kriteria hanya dapat mempersempit hasil (lihat Teorema 3.3.17).

Jika tidak ada kriteria sama sekali ($J=\varnothing$), model memberi $\bigcap^{U}_{j\in\varnothing}F_j=U$, yaitu semua rekaman lolos. Ini sesuai dengan intuisi bahwa daftar syarat yang kosong tidak menolak apa pun. Sebaliknya $\bigcup_{j\in\varnothing}F_j=\varnothing$, karena tidak ada rekaman yang lolos "sedikitnya satu" dari nol kriteria. Konvensi irisan relatif $U$ memberi hasil yang sesuai dengan intuisi penyaringan pada batas indeks kosong.

Distribusi satu himpunan atas keluarga

Di Unit 3.2 irisan didistribusikan atas gabungan dua himpunan, dan sebaliknya. Kini satu himpunan $B$ didistribusikan atas keluarga sembarang. Keluarga $(B\cap A_i)_{i\in I}$ dan $(B\cup A_i)_{i\in I}$ sah menurut Catatan 3.3.6(a).

Teorema 3.3.14 (Hukum distributif untuk keluarga). Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$ dan $B\subseteq U$. Untuk setiap himpunan indeks $I$, termasuk $I=\varnothing$, berlaku

$$\text{(a)}\quad B\cap\bigcup_{i\in I}A_i=\bigcup_{i\in I}(B\cap A_i),\qquad \text{(b)}\quad B\cup\bigcap^{U}_{i\in I}A_i=\bigcap^{U}_{i\in I}(B\cup A_i).$$

Bukti. (a) Arah $\subseteq$. Misalkan $x\in B$ dan $x\in\bigcup_{i\in I}A_i$. Ada $k\in I$ dengan $x\in A_k$. Maka $x\in B\cap A_k$, dan $k$ menjadi saksi bahwa $x\in\bigcup_{i\in I}(B\cap A_i)$.

Arah $\supseteq$. Misalkan ada $k\in I$ dengan $x\in B\cap A_k$. Maka $x\in B$, dan $k$ menjadi saksi bahwa $x\in\bigcup_{i\in I}A_i$.

Dalam kedua arah, saksi $k$ dipilih setelah $x$ diberikan dan boleh bergantung pada $x$. Kita tidak pernah mengklaim satu indeks yang berlaku untuk semua $x$.

(b) Arah $\subseteq$. Misalkan $x\in B\cup\bigcap^{U}_{i\in I}A_i$. Dalam kedua kasus $x\in U$, karena $B\subseteq U$ dan irisan relatif $U$ termuat dalam $U$. Ambil sembarang $i\in I$. Jika $x\in B$, maka $x\in B\cup A_i$. Jika $x$ anggota irisan, maka $x\in A_i\subseteq B\cup A_i$. Jadi $x\in\bigcap^{U}_{i\in I}(B\cup A_i)$.

Arah $\supseteq$. Misalkan $x\in U$ dan $x\in B\cup A_i$ untuk setiap $i\in I$. Jika $x\in B$, selesai. Jika $x\notin B$, ambil sembarang $i\in I$. Dari $x\in B\cup A_i$ dan $x\notin B$ diperoleh $x\in A_i$. Karena $i$ sembarang dan $x\in U$, maka $x\in\bigcap^{U}_{i\in I}A_i$.

Pemisahan kasus "$x\in B$ atau $x\notin B$" dilakukan sebelum $i$ diambil, sehingga satu keputusan berlaku seragam untuk semua indeks.

Batas indeks kosong. Argumen di atas tidak memakai satu pun indeks tertentu, jadi berlaku juga untuk $I=\varnothing$. Pemeriksaan langsung menegaskannya. Pada (a), ruas kiri adalah $B\cap\varnothing=\varnothing$, dan ruas kanan adalah gabungan keluarga kosong, yaitu $\varnothing$. Pada (b), ruas kiri adalah $B\cup U=U$ karena $B\subseteq U$, dan ruas kanan adalah irisan keluarga kosong relatif $U$, yaitu $U$. ∎

Dua hukum "pasangan" lainnya memerlukan $I\ne\varnothing$. Keduanya adalah $B$ yang digabungkan dengan gabungan, dan $B$ yang diirisi dengan irisan. Proposisi berikut menunjukkan tepat di mana keperluan itu muncul.

Proposisi 3.3.15. Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$ dan $B\subseteq U$.

1. Jika $I\ne\varnothing$, maka $B\cup\bigcup_{i\in I}A_i=\bigcup_{i\in I}(B\cup A_i)$.
2. Jika $I\ne\varnothing$, maka $B\cap\bigcap^{U}_{i\in I}A_i=\bigcap^{U}_{i\in I}(B\cap A_i)$.
3. Jika $I=\varnothing$, kesamaan pada butir 1 berlaku jika dan hanya jika $B=\varnothing$, dan kesamaan pada butir 2 berlaku jika dan hanya jika $B=U$.

Bukti. (1) Arah $\supseteq$ berlaku untuk sembarang $I$. Jika $x\in B\cup A_k$ untuk suatu $k\in I$, maka $x\in B$ atau $x\in A_k\subseteq\bigcup_{i\in I}A_i$.

Arah $\subseteq$: jika $x\in A_k$ untuk suatu $k$, maka $x\in B\cup A_k$. Jika $x\in B$, kita memerlukan suatu indeks sebagai saksi. Karena $I\ne\varnothing$, ambil $i_0\in I$, sehingga $x\in B\cup A_{i_0}$. Di sinilah hipotesis $I\ne\varnothing$ dipakai.

(2) Arah $\subseteq$ berlaku untuk sembarang $I$. Jika $x\in B$ dan $x$ anggota irisan, maka $x\in U$ dan $x\in B\cap A_i$ untuk setiap $i$.

Arah $\supseteq$: misalkan $x\in U$ dan $x\in B\cap A_i$ untuk setiap $i\in I$. Maka $x\in A_i$ untuk setiap $i$, sehingga $x\in\bigcap^{U}_{i\in I}A_i$. Untuk mendapatkan $x\in B$, kita memerlukan satu indeks. Karena $I\ne\varnothing$, ambil $i_0\in I$. Dari $x\in B\cap A_{i_0}$ diperoleh $x\in B$.

(3) Untuk $I=\varnothing$, butir 1 menjadi $B\cup\varnothing=\varnothing$, yaitu $B=\varnothing$. Butir 2 menjadi $B\cap U=U$. Karena $B\subseteq U$, ruas kiri sama dengan $B$, sehingga kesamaan itu berarti $B=U$. ∎

Contoh 3.3.16. Lanjutkan Contoh 3.3.12 dengan $B=\{1,2,3,4,5\}$.

Teorema 3.3.14(a) dengan $I=\{2,3,5\}$. Ruas kiri: $B\cap\{2,3,4,5,6,8,9,10\}=\{2,3,4,5\}$. Ruas kanan: $B\cap A_2=\{2,4\}$, $B\cap A_3=\{3\}$, dan $B\cap A_5=\{5\}$, yang gabungannya $\{2,3,4,5\}$. Kedua ruas sama.

Teorema 3.3.14(b) dengan $I=\{2,3,5\}$. Ruas kiri: $B\cup\varnothing=B$. Ruas kanan dihitung dari

$$B\cup A_2=\{1,2,3,4,5,6,8,10\},\quad B\cup A_3=\{1,2,3,4,5,6,9\},\quad B\cup A_5=\{1,2,3,4,5,10\}.$$

Unsur $1,\dots,5$ termuat dalam ketiganya. Unsur $6$ tidak termuat dalam $B\cup A_5$. Unsur $8$ dan $10$ tidak termuat dalam $B\cup A_3$. Unsur $9$ tidak termuat dalam $B\cup A_2$. Unsur $7$ tidak termuat di mana pun. Jadi irisannya adalah $B$, sesuai dengan ruas kiri.

Proposisi 3.3.15 dengan $J=\varnothing$. Pada butir 1, ruas kiri adalah $B\cup\varnothing=B$, sedangkan ruas kanan adalah $\varnothing$. Pada butir 2, ruas kiri adalah $B\cap U=B$, sedangkan ruas kanan adalah $U=\{1,\dots,10\}$. Kedua hukum gagal karena $\varnothing\ne B\ne U$, tepat seperti diramalkan butir 3.

Monotoni terhadap himpunan indeks

Teorema 3.3.17 (Monotoni indeks). Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$ dan $J\subseteq I$, dengan $(A_j)_{j\in J}$ pembatasannya (Catatan 3.3.6(b)). Maka

$$\bigcup_{j\in J}A_j\subseteq\bigcup_{i\in I}A_i \qquad\text{dan}\qquad \bigcap^{U}_{i\in I}A_i\subseteq\bigcap^{U}_{j\in J}A_j.$$

Gabungan mengikuti arah inklusi indeks. Irisan membalik arah itu.

Bukti. Misalkan $x\in\bigcup_{j\in J}A_j$. Ada $j\in J$ dengan $x\in A_j$. Karena $J\subseteq I$, maka $j\in I$, dan indeks yang sama menjadi saksi bahwa $x\in\bigcup_{i\in I}A_i$.

Misalkan $x\in\bigcap^{U}_{i\in I}A_i$, yaitu $x\in U$ dan $x\in A_i$ untuk setiap $i\in I$. Ambil sembarang $j\in J$. Karena $j\in I$, maka $x\in A_j$. Jadi $x\in\bigcap^{U}_{j\in J}A_j$.

Untuk $J=\varnothing$, teorema ini menjadi $\varnothing\subseteq\bigcup_{i\in I}A_i$ dan $\bigcap^{U}_{i\in I}A_i\subseteq U$, yang keduanya benar. Bukti di atas mencakup kasus ini tanpa perlakuan khusus. ∎

Alasan pembalikan dapat dibaca dari kuantifikatornya. Memperbesar himpunan indeks berarti menambah calon saksi bagi "ada $i$", sehingga gabungan membesar. Pada saat yang sama, langkah itu menambah syarat bagi "untuk setiap $i$", sehingga irisan mengecil. Kesalahan yang sering terjadi adalah menyimpulkan $\bigcap^{U}_{j\in J}A_j\subseteq\bigcap^{U}_{i\in I}A_i$ dari $J\subseteq I$ karena mengira arah inklusinya "sejajar".

Contoh 3.3.18. Dari tabel Contoh 3.3.12, ambil rantai $\varnothing\subseteq\{2\}\subseteq\{2,3\}\subseteq\{2,3,5\}$. Diperoleh:

• gabungan naik: $\varnothing\subseteq\{2,4,6,8,10\}\subseteq\{2,3,4,6,8,9,10\}\subseteq\{2,3,4,5,6,8,9,10\}$;
• irisan turun: $U\supseteq\{2,4,6,8,10\}\supseteq\{6\}\supseteq\varnothing$.

Semua inklusi di sini sejati. Jadi teorema tidak dapat dipertajam menjadi kesamaan.

Sebaliknya, inklusi indeks yang sejati tidak menjamin inklusi hasil yang sejati. Ambil keluarga Contoh 3.3.5 dengan $J=\{1,2\}\subsetneq I=\{1,2,3,4\}$. Berlaku $\bigcup_{j\in J}A_j=\{1,2,3\}=\bigcup_{i\in I}A_i$ dan $\bigcap^{U}_{j\in J}A_j=\{2\}=\bigcap^{U}_{i\in I}A_i$, sebab indeks $3$ dan $4$ hanya mengulang suku $A_1$ (Proposisi 3.3.10).

Keluarga naik dan keluarga turun

Banyak keluarga dalam analisis berindeks $\mathbb N_{\ge1}$ dan tersusun menurut inklusi. Susunan itu menyederhanakan separuh perhitungan. Namun separuh lainnya justru memperlihatkan dengan jelas perbedaan antara kasus berhingga dan kasus tak hingga.

Definisi 3.3.19. Keluarga $(A_n)_{n\in\mathbb N_{\ge1}}$ himpunan bagian $U$ disebut naik jika $A_n\subseteq A_{n+1}$ untuk setiap $n\in\mathbb N_{\ge1}$. Keluarga itu disebut turun jika $A_{n+1}\subseteq A_n$ untuk setiap $n\in\mathbb N_{\ge1}$.

Definisi hanya membandingkan indeks yang bertetangga. Lema berikut memperluasnya ke sembarang dua indeks.

Lema 3.3.20. Misalkan $(A_n)_{n\in\mathbb N_{\ge1}}$ keluarga himpunan bagian $U$ dan $1\le m\le n$.

1. Jika keluarga itu naik, maka $A_m\subseteq A_n$.
2. Jika keluarga itu turun, maka $A_n\subseteq A_m$.

Bukti. (1) Tetapkan $m$. Kita buktikan $A_m\subseteq A_n$ untuk setiap $n\ge m$ dengan induksi atas $n$, mulai dari $n=m$ (bentuk induksi yang dimulai dari $m$, yang termasuk dalam perangkat aritmetika yang dipinjam). Untuk $n=m$, inklusi $A_m\subseteq A_m$ berlaku karena setiap himpunan termuat dalam dirinya. Misalkan $A_m\subseteq A_n$ untuk suatu $n\ge m$. Karena keluarga naik, $A_n\subseteq A_{n+1}$. Ketransitifan inklusi memberi $A_m\subseteq A_{n+1}$.

(2) Sama, dengan arah inklusi dibalik: $A_m\supseteq A_n\supseteq A_{n+1}$. ∎

Proposisi 3.3.21. Misalkan $(A_n)_{n\in\mathbb N_{\ge1}}$ keluarga himpunan bagian $U$ dan $k\in\mathbb N_{\ge1}$. Tulis $J_k=\{n\in\mathbb N:1\le n\le k\}$.

1. Jika keluarga itu naik, maka

$$\bigcup_{n\in J_k}A_n=A_k,\qquad \bigcap^{U}_{n\in\mathbb N_{\ge1}}A_n=A_1,\qquad \bigcup_{n\in\mathbb N_{\ge1}}A_n=\bigcup_{n\in\mathbb N_{\ge k}}A_n.$$

2. Jika keluarga itu turun, maka

$$\bigcap^{U}_{n\in J_k}A_n=A_k,\qquad \bigcup_{n\in\mathbb N_{\ge1}}A_n=A_1,\qquad \bigcap^{U}_{n\in\mathbb N_{\ge1}}A_n=\bigcap^{U}_{n\in\mathbb N_{\ge k}}A_n.$$

Ruas-ruas di atas memakai pembatasan pada $J_k$ dan $\mathbb N_{\ge k}$. Keduanya himpunan bagian $\mathbb N_{\ge1}$ karena $k\ge1$.

Bukti. (1) Gabungan berhingga. Karena $k\in J_k$, Proposisi 3.3.11(1) memberi $A_k\subseteq\bigcup_{n\in J_k}A_n$. Sebaliknya, misalkan $x\in A_m$ untuk suatu $m\in J_k$. Karena $m\le k$, Lema 3.3.20(1) memberi $A_m\subseteq A_k$, sehingga $x\in A_k$.

Irisan tak hingga. Proposisi 3.3.11(1) dengan indeks $1$ memberi $\bigcap^{U}_{n\in\mathbb N_{\ge1}}A_n\subseteq A_1$. Sebaliknya, misalkan $x\in A_1$. Maka $x\in U$. Untuk sembarang $n\ge1$, Lema 3.3.20(1) memberi $A_1\subseteq A_n$, sehingga $x\in A_n$. Jadi $x$ anggota irisan.

Ekor gabungan. Karena $\mathbb N_{\ge k}\subseteq\mathbb N_{\ge1}$, Teorema 3.3.17 memberi arah $\supseteq$. Untuk arah $\subseteq$, misalkan $x\in A_m$ untuk suatu $m\ge1$. Ambil $n=\max(m,k)$. Maka $n\ge k$, dan Lema 3.3.20(1) memberi $A_m\subseteq A_n$. Jadi $x\in A_n$ dengan $n\in\mathbb N_{\ge k}$.

(2) Irisan berhingga. Karena $k\in J_k$, Proposisi 3.3.11(1) memberi $\bigcap^{U}_{n\in J_k}A_n\subseteq A_k$. Sebaliknya, misalkan $x\in A_k$. Maka $x\in U$ karena $A_k\subseteq U$. Untuk setiap $m\in J_k$ berlaku $m\le k$, sehingga Lema 3.3.20(2) memberi $A_k\subseteq A_m$ dan $x\in A_m$.

Gabungan tak hingga. Proposisi 3.3.11(1) memberi $A_1\subseteq\bigcup_{n\in\mathbb N_{\ge1}}A_n$. Sebaliknya, jika $x\in A_m$ untuk suatu $m\ge1$, maka Lema 3.3.20(2) memberi $A_m\subseteq A_1$, sehingga $x\in A_1$.

Ekor irisan. Teorema 3.3.17 memberi arah $\subseteq$. Untuk arah $\supseteq$, misalkan $x\in U$ dan $x\in A_n$ untuk setiap $n\ge k$. Ambil sembarang $m\ge1$ dan tulis $n=\max(m,k)$. Maka $n\ge k$, sehingga $x\in A_n$. Karena $m\le n$, Lema 3.3.20(2) memberi $A_n\subseteq A_m$, jadi $x\in A_m$. ∎

Jadi pada keluarga naik, irisannya tidak memuat informasi baru karena sama dengan $A_1$. Seluruh isi keluarga terletak pada gabungannya. Pada keluarga turun keadaannya terbalik. Untuk indeks berhingga $J_k$, operasi yang "sulit" pun diambil alih oleh satu suku, yaitu $A_k$. Untuk indeks $\mathbb N_{\ge1}$ tidak ada suku terakhir yang dapat mengambil alih peran itu, seperti diperlihatkan contoh-contoh berikut.

Contoh 3.3.22 (Keluarga naik di $\mathbb N$). Ambil $U=\mathbb N$, $I=\mathbb N_{\ge1}$, dan

$$A_n=\{m\in\mathbb N: m<n\}=\{0,1,\dots,n-1\}.$$

Jadi $A_1=\{0\}$, $A_2=\{0,1\}$, dan $A_3=\{0,1,2\}$. Keluarga ini naik: jika $m<n$, maka $m<n+1$.

Gabungan. Kita tunjukkan $\bigcup_{n\in\mathbb N_{\ge1}}A_n=\mathbb N$. Arah $\subseteq$ berlaku karena setiap suku termuat dalam $U=\mathbb N$. Untuk arah $\supseteq$, ambil $x\in\mathbb N$. Indeks $n=x+1$ termuat dalam $\mathbb N_{\ge1}$, dan $x<x+1$ memberi $x\in A_{x+1}$. Indeks saksi $x+1$ bergantung pada $x$.

Irisan. Menurut Proposisi 3.3.21(1), $\bigcap^{\mathbb N}_{n\in\mathbb N_{\ge1}}A_n=A_1=\{0\}$.

Tidak ada suku terakhir. Untuk setiap $k\ge1$, gabungan atas $J_k$ adalah $A_k$ (Proposisi 3.3.21(1)). Namun gabungan atas seluruh $\mathbb N_{\ge1}$ tidak sama dengan suku mana pun. Untuk setiap $n\ge1$ berlaku $n\in\mathbb N$ tetapi $n\notin A_n$, sehingga $A_n\ne\mathbb N$. Setiap suku $A_n$ hanya memuat bilangan yang kurang dari $n$, sedangkan gabungannya adalah seluruh $\mathbb N$.

Contoh 3.3.23 (Interval naik di $\mathbb R$). Di sini bilangan real dipinjam sebagai contoh yang telah dikenal. Kita juga memakai satu hasil yang dipinjam dan baru dibuktikan kemudian dalam buku ini.

Sifat Archimedes (dipinjam). Untuk setiap bilangan real $t$ terdapat $n\in\mathbb N_{\ge1}$ dengan $n>t$.

Sifat ini adalah fakta tentang bilangan real. Ia tidak mengikuti dari aljabar himpunan yang dikembangkan di bab ini.

Ambil $U=\mathbb R$, $I=\mathbb N_{\ge1}$, dan

$$S_n=[1/n,1]=\{x\in\mathbb R: 1/n\le x\le 1\}.$$

Keluarga ini naik. Jika $1/n\le x\le1$, maka $1/(n+1)<1/n\le x\le 1$.

Gabungan. Kita tunjukkan $\bigcup_{n\in\mathbb N_{\ge1}}S_n=(0,1]$, dengan $(0,1]=\{x\in\mathbb R:0<x\le1\}$.

• Arah $\subseteq$: jika $x\in S_n$, maka $x\ge 1/n>0$ dan $x\le1$.
• Arah $\supseteq$: misalkan $0<x\le1$. Karena $x>0$, $1/x$ adalah bilangan real. Sifat Archimedes memberi $n\in\mathbb N_{\ge1}$ dengan $n>1/x$. Mengalikan dengan $x>0$ memberi $nx>1$, yaitu $1/n<x$. Bersama $x\le1$, diperoleh $x\in S_n$.

Sebagai pemeriksaan titik ujung: $1\in S_1$, sedangkan $0$ tidak termuat dalam suku mana pun karena $1/n>0$ untuk setiap $n$. Keduanya sesuai dengan $(0,1]$.

Irisan. Menurut Proposisi 3.3.21(1), $\bigcap^{\mathbb R}_{n\in\mathbb N_{\ge1}}S_n=S_1=[1,1]=\{1\}$.

Sifat yang hilang pada gabungan tak hingga. Setiap suku $S_n$ memiliki unsur terkecil, yaitu $1/n$. Untuk setiap $k$, gabungan atas $J_k$ adalah $S_k$, yang juga memiliki unsur terkecil $1/k$. Gabungan atas seluruh $\mathbb N_{\ge1}$ tidak memiliki unsur terkecil. Jika $x\in(0,1]$, maka $x/2\in(0,1]$ dan $x/2<x$. Jadi sifat yang dimiliki setiap suku dan setiap gabungan berhingga tidak otomatis dimiliki gabungan tak hingga.

Urutan kuantifikator: suku tak kosong versus irisan tak kosong

Dua pernyataan berikut tampak mirip, tetapi isinya berbeda:

$$\forall i\in I\;\exists x\;(x\in A_i) \qquad\text{dan}\qquad \exists x\;\bigl(x\in U\wedge\forall i\in I\;(x\in A_i)\bigr).$$

Pernyataan pertama mengatakan bahwa setiap suku tak kosong. Pernyataan kedua mengatakan bahwa irisan relatif $U$ tak kosong. Pada pernyataan pertama, saksi $x$ dipilih sesudah $i$ dan boleh berbeda untuk tiap $i$. Pada pernyataan kedua, satu $x$ harus dipilih sebelum $i$ dan melayani semua indeks sekaligus. Kita menyebut yang kedua pemilihan serentak.

Proposisi 3.3.24. Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$.

1. $\bigcap^{U}_{i\in I}A_i\ne\varnothing$ jika dan hanya jika $\exists x\,\bigl(x\in U\wedge\forall i\in I\,(x\in A_i)\bigr)$. Jika $I\ne\varnothing$, syarat ini setara dengan $\exists x\,\forall i\in I\,(x\in A_i)$.
2. Jika $\bigcap^{U}_{i\in I}A_i\ne\varnothing$, maka $A_i\ne\varnothing$ untuk setiap $i\in I$.
3. Kebalikan butir 2 tidak berlaku secara umum.

Bukti. (1) Bagian pertama adalah definisi irisan relatif $U$ yang dibaca ulang. Bagian kedua mengikuti Proposisi 3.3.8(3).

(2) Ambil $x_0$ dalam irisan. Pemilihan ini dilakukan sekali, sebelum indeks apa pun disebut. Untuk sembarang $i\in I$ berlaku $x_0\in A_i$, sehingga $A_i\ne\varnothing$. Saksi yang sama melayani setiap $i$. Inilah arah $\exists x\,\forall i\Rightarrow\forall i\,\exists x$, yang selalu sah. Untuk $I=\varnothing$, kesimpulan butir 2 benar secara hampa.

(3) Penyangkal yang paling sederhana adalah kasus batas $I=\varnothing$ dan $U=\varnothing$. Syarat "setiap suku tak kosong" benar secara hampa, tetapi irisannya $U=\varnothing$. Contoh 3.3.25 sampai 3.3.27 memberi penyangkal dengan $I$ dan $U$ tak kosong. ∎

Contoh 3.3.25 (Kegagalan berhingga). Ambil $U=\{1,2\}$, $I=\{1,2\}$, $A_1=\{1\}$, dan $A_2=\{2\}$. Kedua suku tak kosong, dengan saksi $1$ untuk $A_1$ dan saksi $2$ untuk $A_2$. Namun menurut Proposisi 3.3.9, irisannya adalah $\{1\}\cap\{2\}=\varnothing$. Tidak ada satu saksi yang melayani kedua indeks.

Kegagalan ini tidak dapat terjadi pada keluarga turun dengan himpunan indeks $J_k$. Jika $(A_n)_{n\in\mathbb N_{\ge1}}$ turun dan setiap suku tak kosong, Proposisi 3.3.21(2) memberi $\bigcap^{U}_{n\in J_k}A_n=A_k\ne\varnothing$ untuk setiap $k\ge1$. Contoh berikut menunjukkan bahwa kesimpulan itu runtuh begitu himpunan indeksnya tak hingga, walaupun keluarganya turun.

Contoh 3.3.26 (Keluarga turun di $\mathbb N$, suku tak kosong, irisan kosong). Ambil $U=\mathbb N$, $I=\mathbb N_{\ge1}$, dan

$$E_n=\{m\in\mathbb N: m\ge n\}.$$

• Turun. Jika $m\ge n+1$, maka $m\ge n$. Jadi $E_{n+1}\subseteq E_n$.
• Setiap suku tak kosong. $n\in E_n$. Jadi $\forall n\in I\;\exists x\,(x\in E_n)$ benar, dengan saksi $x=n$ yang bergantung pada $n$.
• Irisan kosong. Misalkan $x\in\bigcap^{\mathbb N}_{n\in I}E_n$. Maka $x\in\mathbb N$, sehingga $x+1\in I$ dan $x\in E_{x+1}$, yaitu $x\ge x+1$. Ini mustahil. Jadi $\bigcap^{\mathbb N}_{n\in I}E_n=\varnothing$, dan $\exists x\,\forall n\in I\,(x\in E_n)$ salah.
• Irisan berhingga. Untuk setiap $k\ge1$, $\bigcap^{\mathbb N}_{n\in J_k}E_n=E_k\ni k$. Setiap irisan berhingga tak kosong, tetapi irisan tak hingganya kosong.
• Gabungan. Menurut Proposisi 3.3.21(2), $\bigcup_{n\in I}E_n=E_1=\mathbb N_{\ge1}$.

Contoh ini bekerja sepenuhnya di $\mathbb N$ dan tidak memerlukan Sifat Archimedes. Perhatikan juga bahwa $E_n=\mathbb N\setminus A_n$ untuk keluarga $A_n$ dari Contoh 3.3.22, karena untuk bilangan asli $m\ge n$ berlaku tepat ketika $m<n$ tidak berlaku. Gabungan keluarga $(A_n)$ adalah $\mathbb N$, sedangkan irisan keluarga komplemennya adalah $\varnothing=\mathbb N\setminus\mathbb N$. Hubungan komplemen semacam ini dibuktikan secara umum di 3.4.

Contoh 3.3.27 (Interval turun di $\mathbb R$). Ambil $U=\mathbb R$, $I=\mathbb N_{\ge1}$, dan

$$T_n=(0,1/n)=\{x\in\mathbb R: 0<x<1/n\}.$$

• Turun. Jika $0<x<1/(n+1)$, maka $x<1/n$ karena $1/(n+1)<1/n$.
• Setiap suku tak kosong. $0<1/(2n)<1/n$, jadi $1/(2n)\in T_n$. Saksinya bergantung pada $n$.
• Irisan kosong. Misalkan $x\in\bigcap^{\mathbb R}_{n\in I}T_n$. Dari $x\in T_1$ diperoleh $x>0$. Sifat Archimedes memberi $n\in\mathbb N_{\ge1}$ dengan $n>1/x$, sehingga $1/n<x$ dan $x\notin T_n$. Ini kontradiksi.
• Gabungan. Menurut Proposisi 3.3.21(2), $\bigcup_{n\in I}T_n=T_1=(0,1)$.

Berbeda dari Contoh 3.3.26, langkah "irisan kosong" di sini memerlukan Sifat Archimedes. Langkah itu tidak dapat diperoleh dari aljabar himpunan saja. Bila $1/x$ kebetulan bilangan asli, indeks $n=1/x$ sudah cukup, sebab $x\notin(0,x)$. Untuk $x>0$ real sembarang, keberadaan $n\in\mathbb N_{\ge1}$ dengan $n>1/x$ adalah isi Sifat Archimedes.

Catatan 3.3.28 (Pemilihan per suku dan pemilihan serentak dalam bukti). Kekeliruan berikut sering muncul dalam bukti tertulis:

"Setiap $E_n$ tak kosong. Ambil $x\in E_n$. Karena $n$ sembarang, $x\in E_n$ untuk setiap $n$. Jadi irisannya tak kosong."

Di sini $x$ dipilih sesudah $n$ ditetapkan, sehingga $x$ boleh bergantung pada $n$. Generalisasi terhadap $n$ mempertahankan pernyataan bahwa untuk setiap $n$ ada suatu saksi, yaitu $\forall n\,\exists x\,(x\in E_n)$. Ia tidak mengubah saksi yang boleh bergantung pada $n$ menjadi satu objek tetap yang memenuhi $\forall n\,(x\in E_n)$. Untuk menyimpulkan $\exists x\,\forall n\,(x\in E_n)$, diperlukan satu saksi yang sama bagi semua indeks. Contoh 3.3.26 menunjukkan bahwa kesimpulan "bukti" itu salah.

Dalam Contoh 3.3.26 dan 3.3.27, pemilihan per suku diberikan oleh aturan eksplisit, yaitu $x_n=n$ dan $x_n=1/(2n)$. Persoalan memilih saksi per suku tanpa aturan eksplisit tidak dibahas dalam unit ini.

Kekeliruan yang sama dapat terjadi pada gabungan dengan peran kuantifikator dibalik. Pada Contoh 3.3.22, $\bigcup_{n}A_n=\mathbb N$ berarti $\forall x\in\mathbb N\;\exists n\in I\;(x\in A_n)$. Pernyataan ini tidak berarti $\exists n\in I\;\forall x\in\mathbb N\;(x\in A_n)$, yaitu "satu suku sudah memuat segalanya". Pernyataan terakhir salah karena $n\notin A_n$. Bukti Teorema 3.3.14 dan Proposisi 3.3.15 di atas menjaga hal ini dengan memilih saksi indeks setelah anggota $x$ diberikan.

Latihan 3.3

Latihan 1. Ambil $U=\{1,2,\dots,12\}$, $I=\{1,2,3,4\}$, dan untuk $i\in I$

$$A_i=\{x\in U: 2i\le x\le 2i+5\}.$$

Hitung $\bigcup_{j\in J}A_j$ dan $\bigcap^{U}_{j\in J}A_j$ untuk $J=I$, $J=\{1,2,3\}$, $J=\{2,4\}$, dan $J=\varnothing$. Periksa hasilnya terhadap Teorema 3.3.17.

Strategi. Tulis setiap suku secara eksplisit. Untuk irisan, cari syarat terkuat dari batas bawah dan batas atas. Untuk $J=\varnothing$, pakai Proposisi 3.3.8(1).

Pembahasan. Dengan menghitung langsung, dan memotong pada $12$ karena $A_4\subseteq U$:

$$A_1=\{2,\dots,7\},\quad A_2=\{4,\dots,9\},\quad A_3=\{6,\dots,11\},\quad A_4=\{8,\dots,12\}.$$

• $J=I$. Gabungan: setiap $x$ dengan $2\le x\le12$ termuat dalam suatu suku, misalnya $2,\dots,7\in A_1$ dan $8,\dots,12\in A_4$. Bilangan $1$ tidak termuat di suku mana pun karena semua suku hanya memuat bilangan $\ge2$. Jadi gabungannya $\{2,\dots,12\}$. Irisan: anggota irisan harus $\le7$ (dari $A_1$) dan $\ge8$ (dari $A_4$). Ini mustahil, jadi irisannya $\varnothing$.
• $J=\{1,2,3\}$. Gabungan $\{2,\dots,11\}$, karena $12\notin A_1\cup A_2\cup A_3$. Irisan: syaratnya $x\ge6$ (dari $A_3$) dan $x\le7$ (dari $A_1$). Kedua bilangan $6$ dan $7$ memang termuat dalam ketiga suku. Jadi irisannya $\{6,7\}$.
• $J=\{2,4\}$. Menurut Proposisi 3.3.9, gabungannya $A_2\cup A_4=\{4,\dots,12\}$ dan irisannya $A_2\cap A_4=\{8,9\}$.
• $J=\varnothing$. Gabungannya $\varnothing$ dan irisannya $U=\{1,\dots,12\}$.

Pemeriksaan monotoni: $\{2,4\}\subseteq I$ memberi $\{4,\dots,12\}\subseteq\{2,\dots,12\}$ dan $\varnothing\subseteq\{8,9\}$. Demikian pula $\{1,2,3\}\subseteq I$ memberi $\{2,\dots,11\}\subseteq\{2,\dots,12\}$ dan $\varnothing\subseteq\{6,7\}$. Perhatikan bahwa setiap dua suku berurutan beririsan tak kosong, tetapi irisan seluruh keluarga kosong.

Latihan 2 (Monotoni suku). Misalkan $(A_i)_{i\in I}$ dan $(B_i)_{i\in I}$ keluarga himpunan bagian $U$, dan $A_i\subseteq B_i$ untuk setiap $i\in I$.

(a) Buktikan $\bigcup_{i\in I}A_i\subseteq\bigcup_{i\in I}B_i$ dan $\bigcap^{U}_{i\in I}A_i\subseteq\bigcap^{U}_{i\in I}B_i$, termasuk untuk $I=\varnothing$.

(b) Tunjukkan bahwa $\bigcup_{i\in I}A_i\subseteq\bigcup_{i\in I}B_i$ tidak mengakibatkan $A_i\subseteq B_i$ untuk setiap $i$.

Strategi. Pada (a), saksi indeks untuk $x$ dalam keluarga $A$ dipakai ulang untuk keluarga $B$. Bandingkan dengan Teorema 3.3.17: di sana yang berubah adalah himpunan indeks, di sini yang berubah adalah sukunya. Pada (b), cari dua keluarga yang sukunya ditukar.

Pembahasan. (a) Misalkan $x\in\bigcup_{i\in I}A_i$. Ada $k\in I$ dengan $x\in A_k$. Karena $A_k\subseteq B_k$, maka $x\in B_k$, dan $k$ menjadi saksi bagi $x\in\bigcup_{i\in I}B_i$.

Misalkan $x\in\bigcap^{U}_{i\in I}A_i$. Maka $x\in U$. Untuk sembarang $i\in I$ berlaku $x\in A_i\subseteq B_i$. Jadi $x\in\bigcap^{U}_{i\in I}B_i$.

Untuk $I=\varnothing$, kedua inklusi menjadi $\varnothing\subseteq\varnothing$ dan $U\subseteq U$. Bukti di atas sudah mencakup kasus ini. Di sini kedua irisan bergerak ke arah yang sama, berbeda dengan monotoni indeks.

(b) Ambil $U=I=\{1,2\}$, dengan $A_1=\{1\}$, $A_2=\{2\}$, $B_1=\{2\}$, dan $B_2=\{1\}$. Kedua gabungan sama dengan $\{1,2\}$, jadi inklusi gabungan berlaku. Namun $A_1=\{1\}\not\subseteq\{2\}=B_1$.

Latihan 3 (Gabungan himpunan indeks). Misalkan $(A_k)_{k\in K}$ keluarga himpunan bagian $U$ dan $I,J\subseteq K$.

(a) Buktikan $\bigcup_{k\in I\cup J}A_k=\bigcup_{k\in I}A_k\cup\bigcup_{k\in J}A_k$.

(b) Buktikan $\bigcap^{U}_{k\in I\cup J}A_k=\bigcap^{U}_{k\in I}A_k\cap\bigcap^{U}_{k\in J}A_k$.

(c) Buktikan $\bigcup_{k\in I\cap J}A_k\subseteq\bigcup_{k\in I}A_k\cap\bigcup_{k\in J}A_k$, dan beri contoh bahwa inklusi itu dapat sejati.

Periksa (a) dan (b) untuk $I=\varnothing$.

Strategi. Uraikan $k\in I\cup J$ sebagai disjungsi. Kuantifikator $\exists$ terdistribusi atas $\vee$, dan $\forall$ terdistribusi atas $\wedge$. Kuantifikator $\exists$ tidak terdistribusi atas $\wedge$, dan itulah sumber inklusi sejati di (c).

Pembahasan. (a) Untuk sembarang $x$:

$$\exists k\,\bigl((k\in I\vee k\in J)\wedge x\in A_k\bigr) \iff\exists k\,(k\in I\wedge x\in A_k)\;\vee\;\exists k\,(k\in J\wedge x\in A_k).$$

Ruas kiri adalah keanggotaan pada gabungan atas $I\cup J$, dan ruas kanan adalah keanggotaan pada gabungan kedua himpunan. Syarat $x\in U$ berlebih pada ketiga gabungan. Ekstensionalitas menutup bukti.

(b) Karena $\bigl((P\vee Q)\to R\bigr)$ ekuivalen secara logis dengan $(P\to R)\wedge(Q\to R)$, dan $\forall$ terdistribusi atas $\wedge$, diperoleh

$$x\in U\wedge\forall k\,(k\in I\cup J\to x\in A_k) \iff \bigl(x\in U\wedge\forall k\in I\,(x\in A_k)\bigr)\wedge\bigl(x\in U\wedge\forall k\in J\,(x\in A_k)\bigr).$$

Untuk $I=\varnothing$, (a) menjadi $\bigcup_{k\in J}A_k=\varnothing\cup\bigcup_{k\in J}A_k$, dan (b) menjadi $\bigcap^{U}_{k\in J}A_k=U\cap\bigcap^{U}_{k\in J}A_k$. Keduanya benar karena irisan relatif $U$ termuat dalam $U$. Konvensi irisan keluarga kosong relatif $U$ adalah yang membuat (b) tetap berlaku pada batas ini.

(c) Jika ada $k$ dengan $k\in I$, $k\in J$, dan $x\in A_k$, maka $k$ yang sama menjadi saksi untuk kedua gabungan. Inklusi ini juga mengikuti Teorema 3.3.17, karena $I\cap J\subseteq I$ dan $I\cap J\subseteq J$.

Untuk contoh inklusi sejati, ambil $K=\{1,2\}$, $U=\{1\}$, $A_1=A_2=\{1\}$, $I=\{1\}$, dan $J=\{2\}$. Ruas kiri adalah gabungan atas $I\cap J=\varnothing$, yaitu $\varnothing$. Ruas kanan adalah $\{1\}\cap\{1\}=\{1\}$. Saksi untuk $I$ dan saksi untuk $J$ ada, tetapi berbeda, sehingga tidak ada satu saksi dalam $I\cap J$.

Latihan 4. Ambil $U=\mathbb N$, $I=\mathbb N_{\ge1}$, dan

$$C_n=\{m\in\mathbb N: m>0\wedge\exists q\in\mathbb N\,(m=nq)\},$$

yaitu kelipatan positif dari $n$.

(a) Tunjukkan bahwa setiap $C_n$ tak kosong.

(b) Tunjukkan bahwa $\bigcap^{\mathbb N}_{n\in I}C_n=\varnothing$.

(c) Tunjukkan bahwa keluarga ini tidak naik dan tidak turun.

(d) Hitung $\bigcap^{\mathbb N}_{n\in\{1,2,4\}}C_n$ dan $\bigcap^{\mathbb N}_{n\in\varnothing}C_n$.

Strategi. Untuk (b), ulangi pola Contoh 3.3.26: indeks $x+1$ menyingkirkan calon $x$. Untuk (d), periksa inklusi di antara ketiga suku. Untuk indeks kosong, ingat bahwa irisan diambil relatif $U$.

Pembahasan. (a) $n>0$ dan $n=n\cdot1$, jadi $n\in C_n$.

(b) Misalkan $x$ termuat dalam irisan. Dari $x\in C_1$ diperoleh $x>0$. Karena $x+1\in I$, juga $x\in C_{x+1}$, yaitu $x=(x+1)q$ untuk suatu $q\in\mathbb N$. Jika $q=0$, maka $x=0$, bertentangan dengan $x>0$. Jika $q\ge1$, maka $x\ge x+1$, mustahil. Jadi irisannya kosong, walaupun setiap suku tak kosong.

(c) Keluarga tidak turun karena $C_3\not\subseteq C_2$: $3\in C_3$ tetapi $3$ bukan kelipatan $2$. Keluarga tidak naik karena $C_1\not\subseteq C_2$: $1\in C_1$ tetapi $1\notin C_2$. Jadi Proposisi 3.3.21 tidak dapat dipakai di sini.

(d) Jika $m=4q$, maka $m=2(2q)$. Jika $m=2q$, maka $m=1\cdot(2q)$. Jadi $C_4\subseteq C_2\subseteq C_1$. Proposisi 3.3.11(1) memberi irisan $\subseteq C_4$. Sebaliknya, setiap $x\in C_4$ termuat dalam $\mathbb N$ dan dalam ketiga suku, sehingga Proposisi 3.3.11(3) dengan $C=C_4$ memberi $C_4\subseteq$ irisan. Jadi $\bigcap^{\mathbb N}_{n\in\{1,2,4\}}C_n=C_4=\{4,8,12,\dots\}$.

Untuk indeks kosong, irisannya $\mathbb N$. Perhatikan bahwa $0$ termuat dalam irisan ini walaupun $0$ tidak termuat dalam suku $C_n$ mana pun. Ini akibat langsung dari irisan relatif $U$.

Latihan 5. Ambil $U=\mathbb R$, $I=\mathbb N_{\ge1}$, dan $D_n=\{x\in\mathbb R: x\ge n\}$. Tunjukkan bahwa keluarga ini turun dengan suku-suku tak kosong. Hitung irisannya atas $J_k$ dan atas $\mathbb N_{\ge1}$, serta gabungannya. Tunjukkan di mana Sifat Archimedes diperlukan.

Strategi. Pakai Proposisi 3.3.21(2) untuk bagian berhingga dan untuk gabungan. Untuk irisan tak hingga, setiap calon real $x$ harus disingkirkan oleh suatu indeks.

Pembahasan. Keluarga turun karena $x\ge n+1$ mengakibatkan $x\ge n$. Suku $D_n$ tak kosong karena $n\in D_n$.

Menurut Proposisi 3.3.21(2), $\bigcap^{\mathbb R}_{n\in J_k}D_n=D_k\ne\varnothing$ dan $\bigcup_{n\in I}D_n=D_1=\{x\in\mathbb R:x\ge1\}$.

Untuk irisan tak hingga, misalkan $x$ anggota irisan. Sifat Archimedes memberi $n\in\mathbb N_{\ge1}$ dengan $n>x$, sehingga $x\notin D_n$. Ini kontradiksi, jadi $\bigcap^{\mathbb R}_{n\in I}D_n=\varnothing$. Jika calon $x$ diketahui bilangan asli, indeks $x+1$ sudah cukup. Untuk $x$ real sembarang, keberadaan bilangan asli yang melampaui $x$ adalah isi Sifat Archimedes dan tidak diperoleh dari aljabar himpunan.

Latihan 6 (Batas indeks kosong). Misalkan $(A_i)_{i\in I}$ keluarga himpunan bagian $U$.

(a) Buktikan bahwa $\bigcap^{U}_{i\in I}A_i\subseteq\bigcup_{i\in I}A_i$ berlaku jika $I\ne\varnothing$. Untuk $I=\varnothing$, buktikan bahwa inklusi itu berlaku jika dan hanya jika $U=\varnothing$.

(b) Buktikan bahwa $\bigcap^{U}_{i\in I}A_i=U$ jika dan hanya jika $A_i=U$ untuk setiap $i\in I$. Periksa kasus $I=\varnothing$.

Strategi. Untuk (a), satu indeks $i_0$ menjembatani irisan dan gabungan, dan tanpa indeks jembatan itu hilang. Untuk (b), pakai Proposisi 3.3.11.

Pembahasan. (a) Jika $I\ne\varnothing$, ambil $i_0\in I$. Proposisi 3.3.11(1) memberi $\bigcap^{U}_{i\in I}A_i\subseteq A_{i_0}\subseteq\bigcup_{i\in I}A_i$. Jika $I=\varnothing$, inklusi itu menjadi $U\subseteq\varnothing$ menurut Proposisi 3.3.8(1), yang berlaku tepat ketika $U=\varnothing$.

(b) (⇒) Untuk sembarang $i\in I$, Proposisi 3.3.11(1) memberi $U=\bigcap^{U}_{k\in I}A_k\subseteq A_i\subseteq U$, jadi $A_i=U$. (⇐) Jika $A_i=U$ untuk setiap $i$, maka $U\subseteq A_i$ untuk setiap $i$. Proposisi 3.3.11(3) dengan $C=U$ memberi $U\subseteq\bigcap^{U}_{i\in I}A_i$, dan inklusi sebaliknya berlaku menurut definisi.

Untuk $I=\varnothing$, kedua sisi benar: irisannya $U$ menurut Proposisi 3.3.8(1), dan syarat "$A_i=U$ untuk setiap $i$" benar secara hampa.

Latihan 7 (Model penyaringan, lanjutan Contoh 3.3.13). Tambahkan kriteria $F_4=\{r\in U:\text{nilai } r\ge100\}$ dan tulis $I'=\{1,2,3,4\}$.

(a) Hitung $\bigcap^{U}_{j\in\{2,3\}}F_j$ dan $\bigcup_{j\in\{2,3\}}F_j$.

(b) Hitung $\bigcap^{U}_{i\in I'}F_i$ dan $\bigcup_{i\in I'}F_i$.

(c) Tentukan semua $J\subseteq I'$ dengan $\bigcap^{U}_{j\in J}F_j=\varnothing$.

Strategi. Pada (a), pakai Proposisi 3.3.9. Pada (b), pakai Proposisi 3.3.11(1) dan Latihan 3(a). Pada (c), cari satu rekaman yang lolos semua kriteria lama, dan jangan lupakan $J=\varnothing$.

Pembahasan. Nilai terbesar dalam tabel adalah $90$, jadi $F_4=\varnothing$.

(a) $F_2\cap F_3=\{r_1,r_3,r_4\}\cap\{r_1,r_3,r_5,r_6\}=\{r_1,r_3\}$, dan $F_2\cup F_3=\{r_1,r_3,r_4,r_5,r_6\}$. Rekaman $r_2$ tidak lolos keduanya karena berada di Timur dengan nilai $40$.

(b) Proposisi 3.3.11(1) memberi irisan $\subseteq F_4=\varnothing$, jadi irisannya $\varnothing$. Latihan 3(a) dengan $I'=\{1,2,3\}\cup\{4\}$ memberi gabungan $U\cup F_4=U\cup\varnothing=U$.

(c) Jika $4\in J$, irisannya termuat dalam $F_4=\varnothing$. Jika $J\subseteq\{1,2,3\}$ dan $J\ne\varnothing$, rekaman $r_1$ (aktif, Barat, nilai $70$) termuat dalam setiap $F_j$ dengan $j\in J$, sehingga $r_1$ termuat dalam irisan. Jika $J=\varnothing$, irisannya $U\ni r_1$. Jadi irisannya kosong tepat ketika $4\in J$. Dalam model, satu kriteria yang tidak dipenuhi rekaman mana pun mengosongkan hasil "lolos semua", tetapi tidak mengubah hasil "lolos sedikitnya satu".

Latihan 8 (Pemilihan serentak berhingga pada keluarga naik). Misalkan $(A_n)_{n\in\mathbb N_{\ge1}}$ naik dan $p\in\mathbb N$.

(a) Buktikan: jika $x_1,\dots,x_p\in\bigcup_{n\in\mathbb N_{\ge1}}A_n$, maka ada $n\in\mathbb N_{\ge1}$ dengan $x_j\in A_n$ untuk setiap $j$ dengan $1\le j\le p$. Periksa kasus $p=0$.

(b) Tunjukkan dengan Contoh 3.3.22 bahwa pernyataan (a) tidak dapat diperluas menjadi "ada $n$ dengan $x\in A_n$ untuk setiap $x$ dalam gabungan".

Strategi. Induksi atas $p$, dengan memakai indeks terbesar di antara saksi-saksi yang ada beserta Lema 3.3.20. Untuk (b), perhatikan bahwa tidak ada suku yang sama dengan gabungannya.

Pembahasan. (a) Induksi atas $p$. Untuk $p=0$, syarat "untuk setiap $j$ dengan $1\le j\le 0$" benar secara hampa, sehingga cukup ada satu indeks. Ambil $n=1$. Bagian ini memakai fakta bahwa $\mathbb N_{\ge1}\ne\varnothing$. Pembatas $j$ kosong, tetapi kuantifikator $\exists n$ tetap memerlukan saksi.

Langkah induksi: misalkan $n$ melayani $x_1,\dots,x_p$, dan $x_{p+1}\in A_m$ untuk suatu $m\ge1$. Ambil $n'=\max(n,m)$. Lema 3.3.20(1) memberi $A_n\subseteq A_{n'}$ dan $A_m\subseteq A_{n'}$, sehingga $n'$ melayani $x_1,\dots,x_{p+1}$.

(b) Pada Contoh 3.3.22, gabungannya $\mathbb N$. Jika ada $n$ dengan $x\in A_n$ untuk setiap $x\in\mathbb N$, maka $A_n=\mathbb N$. Hal ini mustahil karena $n\notin A_n$. Jadi pemilihan serentak berhasil untuk setiap daftar berhingga, tetapi gagal untuk seluruh gabungan yang tak hingga. Ini pola yang sama dengan Contoh 3.3.26.

Menuju 3.4

Kita kini memiliki gabungan dan irisan keluarga sembarang, keduanya dirumuskan langsung lewat kuantifikator. Kita juga telah melihat bahwa irisan keluarga kosong harus diambil relatif $U$, dan bahwa urutan $\forall$ dan $\exists$ menentukan isi pernyataan. Catatan 3.3.6(a) menyediakan keluarga komplemen $(U\setminus A_i)_{i\in I}$, dan Contoh 3.3.26 sudah memperlihatkan sekilas kaitan antara gabungan suatu keluarga dan irisan komplemennya.

Unit 3.4 membuktikan hukum De Morgan untuk keluarga sembarang, termasuk keluarga tak hingga. Bukti itu memakai negasi kuantifikator dari Bab 2, karena induksi berhingga maupun diagram tidak menjangkau kasus tak hingga. Unit 3.4 juga menghitung irisan wajib $\bigcap^{\mathbb R}_{n\in\mathbb N_{\ge1}}(-1/n,1+1/n)=[0,1]$ dengan dua inklusi dan pemakaian Sifat Archimedes secara eksplisit.

3.4 Hukum De Morgan untuk Himpunan Tak Hingga

Hukum De Morgan untuk dua himpunan telah dibuktikan sebelumnya. Untuk tiga, empat, atau $k$ himpunan, pernyataan yang sama dapat diperoleh dengan induksi pada banyaknya himpunan. Analisis membutuhkan bentuk yang lain. Banyak konstruksi penting di analisis memakai gabungan atau irisan dari tak hingga banyak himpunan. Contohnya adalah himpunan titik yang lolos semua toleransi $1/n$, atau himpunan titik yang lolos paling sedikit satu toleransi. Pada keluarga semacam ini tidak ada "langkah terakhir" yang dapat dicapai induksi.

Unit ini membuktikan hukum De Morgan untuk keluarga berindeks sebarang, termasuk keluarga berindeks kosong. Setelah itu hukum tersebut dipakai pada contoh-contoh interval. Contoh-contoh ini menunjukkan sifat mana yang berubah ketika kita berpindah dari keluarga berhingga ke keluarga tak hingga.

Konvensi kerja

Sepanjang unit ini, $U$ adalah semesta kerja tertentu, yaitu sebuah himpunan yang ditetapkan untuk konteks yang sedang dibahas. $U$ bukan himpunan semua himpunan; menurut argumen Russell di Unit 3.1, himpunan semacam itu tidak ada. Untuk $A \subseteq U$, komplemen $A$ selalu berarti komplemen relatif terhadap $U$:

$$U \setminus A = \{x \in U : x \notin A\}.$$

Keberadaan himpunan ini dijamin oleh separasi pada $U$.

Definisi 3.4.1 (keluarga berindeks dalam $U$). Misalkan $I$ himpunan, mungkin kosong, dan untuk setiap $i \in I$ diberikan tepat satu himpunan $A_i \subseteq U$. Seperti pada representasi keluarga lewat $\psi(i,X)$ yang telah dipakai sebelumnya (lihat Unit 3.1 dan 3.3), hal ini dinyatakan oleh formula $\psi(i, X)$. Untuk setiap $i \in I$, formula itu dipenuhi oleh tepat satu $X \subseteq U$. Ungkapan "$x \in A_i$" adalah singkatan dari

$$\exists X\,(X\subseteq U\ \wedge\ \psi(i,X) \wedge x \in X).$$

Untuk $i \in I$, tepat satu himpunan $X\subseteq U$ memenuhi $\psi(i,X)$. Karena itu singkatan ini ekuivalen dengan $\forall X\,((X\subseteq U\ \wedge\ \psi(i,X)) \rightarrow x \in X)$, dan negasinya, "$x \notin A_i$", dapat dibaca langsung sebagai "$x$ bukan anggota satu-satunya $X\subseteq U$ yang memenuhi $\psi(i,X)$". Jika keluarga sudah diberikan sebagai himpunan, keberadaannya tidak perlu diturunkan kembali.

Didefinisikan

$$\bigcup_{i \in I} A_i = \{x \in U : \exists i\,(i \in I \wedge x \in A_i)\}, \qquad \bigcap_{i \in I} A_i = \{x \in U : \forall i\,(i \in I \rightarrow x \in A_i)\}.$$

Kedua himpunan diperoleh dengan separasi pada $U$, dengan parameter $I$ dan parameter dalam $\psi$.

Untuk gabungan, pembatasan pada $U$ tidak mengubah apa pun, karena setiap $A_i \subseteq U$. Untuk irisan, pembatasan itu penting. Bila $I = \varnothing$, syarat $\forall i\,(i \in I \rightarrow x \in A_i)$ benar secara hampa untuk setiap $x$, sehingga

$$\bigcup_{i \in \varnothing} A_i = \varnothing, \qquad \bigcap_{i \in \varnothing} A_i = U.$$

Inilah konvensi Bab 2. Bandingkan dengan pembahasan gabungan, irisan, dan keluarga berindeks dalam [R3-2]. Di buku ini, irisan keluarga kosong selalu dibaca relatif terhadap $U$, bukan terhadap "semua objek". Pembacaan yang kedua akan menuntut keberadaan himpunan yang dilarang oleh argumen Russell.

Teorema utama

Teorema 3.4.2 (De Morgan untuk keluarga sebarang). Misalkan $U$ himpunan, $I$ himpunan sebarang (boleh kosong, berhingga, atau tak hingga), dan $A_i \subseteq U$ untuk setiap $i \in I$. Maka

$$\text{(a)}\quad U \setminus \bigcup_{i \in I} A_i = \bigcap_{i \in I} (U \setminus A_i), \qquad\qquad \text{(b)}\quad U \setminus \bigcap_{i \in I} A_i = \bigcup_{i \in I} (U \setminus A_i).$$

Sebelum teorema ini dibuktikan, perlu dicek bahwa ruas kanannya bermakna. Keluarga $(U \setminus A_i)_{i \in I}$ adalah keluarga dalam $U$ yang dinyatakan oleh formula

$$\psi'(i, X) :\equiv \exists Y\,\bigl(Y\subseteq U\ \wedge\ \psi(i, Y) \wedge X = U \setminus Y\bigr).$$

Ambil $i \in I$. Himpunan $Y\subseteq U$ yang memenuhi $\psi(i,Y)$ tunggal, dan menurut ekstensionalitas komplemen relatif terhadap $U$ juga tunggal. Jadi $\psi'(i,X)$ dipenuhi oleh tepat satu $X$, dan gabungan serta irisan keluarga ini terdefinisi menurut Definisi 3.4.1.

Bukti. Keempat ruas adalah himpunan bagian $U$. Menurut ekstensionalitas, cukup ditunjukkan bahwa untuk setiap $x$, keanggotaan $x$ di ruas kiri ekuivalen dengan keanggotaannya di ruas kanan. Jika $x \notin U$, kedua ruas sama-sama tidak memuat $x$. Jadi ambil $x \in U$ sebarang.

(a) Dengan $x \in U$ tetap, rantai berikut berlaku. Pembenaran setiap langkah ditulis di sebelah kanannya.

$$\begin{aligned} x \in U \setminus \textstyle\bigcup_{i\in I} A_i &\iff x \notin \textstyle\bigcup_{i\in I} A_i && \text{definisi komplemen relatif, } x \in U\\ &\iff \neg\,\exists i\,(i \in I \wedge x \in A_i) && \text{definisi gabungan, } x \in U\\ &\iff \forall i\,\bigl(i \in I \rightarrow \neg(x \in A_i)\bigr) && \text{negasi kuantifikator eksistensial terbatas (Bab 2)}\\ &\iff \forall i\,\bigl(i \in I \rightarrow x \in U \setminus A_i\bigr) && x \in U;\ \text{keunikan dari } \psi' \text{ dipakai hanya untuk } i \in I\\ &\iff x \in \textstyle\bigcap_{i\in I} (U \setminus A_i) && \text{definisi irisan relatif } U,\ x \in U. \end{aligned}$$

(b) Dengan cara yang sama:

$$\begin{aligned} x \in U \setminus \textstyle\bigcap_{i\in I} A_i &\iff \neg\,\forall i\,(i \in I \rightarrow x \in A_i) && \text{komplemen relatif dan definisi irisan relatif } U,\ x \in U\\ &\iff \exists i\,\bigl(i \in I \wedge \neg(x \in A_i)\bigr) && \text{negasi kuantifikator universal terbatas (Bab 2)}\\ &\iff \exists i\,\bigl(i \in I \wedge x \in U \setminus A_i\bigr) && x \in U;\ \text{keunikan dari } \psi' \text{ untuk } i \in I\\ &\iff x \in \textstyle\bigcup_{i\in I} (U \setminus A_i) && \text{definisi gabungan.} \end{aligned}$$

Ekuivalensi ini berlaku untuk setiap $x \in U$, dan untuk $x \notin U$ kedua ruas sama-sama tidak memuat $x$. Jadi kedua identitas terbukti. $\blacksquare$

Kasus indeks kosong. Bukti di atas tidak memisahkan kasus $I = \varnothing$, dan memang tidak perlu, karena negasi kuantifikator terbatas berlaku untuk pembatas apa pun, termasuk pembatas kosong (Bab 2). Sebagai pemeriksaan, hitung langsung kedua identitas:

• Pada (a), ruas kiri adalah $U \setminus \varnothing = U$. Ruas kanan adalah irisan keluarga kosong relatif $U$, yaitu $U$.
• Pada (b), ruas kiri adalah $U \setminus U = \varnothing$. Ruas kanan adalah gabungan keluarga kosong, yaitu $\varnothing$.

Kecocokan ini bukan kebetulan. Nilai $\bigcup_{i\in\varnothing}A_i=\varnothing$ dipaksa oleh definisi gabungan lewat $\exists$. Karena itu, identitas (a) untuk $I=\varnothing$ memaksa $\bigcap_{i\in\varnothing}(U\setminus A_i)=U$. Andaikan irisan keluarga kosong didefinisikan secara lain, misalnya sebagai $\varnothing$. Maka (a) gagal untuk $I = \varnothing$ dan $U \neq \varnothing$. Jadi, dengan gabungan yang didefinisikan seperti di atas, konvensi "irisan keluarga kosong sama dengan $U$" adalah satu-satunya pilihan yang mempertahankan De Morgan tanpa pengecualian.

Catatan 3.4.3 (mengapa induksi dan diagram tidak cukup). Induksi pada $k \ge 1$ membuktikan, untuk setiap $k$, pernyataan De Morgan bagi keluarga berindeks $\{1, \dots, k\}$. Kasus $k=0$ adalah kasus indeks kosong yang sudah ditangani di atas. Hasil induksi adalah barisan pernyataan tentang keluarga berhingga, dan tidak satu pun membicarakan $\bigcup_{n \ge 1} A_n$. Gabungan tak hingga tidak didefinisikan sebagai hasil "akhir" dari gabungan biner yang diulang. Gabungan itu didefinisikan sekaligus oleh satu kuantifikator $\exists n$.

Lagi pula, himpunan indeks tidak harus dapat didaftar sebagai $1, 2, 3, \dots$. Misalnya $I = \mathbb{R}$, dan induksi atas bilangan asli hanya menghasilkan pernyataan untuk indeks $\{1,\dots,k\}$. Diagram Venn hanya menggambarkan beberapa himpunan, sehingga juga tidak menyentuh kasus tak hingga. Teorema 3.4.2 berlaku umum karena hukum logika "negasi dari ada adalah untuk semua yang dinegasikan", dan hukum ini tidak bergantung pada ukuran $I$.

Akibat 3.4.4. Dengan hipotesis Teorema 3.4.2,

$$\bigcap_{i \in I} A_i = U \setminus \bigcup_{i \in I} (U \setminus A_i), \qquad \bigcup_{i \in I} A_i = U \setminus \bigcap_{i \in I} (U \setminus A_i).$$

Bukti. Pertama, untuk $A \subseteq U$ berlaku komplemen ganda $U \setminus (U \setminus A) = A$. Untuk $x \in U$,

$$x \in U\setminus(U\setminus A) \iff \neg(x \in U \wedge x\notin A) \iff \neg\neg(x\in A) \iff x \in A.$$

Untuk $x \notin U$, kedua ruas tidak memuat $x$, karena $A \subseteq U$.

Tulis $B_i = U \setminus A_i$. Menerapkan Teorema 3.4.2(a) pada keluarga $(B_i)_{i\in I}$ memberikan $U \setminus \bigcup_{i \in I} B_i = \bigcap_{i \in I} (U \setminus B_i)$. Menurut komplemen ganda, $U \setminus B_i = A_i$ untuk setiap $i \in I$, sehingga ruas kanan sama dengan $\bigcap_{i \in I} A_i$. Identitas kedua diperoleh dengan cara yang sama dari Teorema 3.4.2(b), yaitu $U\setminus\bigcap_{i\in I}B_i=\bigcup_{i\in I}A_i$. $\blacksquare$

Akibat ini menunjukkan bahwa, relatif terhadap $U$, irisan sebarang dapat dinyatakan lewat gabungan dan komplemen, dan sebaliknya. Bagian Aturan berhingga yang tidak meluas ke tak hingga memakai fakta ini untuk memindahkan sifat dari gabungan ke irisan.

Contoh inti: $\bigcap_{n \ge 1}(-1/n,\, 1 + 1/n) = [0,1]$

Pada contoh-contoh berikut, bilangan real dipinjam sebagai objek yang sudah dikenal. Yang dipinjam mencakup operasi aljabar, urutan, dan trikotomi: untuk setiap $x, y$, tepat satu dari $x < y$, $x = y$, atau $x > y$ berlaku. Notasi real yang lazim juga dipinjam:

• interval seperti $(a,b) = \{x \in \mathbb{R} : a < x < b\}$ dan $[a,b] = \{x \in \mathbb{R} : a \le x \le b\}$;
• sinar seperti $(-\infty, c) = \{x\in\mathbb R : x<c\}$, $(-\infty,c]$, $(c,\infty)$, dan $[c,\infty)$, yang didefinisikan secara serupa;
• minimum $\min(s,t)$ dan nilai mutlak $|x|$.

Semua himpunan ini dibentuk dengan separasi pada $\mathbb{R}$.

Himpunan $\mathbb{N} = \{0, 1, 2, \dots\}$ dari Bab 2 juga dipinjam sebagai objek yang sudah dikenal, sama seperti $\mathbb{R}$. Separasi hanya dipakai untuk membentuk himpunan indeks

$$\mathbb{N}_{\ge 1} = \{n \in \mathbb{N} : n \ge 1\}.$$

Indeks dimulai dari $1$ agar $1/n$ terdefinisi. Semesta kerjanya $U = \mathbb{R}$.

Satu sifat lagi dibutuhkan. Sifat ini tidak dapat diturunkan dari aljabar himpunan, sehingga dinyatakan terang-terangan sebagai pinjaman.

Fakta pinjaman 3.4.5 (sifat Archimedes). Untuk setiap bilangan real $t$, terdapat $n \in \mathbb{N}_{\ge 1}$ dengan $n > t$.

Sifat ini akan dibuktikan kemudian dalam buku ini, pada pembahasan bilangan real, dari sifat-sifat yang menjadi dasar sistem real. Di bab ini sifat tersebut hanya dipakai, dan setiap tempat pemakaiannya ditandai (Archimedes).

Untuk $n \in \mathbb{N}_{\ge 1}$, tulis

$$J_n = (-1/n,\ 1 + 1/n) = \{x \in \mathbb{R} : -1/n < x < 1 + 1/n\}.$$

Formula $\psi(n, X) :\equiv X = \{x \in \mathbb{R} : -1/n < x < 1 + 1/n\}$ menentukan tepat satu $X \subseteq \mathbb{R}$ untuk setiap $n$. Jadi $(J_n)_{n \ge 1}$ adalah keluarga berindeks dalam $\mathbb{R}$. Karena $\mathbb{N}_{\ge 1} \neq \varnothing$, irisan relatif $\mathbb{R}$ di sini sama dengan irisan dalam pengertian sehari-hari.

Teorema 3.4.6. $\displaystyle\bigcap_{n \ge 1} J_n = [0,1]$.

Bukti. Kesamaan ini dibuktikan lewat dua inklusi.

Inklusi $[0,1] \subseteq \bigcap_{n \ge 1} J_n$. Ambil $x \in [0,1]$, jadi $0 \le x \le 1$, dan ambil $n \in \mathbb{N}_{\ge 1}$ sebarang. Karena $n > 0$, berlaku $1/n > 0$. Akibatnya

$$-1/n < 0 \le x \le 1 < 1 + 1/n,$$

sehingga $-1/n < x < 1 + 1/n$, yaitu $x \in J_n$. Karena $n$ sebarang, $x \in \bigcap_{n \ge 1} J_n$. Arah ini tidak memakai Archimedes.

Pemeriksaan titik ujung $0$ dan $1$. Kedua ujung perlu dicek secara khusus, karena di situlah interval terbuka dan tertutup berbeda. Untuk $x = 0$, ketaksamaan $-1/n < 0$ dan $0 < 1 + 1/n$ berlaku untuk setiap $n \ge 1$. Untuk $x = 1$, ketaksamaan $-1/n < 1$ dan $1 < 1 + 1/n$ juga berlaku untuk setiap $n \ge 1$. Jadi $0$ dan $1$ termuat di setiap $J_n$, padahal tidak ada $J_n$ yang ujungnya $0$ atau $1$. Kedua titik itu termuat karena setiap $J_n$ memberi kelonggaran $1/n > 0$ di kedua sisi.

Inklusi $\bigcap_{n \ge 1} J_n \subseteq [0,1]$. Arah ini dibuktikan secara kontrapositif: setiap $x \in \mathbb{R} \setminus [0,1]$ bukan anggota irisan. Pernyataan "bukan anggota irisan" berarti $\neg \forall n\in\mathbb N_{\ge1}\,(x \in J_n)$, yang ekuivalen dengan $\exists n\in\mathbb N_{\ge1}\,(x \notin J_n)$. Jadi, untuk setiap $x$ seperti itu, cukup ditemukan satu indeks $n$ dengan $x \notin J_n$. Jika $x \notin [0,1]$, menurut trikotomi $x < 0$ atau $x > 1$.

• Kasus $x < 0$. Maka $-x > 0$, sehingga $1/(-x)$ adalah bilangan real positif. (Archimedes) Pilih $n \in \mathbb{N}_{\ge 1}$ dengan $n > 1/(-x)$. Kalikan kedua ruas dengan $-x > 0$ untuk memperoleh $n(-x) > 1$, lalu bagi dengan $n > 0$ untuk memperoleh $-x > 1/n$, yaitu $x < -1/n$. Ketaksamaan $-1/n < x$ gagal, jadi $x \notin J_n$.
• Kasus $x > 1$. Maka $x - 1 > 0$. (Archimedes) Pilih $n \in \mathbb{N}_{\ge 1}$ dengan $n > 1/(x - 1)$. Seperti pada kasus pertama, $n(x-1) > 1$, sehingga $x - 1 > 1/n$, yaitu $x > 1 + 1/n$. Ketaksamaan $x < 1 + 1/n$ gagal, jadi $x \notin J_n$.

Pada kedua kasus, $x \notin \bigcap_{n \ge 1} J_n$. Dengan kedua inklusi, ekstensionalitas memberikan kesamaan. $\blacksquare$

Saksi bergantung pada $x$. Indeks $n$ pada inklusi kedua dipilih setelah $x$ diberikan, dan memang harus demikian. Tabel berikut memberi beberapa perhitungan.

Karena ujung $J_n$ terbuka, indeks $10$, $1000$, dan $4$ juga sudah cukup. Misalnya $1{,}25 = 1 + 1/4$, sehingga $1{,}25 \notin J_4$. Untuk membuktikan keberadaan saksi, pilihan dari Archimedes sudah memadai. Indeks terkecil dibahas pada Latihan 3.4.L7.

Tidak ada satu $n$ yang berfungsi untuk semua $x < 0$ sekaligus. Untuk $n$ tetap, titik $x = -1/(2n)$ negatif, tetapi $-1/n < -1/(2n)$, sehingga $x \in J_n$. Pernyataan yang benar berbentuk $\forall x < 0\ \exists n\in\mathbb N_{\ge1}\ (x \notin J_n)$. Pernyataan $\exists n\in\mathbb N_{\ge1}\ \forall x < 0\ (x \notin J_n)$ salah. Inilah perbedaan urutan kuantifikator dari Bab 2, kali ini dengan akibat yang dapat dihitung.

Mengapa Archimedes diperlukan. Untuk $x<0$ berlaku $x \notin J_n$ jika dan hanya jika $x \le -1/n$, yaitu $1/n \le -x$. Jadi pada inklusi kedua kita membutuhkan $n$ dengan $1/n \le -x$. Andaikan ada $x<0$ dengan $-x<1/n$ untuk semua $n\ge1$. Maka $-1/n<x<0<1+1/n$, sehingga $x\in J_n$ untuk setiap $n$, dan teorema gagal. Sifat Archimedes menyingkirkan kemungkinan ini. Aljabar himpunan tidak berkata apa-apa tentang hal ini, karena Teorema 3.4.2 berlaku untuk keluarga apa saja di semesta apa saja. Jadi Archimedes menentukan nilai irisan pada contoh ini, sedangkan De Morgan menentukan bentuk hubungan antara irisan dan gabungan.

Bacaan lewat De Morgan. Menurut Teorema 3.4.2(b) dengan $U = \mathbb{R}$,

$$\mathbb{R} \setminus \bigcap_{n \ge 1} J_n = \bigcup_{n \ge 1} (\mathbb{R} \setminus J_n) = \bigcup_{n \ge 1} \Bigl( (-\infty, -1/n] \cup [1 + 1/n, \infty) \Bigr).$$

Karena itu, Teorema 3.4.6 ekuivalen dengan

$$\bigcup_{n \ge 1} \Bigl( (-\infty, -1/n] \cup [1 + 1/n, \infty) \Bigr) = (-\infty, 0) \cup (1, \infty).$$

Inklusi kedua dalam bukti di atas, yang mencari saksi $n$, persis merupakan bukti inklusi "$\supseteq$" pada identitas gabungan ini. Ada satu hal yang patut diperhatikan. Setiap himpunan di ruas kiri memuat ujungnya sendiri, tetapi gabungannya tidak memuat $0$ maupun $1$. Gejala ini dibahas pada bagian Aturan berhingga yang tidak meluas ke tak hingga.

Tiga perbandingan

Tiga contoh berikut memakai semesta $\mathbb{R}$ dan pola yang sama dengan contoh inti, yaitu interval yang ujungnya bergeser sejauh $1/n$. Perbedaannya terletak pada pilihan ujung dan operasi. Perbedaan kecil itu mengubah hasilnya secara drastis.

Proposisi 3.4.7. $\displaystyle\bigcap_{n \ge 1} (0, 1/n) = \varnothing$.

Bukti. Inklusi $\varnothing \subseteq \bigcap_{n \ge 1}(0, 1/n)$ selalu berlaku. Untuk arah sebaliknya, cukup ditunjukkan bahwa tidak ada $x \in \mathbb{R}$ yang menjadi anggota irisan. Dengan kata lain, untuk setiap $x$ dicari satu $n$ dengan $x \notin (0, 1/n)$.

• Jika $x \le 0$, ambil $n = 1$, karena $x \notin (0,1)$.
• Jika $x > 0$, (Archimedes) pilih $n \ge 1$ dengan $n > 1/x$. Maka $nx > 1$, sehingga $1/n < x$, dan $x \notin (0, 1/n)$. $\blacksquare$

Setiap faktor tak kosong, misalnya $1/(2n) \in (0, 1/n)$, dan faktor-faktornya menurun: $(0, 1/(n+1)) \subseteq (0, 1/n)$. Untuk keluarga berhingga yang tak kosong dan menurun, irisannya sama dengan faktor terkecil, sehingga tak kosong jika setiap faktornya tak kosong. Untuk keluarga tak hingga, kesimpulan itu gagal. Tidak ada faktor "terkecil", dan setiap calon anggota tersingkir oleh suatu faktor yang cukup jauh.

Proposisi 3.4.8. $\displaystyle\bigcap_{n \ge 1} [0, 1/n] = \{0\}$.

Bukti.

($\supseteq$) Untuk setiap $n \ge 1$ berlaku $0 \le 0 \le 1/n$, jadi $0 \in [0, 1/n]$.

($\subseteq$) Ambil $x \neq 0$.

• Jika $x < 0$, maka $x \notin [0, 1]$, yaitu faktor dengan $n = 1$.
• Jika $x > 0$, (Archimedes) pilih $n > 1/x$. Maka $1/n < x$, sehingga $x \notin [0, 1/n]$.

Jadi setiap anggota irisan sama dengan $0$. $\blacksquare$

Bandingkan dengan Proposisi 3.4.7. Kedua ujung kini ikut dimasukkan, tetapi yang menentukan hanya ujung kiri. Dengan bukti yang sama, $\bigcap_{n\ge1}[0,1/n)$ juga sama dengan $\{0\}$, sedangkan $\bigcap_{n\ge1}(0,1/n]$ tetap $\varnothing$. Ujung kanan $1/n$ selalu tersingkir oleh faktor sesudahnya. Titik $0$, ujung kiri bersama semua faktor, bertahan karena ia anggota setiap faktor.

Proposisi 3.4.9. $\displaystyle\bigcup_{n \ge 2} [1/n,\ 1 - 1/n] = (0, 1)$.

Indeks dimulai dari $2$. Untuk $n = 1$, intervalnya adalah $[1, 0] = \varnothing$. Faktor ini tidak merusak gabungan, tetapi juga tidak menyumbang apa pun. Untuk $n \ge 2$ berlaku $2/n \le 1$, jadi $1/n \le 1 - 1/n$, dan intervalnya tak kosong. Faktor pertama adalah $[1/2, 1/2] = \{1/2\}$.

Bukti.

($\subseteq$) Jika $x \in [1/n, 1 - 1/n]$ untuk suatu $n \ge 2$, maka $0 < 1/n \le x \le 1 - 1/n < 1$, sehingga $x \in (0,1)$.

($\supseteq$) Ambil $x \in (0,1)$. Diperlukan saksi $n \ge 2$ dengan $1/n \le x$ dan $x \le 1 - 1/n$, yaitu $1/n \le x$ dan $1/n \le 1 - x$. Tulis $m = \min(x, 1 - x)$.

• Karena $0 < x < 1$, berlaku $m > 0$.
• Selain itu $m \le 1/2$. Sebab $x + (1 - x) = 1$, sehingga salah satu suku tidak melebihi $1/2$.

(Archimedes) Pilih $n \ge 1$ dengan $n > 1/m$. Karena $1/m \ge 2$, berlaku $n > 2$, sehingga $n$ memang indeks yang sah. Dari $n > 1/m$ diperoleh $1/n < m$. Akibatnya $1/n < x$ dan $1/n < 1 - x$, dan ketaksamaan kedua berarti $x < 1 - 1/n$. Jadi $x \in [1/n, 1 - 1/n]$. $\blacksquare$

Saksinya bergantung pada $x$:

• Untuk $x = 0{,}3$: $m = 0{,}3$ dan syaratnya $n > 3{,}33\ldots$. Pilihan $n = 4$ memberi $0{,}3 \in [0{,}25;\ 0{,}75]$.
• Untuk $x = 0{,}999$: $m = 0{,}001$ dan syaratnya $n > 1000$. Pilihan $n = 1001$ memberi $1 - 1/1001 = 0{,}999000999\ldots > 0{,}999$.

Tidak ada satu faktor yang memuat seluruh $(0,1)$. Untuk $n\ge2$, titik $1/(2n)$ termuat di $(0,1)$, tetapi $1/(2n)<1/n$, sehingga $1/(2n)\notin[1/n,1-1/n]$. Ujung $0$ dan $1$ juga tidak pernah tercapai.

Menurut Teorema 3.4.2(a), Proposisi 3.4.9 ekuivalen dengan

$$\bigcap_{n \ge 2} \Bigl( (-\infty, 1/n) \cup (1 - 1/n, \infty) \Bigr) = (-\infty, 0] \cup [1, \infty).$$

Ruas kiri adalah irisan himpunan yang tidak memuat ujungnya sendiri, tetapi hasilnya memuat $0$ dan $1$. Polanya sama dengan contoh inti, dengan peran gabungan dan irisan yang dibalik.

Aturan berhingga yang tidak meluas ke tak hingga

Contoh-contoh di atas memperlihatkan sebuah pola: sifat yang dimiliki setiap anggota keluarga bisa hilang pada irisan atau gabungan tak hingganya. Pola ini dapat dibuat tepat dengan satu pengertian dari analisis. Pengertian itu dipinjam di sini hanya sebagai ilustrasi; teori keterbukaan yang utuh tidak dikembangkan di bab ini.

Definisi pinjaman 3.4.10. Himpunan $G \subseteq \mathbb{R}$ disebut terbuka jika untuk setiap $x \in G$ terdapat $\varepsilon > 0$ dengan $(x - \varepsilon, x + \varepsilon) \subseteq G$. Himpunan $F \subseteq \mathbb{R}$ disebut tertutup jika $\mathbb{R} \setminus F$ terbuka.

Definisi ini memuat pola kuantifikator $\forall x\, \exists \varepsilon$. Bilangan $\varepsilon$ boleh bergantung pada $x$, sama seperti saksi $n$ pada contoh inti.

Fakta 3.4.11.

1. Setiap interval $(a, b)$ terbuka. Demikian pula setiap sinar $(-\infty, c)$ dan $(c, \infty)$.
2. Gabungan keluarga sebarang himpunan terbuka adalah himpunan terbuka.
3. Irisan dua himpunan terbuka adalah himpunan terbuka.

Bukti.

(1) Jika $a \ge b$, intervalnya kosong dan terbuka secara hampa. Misalkan $a<b$ dan $x \in (a, b)$. Ambil $\varepsilon = \min(x - a, b - x) > 0$. Jika $|y - x| < \varepsilon$, maka

$$y > x - \varepsilon \ge x - (x - a) = a \quad\text{dan}\quad y < x + \varepsilon \le x + (b - x) = b.$$

Untuk sinar $(-\infty,c)$ dan $x < c$, ambil $\varepsilon = c - x$; maka $y < x + \varepsilon = c$. Untuk sinar $(c,\infty)$ dan $x > c$, ambil $\varepsilon = x - c$; maka $y > x - \varepsilon = c$.

(2) Jika $x \in \bigcup_{i \in I} G_i$, ada $i$ dengan $x \in G_i$. Karena $G_i$ terbuka, ada $\varepsilon > 0$ dengan $(x - \varepsilon, x + \varepsilon) \subseteq G_i \subseteq \bigcup_{i \in I} G_i$. Ukuran $I$ tidak berperan sama sekali. Untuk $I = \varnothing$, gabungannya $\varnothing$, yang terbuka secara hampa.

(3) Jika $x \in G \cap H$, ada $\varepsilon_1, \varepsilon_2 > 0$ dengan $(x - \varepsilon_1, x + \varepsilon_1) \subseteq G$ dan $(x - \varepsilon_2, x + \varepsilon_2) \subseteq H$. Bilangan $\varepsilon = \min(\varepsilon_1, \varepsilon_2) > 0$ memenuhi keduanya. $\blacksquare$

Dengan induksi pada $k \ge 1$, butir (3) meluas ke irisan $k$ himpunan terbuka, karena minimum dari berhingga banyak bilangan positif tetap positif. Untuk keluarga kosong, irisannya relatif terhadap $\mathbb{R}$ adalah $\mathbb{R}$, yang terbuka.

Teorema 3.4.6 menunjukkan bahwa perluasan ini gagal untuk keluarga tak hingga. Setiap $J_n = (-1/n, 1 + 1/n)$ terbuka menurut (1), tetapi irisannya, $[0,1]$, tidak terbuka. Untuk $x = 0$ dan $\varepsilon > 0$ sebarang, titik $-\varepsilon/2$ termuat di $(-\varepsilon, \varepsilon)$ tetapi tidak di $[0,1]$.

Penyebab kegagalan itu dapat ditunjuk dengan tepat. Bukti (3) memerlukan satu $\varepsilon$ yang berlaku untuk semua faktor. Untuk $x = 0$ dan faktor $J_n$, inklusi $(-\varepsilon, \varepsilon) \subseteq J_n$ berlaku jika dan hanya jika $\varepsilon \le 1/n$. Satu $\varepsilon > 0$ yang berlaku untuk semua $n$ harus memenuhi $\varepsilon \le 1/n$ untuk setiap $n$. Namun (Archimedes) ada $n > 1/\varepsilon$, yaitu $1/n < \varepsilon$, sehingga bilangan semacam itu tidak ada. Jadi tak hingga banyak bilangan positif $1/n$ tidak mempunyai batas bawah positif bersama. Pengganti minimum yang menolong di kasus berhingga tidak tersedia di kasus tak hingga.

De Morgan memindahkan gejala ini ke himpunan tertutup. Jika setiap $F_i$ tertutup, maka menurut Teorema 3.4.2(b),

$$\mathbb{R} \setminus \bigcap_{i \in I} F_i = \bigcup_{i \in I} (\mathbb{R} \setminus F_i)$$

adalah gabungan himpunan terbuka. Menurut Fakta 3.4.11(2), himpunan itu terbuka. Jadi irisan sebarang himpunan tertutup adalah tertutup. Untuk $I = \varnothing$, irisannya relatif terhadap $\mathbb{R}$ adalah $\mathbb{R}$, yang tertutup karena komplemennya, $\varnothing$, terbuka. Di sini pun konvensi irisan relatif $U$ bekerja tanpa pengecualian.

Untuk gabungan, situasinya berbeda. Gabungan berhingga himpunan tertutup memang tertutup. Menurut Teorema 3.4.2(a) untuk indeks berhingga, komplemennya adalah irisan berhingga himpunan terbuka, dan himpunan itu terbuka menurut perluasan Fakta 3.4.11(3) ke $k$ himpunan. Untuk keluarga tak hingga, jaminan ini hilang, dan Proposisi 3.4.9 memberi contoh penyangkalnya. Setiap $[1/n, 1 - 1/n]$ dengan $n\ge2$ tertutup, karena komplemennya, $(-\infty, 1/n) \cup (1 - 1/n, \infty)$, adalah gabungan dua sinar terbuka. Namun gabungannya, $(0,1)$, tidak tertutup. Komplemennya, $(-\infty, 0] \cup [1, \infty)$, tidak terbuka di $0$, karena untuk setiap $\varepsilon > 0$ titik $\min(\varepsilon/2, 1/2)$ termuat di $(-\varepsilon, \varepsilon)$ dan juga di $(0,1)$.

Ringkasnya, aljabar himpunan (De Morgan) menjamin bahwa setiap aturan untuk gabungan memiliki pasangan untuk irisan, dan sebaliknya. Aljabar himpunan tidak menjamin bahwa aturan yang benar untuk keluarga berhingga tetap benar untuk keluarga tak hingga. Pada contoh di atas, aturan irisan berhingga gagal karena tak hingga banyak $\varepsilon$ positif tidak harus mempunyai batas bawah positif bersama. Archimedes menentukan nilai konkret irisannya. Pembahasan keterbukaan yang sistematis berada di luar bab ini.

Latihan dan pembahasan

Latihan 3.4.L1. Misalkan $a, b \in \mathbb{R}$ dengan $a < b$. Buktikan $\bigcap_{n \ge 1} (a - 1/n,\ b + 1/n) = [a, b]$. Kemudian tentukan irisannya untuk $a = b$ dan untuk $a > b$.

Strategi. Tiru bukti Teorema 3.4.6 dengan menggeser ujung, lalu periksa di mana hipotesis $a < b$ benar-benar dipakai.

Pembahasan.

($\supseteq$) Jika $a \le x \le b$, maka $a - 1/n < a \le x \le b < b + 1/n$ untuk setiap $n \ge 1$.

($\subseteq$) Jika $x \notin [a,b]$, maka menurut trikotomi $x<a$ atau $x>b$.

• Jika $x < a$, maka $a - x > 0$. (Archimedes) Pilih $n > 1/(a - x)$. Maka $a - x > 1/n$, sehingga $x < a - 1/n$ dan $x \notin (a - 1/n, b + 1/n)$.
• Jika $x > b$, (Archimedes) pilih $n > 1/(x - b)$. Maka $x > b + 1/n$.

Hipotesis $a < b$ ternyata tidak pernah dipakai, sehingga identitas ini berlaku untuk semua $a, b \in \mathbb R$.

• Untuk $a = b$: $\bigcap_{n \ge 1} (a - 1/n, a + 1/n) = [a, a] = \{a\}$. Setiap faktor adalah interval terbuka tak kosong, tetapi irisannya satu titik, dan $\{a\}$ tidak terbuka. Untuk $\varepsilon>0$ sebarang, titik $a+\varepsilon/2$ termuat di $(a-\varepsilon,a+\varepsilon)$ tetapi tidak di $\{a\}$. Jadi ini contoh penyangkal kedua untuk anggapan "irisan himpunan terbuka selalu terbuka".
• Untuk $a > b$: $[a, b] = \varnothing$. Sebagai pemeriksaan langsung, $(a - 1/n, b + 1/n)$ kosong begitu $b + 1/n \le a - 1/n$, yaitu $2/n \le a - b$. (Archimedes) Ada $n > 2/(a-b)$, dan $n$ ini memenuhi syarat tersebut. Irisan yang memuat faktor kosong tentu kosong, sehingga hasilnya konsisten dengan rumus umum.

Latihan 3.4.L2. Untuk $a < b$, buktikan $\bigcup_{n \ge 1} [a + 1/n,\ b - 1/n] = (a, b)$. Apa yang terjadi bila $a = b$?

Strategi. Tiru bukti Proposisi 3.4.9. Untuk arah $\supseteq$, cari saksi $n$ melalui jarak $x$ ke ujung terdekat.

Pembahasan. Faktor dengan $2/n > b - a$ kosong. Faktor-faktor itu boleh ikut dalam gabungan karena tidak menambah apa pun.

($\subseteq$) Jika $a + 1/n \le x \le b - 1/n$, maka $a < x < b$.

($\supseteq$) Untuk $x \in (a,b)$, tulis $m = \min(x - a, b - x) > 0$. (Archimedes) Pilih $n > 1/m$. Maka $1/n < x - a$ dan $1/n < b - x$, jadi $x \in [a + 1/n, b - 1/n]$.

Untuk $a = b$, setiap faktor $[a + 1/n, a - 1/n]$ kosong, sehingga gabungannya adalah $\varnothing = (a, a)$. Berbeda dengan Proposisi 3.4.9, di sini tidak diperlukan pembatasan $n \ge 2$, karena faktor kosong tidak mengganggu gabungan.

Latihan 3.4.L3 (pembatas kosong). Ambil $U = \{1,2,3,4,5\}$ dan $I = \varnothing$. Hitung keempat ruas Teorema 3.4.2. Ulangi untuk $U = \mathbb{R}$.

Strategi. Hitung gabungan dan irisan keluarga kosong langsung dari definisi, lalu baru ambil komplemen.

Pembahasan. Untuk $U = \{1,2,3,4,5\}$:

• $\bigcup_{i \in \varnothing} A_i = \varnothing$, jadi ruas kiri (a) adalah $U \setminus \varnothing = \{1,2,3,4,5\}$. Ruas kanan (a) adalah irisan keluarga kosong relatif $U$, yaitu $\{1,2,3,4,5\}$.
• $\bigcap_{i \in \varnothing} A_i = U$, jadi ruas kiri (b) adalah $U \setminus U = \varnothing$. Ruas kanan (b) adalah gabungan keluarga kosong, yaitu $\varnothing$.

Untuk $U = \mathbb{R}$, hasilnya sama dengan $\{1,2,3,4,5\}$ diganti $\mathbb{R}$. Perhatikan bahwa nilai irisan keluarga kosong bergantung pada $U$. Inilah alasan semesta harus dinyatakan.

Latihan 3.4.L4 (De Morgan relatif terhadap $C$). Misalkan $C \subseteq U$ dan $A_i \subseteq U$ untuk setiap $i\in I$. (a) Buktikan $C \setminus \bigcup_{i \in I} A_i = \bigcap_{i \in I} (C \setminus A_i)$ bila $I \neq \varnothing$. (b) Tunjukkan bahwa (a) dapat gagal bila $I = \varnothing$. (c) Buktikan bentuk yang berlaku untuk semua $I$: $C \setminus \bigcup_{i \in I} A_i = C \cap \bigcap_{i \in I} (U \setminus A_i)$.

Strategi. Tulis kedua ruas sebagai rumus keanggotaan, lalu cari langkah yang memerlukan satu indeks konkret.

Pembahasan.

(a) Untuk $x \in U$: $x \in C \setminus \bigcup_{i\in I} A_i$ jika dan hanya jika $x \in C$ dan $\forall i \in I\ (x \notin A_i)$. Ruas kanan menuntut $\forall i \in I\ (x \in C \wedge x \notin A_i)$. Arah "$\Rightarrow$" berlaku untuk setiap $I$. Arah "$\Leftarrow$" memerlukan satu $i_0 \in I$ untuk memperoleh $x \in C$, dan indeks itu tersedia karena $I \neq \varnothing$.

(b) Untuk $I = \varnothing$, ruas kiri adalah $C \setminus \varnothing = C$, sedangkan ruas kanan adalah irisan keluarga kosong relatif $U$, yaitu $U$. Ambil $U = \{1,2,3,4,5\}$ dan $C = \{1,2,3\}$. Maka $C \neq U$, dan (a) gagal. Langkah yang tidak tersedia adalah langkah yang memakai $i_0 \in I$.

(c) Untuk $X \subseteq U$ berlaku $C \setminus X = C \cap (U \setminus X)$, karena keduanya memuat tepat titik $x \in C$ dengan $x \notin X$. Ambil $X = \bigcup_{i\in I} A_i$ dan terapkan Teorema 3.4.2(a); diperoleh rumus yang diminta. Untuk $I = \varnothing$, rumus ini memberi $C \cap U = C$, sesuai dengan ruas kiri.

Latihan 3.4.L5 (urutan kuantifikator). Tunjukkan bahwa $J_n \neq [0,1]$ untuk setiap $n \ge 1$, dan bahwa pernyataan $\exists n\in\mathbb N_{\ge1}\ \forall x\in\mathbb R\ \bigl(x \notin [0,1] \rightarrow x \notin J_n\bigr)$ salah. Jelaskan mengapa hal ini tidak bertentangan dengan Teorema 3.4.6.

Strategi. Untuk $n$ tetap, cari satu titik di luar $[0,1]$ yang masih termuat di $J_n$. Setelah itu tukar urutan kuantifikatornya.

Pembahasan. Untuk $n$ sebarang, titik $x = -1/(2n)$ termuat di $J_n$ tetapi tidak di $[0,1]$. Jadi $J_n \ne [0,1]$. Titik yang sama juga membantah pernyataan eksistensial tadi untuk $n$ tersebut, dan karena $n$ sebarang, pernyataan itu salah.

Teorema 3.4.6 hanya memerlukan $\forall x\in\mathbb R\setminus[0,1]\ \exists n\in\mathbb N_{\ge1}\ (x \notin J_n)$, dan pernyataan ini benar. Untuk $x = -1/(2n)$, indeks $2n$ sudah cukup. Karena ujung $J_{2n}$ terbuka, $x = -1/(2n)$ bukan anggota $J_{2n}$. Indeks lain yang lebih besar, seperti $4n$, juga cukup.

Latihan 3.4.L6. Buktikan $\bigcap_{n \ge 1} [n, \infty) = \varnothing$ dan $\bigcup_{n \ge 1} (-n, n) = \mathbb{R}$. Tunjukkan dengan Teorema 3.4.2(a) bahwa identitas kedua setara dengan $\bigcap_{n\ge1}\bigl((-\infty,-n]\cup[n,\infty)\bigr)=\varnothing$. Kemudian tunjukkan bahwa pernyataan terakhir ini diperoleh dari identitas pertama ditambah simetri $x\mapsto -x$.

Strategi. Tuliskan setiap identitas sebagai pernyataan $\forall x\,\exists n$, lalu bandingkan isi pernyataan-pernyataan itu.

Pembahasan.

• Untuk $x \in \mathbb{R}$, (Archimedes) pilih $n > x$. Maka $x \notin [n, \infty)$, sehingga irisan pertama kosong. Sebaliknya, $x\notin[n,\infty)$ berarti $x<n$. Jadi $\bigcap_{n\ge1}[n,\infty)=\varnothing$ adalah pernyataan $\forall x\in\mathbb R\,\exists n\in\mathbb N_{\ge1}\,(x<n)$, yaitu sifat Archimedes itu sendiri. Aljabar himpunan tidak dapat menggantikannya.
• Untuk gabungan, (Archimedes) pilih $n > |x|$. Maka $-n < x < n$.
• Menurut Teorema 3.4.2(a) dengan $U=\mathbb R$, $\mathbb{R} \setminus \bigcup_{n \ge 1}(-n,n) = \bigcap_{n \ge 1} \bigl( (-\infty, -n] \cup [n, \infty) \bigr)$. Karena $\bigcup_{n\ge1}(-n,n)\subseteq\mathbb R$, gabungan itu sama dengan $\mathbb R$ jika dan hanya jika irisan di ruas kanan kosong.
• Andaikan $x$ termuat di irisan tersebut. Untuk setiap $n$, $x\le -n$ atau $x\ge n$, sehingga $|x|\ge n$. Jadi $|x|\in\bigcap_{n\ge1}[n,\infty)$, padahal irisan itu kosong. Kontradiksi ini menunjukkan bahwa irisannya kosong.

De Morgan saja hanya memberi langkah ketiga. Langkah keempat memakai simetri $x\mapsto -x$, yang muncul lewat $|x|$.

Latihan 3.4.L7 (filter data, model terhitung). Sebuah daftar pembacaan dimodelkan sebagai himpunan berhingga

$$U = \{-0{,}3;\ -0{,}05;\ 0;\ 0{,}5;\ 1;\ 1{,}002;\ 1{,}2\}.$$

Filter tingkat ke-$n$ meloloskan $F_n = U \cap J_n = U\cap(-1/n,\ 1 + 1/n)$. Tentukan $\bigcap_{n \ge 1} F_n$ (relatif $U$) dan indeks terkecil $N$ yang memenuhi $F_n = \bigcap_{k \ge 1} F_k$ untuk semua $n \ge N$.

Strategi. Gunakan Teorema 3.4.6 untuk menentukan nilai irisan. Untuk indeks terkecil, tulis syarat tepat agar sebuah titik tersingkir, bukan syarat Archimedes yang ketat.

Pembahasan. Untuk $x\in U$, $x\in\bigcap_{n\ge1}F_n$ jika dan hanya jika $x\in J_n$ untuk setiap $n\ge1$. Menurut Teorema 3.4.6, hal ini berarti $x\in[0,1]$. Jadi $\bigcap_{n\ge1}F_n=U\cap[0,1]=\{0;\ 0{,}5;\ 1\}$. Ini model himpunan saja, bukan uji pada data sungguhan.

Untuk indeks penyingkiran, perhatikan bahwa $p\notin J_n$ jika dan hanya jika $p\le -1/n$ atau $p\ge 1+1/n$. Kedua ketaksamaan ini tidak ketat karena ujung $J_n$ terbuka.

• $-0{,}3\notin J_n \iff 1/n\le 0{,}3 \iff n\ge 4$. Pada $n=3$, $-1/3\approx-0{,}333<-0{,}3$, jadi titik itu masih lolos.
• $-0{,}05\notin J_n \iff 1/n\le 0{,}05 \iff n\ge 20$.
• $1{,}2\notin J_n \iff 1/n\le 0{,}2 \iff n\ge 5$.
• $1{,}002\notin J_n \iff 1/n\le 0{,}002 \iff n\ge 500$. Pada $n=499$, $1+1/499\approx1{,}002004>1{,}002$, jadi titik itu masih lolos.
• $0$, $0{,}5$, dan $1$ lolos di semua tingkat.

Karena $1/(n+1)<1/n$, berlaku $J_{n+1}\subseteq J_n$, sehingga $F_{n+1}\subseteq F_n$. Titik yang tersingkir pada suatu tingkat tetap tersingkir sesudahnya. Jadi $F_n=\{0;\,0{,}5;\,1\}$ tepat untuk $n\ge 500$, dan $N=500$.

Pada semesta berhingga, keluarga $(F_n)_{n\ge1}$ yang menurun ini stabil setelah berhingga langkah, karena hanya berhingga banyak titik yang perlu disingkirkan. Jadi gejala tak hingga pada bagian-bagian sebelumnya bersumber dari $\mathbb R$, bukan dari aljabar himpunan. Perhatikan pula bahwa pilihan Archimedes yang ketat ($n>t$) cukup untuk membuktikan keberadaan saksi. Indeks terkecil ditentukan oleh syarat yang tepat ($n\ge t$), dan keduanya dapat berbeda satu indeks.

Penutup Bab 3 dan transisi ke Bab 4

Bab ini dibangun dalam tiga tahap.

1. Ekstensionalitas menetapkan kapan dua himpunan sama, dan separasi menetapkan himpunan mana yang boleh dibentuk dari himpunan yang sudah ada. Argumen Russell menunjukkan mengapa pembatasan ini perlu.
2. Operasi biner dan keluarga berindeks dikerjakan di dalam semesta kerja $U$ yang dinyatakan. Pilihan ini membuat komplemen dan irisan keluarga kosong bermakna.
3. Unit ini menunjukkan bahwa hukum aljabar himpunan berlaku untuk keluarga berukuran apa pun, karena hukum itu pada dasarnya adalah hukum kuantifikator. Sebaliknya, sifat seperti keterbukaan atau ketakkosongan irisan yang menurun bergantung pada struktur tambahan, dan dapat runtuh ketika keluarga menjadi tak hingga.

Semua contoh interval di unit ini diam-diam memakai satu objek yang belum diberi nama, yaitu kaitan antara titik $x$ dan indeks $n$. Secara informal, pada contoh inti bayangkan kumpulan semua pasangan $(x, n)$ dengan $x \in J_n$:

$$S = \{(x, n) : x \in \mathbb{R},\ n \in \mathbb{N}_{\ge 1},\ -1/n < x < 1 + 1/n\}.$$

Dalam bahasa ini, $\bigcap_{n \ge 1} J_n$ adalah himpunan $x$ yang berkaitan dengan semua $n$, dan $\bigcup_{n \ge 1} J_n$ adalah himpunan $x$ yang berkaitan dengan suatu $n$. Hukum De Morgan menjadi pernyataan tentang $x$ yang tidak berkaitan dengan suatu $n$, atau dengan semua $n$.

Untuk menjadikan $S$ himpunan yang sah, diperlukan pasangan terurut dan hasil kali Kartesius. Keduanya lebih dari aksioma pasangan tak terurut di Unit 3.1. Bab 4 dimulai dari sana. Bab itu mendefinisikan relasi sebagai himpunan bagian hasil kali Kartesius, kemudian mempelajari relasi yang membagi semesta menjadi blok-blok yang saling lepas.

Contoh awal yang dapat diperiksa langsung adalah $U=\{1,2,3\}$ dengan keluarga $\{\{1,2\},\{3\}\}$. Kedua blok tidak kosong, irisannya kosong, dan gabungannya $U$. Relasi "terletak di blok yang sama" menghasilkan pasangan $(1,1),(1,2),(2,1),(2,2),(3,3)$; pengertian pasangan terurut dan sifat relasi itu akan diformalkan pada Bab 4. Contoh ini mengantar hubungan antara relasi ekuivalensi dan partisi, lalu pembahasan kuosien dan urutan parsial. Inklusi $\subseteq$ pada $\mathcal P(U)$, yang dipakai sepanjang bab ini, akan menjadi contoh baku urutan parsial.

Rujukan Bab 3

[R3-1] Axioms of Set Theory, Chapter 3. Bahan ajar pada halaman Lorenz Halbeisen, ETH Zurich. https://people.math.ethz.ch/~halorenz/4students/LogikML/ZFC.pdf

[R3-2] Open Logic Project. Unions and Intersections, revisi 9620cc7, 12 Juli 2026. https://builds.openlogicproject.org/content/sets-functions-relations/sets/unions-and-intersections.pdf

[R3-3] Jonathan Pila. B1.2 Set Theory. Lecture notes, Hilary Term 2018, University of Oxford. https://www.maths.ox.ac.uk/system/files/attachments/SetTheoryHT18.pdf