Logika Predikat dan Kuantifikasi Tingkat Lanjut

ARSTEMA ACADEMY ANALISIS MATEMATIKA DAN FONDASI RIGOR Bagian I · Bab 2 Naskah hasil telaah dan pengembangan · 1 Oktober 2026

Draf Gamma asal: https://gamma.app/docs/lfy6ox5pg3pclq9 Versi ini memuat koreksi matematis dan pendalaman editorial. Dokumen daring Gamma tetap draf asal; koreksi di sini tidak mengubahnya. Bab ini melanjutkan buku yang masih dalam pengerjaan.

Bab 2: Logika Predikat dan Kuantifikasi Tingkat Lanjut

Satu jawaban untuk setiap pertanyaan belum tentu berarti satu jawaban untuk semua pertanyaan. Perbedaan itu telah terlihat pada akhir Bab 1 melalui ∀x∃y(y>x) dan ∃y∀x(y>x). Di ℝ, kita dapat menjawab tantangan x dengan y=x+1; kita tidak dapat memilih satu bilangan yang lebih besar daripada setiap bilangan riil. Yang berubah adalah kapan saksi boleh dipilih dan informasi apa yang boleh dipakainya. Bab ini menjadikan ketergantungan tersebut alat untuk membaca rumus, membangun bukti, dan menemukan kesalahan. Notasi dari Bab 1 dipertahankan: → dan ↔ adalah konektif, ≡ menyatakan ekuivalensi logis di tingkat metabahasa, ⊨ konsekuensi semantik, dan ⊢ derivabilitas formal.

Kita mulai dari bahasa yang menyebut objek dan sifatnya, lalu menetapkan makna “setiap” serta “terdapat”. Sesudah itu, perpindahan dan negasi kuantifikator akan diuji pada definisi limit ε–δ. Bagian terakhir memakai pola yang sama untuk keterbagian, paritas, dan penugasan hingga. Contoh numerik menyertai bukti agar perhitungannya dapat diperiksa; contoh-contoh itu tidak menggantikan argumen yang mencakup seluruh domain.

Untuk semantik logika orde pertama, kita memakai struktur dengan semesta tak kosong. Himpunan pembatas seperti A dalam ∀x∈A boleh kosong. Pada contoh analisis, D menyatakan domain fungsi yang disebut secara eksplisit. Konvensi semesta tak kosong merupakan pilihan kerangka, bukan akibat dari kata “universal”. Salah satu konsekuensinya: dari ∀xP(x) kita dapat menyimpulkan ∃xP(x). Untuk kuantifikasi terbatas pada A, konsekuensi itu memerlukan A≠∅.

2.1 Fungsi Proposisional dan Variabel

Term, Formula, dan Perbedaan Dasarnya

Logika proposisional memperlakukan kalimat sebagai unit yang menerima nilai kebenaran. Logika predikat membuka struktur internalnya: objek apa yang dibicarakan, sifat apa yang dimilikinya, dan bagaimana objek-objek berhubungan. Sebuah term menyebut objek, sedangkan formula mengungkapkan kondisi yang benar atau salah setelah struktur dan penetapan variabel diberikan. Ekspresi x² menyebut suatu bilangan; ekspresi x²≥4 menanyakan apakah bilangan itu memenuhi sebuah kondisi. Perbedaan jenis ekspresi ini harus dijaga sebelum kita mulai menghitung atau membuktikan.

Term dibangun secara rekursif. Variabel dan simbol konstanta adalah term. Jika f adalah simbol fungsi beraritas n dan t₁,…,tₙ merupakan term, maka f(t₁,…,tₙ) juga term. Formula atomik berbentuk P(t₁,…,tₙ), atau t₁=t₂ dalam bahasa dengan kesamaan. Dari formula kita membangun negasi, konjungsi, disjungsi, kondisional, bikondisional, serta ∀xφ dan ∃xφ. Tidak semua susunan simbol merupakan formula: menulis x+∃y tanpa aturan pembentukan tidak menghasilkan ekspresi matematis yang terdefinisi. Dalam struktur M dengan semesta U, simbol fungsi beraritas n ditafsirkan sebagai fungsi total Uⁿ→U, sedangkan simbol predikat beraritas n ditafsirkan sebagai relasi, yaitu himpunan bagian Uⁿ. Konvensi sintaks dan struktur ini dapat dibandingkan dengan Open Logic Project [R1].

Pada struktur bilangan riil, simbol + ditafsirkan sebagai penjumlahan total ℝ×ℝ→ℝ. Misalkan f ditafsirkan sebagai fungsi kuadrat. Ekspresi f(x) dan x² adalah term. Tulisan f(x)=x² adalah persamaan atau penetapan definisi, bukan term tunggal. Definisikan predikat P(x) sebagai x²≥4. Untuk x=−2, term kuadrat bernilai 4 dan P(−2) benar. Untuk x=1, term bernilai 1 dan P(1) salah. Untuk x=3, term bernilai 9 dan P(3) benar. Istilah “fungsi proposisional” menunjuk kondisi dengan tempat masukan semacam ini; ia tidak menyamakan predikat dengan fungsi numerik f.

Variabel Bebas dan Terikat Per Kemunculan

Status bebas atau terikat melekat pada setiap kemunculan variabel di dalam term formula. Dalam formula atomik, kemunculan-kemunculan itu bebas. Negasi dan konektif mempertahankan status dari subformula masing-masing. Pada ∀xφ atau ∃xφ, hanya kemunculan x yang bebas di dalam φ yang kemudian diikat oleh kuantifikator baru tersebut. Kemunculan yang sudah diikat kuantifikator lebih dalam tetap mengikuti pengikat terdekatnya. Contohnya, pada ∀x(P(x)∧∃xQ(x)), x pada P diikat ∀x, sedangkan x pada Q diikat ∃x. Formula ini dapat ditulis lebih jernih sebagai ∀x(P(x)∧∃zQ(z)), dengan z nama baru. Nama pada tanda ∀x sendiri adalah penanda pengikat, bukan kemunculan masukan bebas. Pembahasan kemunculan dan lingkup ini mengikuti konvensi umum yang diterangkan dalam forall x: Calgary [R2].

Contoh krusial yang sering membingungkan: perhatikan formula (∀x R(x, y)) ∧ S(x). Dalam konjung pertama ∀x R(x, y), kemunculan x terikat oleh ∀x, sedangkan kemunculan y bebas. Dalam konjung kedua S(x), kemunculan x bebas karena tidak berada dalam lingkup kuantifikator ∀x yang ada di konjung pertama. Dengan demikian, nama variabel "x" muncul dua kali dalam formula ini dengan status yang berbeda: sekali terikat (dalam konjung kiri) dan sekali bebas (dalam konjung kanan). Secara formal, himpunan variabel bebas FV dihitung secara rekursif: FV((∀x R(x,y)) ∧ S(x)) = FV(∀x R(x,y)) ∪ FV(S(x)) = {y} ∪ {x} = {x, y}. Himpunan variabel terikat BV = {x} juga. Perhatikan bahwa x ∈ FV ∩ BV—ini bukan kontradiksi, ini menunjukkan bahwa nama yang sama memainkan dua peran berbeda di posisi berbeda.

Makna semantik ditentukan oleh struktur M dan assignment s yang memberi setiap variabel nilai dalam semesta. Notasi M,s⊨φ berarti φ benar pada pasangan itu. Untuk predikat satu tempat P, formula P(t) benar tepat ketika nilai term t termasuk relasi yang menafsirkan P. Untuk predikat banyak tempat, yang diuji ialah tuple nilai term terhadap relasi yang sesuai. Formula φ∧ψ benar tepat ketika kedua bagiannya benar. Penetapan kepada variabel yang tidak bebas tidak mengubah nilai formula: bila s dan s′ sepakat pada FV(φ), maka M,s⊨φ jika dan hanya jika M,s′⊨φ. Pernyataan ini dikenal sebagai lemma koinsiden. Kita menuliskan “jika dan hanya jika” di metabahasa agar tidak mencampur penilaian semantik dengan formula dalam bahasa objek.

Menghitung FV secara rekursif

Untuk term t, tuliskan Var(t) sebagai himpunan variabel yang muncul di dalamnya. Maka FV(P(t₁,…,tₙ)) adalah gabungan Var(t₁),…,Var(tₙ), dan FV(t=u)=Var(t)∪Var(u). Selanjutnya FV(¬φ)=FV(φ), FV(φ∘ψ)=FV(φ)∪FV(ψ) untuk setiap konektif biner ∘, serta FV(∀xφ)=FV(∃xφ)=FV(φ)∖{x}. Aturan terakhir menghapus nama x dari daftar parameter bebas, bukan menghapus simbol x dari teks. Untuk φ=(∀xR(x,y))∧S(x), kita mendapat {y}∪{x}={x,y}. Dalam pemakaian BV di bab ini, BV mencatat nama variabel yang memiliki kemunculan terikat di tubuh formula; kemunculan nama pada penanda kuantifikator tidak dihitung sebagai masukan.

Kalimat Tertutup dan Penangkapan Variabel

Formula tanpa variabel bebas disebut kalimat tertutup (sentence). Nilai kebenarannya tidak bergantung pada assignment—hanya pada struktur M—sehingga kita dapat menulis M ⊨ φ tanpa menyebut s. Penting untuk dicatat: kalimat tertutup tidak otomatis valid. Kalimat ∃x(x>0) benar pada ℝ dengan urutan biasa. Pada struktur bersemesta {0}, dengan konstanta 0 menamai satu-satunya objek dan relasi > kosong, kalimat itu salah. Kalimat ∀x∀y(x = y) salah pada setiap domain dengan lebih dari satu elemen. Kevalidan memerlukan kebenaran pada semua struktur tak kosong.

