Misalkan ada 15 orang di sebuah pesta. Sebagian besar dari mereka sudah saling mengenal, tetapi beberapa orang tetap memutuskan untuk berjabat tangan. Mungkinkah setiap orang di pesta itu berjabat tangan dengan tepat tiga orang lainnya?
Sejauh ini kita telah melihat bagaimana bentuk logis suatu pernyataan dapat membantu kita menyusun kerangka bukti. Namun, hal ini hanya membawa kita sampai pada batas tertentu: Untuk melengkapi kerangka bukti tersebut, kita perlu memahami objek dan struktur matematis yang dibahas dalam bukti. Sebagian pemahaman ini dapat diperoleh dengan membaca definisi secara cermat. Meskipun demikian, bekerja dengan objek dan struktur juga menumbuhkan pemahaman serta intuisi yang tidak selalu berwujud konkret; keduanya dapat memunculkan momen “aha!” yang memberi petunjuk tentang cara melanjutkan suatu bukti.
Alasan lain untuk mengalihkan perhatian kita kepada bukti tentang struktur diskret adalah bahwa hal ini memperlihatkan salah satu ciri penting matematika: abstraksi. Selama ini kita membuktikan fakta tertentu tentang masalah tertentu. Kita mungkin mulai melihat kemiripan di antara bukti beberapa pernyataan. Kemiripan tersebut dapat muncul karena struktur matematis yang mendasari masalah-masalah itu, meskipun tidak dinyatakan secara terang-terangan. Jika kita membuktikan fakta umum tentang struktur tersebut, kita dapat menerapkan “teorema” itu pada banyak masalah yang berbeda.
Beberapa struktur diskret cocok ditangani dengan gaya bukti tertentu, dan beberapa teknik pembuktian “baku” dapat diterapkan pada struktur tertentu. Kita akan melihat beberapa di antaranya di sini, tetapi terutama kita akan menggunakan kesempatan ini untuk mengingat kembali sejumlah definisi dan sifat dasar struktur diskret, lalu memanfaatkan bukti tentangnya agar kita semakin memahami struktur tersebut.
Dalam aktivitas pratinjau ini, kita akan menjelajahi beberapa sifat dasar himpunan dan fungsi. Selanjutnya dalam bagian ini, kita akan menulis bukti tentang gagasan-gagasan tersebut.
Ingatlah bahwa himpunan hanyalah kumpulan elemen. Berikut dua definisi tentang himpunan:
Suatu himpunan \(A\) merupakan himpunan bagian dari himpunan \(B\text{,}\) ditulis \(A \subseteq B\text{,}\) jika setiap elemen \(A\) juga merupakan elemen \(B\text{.}\)
Untuk himpunan \(A\) dan \(B\text{,}\) gabungan \(A\) dan \(B\text{,}\) ditulis \(A \cup B\text{,}\) adalah himpunan yang memuat setiap elemen yang terdapat dalam \(A\text{,}\) dalam \(B\text{,}\) atau dalam keduanya.
Untuk sembarang fungsi \(f: \mathbb{N} \to \mathbb{N}\) dan sembarang himpunan \(A \subseteq \mathbb{N}\text{,}\) kita dapat mendefinisikan citra \(A\) oleh \(f\) sebagai himpunan semua keluaran \(f\) ketika masukannya merupakan elemen \(A\text{.}\) Kita menuliskannya sebagai \(f(A) = \{f(x) ~:~ x \in A\}\text{.}\)
Berikan contoh, jika ada, berupa dua himpunan berbeda \(A\) dan \(B\) sedemikian sehingga \(A \subseteq B\text{,}\) tetapi \(f(A) \not\subseteq f(B)\text{.}\)
Ingatlah bahwa himpunan adalah kumpulan elemen yang tidak berurutan. Kita dapat mendeskripsikan suatu himpunan dengan mendaftarkan elemen-elemennya atau dengan menyatakan suatu sifat yang dipenuhi oleh semua elemen dalam himpunan tersebut. Sebagai contoh,
\begin{equation*}
A = \{1,2,3,4,5\}\text{,}
\end{equation*}
atau
\begin{equation*}
B = \{x \in \N \st x \lt 10 \}\text{.}
\end{equation*}
Himpunan kedua di sini adalah himpunan bilangan asli (\(0, 1, 2, \ldots\)) yang kurang dari 10. Perhatikan bahwa setiap elemen \(A\) juga merupakan elemen \(B\text{.}\) Definisi berikut menangkap gagasan tersebut.
Suatu himpunan \(A\) merupakan himpunan bagian dari himpunan \(B\text{,}\) ditulis \(A \subseteq B\text{,}\) jika setiap elemen \(A\) juga merupakan elemen \(B\text{.}\)
Kita mengatakan bahwa \(A\) merupakan himpunan bagian sejati dari \(B\text{,}\) ditulis \(A \subset B\text{,}\) jika \(A \subseteq B\) dan \(A \neq B\text{.}\) Dengan kata lain, setiap elemen \(A\) merupakan elemen \(B\text{,}\) dan terdapat setidaknya satu elemen \(B\) yang bukan elemen \(A\text{.}\)
Kita sedang menanyakan apakah setiap bilangan asli yang kuadratnya kurang dari 10 juga merupakan bilangan asli yang kurang dari 5. Kita dapat langsung menuliskan elemen-elemen himpunan tersebut: \(A = \{0,1,2,3,4\}\) dan \(B = \{0,1,2,3\}\) (karena \(3^2 = 9\) dan \(4^2 = 16\)). Jadi, \(B \subseteq A\text{.}\) Akan tetapi, \(B \neq A\text{,}\) sehingga sebenarnya \(B \subset A\text{.}\)
Himpunan-himpunan dalam contoh di atas berukuran kecil sehingga elemen-elemennya cukup mudah dituliskan. Namun, kita juga dapat membuktikan hubungan himpunan bagian ketika menuliskan semua elemen tidak praktis atau bahkan tidak mungkin dilakukan (misalnya karena himpunannya tak hingga). Mari kita cermati bagaimana kita dapat menalar contoh di atas.
Kita mengklaim bahwa setiap elemen \(B\) juga merupakan elemen \(A\text{.}\) Dengan kata lain: Untuk semua bilangan \(n\text{,}\)jika\(n\) merupakan elemen \(B\text{,}\)maka\(n\) juga merupakan elemen \(A\text{.}\) Setelah mengenalinya sebagai pernyataan bersyarat, kita dapat memberikan bukti langsung, bukti dengan kontraposisi, atau bukti dengan kontradiksi. Dalam hal ini, bukti langsung sangat memadai. Mari kita coba:
Misalkan \(n\) merupakan elemen himpunan \(B\text{.}\) Maka, \(n^2 \lt 10\) berdasarkan definisi \(B\text{.}\) Karena \(4^2 = 16\text{,}\) harus berlaku \(n \lt 4\text{.}\) Berdasarkan definisi \(A\) dan fakta bahwa \(4 \lt 5\text{,}\) kita memperoleh \(n \in A\text{.}\)
Jelasnya, bukti ini jauh lebih panjang daripada yang biasanya kita perlukan untuk contoh tersebut, tetapi bentuknya memberi wawasan. Membuktikan bahwa suatu himpunan merupakan himpunan bagian dari himpunan lain sesungguhnya sama dengan membuktikan sebuah implikasi!
Untuk sembarang himpunan \(A\text{,}\)\(B\text{,}\) dan \(C\text{,}\) jika \(A \subseteq B\) dan \(B \subseteq C\text{,}\) maka \(A \subseteq C\text{.}\)
Kita akan memberikan bukti langsung. Misalkan \(A\text{,}\)\(B\text{,}\) dan \(C\) adalah himpunan, serta andaikan bahwa \(A \subseteq B\) dan \(B \subseteq C\text{.}\) Kita akan membuktikan bahwa \(A \subseteq C\text{.}\)
Misalkan \(x\) merupakan elemen \(A\text{.}\) Karena \(A \subseteq B\text{,}\) kita mengetahui bahwa \(x \in B\text{.}\) Karena \(B \subseteq C\text{,}\) kita mengetahui bahwa \(x \in C\text{.}\) Oleh karena itu, \(A \subseteq C\text{.}\)
Sekarang mari kita buktikan sebuah fakta tentang bilangan: Setiap kelipatan 9100 juga merupakan kelipatan 13. Kita dapat memfaktorkan 9100, tetapi ada cara yang lebih mudah. Himpunan kelipatan 9100 merupakan himpunan bagian dari himpunan kelipatan 91. Selanjutnya, himpunan kelipatan 91 merupakan himpunan bagian dari himpunan kelipatan 13. Sekarang terapkan proposisi di atas.
Bukti pada Proposisi 1.5.3 kadang-kadang disebut bukti dengan penelusuran elemen. Berdasarkan definisi himpunan bagian, \(A \subseteq B\) berarti bahwa setiap elemen \(A\) merupakan elemen \(B\text{,}\) atau secara ekuivalen, untuk semua \(x\text{,}\) jika \(x\) merupakan elemen \(A\text{,}\) maka \(x\) merupakan elemen \(B\text{.}\) Salah satu cara membuktikannya adalah dengan “menelusuri” elemen \(x\) dari \(A\) ke \(B\text{.}\)
Buktikan bahwa jika \(A \subseteq B\text{,}\) maka \(A \cup B \subseteq B\text{.}\) Ingatlah bahwa \(A \cup B\) merupakan gabungan himpunan \(A\) dan \(B\text{,}\) serta memuat semua elemen yang terdapat dalam \(A\text{,}\) dalam \(B\text{,}\) atau dalam keduanya.
Kita akan menulis bukti langsung. Jadi, kita akan mengasumsikan bahwa \(A \subseteq B\) dan membuktikan bahwa \(A \cup B \subseteq B\text{.}\) Kesimpulan yang ingin kita peroleh merupakan pernyataan tentang himpunan bagian, sehingga mari kita gunakan bukti dengan penelusuran elemen.
Misalkan \(A\) dan \(B\) adalah himpunan dan andaikan \(A \subseteq B\text{.}\) Selanjutnya, misalkan \(x\) merupakan elemen \(A \cup B\text{.}\) Ini berarti bahwa \(x\) merupakan elemen \(A\text{,}\) atau \(x\) merupakan elemen \(B\text{,}\) atau elemen keduanya. 5
Tinjau kedua kasus. Jika \(x\) merupakan elemen \(A\text{,}\) maka karena \(A \subseteq B\text{,}\) kita mengetahui bahwa \(x\) merupakan elemen \(B\text{.}\) Di sisi lain, jika \(x\) bukan elemen \(A\text{,}\) maka \(x\) harus merupakan elemen \(B\) (karena \(x\) berada dalam \(A \cup B\)). Dalam kedua kasus tersebut, \(x\) merupakan elemen \(B\text{.}\) Oleh karena itu, \(A \cup B \subseteq B\text{.}\)
Sebenarnya kita dapat membuktikan pernyataan yang lebih kuat: \(A \subseteq B\) jika dan hanya jika \(A \cup B = B\text{.}\) Anda diminta membuktikannya dalam latihan.
Fungsi \(f:A \to B\) adalah aturan yang memasangkan setiap elemen himpunan \(A\) (domain) dengan tepat satu elemen himpunan \(B\) (kodomain). Aturannya dapat berupa apa saja: Tidak harus ada rumus atau alasan tertentu; kita hanya perlu memasangkan elemen-elemen \(A\) dengan elemen-elemen \(B\text{.}\) Sebagai contoh, misalkan \(A\) adalah himpunan mahasiswa yang mengikuti suatu mata kuliah Matematika Diskret dan \(B\) adalah himpunan bulan dalam setahun. Sekarang definisikan fungsi \(f:A \to B\) sebagai aturan yang memasangkan setiap mahasiswa dengan bulan kelahirannya. Karena setiap mahasiswa dipasangkan dengan satu bulan, dan tidak lebih dari satu bulan, aturan ini merupakan fungsi.
Fungsi \(f:A \to B\) bersifat injektif (atau satu-satu) jika setiap elemen \(B\) merupakan citra dari paling banyak satu elemen \(A\text{.}\) Dengan kata lain, tidak ada elemen \(B\) yang menjadi keluaran bagi lebih dari satu masukan dari \(A\text{.}\)
Dalam contoh berikut, kita menggunakan notasi dua baris untuk mendeskripsikan fungsi. Baris atas memuat masukan, sedangkan baris bawah mencantumkan keluaran yang bersesuaian. Jadi, \(f:\{1,2,3,4\} \to \{a,b,c,d\}\) dapat didefinisikan sebagai
\begin{equation*}
f = \twoline{1 \amp 2 \amp 3 \amp 4}{a \amp b \amp c \amp d}\text{,}
\end{equation*}
yang berarti bahwa \(f(1) = a\text{,}\)\(f(2) = b\text{,}\)\(f(3) = c\text{,}\) dan \(f(4) = d\text{.}\)
Fungsi \(f\) bersifat injektif: Setiap elemen \(B\) merupakan citra dari paling banyak satu elemen \(A\text{.}\) Fungsi \(g\) tidak bersifat injektif: Elemen 4 dalam \(B\) merupakan citra dari 1 dan 3 dalam \(A\text{.}\)
Tinjau kembali fungsi yang memetakan mahasiswa ke bulan kelahirannya. Mungkinkah fungsi ini bersifat injektif? Atau, dengan kata lain, apakah harus ada dua mahasiswa dalam mata kuliah tersebut yang lahir pada bulan yang sama (yang berarti bahwa fungsi itu tidak injektif)? Jawabannya tampaknya bergantung pada banyaknya mahasiswa di kelas.
Namun, mari kita berhenti sejenak dan memikirkan fakta yang lebih umum tentang fungsi dalam situasi ini. Mari kita buktikan fakta berikut. Ingatlah bahwa \(|A|\) menyatakan kardinalitas (ukuran) himpunan \(A\text{,}\) yaitu banyaknya elemen dalam \(A\text{.}\)
Misalkan \(f:A \to B\) adalah fungsi dengan \(A\) dan \(B\) keduanya merupakan himpunan berhingga. Jika \(|A| \gt |B|\text{,}\) maka \(f\)tidak injektif.
Kita akan memberikan bukti melalui kontraposisi: Jika \(f\) injektif, maka \(|A| \le |B|\text{.}\) Misalkan \(|B| = n\text{.}\) Karena \(f\) injektif, setiap elemen \(B\) harus menjadi keluaran bagi paling banyak satu elemen \(A\text{.}\) Dengan demikian, terdapat paling banyak \(n\) elemen \(A\) yang dipetakan ke \(B\) oleh \(f\text{.}\) Namun, definisi fungsi mengharuskan setiap elemen domain dipetakan ke tepat satu elemen kodomain, sehingga terdapat paling banyak \(n\) elemen dalam \(A\text{.}\)
Apakah bukti ini mengingatkan Anda pada bukti-bukti kita yang menyerupai prinsip sarang merpati? Seharusnya demikian, karena inilah salah satu perumusan cermat prinsip sarang merpati. Kita dapat saja membuktikan fakta tentang mahasiswa yang lahir pada bulan yang sama, tetapi sekarang kita cukup menerapkan proposisi di atas. Ketika suatu teorema atau proposisi diterapkan untuk membuktikan hasil lain secara langsung, hasil yang terakhir itu disebut korolari.
Tinjau fungsi yang memetakan setiap mahasiswa ke bulan kelahirannya. Karena domainnya memiliki 25 elemen dan kodomainnya memiliki 12 elemen, fungsi tersebut tidak injektif berdasarkan Proposisi 1.5.7. Oleh karena itu, setidaknya dua mahasiswa lahir pada bulan yang sama.
Masukan fungsi selalu berasal dari suatu himpunan (disebut domain), dan keluarannya juga berada dalam suatu himpunan (disebut kodomain). Hal ini secara alami mengarahkan kita pada berbagai fakta tentang interaksi antara himpunan dan fungsi.
Diberikan fungsi \(f:X \to Y\) dan himpunan \(A \subseteq X\text{,}\) kita mendefinisikan citra \(A\) oleh \(f\) sebagai himpunan \(f(A) = \{f(a) \in Y \st a \in A\}\text{.}\) Artinya, \(f(A)\) adalah himpunan semua keluaran fungsi untuk masukan dalam \(A\text{.}\)
Misalkan \(f:X \to Y\) adalah fungsi, dan misalkan \(A\) serta \(B\) merupakan himpunan bagian dari \(X\text{.}\) Jika \(A \subseteq B\text{,}\) maka \(f(A) \subseteq f(B)\text{.}\)
Misalkan \(f\text{,}\)\(A\text{,}\) dan \(B\) seperti dalam proposisi. Andaikan bahwa \(A \subseteq B\text{.}\) Sekarang tinjau suatu elemen \(y \in f(A)\text{.}\) Berdasarkan definisi, ini berarti terdapat suatu \(a \in A\) sedemikian sehingga \(f(a) = y\text{.}\) Karena \(a \in A\) dan \(A \subseteq B\text{,}\) kita memperoleh \(a \in B\text{.}\) Dengan demikian, berdasarkan definisi,
\begin{equation*}
y = f(a) \in f(B)\text{.}
\end{equation*}
Karena \(y\) merupakan elemen sembarang dari \(f(A)\text{,}\) kita telah membuktikan bahwa \(f(A) \subseteq f(B)\text{.}\)
Perhatikan bahwa bukti di atas kembali merupakan bukti dengan penelusuran elemen. Hal ini masuk akal begitu Anda mengingat bahwa \(f(A)\) dan \(f(B)\) hanyalah nama himpunan. Untuk membuktikan bahwa suatu himpunan merupakan himpunan bagian dari himpunan lain, kita menelusuri elemen dari himpunan bagian ke superhimpunannya.
Suatu relasi pada himpunan \(A\) adalah himpunan pasangan terurut dari elemen-elemen \(A\text{.}\) Kita dapat memandang relasi sebagai cara mendeskripsikan suatu jenis hubungan di antara elemen-elemen \(A\text{.}\) Sebagai contoh, kita dapat memiliki relasi pada himpunan orang di sebuah pesta yang mendeskripsikan siapa berteman dengan siapa. Kita juga dapat memiliki relasi pada himpunan bilangan asli yang mendeskripsikan pasangan bilangan mana saja yang dihubungkan oleh relasi \(x \lt y\text{.}\)
Relasi meresapi seluruh matematika, sering kali tanpa kita sadari. Setiap kali kita membuat pernyataan tentang dua elemen suatu himpunan, secara implisit kita sedang mendefinisikan relasi. Pernyataan tersebut benar apabila pasangannya berada dalam relasi. Sebagai contoh, pernyataan “3 kurang dari 5” benar karena pasangan \((3,5)\) berada dalam relasi \(\lt\text{.}\) Bahkan, dengan menggunakan bahasa yang kita kembangkan dalam subbagian Kuantor dan Predikat, kita dapat mengatakan bahwa relasi hanyalah predikat yang variabel-variabelnya berasal dari himpunan yang sama.
Relasi sering memiliki simbol khusus seperti “\(=\)”, “\(\le\)”, atau “\(\perp\)”. Ketika membicarakan relasi secara umum, kita akan menggunakan \(\sim\) dan menulis \(x \sim y\text{,}\) atau menggunakan huruf kapital seperti \(R\) dan menulis \(R(x,y)\text{,}\)\(xRy\text{,}\) atau bahkan \((x,y) \in R\) (semuanya memiliki arti yang sama).
Tinjau relasi \(\sim\) pada himpunan mahasiswa dalam mata kuliah Matematika Diskret Anda yang berlaku bagi dua mahasiswa jika mereka mengikuti mata kuliah lain yang sama. Apakah relasi ini bersifat transitif?
Tidak selalu (meskipun relasi ini dapat bersifat transitif untuk himpunan mahasiswa tertentu). Sebagai contoh, misalkan Alice mengikuti mata kuliah lain bersama Bruce, katakanlah Pengantar Pemrograman. Carlos tidak mengikuti Pengantar Pemrograman, tetapi ia dan Bruce sama-sama mengikuti Kimia Organik. Dengan demikian, Alice\(\sim\)Bruce dan Bruce\(\sim\)Carlos, tetapi belum tentu Alice\(\sim\)Carlos (karena Alice tidak harus mengikuti Kimia Organik bersama Carlos).
Untuk membuktikan bahwa suatu relasi tidak transitif, kita cukup menemukan contoh penyangkal, yaitu tiga elemen \(a\text{,}\)\(b\text{,}\) dan \(c\) sedemikian sehingga \(a \sim b\) dan \(b \sim c\text{,}\) tetapi \(a \not\sim c\) (ingat, satu-satunya cara suatu implikasi bernilai salah adalah ketika premisnya benar dan kesimpulannya salah).
Tinjau himpunan semua mahasiswa dalam kelas Matematika Diskret Anda, lalu definisikan relasi \(\sim\) yang berlaku bagi mahasiswa \(a\) dan \(b\) (sehingga \(a \sim b\) benar) jika \(a\) lebih tinggi daripada \(b\text{.}\) Buktikan bahwa relasi ini bersifat transitif.
Misalkan \(a\text{,}\)\(b\text{,}\) dan \(c\) adalah sembarang mahasiswa dalam mata kuliah Matematika Diskret Anda. Andaikan \(a \sim b\) dan \(b \sim c\text{.}\) Artinya, \(a\) lebih tinggi daripada \(b\text{,}\) dan \(b\) lebih tinggi daripada \(c\text{.}\) Oleh karena itu, \(a\) tentu lebih tinggi daripada \(c\text{,}\) dengan \(b\) sebagai pembanding perantara, sehingga \(a \sim c\) juga benar. Jadi, \(\sim\) bersifat transitif pada himpunan ini.
Kita akan menggunakan seluruh Bab 2 untuk mempelajari bukti tentang graf karena bidang matematika ini begitu kaya. Sebagai pratinjau, berikut adalah contoh bagaimana bukti tentang graf dapat disusun.
Suatu graf terdiri atas himpunan \(V\) yang berisi simpul dan himpunan \(E\) yang berisi sisi. Sisi-sisinya merupakan himpunan bagian beranggota dua dari himpunan simpul, dan kita dapat memandangnya sebagai representasi hubungan antarsimpul. Perhatikan bahwa ini merupakan definisi abstrak graf dengan menggunakan himpunan. Namun, kita sering menggambar graf dengan titik sebagai simpul dan garis yang menghubungkan titik-titik tersebut sebagai sisi karena gambar semacam itu membantu kita melihat apa yang terjadi.
Karena graf merepresentasikan suatu jenis hubungan antarelemen (simpul), kita dapat menggunakan graf untuk merepresentasikan banyak masalah dunia nyata. Sebagai contoh, simpul-simpul suatu graf dapat merepresentasikan orang-orang di sebuah pesta. Setiap sisi dapat merepresentasikan jabat tangan antara dua orang. Jadi, ketika kita bertanya apakah 15 orang di sebuah pesta mungkin masing-masing berjabat tangan dengan tepat 3 orang lain, sebenarnya kita sedang bertanya apakah ada graf dengan 15 simpul yang setiap simpulnya termasuk dalam 3 sisi. (“Termasuk dalam”?? Ya, karena suatu sisi merupakan himpunan bagian beranggota dua dari himpunan simpul. Jadi, jika suatu sisi “menyentuh” atau “keluar dari” suatu simpul, artinya simpul tersebut termasuk dalam himpunan bagian beranggota dua itu.)
Misalkan \(v\) adalah simpul dalam graf \(G\text{.}\) Derajat \(v\text{,}\) ditulis \(d(v)\text{,}\) adalah banyaknya sisi yang memuat \(v\text{,}\) yaitu banyaknya sisi yang berinsiden dengan \(v\text{.}\)
Tinjau graf \(G\) dengan himpunan simpul \(V = \{1,2,3,4\}\) dan himpunan sisi \(E = \{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}\text{.}\) Berapakah derajat setiap simpul dalam \(G\text{?}\)
Kita memperoleh \(d(1) = 3\text{,}\)\(d(2) = 2\text{,}\)\(d(3) = 2\text{,}\) dan \(d(4) = 1\text{.}\) Anda dapat melihatnya dengan menghitung banyaknya sisi yang berinsiden dengan setiap simpul, atau dengan menghitung banyaknya sisi (himpunan bagian) yang memuat setiap simpul.
Jadi, mungkinkah 15 orang masing-masing berjabat tangan dengan tepat tiga orang dalam kelompoknya? Dengan kata lain, adakah graf dengan 15 simpul yang semuanya berderajat 3? Jawabannya tidak!
Salah satu cara melihatnya adalah dengan menanyakan berapa banyak sisi yang akan dimiliki graf semacam itu. Setiap simpul berinsiden dengan tiga sisi, sehingga dengan menghitung insidensi kita memperoleh \(15\cdot 3 = 45\text{.}\) Namun, setiap sisi berinsiden dengan dua simpul, sehingga setiap sisi telah kita hitung dua kali. Jadi, banyaknya sisi pada graf tersebut seharusnya \(45/2 = 22.5\text{.}\) Akan tetapi, banyaknya sisi dalam graf harus berupa bilangan bulat, sehingga graf semacam itu tidak ada.
Hal ini menunjukkan bahwa kita dapat menyatakan sesuatu yang lebih umum. Proposisi berikut merupakan konsekuensi sederhana dari Lemma Jabat Tangan 2.1.8, yang akan kita buktikan dalam Subbab 2.1. Di sini kita memberikan bukti lengkap untuk perumusan khusus berikut.
Kita akan membuktikannya dengan kontradiksi. Misalkan terdapat graf dengan banyaknya simpul berderajat ganjil yang ganjil. Tinjau jumlah derajat semua simpul. Jumlah derajat simpul-simpul berderajat ganjil akan bernilai ganjil (karena jumlah dari sebanyak ganjil bilangan ganjil adalah ganjil). Jumlah derajat simpul-simpul berderajat genap akan bernilai genap (setiap jumlah bilangan genap pasti genap). Jumlah bilangan ganjil dan bilangan genap adalah ganjil. Dengan demikian, jumlah semua derajat akan bernilai ganjil.
Namun, banyaknya sisi dalam graf sama dengan setengah jumlah derajat (berdasarkan Lema 2.1.8, atau cukup karena setiap sisi menyumbang satu pada perhitungan derajat masing-masing dari dua simpul). Karena banyaknya sisi merupakan bilangan bulat, kita melihat bahwa jumlah derajat harus genap. Hal ini bertentangan dengan hasil yang kita peroleh dalam paragraf sebelumnya.
Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu lebih lanjut.
Diberikan himpunan \(A\) dan \(B\text{,}\) irisan \(A\) dan \(B\text{,}\) ditulis \(A \cap B\text{,}\) adalah himpunan semua elemen yang terdapat dalam \(A\) dan \(B\) sekaligus.
Misalkan Anda ingin membuktikan bahwa untuk semua himpunan \(A\) dan \(B\text{,}\) berlaku \(A \cap B \subseteq A\text{.}\) Manakah di antara pilihan berikut yang merupakan awal yang baik bagi bukti dengan kontradiksi?
Susunlah beberapa pernyataan di bawah ini sehingga membentuk bukti yang benar bagi pernyataan berikut: “Untuk sebarang himpunan \(A\) dan \(B\text{,}\) jika \(B \subseteq A \cap B\text{,}\) maka \(B \subseteq A\text{.}\)”
Misalkan \(f:X \to Y\) adalah fungsi dan \(B \subseteq Y\) merupakan himpunan bagian dari kodomain. Definisikan citra invers \(B\) oleh \(f\) sebagai himpunan \(f\inv(B) = \{x \in X \st f(x) \in B\}\text{.}\) Artinya, himpunan ini memuat semua elemen domain yang dipetakan ke elemen-elemen dalam \(B\text{.}\)
Irisan himpunan \(A\) dan \(B\text{,}\) dilambangkan dengan \(A \cap B\text{,}\) adalah himpunan semua elemen yang terdapat dalam \(A\) dan \(B\) sekaligus.
Buktikan bahwa untuk sebarang himpunan \(A\text{,}\)\(B\text{,}\) dan \(C\text{,}\) jika \(A \cup B \subseteq C\text{,}\) maka \(A \subseteq C\) dan \(B \subseteq C\text{.}\)
Buktikan bahwa untuk sebarang himpunan \(A\text{,}\)\(B\text{,}\) dan \(C\text{,}\) jika \(A \subseteq C\) dan \(B \subseteq C\text{,}\) maka \(A \cup B \subseteq C\text{.}\)
Selisih himpunan \(A\) dan \(B\text{,}\) ditulis \(A \setminus B\text{,}\) adalah himpunan semua elemen yang terdapat dalam \(A\text{,}\) tetapi tidak terdapat dalam \(B\text{.}\)
Diberikan fungsi \(f:X \to Y\) dan himpunan \(B \subseteq Y\text{,}\) kita mendefinisikan citra invers \(B\) oleh \(f\) sebagai himpunan \(f\inv(B) = \{x \in X \st f(x) \in B\}\text{.}\) Artinya, himpunan ini memuat semua elemen domain yang dipetakan ke elemen-elemen dalam \(B\text{.}\)
Misalkan \(f:X \to Y\) adalah fungsi, dan misalkan \(A\) serta \(B\) merupakan himpunan bagian dari \(Y\text{.}\) Buktikan bahwa \(f\inv(A \cap B) = f\inv(A) \cap f\inv(B)\text{.}\)
Misalkan \(f:X \to Y\) adalah fungsi, dan misalkan \(A\) serta \(B\) merupakan himpunan bagian dari \(Y\text{.}\) Buktikan bahwa \(f\inv(A \cup B) = f\inv(A) \cup f\inv(B)\text{.}\)
Relasi “\(\sim\)” (sebangun dengan) pada himpunan segitiga di bidang (dua segitiga sebangun jika sudut-sudutnya sama, tetapi ukurannya tidak harus sama).
