T.7 · Citra himpunan, relasi ekuivalen, dan negasi logis

Persiapan GRE tingkat sarjana. Tujuan lokal dalam cakupan ETS yang ditinjau; ini adalah pengajaran orisinal, bukan uji coba resmi atau prediktor skor.

Prasyarat: Operasi himpunan, kuantor, fungsi, dan pembuktian dasar.

• Buktikan identitas citra dan bedakan inklusi dari kesamaan
• Periksa refleksivitas, simetri, dan transitivitas dengan kasus eksplisit
• Negasikan implikasi dan pernyataan berkuantor tanpa mengubah jangkauan mereka

preimage: Himpunan input yang outputnya berada dalam himpunan target tertentu.

equivalence relation: Relasi yang bersifat refleksif, simetris, dan transitif.

Untuk f:X→Y dan A⊆X, citra f(A) terdiri dari semua output f(a) dengan a dalam A. Suatu titik berada dalam f(A∪B) tepat ketika berasal dari A atau B, sehingga f(A∪B)=f(A)∪f(B). Jika A⊆B, maka f(A)⊆f(B). Untuk irisan saja, hanya f(A∩B)⊆f(A)∩f(B) yang otomatis: output yang sama dapat berasal dari input yang berbeda. Gunakan f(x)=x², A={−1}, B={1}; citra kiri kosong sementara irisan kanan adalah {1}.

Preimage berperilaku berbeda. Untuk C⊆Y, f⁻¹(C) di sini menunjukkan himpunan semua input yang dipetakan ke dalam C, bahkan jika f tidak memiliki fungsi invers. Keanggotaan dalam dua preimage berarti input yang sama persis memetakan ke kedua himpunan target. Akibatnya, preimage mempertahankan union, irisan, dan komplemen relatif terhadap domain/kodomain yang disebutkan. Jangan meneruskan teorema tentang preimage ke citra. Jika f injektif, irisan citra menjadi sama, karena output yang sama kemudian memaksa adanya input bersama.

Suatu relasi R pada X bersifat refleksif jika xRx untuk setiap x, simetris jika xRy mengimplikasikan yRx, dan transitif jika xRy dan yRz mengimplikasikan xRz. Ketiganya membentuk relasi ekuivalen; kelas-kelasnya mempartisi X. Pada bilangan bulat, xRy ketika x dan y memiliki sisa bagi yang sama modulo empat memberikan empat kelas. Relasi |x−y|≤1 bersifat refleksif dan simetris tetapi tidak transitif: 0R1 dan 1R2 sedangkan 0 tidak berelasi dengan 2. Memeriksa hanya diagram atau dua sifat saja tidak cukup.

Sebuah implikasi P⇒Q salah tepat ketika P benar dan Q salah. Dengan demikian negasi dari P⇒(Q∧R) adalah P∧(¬Q∨¬R), bukan ¬P⇒(¬Q∧¬R). Menegasi “setiap x memiliki sifat A” menghasilkan “terdapat x tanpa A”; menegasi “terdapat x” menghasilkan “setiap x tidak”. Contoh penyangkal dapat membantah klaim universal, sementara contoh tidak bisa membuktilkannya. Kuantor mempertahankan urutan mereka saat dinegasikan secara individual: ¬(∀x∃y S(x,y)) adalah ∃x∀y ¬S(x,y).

Misalkan f memetakan a dan b ke label L. Dengan A={a}, B={b}, f(A∩B)=∅ tetapi f(A)∩f(B)={L}. Untuk xRy yang didefinisikan oleh x=y atau x=−y pada R, refleksivitas dan simetri mengikuti langsung, dan dua perubahan tanda masih menghasilkan z=±x, membuktikan transitivitas. Kelas-kelasnya adalah {x,−x}, dengan {0} sebagai himpunan tunggal. Pernyataan salah “setiap file yang disimpan memiliki hash” berarti setidaknya satu file yang disimpan tidak memiliki hash; itu tidak berarti semua file tidak memiliki hash.

f⁻¹(C) bisa berarti himpunan pra-citra tanpa fungsi invers. Relasi refleksif dan simetris masih bisa gagal transitif. Negasikan seluruh pernyataan sebelum menyederhanakan bagian-bagiannya.

Buktikan $f(A\cap B)\subseteq f(A)\cap f(B)$. Berikan contoh inklusi ketat. Di bawah asumsi tambahan apa pada f kesamaan mengikuti untuk semua A dan B?

Penyelesaian terarah

Jika $y=f(x)$ untuk $x\in A\cap B$, maka x thuộc vào mỗi tập hợp, do đó y thuộc vào mỗi image. Untuk ketatnya, peta distinct a,b to the same c and take $A=\{a\}$, $B=\{b\}$. The left image is empty and the right intersection is $\{c\}$. Jika f injektif dan $y=f(a)=f(b)$ dengan $a\in A,b\in B$, injektivitas memberikan a=b dalam irisan, membuktikan inklusi terbalik. Sebaliknya, contoh singleton menunjukkan bahwa kesamaan untuk semua pasangan memaksa injektivitas.

Pada bilangan bulat, definisikan $aRb$ ketika $a-b$ habis dibagi oleh 4. Buktikan bahwa ini adalah relasi ekuivalensi dan deskripsikan setiap kelasnya. Negasikan: “Untuk setiap bilangan bulat n terdapat bilangan bulat m yang lebih besar dari n dengan sifat P.”

Periksa setelah mencoba

Refleksivitas menggunakan $a-a=0$; simetri menggunakan negatif dari kelipatan empat; transitivitas menggunakan jumlah dari dua kelipatan seperti itu. Kelas-kelasnya adalah empat residu modulo empat; kelas dari a adalah $a+4\mathbb Z$. Negasinya adalah: terdapat bilangan bulat n sedemikian sehingga setiap bilangan bulat m yang lebih besar dari n gagal memenuhi P. Setara dengan $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$. Ini tidak menyatakan bahwa P gagal untuk setiap bilangan bulat, maupun bahwa m paling banyak n untuk setiap m.