Masalah penangkapan variabel (variable capture) muncul ketika kita melakukan substitusi term untuk variabel bebas. Substitusi x ↦ t dalam formula φ, ditulis φ[t/x], harus dilakukan dengan hati-hati agar term t tidak "ditangkap" oleh kuantifikator di dalam φ. Pertimbangkan formula ∃y(y > x) dengan variabel bebas x. Misalkan kita ingin mensubstitusi x ↦ y (misalnya karena dalam konteks pembuktian kita menginginkan instance dengan nilai y). Hasil naif adalah ∃y(y > y)—yang jelas-jelas memiliki makna berbeda dan umumnya salah. Variabel y yang kita masukkan "ditangkap" oleh kuantifikator ∃y di dalam formula. Solusinya adalah alpha-renaming: sebelum substitusi, ganti variabel terikat y menjadi nama segar, misalnya z, sehingga formula menjadi ∃z(z > x). Kini substitusi x ↦ y menghasilkan ∃z(z > y), yang mempertahankan y sebagai parameter bebas. Pada ℝ dengan urutan biasa, formula itu benar untuk setiap nilai y.

Ekspresi 1/x memerlukan perhatian tersendiri. Dalam analisis, fungsi r:ℝ∖{0}→ℝ dengan r(x)=1/x terdefinisi pada domain yang dinyatakan, sehingga kita hanya memakainya untuk x≠0. Dalam logika orde pertama dengan simbol fungsi total pada satu semesta, menaruh syarat x≠0 di depan sebuah implikasi tidak dengan sendirinya memberikan interpretasi pada term pembagian di x=0. Formalisasi tanpa fungsi parsial dapat memakai relasi Inv(x,y) yang berarti xy=1; pada x=0 relasi itu tidak memiliki saksi, tanpa pernah menulis 1/0. Pilihan lain adalah memperluas fungsi invers menjadi total dengan nilai buatan di 0, lalu membatasi teorema invers pada x≠0; nilai buatan itu bukan invers aritmetis nol. Kita tidak memerlukan pilihan tersebut di sini. Membatasi seluruh semesta menjadi ℝ∖{0} juga harus diperiksa terhadap simbol lain: penjumlahan tidak tertutup di semesta itu, sebab 1+(−1)=0. Domain bukan perbaikan mekanis yang boleh diterapkan tanpa memeriksa seluruh bahasa.

Apa yang sebenarnya berubah saat sebuah variabel diganti?

Ambil formula φ(x,y) = R(x,y) ∧ ∀x S(x,y). Dua kemunculan x di sini mempunyai tugas berbeda. Pada R(x,y), x merupakan masukan bebas. Pada S(x,y), x dikendalikan oleh ∀x yang langsung menaunginya. Jika kita memasukkan konstanta c untuk masukan bebas x, hasilnya ialah R(c,y) ∧ ∀x S(x,y). Mengganti x kedua juga akan menghapus pekerjaan kuantifikator dan menghasilkan pernyataan lain. Substitusi dalam formula karena itu tidak sama dengan fitur “ganti semua” dalam pengolah kata.

Aturan ini dapat dilihat tanpa terminologi teknis yang berat. Misalkan domainnya ℤ, R(u,v) berarti u>v, dan S(u,v) berarti u+v=v+u. Formula awal berbicara tentang satu masukan x yang lebih besar daripada y, sekaligus menyatakan komutativitas penjumlahan untuk semua masukan di posisi x yang kedua. Mengisi masukan pertama dengan 4 tidak boleh menyempitkan pernyataan komutativitas itu menjadi kasus 4 saja. Pembacaan struktur harus mendahului penggantian simbol.

Ada kesalahan yang lebih sulit dideteksi karena hasilnya tetap terlihat rapi. Pada φ(x)=∃y R(x,y), gantilah masukan bebas x dengan term f(y). Bila dilakukan secara harfiah, kita memperoleh ∃y R(f(y),y). Sekarang y di dalam f(y) menjadi terikat, padahal y yang hendak kita masukkan semula merupakan parameter dari luar. Cara yang sah ialah mengganti lebih dahulu nama variabel terikat dengan nama baru, misalnya z, lalu melakukan substitusi:

φ(x) ≡ ∃z R(x,z), sehingga φ[f(y)/x] = ∃z R(f(y),z).

Nama z harus dipilih sehingga tidak berbenturan dengan variabel relevan yang sudah ada. Sekadar memilih huruf berbeda dari y belum selalu cukup: jika z sudah muncul bebas pada formula yang lebih besar, penggantian itu dapat menangkap z. Dalam praktik, ambil nama yang sama sekali belum dipakai pada formula dan term yang sedang dikerjakan. Kita tidak mengubah objek matematika; kita memperbaiki penamaan agar peran tiap masukan terlihat.

Perbedaan tersebut dapat diuji pada domain {0,1}. Tafsirkan f sebagai fungsi konstan 0, dan R(u,v) sebagai u≠v. Pada formula yang benar, ∃z R(f(y),z), saksi z=1 selalu bekerja, apa pun nilai parameter y. Formula yang salah kebetulan juga benar pada contoh ini. Itu peringatan penting: satu contoh yang tidak membedakan dua formula tidak membuktikan penggantian tersebut sah. Untuk memisahkannya, gunakan f identitas dan R(u,v) sebagai u≠v. Formula benar menjadi ∃z(y≠z), yang benar bagi kedua nilai y. Formula salah menjadi ∃y(y≠y), yang salah. Model kecil sering lebih efektif daripada penjelasan panjang ketika kita ingin menemukan cacat sebuah aturan.

2.2 Kuantifikator Universal dan Eksistensial

Definisi Semantik Formal

Di subbab ini, D adalah semesta tak kosong dari struktur M. Klausa semantik untuk kuantifikator dibangun di atas konsep assignment yang diperbarui. Jika s adalah assignment dan a ∈ D, kita mendefinisikan assignment s[x ↦ a] sebagai fungsi yang identik dengan s kecuali pada variabel x, di mana nilainya adalah a. Dengan notasi ini:

M, s ⊨ ∀x φ jika dan hanya jika untuk setiap a ∈ D, berlaku M, s[x ↦ a] ⊨ φ. M, s ⊨ ∃x φ jika dan hanya jika terdapat a ∈ D sedemikian sehingga M, s[x ↦ a] ⊨ φ.

Kita menerapkan kedua klausa tersebut dalam kerangka semesta tak kosong yang telah disepakati. Untuk universal, setiap pembaruan nilai x harus memenuhi φ; untuk eksistensial, cukup satu pembaruan yang berhasil. Penetapan variabel lain tetap sama. Jika φ juga memuat y bebas, kuantifikasi x tidak memilih nilai baru bagi y. Cara membaca ini akan penting ketika satu saksi dipilih sesudah parameter lain ditetapkan.

Kuantifikasi Terbatas dan Dua Tafsirnya

Dalam matematika, kita sering menulis ∀x ∈ A P(x) dan ∃x ∈ A P(x). Ini bukan konstruksi baru dalam logika predikat; keduanya adalah singkatan definitorial. Secara formal:

∀x ∈ A P(x)  adalah singkatan dari  ∀x(x ∈ A → P(x)). ∃x ∈ A P(x)  adalah singkatan dari  ∃x(x ∈ A ∧ P(x)).

Pilihan konektor yang berbeda—implikasi untuk universal, konjungsi untuk eksistensial—bukan arbitrer. Pertimbangkan klaim ∀x ∈ ∅ P(x). Ini menjadi ∀x(x ∈ ∅ → P(x)). Karena anteseden x ∈ ∅ selalu salah, implikasi selalu benar secara vakum: pernyataan universal atas himpunan kosong adalah benar. Ini konsisten dengan intuisi "tidak ada contoh penyangkal." Sekarang ∃x ∈ ∅ P(x) menjadi ∃x(x ∈ ∅ ∧ P(x)). Karena konjung pertama selalu salah, tidak ada x yang memenuhi kondisi, sehingga pernyataan eksistensial atas himpunan kosong adalah salah. Ini juga konsisten: klaim keberadaan atas populasi kosong tak dapat dipenuhi.

Perhatikan implikasi penting: kebenaran universal kosong bukan bukti keberadaan. Pernyataan ∀x ∈ ∅ (x = x ∧ x ≠ x) benar—padahal ia mengklaim bahwa semua elemen himpunan kosong memenuhi kontradiksi! Kebenaran ini bermakna semantik (tidak ada contoh penyangkal), bukan bermakna ontologis (ada objek demikian).

Domain Mengubah Nilai Kebenaran: Contoh √2

Nilai kebenaran kalimat eksistensial sangat bergantung pada domain struktur. Pertimbangkan kalimat ∃x(x² = 2). Dalam domain ℤ: tidak ada bilangan bulat yang kuadratnya tepat 2, sehingga kalimat ini salah. Dalam domain ℚ: dengan argumen yang akan dikembangkan sepenuhnya di Bab 8 (kita tidak akan mengulangi bukti irasionalitas √2 di sini), tidak ada bilangan rasional yang kuadratnya 2, sehingga kalimat ini salah di ℚ. Dalam domain ℝ: bilangan irasional √2 ada sebagai elemen ℝ (dijamin oleh sifat lengkap ℝ), sehingga kalimat ini benar. Contoh ini memperlihatkan bahwa kalimat "sama" dapat memiliki nilai kebenaran berlainan pada struktur berbeda. Makna operasi dan domain harus diketahui, meskipun penulis tidak selalu mengulangnya sesudah konteks ditetapkan.

Kalimat ∀x∈ℝ(x²≥0) benar berdasarkan sifat urutan bilangan riil. Bila x>0, perkalian x dengan dirinya positif. Bila x<0, tulis x=−u dengan u>0, sehingga x²=u²>0. Bila x=0, kuadratnya 0. Ketiga kemungkinan itu mencakup semua x∈ℝ. Angka (−2)²=4 dan 1,5²=2,25 merupakan ilustrasi perhitungan. Kita tidak boleh begitu saja memindahkan formula berurutan ini ke ℂ: simbol ≥ belum memiliki interpretasi yang disepakati di sana, dan ℂ tidak mempunyai urutan lapangan yang memperluas urutan biasa pada ℝ. Fakta i²=−1 tidak membolehkan kita memperlakukan semua bilangan kompleks sebagai bilangan yang terurut seperti bilangan riil.

Keunikan: ∃! dan Formulasinya

Kuantifikator ∃! (dibaca "terdapat tepat satu") bukan primitif logika predikat standar, melainkan didefinisikan sebagai:

∃!x P(x)  ≡  ∃x(P(x) ∧ ∀y(P(y) → y = x)).

Formula ini menyatakan dua hal: (1) ada setidaknya satu x yang memenuhi P, dan (2) siapa pun yang memenuhi P haruslah sama dengan x tersebut. Contoh: dalam ℝ, setiap bilangan a memiliki tepat satu invers aditif, yaitu −a, yang memenuhi a + (−a) = 0. Kalimat ∀a∈ℝ ∃!b∈ℝ (a + b = 0) dapat diverifikasi: keberadaan b = −a adalah aksioma lapangan, dan keunikannya mengikuti dari a + b = 0 = a + b' ⟹ b = b' menggunakan hukum pembatalan. Sebaliknya, persamaan x² = 4 memiliki dua solusi di ℝ (x = 2 dan x = −2), sehingga ∃!x∈ℝ (x² = 4) adalah salah.

Aturan Instansiasi, Generalisasi, dan Saksi Eksistensial

Dalam sistem deduktif, kuantifikator memiliki aturan eliminasi dan introduksi yang memerlukan kehati-hatian. Instansiasi Universal (UI): dari ∀x P(x), kita boleh menyimpulkan P(t) untuk term t apa pun yang bebas dari penangkapan dalam P. Term tersebut harus terdefinisi dalam bahasa dan struktur yang sedang dipakai; syarat bebas dari penangkapan tidak boleh dihilangkan. Generalisasi Universal (UG): dari P(x) di mana x adalah variabel arbitrer yang tidak bergantung pada asumsi apa pun dalam pembuktian saat ini, kita boleh menyimpulkan ∀x P(x). Kata "arbitrer" di sini sangat krusial: variabel x tidak boleh muncul bebas dalam asumsi aktif pembuktian, karena itu akan berarti kita telah mengasumsikan sesuatu khusus tentang x.

Introduksi eksistensial: bila P(t) telah dibuktikan untuk term t yang sah dan bebas dari penangkapan pada substitusi, kita boleh menyimpulkan ∃xP(x). Nilai t menyediakan satu saksi; kesimpulan tidak mengklaim bahwa saksi itu satu-satunya.

Eliminasi eksistensial memakai subbukti. Dari ∃xP(x), buka asumsi sementara P(c), dengan c parameter atau konstanta baru. Turunkan kesimpulan C tanpa memakai sifat khusus c selain P(c). Lalu tutup subbukti dan simpulkan C, asalkan c tidak muncul dalam C maupun dalam premis atau asumsi terbuka dari luar subbukti. Jika c ditulis sebagai konstanta, larangannya adalah tidak muncul sama sekali pada tempat-tempat tersebut; istilah “bebas” secara teknis dipakai untuk variabel. Menutup asumsi P(c) merupakan langkah wajib: aturan ini tidak membenarkan menyatakan P(c) sebagai fakta dengan nama objek yang telah ditentukan sebelumnya.

Kesalahan umum: dari premis ∃x P(x) dan premis terpisah ∃x Q(x), kita tidak boleh menyimpulkan bahwa ada objek tunggal yang memenuhi P sekaligus Q. Masing-masing premis memberikan saksinya sendiri—c₁ untuk P dan c₂ untuk Q—dan keduanya bisa saja berbeda. Misalnya: dalam ℤ, ∃x(x > 100) benar (saksi: 101) dan ∃x(x < −100) benar (saksi: −101), tetapi tidak ada satu objek yang sekaligus lebih besar dari 100 dan lebih kecil dari −100.

Subbukti yang Menutup Saksi dengan Benar

Dari premis ∀x(P(x)→Q(x)) dan ∃xP(x), kita ingin menurunkan ∃xQ(x). Buka subbukti dengan P(c), di mana c nama baru. Instansiasi premis universal memberi P(c)→Q(c). Modus ponens menghasilkan Q(c). Introduksi eksistensial lalu memberi ∃xQ(x). Kesimpulan terakhir sudah tidak menyebut c, sehingga kita boleh menutup asumsi sementara P(c) dan memakai eliminasi eksistensial terhadap premis ∃xP(x). Yang disimpulkan adalah adanya suatu objek yang memenuhi Q, bukan bahwa objek dengan nama lama tertentu pasti memenuhi Q. Dengan notasi Bab 1, dua premis itu menurunkan ∃xQ(x) melalui ⊢; penjelasan memakai objek saksi juga memperlihatkan mengapa konsekuensi semantiknya, ⊨, berlaku.

Bandingkan generalisasi yang tidak sah: dari asumsi P(c), lalu menulis ∀xP(x). Nama c dalam asumsi itu tidak arbitrer terhadap bukti, sebab bukti memerlukan sifat P(c) yang baru diasumsikan. Sebaliknya, untuk membuktikan ∀x(x=x), ambil parameter c sebarang, gunakan refleksivitas kesamaan, lalu generalisasikan. Tidak ada asumsi terbuka yang menuntut sifat khusus c.

Tiga tingkat klaim yang sering tertukar

Kalimat tertutup, kalimat benar pada sebuah struktur, dan kalimat valid secara logis bukan tiga nama untuk hal yang sama. Kalimat ∀x∀y(x+y=y+x) tertutup karena tidak memiliki variabel bebas. Jika + ditafsirkan sebagai penjumlahan biasa pada ℤ, kalimat itu benar. Namun kebenarannya tidak lahir dari bentuk logis saja. Pada domain {0,1}, tafsirkan simbol biner + sebagai proyeksi pertama, yaitu u+v=u. Untuk u=0 dan v=1, u+v=0 sedangkan v+u=1. Kalimat komutativitas gagal pada struktur itu.

Sebaliknya, ∀x(x=x) benar pada setiap struktur dengan kesamaan yang ditafsirkan sebagai identitas. Kesimpulan ini memakai konvensi tentang simbol kesamaan, bukan sifat khusus bilangan bulat. Jika suatu teori T memuat aksioma yang memaksa + komutatif, kita dapat menulis T ⊨ ∀x∀y(x+y=y+x). Pernyataan tersebut berbeda dari ⊨ ∀x∀y(x+y=y+x), yang mengklaim validitas tanpa pembatas teori. Simbol ⊢ digunakan ketika kita membicarakan turunan formal dari aksioma dan aturan tertentu. Pemisahan yang dibuat dalam Bab 1 tetap berlaku setelah kuantifikator diperkenalkan.

Ketelitian ini berguna saat seseorang berkata, “rumus itu benar untuk semua x.” Kita masih perlu bertanya: semua x dari domain apa, dengan operasi yang ditafsirkan bagaimana, dan dengan asumsi apa? Di dalam satu pembuktian aritmetis, kita biasanya sudah menyepakati jawaban itu sehingga tidak perlu mengulangnya pada setiap baris. Tetapi ketika berpindah ke pembuktian tentang logika itu sendiri, kesepakatan aritmetis tidak boleh diam-diam dibawa masuk.

2.3 Pertukaran dan Negasi Kuantifikator Ganda

Komutativitas Kuantifikator Sejenis

Ketika dua kuantifikator dari jenis yang sama berurutan, urutannya dapat ditukar tanpa mengubah nilai kebenaran kalimat. Secara formal: ∀x∀y φ ≡ ∀y∀x φ dan ∃x∃y φ ≡ ∃y∃x φ. Pembuktian untuk kasus universal bersifat langsung: M, s ⊨ ∀x∀y φ berarti untuk setiap a ∈ D, untuk setiap b ∈ D, berlaku M, s[x↦a][y↦b] ⊨ φ. Ini adalah kondisi atas semua pasangan (a,b)∈D². Untuk variabel x dan y yang berbeda, pembaruan s[x↦a][y↦b] sama dengan s[y↦b][x↦a]. Yang tidak berubah ialah cakupan semua pasangan, bukan tuntutan bahwa relasi φ simetris. Contohnya, predikat x<y tidak simetris, tetapi dua kalimat universal yang mempertukarkan urutan kuantifikator tetap ekuivalen. Kasus eksistensial serupa: adanya pasangan (a,b) yang memenuhi φ tidak berubah bila urutan pemilihan koordinat ditukar.

Namun kuantifikator campuran tidak komutatif. Kita telah menyinggung ini di Bab 1; sekarang kita membuktikannya secara eksplisit. Klaim: ∃y∀x R(x, y) ⊨ ∀x∃y R(x, y), tetapi implikasi arah sebaliknya tidak berlaku secara umum. Untuk membuktikan arah pertama: asumsikan M, s ⊨ ∃y∀x R(x, y). Maka ada b ∈ D sehingga untuk semua a ∈ D, M, s[x↦a][y↦b] ⊨ R(x, y), yaitu R(a, b) benar. Ambil sembarang a ∈ D; saksi b yang sama membuktikan ∃y R(a, y). Karena a arbitrer, ∀x∃y R(x, y) benar.

Untuk contoh penyangkal arah sebaliknya, ambil domain D = {0, 1} dan relasi R didefinisikan sebagai: R(0, 0) = B, R(0, 1) = S, R(1, 0) = S, R(1, 1) = B. Dalam bahasa matriks (baris = nilai x, kolom = nilai y):

R(x,y) y=0 y=1 x=0 Benar Salah x=1 Salah Benar

Untuk ∀x∃y R(x, y): untuk x = 0, saksi y = 0; untuk x = 1, saksi y = 1. Jadi ∀x∃y R(x, y) benar. Namun ∃y∀x R(x, y) memerlukan satu y yang bekerja untuk semua x: y = 0 gagal karena R(1, 0) salah; y = 1 gagal karena R(0, 1) salah. Jadi ∃y∀x R(x, y) salah. Ini membuktikan bahwa implikasi balik tidak berlaku.

Permainan Saksi dan Kuantifikator Tiga Lapis

Cara paling intuitif untuk memahami kuantifikator ganda adalah melalui analogi permainan adversarial. Pertimbangkan kalimat ∀x∃y∀z (y > x + z) di ℝ. Bacaan permainan: pemain ∀ memilih x sembarang, lalu pemain ∃ harus menyediakan y (boleh bergantung pada x yang dipilih), lalu pemain ∀ memilih z sembarang, dan kita cek apakah y > x + z. Kalimat ini mustahil benar di ℝ: setelah pemain ∃ memilih y (nilai tetap), pemain ∀ dapat memilih z = y − x + 1000, sehingga x + z = y + 1000 > y, membuat kondisi gagal. Nilai y tidak dapat mengantisipasi pilihan z yang belum diketahui saat y dipilih.

Sebaliknya, ∀x∀z∃y (y > x + z) benar di ℝ: setelah pemain ∀ memilih x dan z (keduanya tetap), pemain ∃ mengetahui kedua nilai itu dan dapat memilih y = x + z + 1 sebagai saksi. Perbedaan antara dua kalimat ini adalah posisi ∃y: apakah y harus dipilih sebelum (tidak mengetahui) atau setelah (mengetahui) z. Ini adalah manifestasi paling konkret dari ketergantungan saksi.

Negasi Kuantifikator dan Hukum De Morgan Umum

Negasi kuantifikator mengikuti hukum dualitas yang merupakan generalisasi hukum De Morgan. Secara formal:

¬∀x φ ≡ ∃x ¬φ ¬∃x φ ≡ ∀x ¬φ

Pembuktian ekuivalensi pertama: M, s ⊨ ¬∀x φ iff tidak berlaku M, s ⊨ ∀x φ iff tidak untuk semua a ∈ D berlaku M, s[x↦a] ⊨ φ iff ada a ∈ D sehingga M, s[x↦a] ⊭ φ iff ada a ∈ D sehingga M, s[x↦a] ⊨ ¬φ iff M, s ⊨ ∃x ¬φ. Dengan mengaplikasikan aturan ini berulang, kita mendapat:

¬∀x∃y P(x, y) ≡ ∃x∀y ¬P(x, y) ¬∃x∀y P(x, y) ≡ ∀x∃y ¬P(x, y)

Perlu diperhatikan tentang negasi implikasi: ¬(A → B) ≡ A ∧ ¬B, bukan A → ¬B. Kesalahan ini sering muncul dalam pembuktian ketiadaan limit. Untuk kuantifikasi terbatas: ¬∀x∈A P(x) ≡ ∃x∈A ¬P(x) dan ¬∃x∈A P(x) ≡ ∀x∈A ¬P(x)—ini mengikuti langsung dari definisi singkatan.

Distribusi Kuantifikator atas Konektor

Dua ekuivalensi distribusi yang sah:

∀x(φ ∧ ψ) ≡ (∀x φ) ∧ (∀x ψ) ∃x(φ ∨ ψ) ≡ (∃x φ) ∨ (∃x ψ)

Implikasi yang tidak sah dalam arah tertentu: (1) (∀x φ) ∨ (∀x ψ) ⊨ ∀x(φ ∨ ψ) sah, tetapi arah sebaliknya gagal. (2) ∃x(φ ∧ ψ) ⊨ (∃x φ) ∧ (∃x ψ) sah, tetapi arah sebaliknya gagal. Kontraeksempel untuk ∀x(φ ∨ ψ) ⊨ (∀x φ) ∨ (∀x ψ): ambil domain ℤ, φ(x) ≡ "x genap", ψ(x) ≡ "x ganjil". Setiap bilangan bulat genap atau ganjil, jadi ∀x(φ ∨ ψ) benar. Tetapi tidak semua bilangan genap (∀x φ salah: 1 ganjil) dan tidak semua bilangan ganjil (∀x ψ salah: 2 genap). Jadi disjungsi (∀x φ) ∨ (∀x ψ) salah.

Studi Kasus Mendalam: Limit, Negasinya, dan Keseragaman

Tetapkan D⊆ℝ dan fungsi f:D→ℝ, serta titik a∈ℝ yang merupakan titik akumulasi D, dan kandidat L∈ℝ. Titik akumulasi berarti: untuk setiap ρ>0, terdapat x∈D dengan 0<|x−a|<ρ. Titik a sendiri tidak harus termasuk D. Dengan konvensi ini, lim_{x→a}f(x)=L berarti rumus berikut; ε dan δ adalah bilangan riil positif. Definisi ini dapat diperiksa pada Basic Analysis §3.1 [R3].

∀ε > 0 ∃δ > 0 ∀x ∈ D [0 < |x − a| < δ → |f(x) − L| < ε]

Negasi dari definisi ini—yang menyatakan "L bukan limit f di a"—adalah:

∃ε₀ > 0 ∀δ > 0 ∃x ∈ D [0 < |x − a| < δ ∧ |f(x) − L| ≥ ε₀]

Perhatikan dengan cermat mengapa konektor berubah dari implikasi (→) menjadi konjungsi (∧): kita menerapkan ¬(A → B) ≡ A ∧ ¬B. Pernyataan “tidak ada limit hingga bernilai riil” lebih kuat lagi: ∀L ∈ ℝ berlaku negasi di atas, di mana ε₀ boleh bergantung pada L. Perbedaan antara "L bukan limit" dan "limit tidak ada" penting: yang pertama berbicara tentang nilai kandidat spesifik, yang kedua berbicara tentang ketiadaan nilai limit apa pun.

Langkah Negasi tanpa Lompatan

Untuk melihat semua perubahan sekaligus, sebut A(x,δ) kondisi 0<|x−a|<δ dan B(x,ε) kondisi |f(x)−L|<ε. Mulai dari ¬[∀ε>0∃δ>0∀x∈D(A→B)]. Negasi universal ε menghasilkan ∃ε₀>0¬[∃δ>0∀x∈D(A→B)]. Negasi eksistensial δ menghasilkan ∃ε₀>0∀δ>0¬[∀x∈D(A→B)]. Negasi universal x menghasilkan ∃ε₀>0∀δ>0∃x∈D¬(A→B). Terakhir, ¬(A→B)≡A∧¬B dan ¬(|f(x)−L|<ε₀) berarti |f(x)−L|≥ε₀. Domain pembatas tetap; kita tidak mencari ε≤0 atau x di luar D.

Galat sebesar ε₀ yang tepat sama dengan batas sudah cukup untuk menggagalkan syarat <ε₀. Karena itu, negasi langsung pada batas ε₀ yang sama harus memakai ≥. Untuk keseluruhan pernyataan eksistensial tentang adanya ε₀, bentuk dengan > sebenarnya ekuivalen: dari galat ≥ε₀ kita mendapat galat >ε₀/2, lalu memakai ambang positif yang lebih kecil. Perubahan ambang itulah yang membenarkan bentuk alternatif, bukan sekadar mengganti tanda pada angka yang sama. Sebaliknya, syarat kedekatan 0<|x−a|<δ tidak dinegasikan: penyangkal harus benar-benar berada di lingkungan berlubang yang dijanjikan. Memilih x jauh dari a, atau memilih x=a, tidak menggagalkan janji limit.

Bukti: lim_{x→2} x² = 4

Klaim: Untuk setiap ε > 0, terdapat δ > 0 sehingga untuk semua x ∈ ℝ dengan 0 < |x − 2| < δ, berlaku |x² − 4| < ε.

Bukti. Faktorkan |x²−4|=|x−2|·|x+2|. Ambil ε>0 sebarang dan pilih δ=min(1,ε/5)>0. Syarat δ≤1 memberi batas lokal: jika |x−2|<δ, maka 1<x<3 dan |x+2|<5. Karena itu, cukup menjamin 5δ≤ε; ketaksamaan ketat yang diperlukan sudah datang dari |x−2|<δ. Kita tidak memerlukan 5δ<ε. Untuk setiap x dengan 0<|x−2|<δ:

1. |x − 2| < 1, sehingga |x + 2| < 5; dan 2) |x − 2| < ε/5. Oleh karena itu |x² − 4| < (ε/5) · 5 = ε. ∎

Verifikasi numerik: Ambil ε = 0.1. Maka δ = min(1, 0.1/5) = min(1, 0.02) = 0.02. Ambil x = 2.01, sehingga |x − 2| = 0.01 < 0.02 = δ. Hitung: x² = (2.01)² = 4.0401. Maka |x² − 4| = 0.0401 < 0.1 = ε. ✓ Ambil x = 1.99, |x − 2| = 0.01: x² = 3.9601, |x² − 4| = 0.0399 < 0.1. ✓

Bukti: f(x) = sgn(x) tidak memiliki limit di x = 0

Definisikan f: ℝ \ {0} → ℝ dengan f(x) = 1 untuk x > 0 dan f(x) = −1 untuk x < 0. Klaim: tidak ada L ∈ ℝ sehingga lim_{x→0} f(x) = L.

Bukti. Misalkan L ∈ ℝ sembarang. Pilih ε₀ = 1. Ambil δ > 0 sembarang. Kita harus menunjukkan ada x dengan 0 < |x| < δ dan |f(x) − L| ≥ 1. Kasus 1: L ≥ 0. Pilih x = −δ/2. Maka 0 < |x| = δ/2 < δ, dan f(x) = −1. Maka |f(x) − L| = |−1 − L| = 1 + L ≥ 1 = ε₀. Kasus 2: L < 0. Pilih x = δ/2. Maka 0 < |x| = δ/2 < δ, dan f(x) = 1. Maka |f(x) − L| = |1 − L| = 1 + |L| > 1 = ε₀. Dalam kedua kasus, untuk δ > 0 sembarang kita menemukan x yang melanggar kondisi limit. Karena L ∈ ℝ sembarang, limit tidak ada. ∎

Kontinuitas Titikwise versus Keseragaman

Untuk D⊆ℝ dan fungsi f:D→ℝ, kontinuitas di setiap titik domain ditulis

∀a∈D ∀ε>0 ∃δ>0 ∀x∈D [|x−a|<δ → |f(x)−f(a)|<ε].

Kontinuitas seragam ditulis

∀ε>0 ∃δ>0 ∀a∈D ∀x∈D [|x−a|<δ → |f(x)−f(a)|<ε].

Pada formula pertama, δ boleh bergantung pada a dan ε. Pada formula kedua, satu δ harus bekerja pada seluruh D setelah ε diberikan. Kedua definisi menyertakan x=a; tidak ada syarat 0<|x−a|. Definisi kontinuitas dan kontinuitas seragam diperiksa pada [R4] dan [R5].

Fungsi f(x)=x² kontinu di setiap a∈ℝ. Ambil a dan ε>0 sebarang, lalu pilih δ=min(1,ε/(2|a|+1))>0. Untuk |x−a|<δ, ketaksamaan segitiga memberi |x+a|≤|x−a|+2|a|<2|a|+1. Jika x=a, selisih kuadrat nol. Jika x≠a, maka |x²−a²|=|x−a||x+a|<δ(2|a|+1)≤ε. Pilihan δ ini bergantung pada a. Ketergantungan suatu pilihan δ belum membuktikan kegagalan kontinuitas seragam, sebab mungkin ada pilihan lain yang lebih baik. Untuk menyangkal keseragaman, kita harus menggagalkan setiap δ yang ditawarkan.

Untuk menyangkal kontinuitas seragam x² pada ℝ, pilih ε₀=1. Diberikan δ>0 sebarang, ambil h=δ/2, a=1/h, dan x=a+h. Kedua titik merupakan bilangan riil dan |x−a|=h<δ, tetapi |x²−a²|=2ah+h²=2+h²>1. Jadi setiap kandidat δ gagal. Sebaliknya, pada D=[−M,M] dengan M>0, kedua titik a,x∈D memenuhi |x+a|≤2M. Pilih δ=ε/(2M)>0. Jika |x−a|<δ, maka |x²−a²|≤2M|x−a|<2Mδ=ε. Pilihan ini tidak bergantung pada a. Jika M=0, domainnya {0}; fungsi otomatis kontinu seragam, misalnya dengan δ=1 untuk setiap ε>0, karena selisih nilai selalu nol.

Memindahkan kuantifikator tanpa merusak parameter

Salah satu alasan orang ingin memindahkan kuantifikator ialah agar semua pilihan objek tampak di bagian depan formula. Proses ini tidak boleh dikerjakan sebagai pemindahan huruf semata. Pertimbangkan

(∀x P(x)) ∨ Q(x).

Kemunculan x pada Q(x) bebas. Mengubah formula itu menjadi ∀x(P(x)∨Q(x)) memperluas jangkauan pengikatan sampai ke Q dan mengubah makna. Pada domain {0,1}, ambil P(0) benar, P(1) salah, dan Q(u) berarti u=1. Beri masukan bebas x nilai 0. Formula awal salah: ∀xP(x) salah dan Q(0) salah. Formula hasil pemindahan justru benar: pada 0 bagian P benar, pada 1 bagian Q benar. Kesalahan tersebut tidak dapat diperbaiki dengan argumen bahwa kedua ekspresi sama-sama memakai ∀ dan ∨.

Langkah aman dimulai dengan penggantian nama terikat:

(∀z P(z)) ∨ Q(x) ≡ ∀z(P(z)∨Q(x)).

Kini z tidak bebas di Q(x). Selama z berjalan di seluruh domain, nilai Q(x) tetap, karena x masih merupakan masukan dari luar. Jika Q(x) benar, kedua sisi benar. Jika Q(x) salah, kedua sisi menuntut P(z) untuk setiap z. Inilah alasan semantiknya. Syarat “z tidak bebas pada Q(x)” menjamin nilai bagian yang dipindahkan melewati kuantifikator tidak diam-diam ikut berubah.

Dengan disiplin serupa, kita dapat memeriksa

∀x(P(x) → ∃y R(x,y)) ≡ ∀x∃y(P(x) → R(x,y))

pada domain struktur tak kosong. Untuk x yang memenuhi P, sisi kiri menyediakan saksi yang diperlukan. Untuk x yang tidak memenuhi P, pilih sembarang anggota domain sebagai y; kondisional benar karena antesedennya salah. Arah balik langsung: bila P(x) benar, saksi y pada sisi kanan harus memenuhi R(x,y). Langkah “pilih sembarang anggota” menggunakan ketersediaan nilai bagi y. Untuk seluruh formula dengan ∀x terluar pada satu semesta yang sama, kedua sisi juga benar bila semesta itu kosong. Jadi jangan membaca argumen ini sebagai bukti bahwa semesta tak kosong merupakan syarat perlu bagi ekuivalensi lengkap tersebut. Perbedaannya menjadi nyata ketika domain y dibatasi secara terpisah.

Jika kuantifikasi y dibatasi pada himpunan B yang mungkin kosong, jangan menerapkan bentuk tadi tanpa pemeriksaan. Ambil domain x={0}, B=∅, dan P(0) salah. Pernyataan ∀x(P(x)→∃y∈B R(x,y)) benar, sebab anteseden selalu salah. Tetapi ∀x∃y∈B(P(x)→R(x,y)) salah karena tidak ada y∈B. Mengabaikan pembatas domain dapat mengubah pernyataan benar menjadi salah meskipun pola simbol tampak familiar.

Ketunggalan limit menguji urutan pilihan

Definisi limit bukan hanya memberikan resep pembuktian eksistensi. Ia juga cukup kuat untuk membuktikan bahwa limit, jika ada, hanya satu. Hasil ini membantu kita melihat mengapa titik akumulasi merupakan syarat substantif.

Misalkan a titik akumulasi D, dan f:D→ℝ mempunyai limit L serta M ketika x mendekati a. Andaikan L≠M. Tetapkan ε=|L−M|/3, yang positif. Definisi untuk L memberikan δ₁>0; definisi untuk M memberikan δ₂>0. Kita sekarang membutuhkan satu x yang memenuhi kedua kendali sekaligus. Pilih radius δ=min(δ₁,δ₂)>0. Karena a titik akumulasi D, terdapat x∈D dengan 0<|x−a|<δ. Untuk x yang sama ini, dua perkiraan berikut berlaku:

|f(x)−L|<ε dan |f(x)−M|<ε.

Dengan ketaksamaan segitiga,

|L−M| ≤ |L−f(x)|+|f(x)−M| < 2ε = 2|L−M|/3.

Membagi dengan bilangan positif |L−M| menghasilkan 1<2/3, kontradiksi. Jadi L=M.

Perhatikan penjadwalan pilihan dalam bukti ini. ε dipilih setelah L dan M diketahui. Radius δ₁ dan δ₂ kemudian boleh bergantung pada ε serta fungsi dan titik yang sedang dibahas. Satu x dipilih terakhir, sesudah kedua radius tersedia. Kita tidak memakai dua saksi x yang berlainan, sebab ketaksamaan segitiga memerlukan nilai f pada objek yang sama. Operasi min merupakan cara memperoleh satu lingkungan yang cukup kecil untuk memenuhi kedua tuntutan.

Apa yang gagal tanpa titik akumulasi? Ambil D={2}, a=2, dan f(2)=7. Dengan δ=1 tidak ada x∈D yang memenuhi 0<|x−2|<δ. Maka implikasi dalam rumus ε–δ benar untuk setiap kandidat L, semata-mata karena antesedennya tidak pernah terpenuhi. Rumus itu tidak lagi memilih satu nilai limit. Sebaliknya, kontinuitas pada domain satu titik tetap wajar: syarat |x−2|<δ mengizinkan x=2, dan |f(2)−f(2)|=0<ε. Membedakan limit berlubang dan kontinuitas mencegah kita memperlakukan dua definisi yang berdekatan seolah-olah identik.

2.4 Aplikasi dalam Pembuktian Matematika Diskrit

Keterbagian dan Transitivitasnya

Untuk a,b∈ℤ, definisikan a|b jika dan hanya jika ada k∈ℤ dengan b=ak. Definisi ini mengizinkan a=0: pernyataan 0|b benar tepat ketika b=0. Kita akan membuktikan keterbagian dengan menampilkan saksi k secara eksplisit. Secara logis, pembuktian eksistensial juga dapat memakai cara lain; definisi tersebut tidak memaksa setiap bukti matematika menjadi algoritme konstruksi.

Proposisi (Transitivitas keterbagian): ∀a, b, c ∈ ℤ [(a | b ∧ b | c) → a | c].

Bukti. Misalkan a, b, c ∈ ℤ sembarang. Asumsikan a | b dan b | c. Dari a | b, ada k ∈ ℤ dengan b = a · k (saksi pertama). Dari b | c, ada ℓ ∈ ℤ dengan c = b · ℓ (saksi kedua—perhatikan bahwa k dan ℓ adalah saksi dari dua premis berbeda; nilainya mungkin sama atau berbeda, tetapi kita tidak boleh mengasumsikan persamaan mereka). Substitusikan: c = b · ℓ = (a · k) · ℓ = a · (k · ℓ). Karena k · ℓ ∈ ℤ (hasil kali dua bilangan bulat adalah bilangan bulat), kita memiliki saksi m = k · ℓ ∈ ℤ sehingga c = a · m. Oleh definisi, a | c. ∎

Catatan penting: kita sama sekali tidak membagi dengan a. Ini benar karena kita bekerja dengan definisi eksistensial—kita hanya mengkonstruksi saksi. Jika a = 0: dari b = 0·k kita mendapat b = 0; dari c = b·ℓ = 0 kita mendapat c = 0; dan 0 | 0 karena 0 = 0·(apapun). Kasus a = 0 tetap valid tanpa perlakuan khusus.

Paritas: n(n+1) Selalu Genap dan Kuadrat Ganjil

Proposisi: ∀n ∈ ℤ, 2 | n(n+1).

Bukti. Misalkan n ∈ ℤ sembarang. Menurut pembagian bilangan bulat dengan sisa oleh 2, setiap n dapat ditulis n=2k+r dengan k∈ℤ dan r∈{0,1}. Karena itu ada dua kasus yang mencakup semua kemungkinan: (i) n = 2k untuk suatu k ∈ ℤ (n genap), atau (ii) n = 2k+1 untuk suatu k ∈ ℤ (n ganjil). Dalam kasus (i): n(n+1) = 2k(2k+1). Saksi untuk 2 | n(n+1): m = k(2k+1) ∈ ℤ, sehingga n(n+1) = 2m. Dalam kasus (ii): n(n+1) = (2k+1)(2k+2) = (2k+1)·2(k+1). Saksi: m = (2k+1)(k+1) ∈ ℤ, sehingga n(n+1) = 2m. Dalam kedua kasus, 2 | n(n+1). ∎

Contoh angka: n = 7 (ganjil, k = 3): n(n+1) = 7·8 = 56 = 2·28. Saksi: m = 4·7 = 28. n = −3 (ganjil, k = −2): n(n+1) = (−3)(−2) = 6 = 2·3. Saksi: m = 3. n = 4 (genap, k = 2): n(n+1) = 4·5 = 20 = 2·10. Saksi: m = 2·5 = 10. ✓

Proposisi: ∀n ∈ ℤ [n² ganjil ↔ n ganjil].

Bukti (⟹): Kontraposisi—jika n genap (n = 2k), maka n² = 4k² = 2(2k²) genap. (⟸): Jika n ganjil (n = 2k+1), maka n² = 4k²+4k+1 = 2(2k²+2k)+1 ganjil. ∎

Kongruensi Modular dan Pemisahan Simbol

Tetapkan modulus n∈ℤ dengan n≥1. Definisikan a≡b (mod n) jika dan hanya jika n|(a−b), atau setara dengan adanya k∈ℤ sehingga a−b=nk. Simbol ≡ yang diikuti keterangan modulus menyatakan relasi aritmetis antara bilangan. Ini berbeda dari φ≡ψ, yang menyatakan ekuivalensi logis antara formula. Menulis modulus secara lengkap mencegah kedua pemakaian bercampur.

Contoh: 17 ≡ 2 (mod 5) karena 17 − 2 = 15 = 5·3; saksi k = 3. Pernyataan ∀a, b ∈ ℤ [a ≡ b (mod n) → a² ≡ b² (mod n)] benar: dari a − b = nk, kita punya a² − b² = (a−b)(a+b) = nk(a+b), sehingga n | (a² − b²). Saksi: m = k(a+b).

Formulasi Kuantifikator untuk Kebenaran Algoritma

Relasi spesifikasi R dari masukan D ke keluaran C dapat memenuhi ∀i∈D∃o∈C R(i,o). Formula ini menyatakan adanya keluaran yang diizinkan pada setiap masukan. Ia belum membuktikan bahwa suatu algoritme A benar. Untuk kebenaran total A, kita juga harus membuktikan bahwa setiap eksekusi yang relevan selesai dan hasil yang benar-benar dikeluarkannya memenuhi R. Algoritme yang terus berulang tanpa mengeluarkan hasil tidak menjadi benar total hanya karena solusi matematis bagi masukannya ada. Pembuktian terminasi dan ketepatan hasil merupakan kewajiban yang terpisah.

Penugasan Tugas dan Masalah Kemunculan Ganda Saksi

Misalkan J={j₁,j₂,j₃} dan C={c₁,c₂}. Dengan urutan (kandidat,pekerjaan), pasangan yang diizinkan tepat (c₁,j₁), (c₁,j₂), dan (c₂,j₃). Setiap pekerjaan memiliki kandidat, sehingga ∀j∈J∃c∈C Mampu(c,j) benar. Namun jika satu kandidat hanya boleh mengerjakan satu pekerjaan, penugasan seluruh pekerjaan mustahil: j₁ dan j₂ sama-sama memerlukan c₁. Klaim eksistensi lokal tidak menyatakan bahwa saksi untuk pekerjaan berbeda harus berbeda. Syarat penugasan injektif merupakan syarat tambahan atas keluarga pilihan. Masalah ini akan muncul lagi ketika relasi dan fungsi dibahas; kita tidak memerlukan teori pencocokan lengkap untuk melihat kegagalan contoh tersebut.

Dari saksi lokal menuju hasil algoritme

Andaikan data masukan sebuah program berada dalam himpunan I, hasil berada dalam O, dan R(i,o) menyatakan bahwa o memenuhi spesifikasi untuk i. Formula ∀i∈I∃o∈O R(i,o) mengatakan bahwa spesifikasi dapat dipenuhi pada tiap masukan. Ia belum menunjuk program yang menghitung o. Ia juga belum memberi waktu selesai. Bahkan bila setiap masukan memiliki tepat satu keluaran yang benar, ketunggalan matematis sendiri bukan analisis algoritme.

Pada contoh hingga kita dapat melihat pekerjaan tambahan yang dibutuhkan. Misalkan I={1,2,3}, O={0,1,2,3}, dan R(i,o) berarti o²≥i. Saksi o=1 bekerja untuk i=1; o=2 bekerja untuk i=2 dan i=3. Sebuah prosedur konkret dapat memeriksa o=0, lalu 1, lalu 2, lalu 3, dan berhenti pada nilai pertama yang memenuhi relasi. Bukti bahwa prosedur ini selesai menggunakan dua fakta yang tidak tercantum hanya sebagai susunan ∀∃: daftar O berhingga, dan pemeriksaan R pada setiap pasangan selesai. Bukti kebenarannya memakai cara berhenti: prosedur mengeluarkan o hanya setelah R(i,o) terverifikasi. Jaminan adanya saksi memastikan pencarian tidak menghabiskan seluruh daftar tanpa hasil.

Mengganti O dengan himpunan tak hingga menuntut pemeriksaan baru. Pencarian berurutan masih dapat selesai jika O dapat dienumerasi secara efektif, tiap pengujian selesai, dan saksi pasti muncul pada posisi hingga; syarat itu harus dinyatakan. Pada relasi matematis sebarang, kita tidak boleh menganggap pengujian selalu dapat dilakukan oleh komputer. Pembahasan ini tidak memerlukan teori komputabilitas lengkap. Cukup bedakan bukti bahwa solusi ada dari bukti bahwa metode tertentu benar-benar mendapatkannya.

Persoalan berubah lagi ketika beberapa masukan harus diselesaikan dengan keluaran yang berbeda. Ada tiga pekerjaan J={A,B,C} dan dua mesin M={1,2}. Andaikan semua pasangan diizinkan. Pernyataan ∀j∈J∃m∈M R(j,m) benar. Namun tidak ada fungsi penugasan g:J→M yang sekaligus memenuhi R(j,g(j)) untuk semua j dan g(j)≠g(k) bagi setiap j≠k. Dua pekerjaan pertama yang mendapat mesin berbeda sudah memakai kedua mesin; pekerjaan ketiga harus mengulangi salah satunya. Jadi daftar saksi per pekerjaan tidak menjamin kesesuaian antar-saksi. Ketika membaca spesifikasi, cari apakah yang diminta sekadar adanya jawaban untuk setiap kasus, satu jawaban seragam, atau satu keluarga jawaban yang tunduk pada syarat bersama. Ketiganya memerlukan formula dan pembuktian yang berbeda.

Latihan Berbobot dengan Pembahasan Lengkap

Latihan 2.1 — Variabel Bebas dan Terikat

Soal: Untuk setiap formula berikut, (a) identifikasi setiap kemunculan variabel dan tentukan apakah ia bebas atau terikat, (b) hitung FV dan BV, (c) tentukan apakah formula itu merupakan kalimat tertutup.

(i) ∀x∃y(P(x, y) ∧ Q(y, z))   (ii) (∃x R(x, x)) → S(x)   (iii) ∀x(∀y R(x, y) → T(x, y))

Pembahasan:

(i) Dalam ∀x∃y(P(x, y) ∧ Q(y, z)): x dalam P(x, y) terikat oleh ∀x. y dalam P(x, y) terikat oleh ∃y. y dalam Q(y, z) terikat oleh ∃y (karena kuantifikator ∃y mencakup seluruh subformula P(x,y) ∧ Q(y,z)). z dalam Q(y, z) bebas. FV = {z}, BV = {x, y}. Bukan kalimat tertutup karena z bebas.

(ii) Dalam (∃x R(x, x)) → S(x): dua kemunculan x dalam R(x, x) terikat oleh ∃x. x dalam S(x) bebas—ia berada di luar lingkup ∃x (anteseden implikasi hanya mencakup ∃x R(x, x)). FV = {x}, BV = {x}. Bukan kalimat tertutup. Ini adalah analog dalam aritmetika dari contoh (∀x R(x, y)) ∧ S(x) di Subbab 2.1.

(iii) Dalam ∀x(∀y R(x, y) → T(x, y)): x dalam R(x, y) terikat oleh ∀x terluar. y dalam R(x, y) terikat oleh ∀y. x dalam T(x, y) terikat oleh ∀x terluar. Namun y dalam T(x, y): kuantifikator ∀y hanya mencakup R(x, y) sebagai subformula dari anteseden implikasi, dan T(x, y) berada di luar lingkup ∀y. Oleh karena itu, y dalam T(x, y) bebas. FV = {y}, BV = {x, y}. Bukan kalimat tertutup.

Latihan 2.2 — Penggabungan Saksi yang Tidak Valid

Soal: Identifikasi kesalahan dalam argumen berikut: "Karena ∃x(x > 5) dan ∃x(x < 0) keduanya benar di ℝ, maka terdapat x yang memenuhi (x > 5) ∧ (x < 0)."

Pembahasan: Argumen ini melakukan kesalahan penggabungan saksi yang dilarang. Dari ∃x(x > 5), kita memperoleh saksi c₁ dengan c₁ > 5 (misalnya, c₁ = 6). Dari ∃x(x < 0), kita memperoleh saksi c₂ dengan c₂ < 0 (misalnya, c₂ = −1). Kedua saksi adalah objek yang berbeda—variabel x dalam kedua kalimat terikat secara independen. Menggabungkan mereka menjadi satu objek yang memenuhi konjungsi memerlukan kalimat yang lebih kuat: ∃x((x > 5) ∧ (x < 0))—yang jelas salah karena tidak ada bilangan riil yang sekaligus lebih besar dari 5 dan lebih kecil dari 0. Secara formal: dari ∃x P(x) dan ∃x Q(x), kita hanya dapat menyimpulkan (∃x P(x)) ∧ (∃x Q(x)), bukan ∃x(P(x) ∧ Q(x)).

Latihan 2.3 — Negasi Kuantifikator Berlapis

Soal: Tuliskan negasi dari setiap kalimat berikut, kemudian tentukan mana yang benar dan mana yang salah di ℝ.

(i) ∀x∈ℝ ∃y∈ℝ (x + y = 0)   (ii) ∃x∈ℝ ∀y∈ℝ (xy = y)   (iii) ∀x∈ℝ ∀y∈ℝ (x² + y² = 0 → x = 0 ∧ y = 0)

Pembahasan:

(i) Negasi: ∃x∈ℝ ∀y∈ℝ (x + y ≠ 0). Kalimat asli benar: untuk setiap x, saksi y = −x memenuhi x + (−x) = 0. Negasinya salah.

(ii) Negasi: ∀x∈ℝ ∃y∈ℝ (xy ≠ y). Kalimat asli: apakah ada x yang menjadi "identitas perkalian universal"? Untuk x = 1: 1·y = y untuk semua y ∈ ℝ. Jadi ∃x∈ℝ ∀y∈ℝ (xy = y) benar (saksi x = 1). Negasinya salah.

(iii) Negasi: ∃x∈ℝ ∃y∈ℝ (x² + y² = 0 ∧ ¬(x = 0 ∧ y = 0)), yang sama dengan ∃x∈ℝ ∃y∈ℝ (x² + y² = 0 ∧ (x ≠ 0 ∨ y ≠ 0)). Kalimat asli benar: jika x² + y² = 0 dan semua suku non-negatif, maka x² = 0 dan y² = 0, sehingga x = 0 dan y = 0. Negasinya salah.

Latihan 2.4 — Kegagalan Limit dan Ketidakseragaman

Soal: (a) Tunjukkan bahwa f(x) = sin(1/x) tidak memiliki limit di x = 0 (domain D = ℝ \ {0}). (b) Tunjukkan bahwa f(x) = x² tidak seragam kontinu di (0, ∞) dengan menampilkan saksi eksplisit untuk setiap δ > 0 yang diberikan.

Pembahasan (a): Misalkan L∈ℝ sebarang dan pilih ε₀=1. Untuk δ>0 sebarang, sifat Archimedes memberi bilangan asli positif n>1/(2πδ). Jika L≥0, pilih x=1/(3π/2+2πn). Maka 0<x<1/(2πn)<δ dan sin(1/x)=−1, sehingga |sin(1/x)−L|=1+L≥1. Jika L<0, pilih x=1/(π/2+2πn). Lagi-lagi 0<x<δ, sedangkan sin(1/x)=1, sehingga |sin(1/x)−L|=1−L>1. Jadi setiap kandidat L gagal memenuhi definisi limit. Bukti memakai sifat Archimedes serta nilai periodik sinus sebagai fakta yang sudah dikenal; fondasi bilangan riilnya akan dikembangkan pada bab-bab berikutnya. Perhatikan bahwa sin(πn/2) pada semua bilangan bulat n tidak hanya bergantian antara 1 dan −1: ia juga bernilai 0. Pemilihan fase yang tepat diperlukan untuk mendapatkan saksi penyangkal yang benar.

Pembahasan (b): Negasi keseragaman untuk f(x) = x² di (0,∞): ∃ε₀ > 0 ∀δ > 0 ∃a, x ∈ (0,∞) (|x − a| < δ ∧ |x² − a²| ≥ ε₀). Pilih ε₀ = 1. Diberikan δ > 0 sembarang: pilih a = 1/δ dan x = a + δ/2 = 1/δ + δ/2. Maka |x − a| = δ/2 < δ. Dan |x² − a²| = |x − a|·|x + a| = (δ/2)·(2/δ + δ/2) = 1 + δ²/4 > 1 = ε₀. ✓

Latihan 2.5 — Keterbagian dan Paritas

Soal: (a) Buktikan: ∀a, b ∈ ℤ ∀n ∈ ℤ⁺ [(n | a ∧ n | b) → n | (a + b)]. (b) Buktikan atau sangkal: ∀n ∈ ℤ [n² ≡ 0 (mod 4) ∨ n² ≡ 1 (mod 4)].

Pembahasan (a): Asumsikan n | a dan n | b. Ada k, ℓ ∈ ℤ dengan a = nk dan b = nℓ. Maka a + b = nk + nℓ = n(k + ℓ). Saksi: m = k + ℓ ∈ ℤ. Jadi n | (a + b). ∎

Pembahasan (b): Benar. Kasus (i): n genap, n = 2k. Maka n² = 4k², sehingga n² ≡ 0 (mod 4). Kasus (ii): n ganjil, n = 2k+1. Maka n² = 4k²+4k+1 = 4(k²+k)+1, sehingga n² ≡ 1 (mod 4). Kedua kasus mencakup semua n ∈ ℤ. ∎ Implikasi: n² ≡ 2 (mod 4) atau n² ≡ 3 (mod 4) tidak pernah terjadi, sebuah fakta berguna dalam teori bilangan.

Latihan pendalaman dengan pembahasan

Latihan-latihan berikut meminta alasan, bukan sekadar hasil transformasi simbol. Sebelum membaca pembahasan, tulis domain, urutan pilihan, dan tempat sebuah saksi boleh bergantung pada parameter lain.

P1 — Menemukan saksi penyangkal yang boleh bergantung pada tantangan

Pada ℝ, tentukan nilai kebenaran

A: ∀x∃y∀z(y>x+z),

B: ∀x∀z∃y(y>x+z),

C: ∃y∀x∀z(y>x+z).

Pembahasan. B benar: sesudah x dan z diberikan, pilih y=x+z+1. Pilihan ini sah karena y berada sesudah kedua universal, dan y−(x+z)=1>0. A salah. Tetapkan x=0. Apa pun y yang diajukan, pilih z=y. Pertaksamaan yang dituntut menjadi y>y, yang salah. Penyangkal tersebut berstruktur ∃x∀y∃z(y≤x+z): pilihan z boleh bergantung pada y. C juga salah. Untuk kandidat y apa pun, ambil x=y dan z=0, sehingga tuntutannya kembali y>y. Menulis y=x+z+1 sebagai “bukti” bagi A adalah memakai z sebelum z tersedia; rumus saksi yang baik pada B berubah menjadi alasan yang tidak sah pada A.

P2 — Universal pada kondisional

Apakah formula ∀x(P(x)→Q(x)) ekuivalen dengan (∀xP(x))→(∀xQ(x))?

Pembahasan. Arah dari kiri ke kanan sah. Jika P berlaku pada semua objek dan tiap objek yang memenuhi P memenuhi Q, maka Q berlaku pada semua objek. Tetapi arah balik gagal. Ambil domain {0,1}, dengan P(0) benar, P(1) salah, Q(0) salah, dan Q(1) benar. Formula kanan benar karena ∀xP(x) salah. Formula kiri salah pada x=0. Jadi kalimat “jika semuanya mempunyai sifat P, maka semuanya mempunyai sifat Q” lebih lemah daripada “setiap objek yang mempunyai sifat P mempunyai sifat Q”. Pada ∀x(P(x)→Q(x)), objek yang memenuhi P tetap harus diperiksa sekalipun terdapat objek lain yang tidak memenuhi P.

P3 — Apa tepatnya negasi keunikan?

Tuliskan negasi dari “terdapat tepat satu x dengan P(x)” tanpa memakai simbol ∃!. Terapkan pada P(x):x²=4 di ℝ dan pada Q(x):x²=−1 di ℝ.

Pembahasan. Ada dua cara keunikan eksistensial dapat gagal: tidak ada objek yang memenuhi sifat, atau terdapat setidaknya dua objek berbeda yang memenuhinya. Dalam logika klasik,

¬∃!x P(x) ≡ (∀x¬P(x)) ∨ ∃u∃v(P(u)∧P(v)∧u≠v).

Untuk melihat arah dari kanan ke kiri, alternatif pertama menggagalkan keberadaan, sedangkan alternatif kedua menggagalkan ketunggalan. Untuk arah sebaliknya, jika tidak ada saksi, alternatif pertama berlaku. Jika ada saksi u, kegagalan “tepat satu” berarti tidak semua saksi lain sama dengan u; ada v yang memenuhi P dan berbeda dari u. Untuk x²=4, saksi u=2 dan v=−2 memenuhi alternatif kedua. Untuk x²=−1 di ℝ, tak satu pun objek memenuhi sifat karena kuadrat riil tidak negatif; alternatif pertama berlaku. Menulis negasi keunikan hanya sebagai “ada dua” akan kehilangan kasus tanpa saksi.

P4 — Klaim tentang pertambahan yang tampak seragam

Untuk setiap n∈ℕ={0,1,2,…}, ada m∈ℕ dengan m>n². Apakah ini berarti ada m yang melampaui semua n² sekaligus?

Pembahasan. Klaim pertama benar dengan m=n²+1. Untuk membantah klaim kedua, ambil kandidat m sembarang dan pilih n=m+1. Karena m≥0, n²=(m+1)²=m²+2m+1>m. Jadi m bukan batas bagi semua kuadrat. Pada m=3, misalnya, n=4 memberi n²=16>3, tetapi angka ini hanya ilustrasi. Penyangkalan umum memerlukan aturan memilih n untuk setiap kandidat m, dan aturan n=m+1 memenuhi kebutuhan itu tanpa mengandalkan intuisi “bilangan asli terus bertambah”.

P5 — Dua radius, satu titik

Misalkan a titik akumulasi D, f:D→ℝ, dan terdapat L≠M yang masing-masing diklaim sebagai limit f di a. Seorang pembaca memilih x₁ dekat a untuk perkiraan terhadap L dan x₂ dekat a untuk perkiraan terhadap M, kemudian menyimpulkan |L−M| kecil. Apa yang kurang?

Pembahasan. Dua perkiraan |f(x₁)−L|<ε dan |f(x₂)−M|<ε saja tidak mengendalikan |f(x₁)−f(x₂)|. Ketaksamaan segitiga menghasilkan suku tambahan yang belum dibatasi. Perbaikannya ialah memilih satu x yang masuk ke kedua lingkungan sekaligus. Setelah radius δ₁ dan δ₂ tersedia, gunakan δ=min(δ₁,δ₂), lalu pakai sifat titik akumulasi untuk memperoleh 0<|x−a|<δ. Sekarang kedua perkiraan berlaku pada f(x) yang sama, dan suku tengah saling menghapus. Kekurangan awal bukan manipulasi nilai mutlak, melainkan koordinasi saksi.

P6 — Saksi seragam untuk fungsi linear

Buktikan bahwa f(x)=3x−2 kontinu seragam pada ℝ. Bandingkan pilihan δ dengan pembuktian untuk f(x)=x².

Pembahasan. Ambil ε>0 sebarang dan pilih δ=ε/3. Untuk a,x∈ℝ dengan |x−a|<δ,

|f(x)−f(a)|=|(3x−2)−(3a−2)|=3|x−a|<3δ=ε.

Pilihan δ tidak memakai a maupun x, sehingga urutan ∀ε∃δ∀a∀x dipenuhi. Untuk x², faktor tambahan |x+a| tidak memiliki batas seragam di seluruh ℝ. Bukti kontinuitas titik demi titik dapat membatasinya setelah a diketahui, tetapi langkah itu tidak memberi δ yang sama untuk semua a. Kesulitan ini bukan berarti semua fungsi nonlinier gagal kontinu seragam; contoh dan kontracontoh harus diperiksa menurut sifatnya, bukan berdasarkan label linear atau nonlinier.

P7 — Himpunan kandidat yang kosong

Misalkan A={1,2}, B=∅, dan R adalah relasi dari A ke B. Tentukan nilai kebenaran ∀x∈A∃y∈B R(x,y), ∃y∈B∀x∈A R(x,y), dan ∀y∈B∃x∈A R(x,y). Kemudian ganti A dengan ∅ dan pertahankan B=∅.

Pembahasan. Pada A={1,2}, formula pertama salah karena x=1 tidak memiliki saksi y. Formula kedua salah karena tidak ada anggota B sama sekali. Formula ketiga benar secara vakum: tidak ada y∈B yang dapat menggagalkannya. Ketika A dan B keduanya kosong, formula pertama menjadi benar karena universal terluarnya tidak menghadapi satu kasus pun; formula kedua tetap salah karena eksistensial terluarnya tidak memiliki saksi; formula ketiga tetap benar. Ini juga menunjukkan bahwa ∀x∈A∃y∈B R tidak memaksa B tak kosong jika A sendiri kosong. Tidak ada pertentangan dengan konvensi semesta struktur tak kosong: A dan B merupakan himpunan pembatas di dalam semesta itu.

P8 — Pembagian tanpa membagi

Buktikan bahwa untuk a,b,c∈ℤ, jika a|b dan a|c, maka a|(7b−4c). Periksa a=0 secara eksplisit.

Pembahasan. Dari a|b diperoleh k∈ℤ dengan b=ak; dari a|c diperoleh ℓ∈ℤ dengan c=aℓ. Maka 7b−4c=7ak−4aℓ=a(7k−4ℓ). Karena 7k−4ℓ bilangan bulat, ia merupakan saksi yang diminta. Bila a=0, kedua premis memaksa b=c=0, dan 7b−4c=0; saksi 0 membuktikan 0|0. Untuk contoh numerik a=3,b=12,c=−6, kita dapat memakai k=4,ℓ=−2 sehingga 7k−4ℓ=36 dan 7b−4c=108=3·36. Bukti tetap benar pada kasus yang membuat pembagian b/a tidak sah, sebab sejak awal ia bekerja dengan persamaan perkalian.

Jembatan ke Teori Himpunan: Kuantifikator sebagai Operasi Himpunan

Irisan, Gabungan, dan Kuantifikasi Universal/Eksistensial

Tetapkan satu semesta U dan keluarga himpunan Aᵢ⊆U dengan indeks i∈I. Untuk x∈U, irisan dan gabungan keluarga itu dinyatakan melalui kuantifikator:

x ∈ ⋂{i∈I} Aᵢ  jika dan hanya jika  ∀i ∈ I (x ∈ Aᵢ). x ∈ ⋃{i∈I} Aᵢ  jika dan hanya jika  ∃i ∈ I (x ∈ Aᵢ).

Dengan komplemen selalu relatif terhadap U, hukum De Morgan mengikuti dari negasi kuantifikator. Untuk x∈U,

x∈U∖(⋂{i∈I}Aᵢ) jika dan hanya jika ¬∀i∈I(x∈Aᵢ), jika dan hanya jika ∃i∈I(x∉Aᵢ), jika dan hanya jika x∈⋃{i∈I}(U∖Aᵢ).

Jika I kosong, kita memakai irisan kosong relatif U sebagai U dan gabungan kosong sebagai ∅. Konvensi ini sesuai dengan kebenaran universal kosong dan kesalahan eksistensial kosong. Menyebut U penting: kita tidak sedang mengandaikan ada himpunan universal semua objek dalam teori himpunan.

Pada langkah berikutnya, pembaca akan menggunakan formula keanggotaan semacam ini untuk membuktikan kesamaan himpunan dengan mengambil anggota sebarang dan memeriksa kedua arah. Aturan logisnya sudah tersedia; objek yang dibicarakan akan bertambah kaya.

Subset dan Implikasi Universal

Relasi A⊆B dinyatakan oleh ∀x(x∈A→x∈B). Karena tidak ada anggota ∅, kita memperoleh ∅⊆B. Selanjutnya, A⊆B dan B⊆A berarti A dan B mempunyai anggota yang sama. Aksioma ekstensionalitas menghubungkan kesamaan anggota dengan A=B; kita tidak mengganti simbol kesamaan dengan definisi sembarang. Inilah salah satu titik pertemuan antara logika dan aksioma teori himpunan yang akan dijelaskan pada Bab 3.

Ketika sebuah bukti dimulai dengan “ambil ε>0 sebarang”, penulis menyiapkan generalisasi universal terhadap ε. Ketika ia memilih δ sesudah ε diketahui, ia menyiapkan saksi eksistensial yang boleh bergantung pada ε. Membaca urutan pilihan secara teliti sering cukup untuk menemukan letak kegagalan argumen yang secara aljabar tampak benar. Sebelum menerima suatu bukti, tanyakan dari mana setiap objek datang dan kepada parameter mana ia boleh bergantung.

Catatan Rujukan

Naskah ini berasal dari satu draf baru Gamma, kemudian diperiksa dan dikembangkan menjadi bab utuh dalam versi ini. Definisi dan pola bukti merupakan materi standar. Contoh angka dan urutan penjelasan dirancang untuk naskah ini; tidak diklaim sebagai penemuan matematis baru. Rujukan dipakai untuk memeriksa konvensi dan menyediakan bacaan lanjutan, bukan untuk menggantikan bukti yang tertulis.

[R1] Open Logic Project, First-order Logic, revisi 9620cc7, 12 Juli 2026. Bagian sintaks, struktur, variabel bebas, dan substitusi. https://builds.openlogicproject.org/content/first-order-logic/first-order-logic.pdf

[R2] forall x: Calgary, Bab 27, Sentences of FOL. Rujukan lingkup dan kemunculan variabel. Bahasa dasar bab tersebut lebih sederhana daripada bahasa dengan simbol fungsi umum yang digunakan di sini. https://forallx.openlogicproject.org/html/Ch27.html

[R3] Jiří Lebl, Basic Analysis, §3.1, Limits of functions. Rujukan definisi limit dan syarat titik akumulasi. https://www.jirka.org/ra/html/sec_limoffunc.html

[R4] Jiří Lebl, Basic Analysis, §3.2, Continuous functions. Rujukan kontinuitas pada domain fungsi, termasuk titik terisolasi. https://www.jirka.org/ra/html/sec_cont.html

[R5] Jiří Lebl, Basic Analysis, §3.4, Uniform continuity. Rujukan pembedaan ketergantungan δ. https://www.jirka.org/ra/html/sec_unifcont.html

[R6] Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, 18 Mei 2015, §3.6, Predicate Formulas. Bacaan pembanding untuk kuantifikasi dan penggunaan logika dalam matematika diskrit. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf

Semua sumber di atas diakses pada 1 Oktober 2026. Pemeriksaan komputasi untuk contoh berhingga dan aritmetika rasional berfungsi sebagai audit tambahan; bukti universal tetap diberikan dalam uraian.