More Info
KPOP Image Download
  • Top University
  • Top Anime
  • Home Design
  • Top Legend



  1. ENSIKLOPEDIA
  2. Teorema Cantor - Wikipedia bahasa Indonesia, ensiklopedia bebas
Teorema Cantor - Wikipedia bahasa Indonesia, ensiklopedia bebas

Teorema Cantor

  • العربية
  • Asturianu
  • Català
  • Čeština
  • Deutsch
  • Ελληνικά
  • English
  • Español
  • Euskara
  • فارسی
  • Suomi
  • Français
  • Galego
  • עברית
  • Hrvatski
  • Magyar
  • Italiano
  • 日本語
  • ქართული
  • 한국어
  • Lombard
  • Nederlands
  • Norsk nynorsk
  • Norsk bokmål
  • Occitan
  • Polski
  • Português
  • Română
  • Русский
  • Simple English
  • Српски / srpski
  • Svenska
  • ไทย
  • Türkçe
  • Українська
  • Tiếng Việt
  • 中文
  • 文言
  • 粵語
Sunting pranala
  • Halaman
  • Pembicaraan
  • Baca
  • Sunting
  • Sunting sumber
  • Lihat riwayat
Perkakas
Tindakan
  • Baca
  • Sunting
  • Sunting sumber
  • Lihat riwayat
Umum
  • Pranala balik
  • Perubahan terkait
  • Pranala permanen
  • Informasi halaman
  • Kutip halaman ini
  • Lihat URL pendek
  • Unduh kode QR
Cetak/ekspor
  • Buat buku
  • Unduh versi PDF
  • Versi cetak
Dalam proyek lain
  • Wikimedia Commons
  • Butir di Wikidata
Tampilan
Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Untuk teorema lain yang menggunakan nama Cantor, lihat Teorema Cantor (disambiguasi).
Kardinalitas dari himpunan { x , y , z } {\displaystyle \left\{x,\,y,\,z\right\}} {\displaystyle \left\{x,\,y,\,z\right\}} adalah 3 {\displaystyle 3} {\displaystyle 3}, sedangkan terdapat delapan elemen pada himpunan kuasanya ( 3 < 2 3 {\displaystyle 3<2^{3}} {\displaystyle 3<2^{3}}), yang diurutkan berdasarkan relasi himpunan bagian.

Dalam teori himpunan, teorema Cantor merupakan hasil fundamental yang menyatakan bahwa, untuk setiap himpunan X {\displaystyle X} {\displaystyle X}, himpunan seluruh himpunan bagian dari X {\displaystyle X} {\displaystyle X} (yang dikenal sebagai himpunan kuasa dari X {\displaystyle X} {\displaystyle X}, dan ditulis sebagai P ( X ) {\displaystyle {\mathcal {P}}\!\left(X\right)} {\displaystyle {\mathcal {P}}\!\left(X\right)}) memiliki kardinalitas yang lebih dari X {\displaystyle X} {\displaystyle X} itu sendiri. Secara simbolis, jika notasi | X | {\displaystyle \left|X\right|} {\displaystyle \left|X\right|} menyatakan kardinalitas dari himpunan X {\displaystyle X} {\displaystyle X}, maka teorema Cantor menyatakan bahwa | P ( X ) | > | X | {\displaystyle \left|{\mathcal {P}}\!\left(X\right)\right|>\left|X\right|} {\displaystyle \left|{\mathcal {P}}\!\left(X\right)\right|>\left|X\right|}

Jika himpunannya berhingga, teorema Cantor dapat dipandang sebagai kebenaran melalui enumerasi sederhana dari banyaknya himpunan bagian. Apabila himpunan kosong dihitung sebagai himpunan bagian, maka suatu himpunan dengan n {\displaystyle n} {\displaystyle n} elemen memiliki 2 n {\displaystyle 2^{n}} {\displaystyle 2^{n}} himpunan bagian, dan teoremanya bernilai benar sebab 2 n > n {\displaystyle 2^{n}>n} {\displaystyle 2^{n}>n} untuk setiap bilangan cacah n {\displaystyle n} {\displaystyle n}.

Hal yang lebih signifikan ialah penemuan Cantor akan argumentasi yang dapat diterapkan pada sembarang himpunan, dan menunjukkan bahwa teoremanya juga berlaku untuk himpunan takhingga. Akibatnya, kardinalitas dari bilangan riil, yang sama dengan kardinalitas himpunan kuasa dari bilangan bulat, lebih dari kardinalitas bilngan bulat; lihat kardinalitas dari kontinum untuk pembahasan lebih lanjut.

Teorema ini dinamai untuk Georg Cantor, orang pertama yang menyatakan sekaligus membuktikan teorema ini pada akhir abad ke-19. Teorema Cantor memiliki akibat yang penting untuk filsafat matematika. Misalnya, dengan mengambil himpunan kuasa dari suatu himpunan tak terhingga secara berulang dan menerapkan teorema Cantor, maka diperoleh kardinal tak terhingga yang hierarkinya tiada habisnya. Akibatnya, teorema ini menyiratkan bahwa tidak ada bilangan kardinal terbesar (dalam bahasa sehari-hari, "tidak ada takhingga terbesar").

Bukti

[sunting | sunting sumber]

Kasus khusus

[sunting | sunting sumber]

Bagian ini akan menggunakan kasus spesifik ketika H {\displaystyle H} {\displaystyle H} merupakan himpunan terhitung tak terhingga. Tanpa mengurangi keumuman, akan digunakan himpunan H = N = { 1 , 2 , 3 , 4 , … } {\displaystyle H=\mathbb {N} =\left\{1,\,2,\,3,\,4,\,\ldots \right\}} {\displaystyle H=\mathbb {N} =\left\{1,\,2,\,3,\,4,\,\ldots \right\}}, yaitu himpunan semua bilangan asli.

Misalkan himpunan N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } sama banyaknya dengan himpunan kuasanya, P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}. Himpunan P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} memuat tak terhingga banyaknya himpunan bagian dari N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} }, seperti himpunan bilangan genap positif { 2 , 4 , 6 , 8 , … } = { 2 n ∣ n ∈ N } {\displaystyle \left\{2,\,4,\,6,\,8,\,\ldots \right\}=\left\{2n\mid n\in \mathbb {N} \right\}} {\displaystyle \left\{2,\,4,\,6,\,8,\,\ldots \right\}=\left\{2n\mid n\in \mathbb {N} \right\}} dan himpunan kosong ∅ {\displaystyle \varnothing } {\displaystyle \varnothing }. Beberapa himpunan yang termuat pada P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} antara lain: P ( N ) = { ∅ , { 1 , 2 } , { 1 , 2 , 3 } , { 4 } , { 1 , 5 } , { 3 , 4 , 6 } , { 2 , 4 , 6 , 8 , … } , … } {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)=\left\{\varnothing ,\,\left\{1,\,2\right\},\,\left\{1,\,2,\,3\right\},\,\left\{4\right\},\,\left\{1,\,5\right\},\,\left\{3,\,4,\,6\right\},\,\left\{2,\,4,\,6,\,8,\,\ldots \right\},\,\ldots \right\}} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)=\left\{\varnothing ,\,\left\{1,\,2\right\},\,\left\{1,\,2,\,3\right\},\,\left\{4\right\},\,\left\{1,\,5\right\},\,\left\{3,\,4,\,6\right\},\,\left\{2,\,4,\,6,\,8,\,\ldots \right\},\,\ldots \right\}}

Oleh karena N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } diasumsikan sama banyaknya dengan P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}, maka setiap elemen dari N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } dapat melabeli setiap elemen dari P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}, dengan syarat tidak ada elemen dari kedua himpunan yang tidak terlabeli. Salah satu cara pelabelannya adalah sebagai berikut: N { 1 ⟷ { 4 , 5 } 2 ⟷ { 1 , 2 , 3 } 3 ⟷ { 4 , 5 , 6 } 4 ⟷ { 1 , 3 , 5 } ⋮ ⋮ ⋮ } P ( N ) {\displaystyle \mathbb {N} \,{\begin{Bmatrix}1&\longleftrightarrow &\left\{4,\,5\right\}\\2&\longleftrightarrow &\left\{1,\,2,\,3\right\}\\3&\longleftrightarrow &\left\{4,\,5,\,6\right\}\\4&\longleftrightarrow &\left\{1,\,3,\,5\right\}\\\vdots &\vdots &\vdots \end{Bmatrix}}\,{\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle \mathbb {N} \,{\begin{Bmatrix}1&\longleftrightarrow &\left\{4,\,5\right\}\\2&\longleftrightarrow &\left\{1,\,2,\,3\right\}\\3&\longleftrightarrow &\left\{4,\,5,\,6\right\}\\4&\longleftrightarrow &\left\{1,\,3,\,5\right\}\\\vdots &\vdots &\vdots \end{Bmatrix}}\,{\mathcal {P}}\!\left(\mathbb {N} \right)} Diberikan suatu proses pelabelan, beberapa bilangan asli melabelkan himpunan bagian yang memuat dirinya sendiri. Misalnya, pada contoh di atas, bilangan 2 {\displaystyle 2} {\displaystyle 2} melabelkan himpunan { 1 , 2 , 3 } {\displaystyle \left\{1,\,2,\,3\right\}} {\displaystyle \left\{1,\,2,\,3\right\}}, yang memuat 2 {\displaystyle 2} {\displaystyle 2} sebagai anggotanya. Misalkan bilangan-bilangan tersebut disebut egois. Beberapa bilangan asli lainnya melabelkan himpunan bagian yang tidak memuat dirinya sendiri. Misalnya, pada contoh di atas, bilangan 1 {\displaystyle 1} {\displaystyle 1} melabelkan himpunan { 4 , 5 } {\displaystyle \left\{4,\,5\right\}} {\displaystyle \left\{4,\,5\right\}}, yang tidak memuat 1 {\displaystyle 1} {\displaystyle 1} sebagai anggotanya.

Dengan menggunakan ide ini, maka dapat dikonstruksikan suatu himpunan bilangan asli yang istimewa. Himpunan ini akan memberikan kontradiksi yang sedang diincar. Misalkan E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}} adalah himpunan semua bilangan yang tidak egois. Berdasarkan definisi, himpunan kuasa P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} memuat semua himpunan bilangan asli, yang mengakibatkan E ∈ P ( N ) {\displaystyle {\cancel {E}}\in {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\cancel {E}}\in {\mathcal {P}}\!\left(\mathbb {N} \right)}. Jika pemetaannya bersifat bijektif, maka E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}} harus dilabelkan dengan suatu bilangan asli, misalnya e {\displaystyle e} {\displaystyle e}. Akan tetapi, hal ini menimbulkan masalah.

  1. Jika e ∈ E {\displaystyle e\in {\cancel {E}}} {\displaystyle e\in {\cancel {E}}}, maka e {\displaystyle e} {\displaystyle e} merupakan bilangan egois, dan hal ini bertentangan dengan definisi dari E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}}.
  2. Jika e ∉ E {\displaystyle e\not \in {\cancel {E}}} {\displaystyle e\not \in {\cancel {E}}}, maka e {\displaystyle e} {\displaystyle e} adalah bilangan yang tidak egois, sehingga e {\displaystyle e} {\displaystyle e} seharusnya menjadi anggota dari E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}}.

Akibatnya, tidak mungkin ada elemen e {\displaystyle e} {\displaystyle e} yang dipetakan ke E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}}.

Oleh karena tidak ada bilangan asli yang melabelkan himpunan E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}}, maka pengandaian di awal bernilai salah, yaitu terdapat bijeksi antara N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } dan P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}.

Perhatikan bahwa himpunan E {\displaystyle {\cancel {E}}} {\displaystyle {\cancel {E}}} mungkin saja kosong. Hal ini mengakibatkan setiap bilangan asli n {\displaystyle n} {\displaystyle n} dipetakan ke himpunan bagian yang memuat n {\displaystyle n} {\displaystyle n}. Dengan kata lain, setiap bilangan asli melabelkan suatu himpunan tak kosong dan tidak ada bilangan yang melabelkan himpunan kosong. Akan tetapi, ∅ ∈ P ( N ) {\displaystyle \varnothing \in {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle \varnothing \in {\mathcal {P}}\!\left(\mathbb {N} \right)}, sehingga pemetaannya tetap tidak meliput P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}.

Berdasarkan pembuktian melalui kontradiksi ini, terbukti bahwa | N | ≠ | P ( N ) | {\displaystyle \left|\mathbb {N} \right|\neq \left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|} {\displaystyle \left|\mathbb {N} \right|\neq \left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|}. Selain itu, | N | > | P ( N ) | {\displaystyle \left|\mathbb {N} \right|>\left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|} {\displaystyle \left|\mathbb {N} \right|>\left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|} juga tidaklah mungkin, sebab berdasarkan definisi, P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} memuat semua singleton, dan singleton-singleton ini membentuk "salinan" dari N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } di dalam P ( N ) {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)} {\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}. Akibatnya, hanya tersisa satu kemungkinan, yaitu | N | < | P ( N ) | {\displaystyle \left|\mathbb {N} \right|<\left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|} {\displaystyle \left|\mathbb {N} \right|<\left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|}

Kasus umum

[sunting | sunting sumber]

Argumen Cantor terbilang elegan dan sangat sederhana. Bukti lengkapnya disajikan dibawah, beserta penjelasan rinci setelahnya.

Teorema Cantor — Jika f {\displaystyle f} {\displaystyle f} adalah pemetaan dari himpunan H {\displaystyle H} {\displaystyle H} ke himpunan kuasanya, P ( H ) {\displaystyle {\mathcal {P}}\!\left(H\right)} {\displaystyle {\mathcal {P}}\!\left(H\right)}, maka f {\displaystyle f} {\displaystyle f} tidak surjektif. Lebih lanjut, berlaku pertidaksamaan | H | < | P ( H ) | {\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|} {\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|} untuk sembarang himpunan H {\displaystyle H} {\displaystyle H}.

Bukti —

Didefinisikan himpunan H = { x ∈ H ∣ x ∉ f ( x ) } {\displaystyle {\cancel {H}}=\left\{x\in H\mid x\not \in f\!\left(x\right)\right\}} {\displaystyle {\cancel {H}}=\left\{x\in H\mid x\not \in f\!\left(x\right)\right\}} Himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}} terjamin keujudannya melalui skema aksioma spesifikasi. Berdasarkan definisi, maka H ∈ P ( H ) {\displaystyle {\cancel {H}}\in {\mathcal {P}}\!\left(H\right)} {\displaystyle {\cancel {H}}\in {\mathcal {P}}\!\left(H\right)} sebab H ⊆ H {\displaystyle {\cancel {H}}\subseteq H} {\displaystyle {\cancel {H}}\subseteq H}.
Akan dibuktikan bahwa f {\displaystyle f} {\displaystyle f} tidak bersifat surjektif melalui kontradiksi. Diasumsikan f {\displaystyle f} {\displaystyle f} bersifat surjektif.
Berdasarkan definisi fungsi surjektif, maka terdapat suatu elemen c ∈ H {\displaystyle c\in H} {\displaystyle c\in H} sedemikian sehingga berlaku f ( c ) = H {\displaystyle f\!\left(c\right)={\cancel {H}}} {\displaystyle f\!\left(c\right)={\cancel {H}}} Oleh karena c ∈ H {\displaystyle c\in H} {\displaystyle c\in H}, maka berdasarkan definisi dari himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}}, diperoleh c ∈ H ⟺ c ∉ f ( c ) {\displaystyle c\in {\cancel {H}}\iff c\not \in f\!\left(c\right)} {\displaystyle c\in {\cancel {H}}\iff c\not \in f\!\left(c\right)} sehingga didapatkan c ∈ H ⟺ c ∉ H {\displaystyle c\in {\cancel {H}}\iff c\not \in {\cancel {H}}} {\displaystyle c\in {\cancel {H}}\iff c\not \in {\cancel {H}}} yang tentunya mustahil terjadi. Akibatnya, f {\displaystyle f} {\displaystyle f} tidak bersifat surjektif, via reductio ad absurdum.
Di sisi lain, f {\displaystyle f} {\displaystyle f} dimungkinkan bersifat injektif, salah satunya ialah f ( x ) = { x } {\displaystyle f\!\left(x\right)=\left\{x\right\}} {\displaystyle f\!\left(x\right)=\left\{x\right\}} yang mengakibatkan | H | < | P ( H ) | {\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|} {\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|}.

Misalkan X {\displaystyle X} {\displaystyle X} dan Y {\displaystyle Y} {\displaystyle Y} adalah sembarang himpunan. Berdasarkan definisi dari kardinalitas, maka | X | < | Y | {\displaystyle \left|X\right|<\left|Y\right|} {\displaystyle \left|X\right|<\left|Y\right|} jika dan hanya jika terdapat suatu fungsi injektif namun tidak bijektif dari X {\displaystyle X} {\displaystyle X} ke Y {\displaystyle Y} {\displaystyle Y}. Hal ini dapat diraih dengan menunjukkan bahwa tidak ada pemetaan surjektif dari X {\displaystyle X} {\displaystyle X} ke Y {\displaystyle Y} {\displaystyle Y}. Inilah inti dari teorema Cantor: tidak ada fungsi surjektif dari sembarang himpunan H {\displaystyle H} {\displaystyle H} ke himpunan kuasanya. Untuk membuktikan ini, maka cukup dengan menunjukkan bahwa tidak ada fungsi f {\displaystyle f} {\displaystyle f} (yang memetakan elemen pada H {\displaystyle H} {\displaystyle H} ke himpunan bagian dari H {\displaystyle H} {\displaystyle H}) yang dapat meraih setiap himpunan bagian yang ada. Dengan kata lain, maka cukup ditunjukkan bahwa terdapat suatu himpunan bagian dari H {\displaystyle H} {\displaystyle H} yang tidak sama dengan f ( x ) {\displaystyle f\!\left(x\right)} {\displaystyle f\!\left(x\right)}, untuk setiap x ∈ H {\displaystyle x\in H} {\displaystyle x\in H}. Ingat kembali bahwa setiap f ( x ) {\displaystyle f\!\left(x\right)} {\displaystyle f\!\left(x\right)} merupakan himpunan bagian dari H {\displaystyle H} {\displaystyle H}. Himpunan bagian dengan sifat tersebut diberikan melalui konstruksi berikut: H = { x ∈ H ∣ x ∉ f ( x ) } {\displaystyle {\cancel {H}}=\left\{x\in H\mid x\not \in f\!\left(x\right)\right\}} {\displaystyle {\cancel {H}}=\left\{x\in H\mid x\not \in f\!\left(x\right)\right\}} Himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}} terkadang dikenal sebagai himpunan diagonal Cantor dari f {\displaystyle f} {\displaystyle f}. Berdasarkan definisi dari himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}}, maka untuk setiap x ∈ H {\displaystyle x\in H} {\displaystyle x\in H}, x ∈ H {\displaystyle x\in {\cancel {H}}} {\displaystyle x\in {\cancel {H}}} jika dan hanya jika x ∉ f ( x ) {\displaystyle x\not \in f\!\left(x\right)} {\displaystyle x\not \in f\!\left(x\right)}. Akan dikaji dua kasus berikut:

  1. Jika x ∈ f ( x ) {\displaystyle x\in f\!\left(x\right)} {\displaystyle x\in f\!\left(x\right)}, maka x ∉ H {\displaystyle x\not \in {\cancel {H}}} {\displaystyle x\not \in {\cancel {H}}}, sehingga f ( x ) ≠ H {\displaystyle f\!\left(x\right)\neq {\cancel {H}}} {\displaystyle f\!\left(x\right)\neq {\cancel {H}}}.
  2. Jika x ∉ f ( x ) {\displaystyle x\not \in f\!\left(x\right)} {\displaystyle x\not \in f\!\left(x\right)}, maka x ∈ H {\displaystyle x\in {\cancel {H}}} {\displaystyle x\in {\cancel {H}}}, sehingga f ( x ) ≠ H {\displaystyle f\!\left(x\right)\neq {\cancel {H}}} {\displaystyle f\!\left(x\right)\neq {\cancel {H}}}.

Berdasarkan kedua kasus di atas, himpunan f ( x ) ≠ H {\displaystyle f\!\left(x\right)\neq {\cancel {H}}} {\displaystyle f\!\left(x\right)\neq {\cancel {H}}} untuk setiap x ∈ H {\displaystyle x\in H} {\displaystyle x\in H} sebab himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}} dikonstruksikan dari elemen pada H {\displaystyle H} {\displaystyle H} yang bayangan oleh fungsi f {\displaystyle f} {\displaystyle f} tidak memuat dirinya sendiri. Dengan kata lain, terbukti bahwa terdapat suatu elemen c ∈ H {\displaystyle c\in H} {\displaystyle c\in H} sedemikian sehingga persyaratan f ( c ) = B {\displaystyle f\!\left(c\right)=B} {\displaystyle f\!\left(c\right)=B} mengakibatkan kontradiksi berikut: c ∈ H ⟺ c ∉ f ( c ) (berdasarkan definisi dari  H ) c ∈ H ⟺ c ∈ f ( c ) (berdasarkan asumsi bahwa  f ( x ) = H ) {\displaystyle {\begin{aligned}c\in {\cancel {H}}&\iff c\not \in f\!\left(c\right)&&{\text{(berdasarkan definisi dari }}{\cancel {H}}{\text{)}}\\c\in {\cancel {H}}&\iff c\in f\!\left(c\right)&&{\text{(berdasarkan asumsi bahwa }}f\!\left(x\right)={\cancel {H}}{\text{)}}\\\end{aligned}}} {\displaystyle {\begin{aligned}c\in {\cancel {H}}&\iff c\not \in f\!\left(c\right)&&{\text{(berdasarkan definisi dari }}{\cancel {H}}{\text{)}}\\c\in {\cancel {H}}&\iff c\in f\!\left(c\right)&&{\text{(berdasarkan asumsi bahwa }}f\!\left(x\right)={\cancel {H}}{\text{)}}\\\end{aligned}}} sehingga berdasarkan reductio ad absurdum, asumsi di awal bernilai salah.[1] Akibatnya, tidak ada c ∈ H {\displaystyle c\in H} {\displaystyle c\in H} yang memenuhi f ( c ) = H {\displaystyle f\!\left(c\right)={\cancel {H}}} {\displaystyle f\!\left(c\right)={\cancel {H}}}. Dengan kata lain, himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}} bukanlah bayangan dari f {\displaystyle f} {\displaystyle f} dan fungsi f {\displaystyle f} {\displaystyle f} tidak memetakan setiap elemen ke himpunan kuasa dari H {\displaystyle H} {\displaystyle H}, yang berarti, f {\displaystyle f} {\displaystyle f} tidak bersifat surjektif.

Terakhir, untuk melengkapi pembuktiannya, perlu ditunjukkan bahwa terdapat suatu fungsi injektif dari H {\displaystyle H} {\displaystyle H} ke himpunan kuasanya. Proses mencari fungsi tersebut tidaklah sulit: petakan elemen x {\displaystyle x} {\displaystyle x} ke himpunan singleton { x } {\displaystyle \left\{x\right\}} {\displaystyle \left\{x\right\}}. Sekarang pembuktiannya sudah lengkap, dan berlaku ketaksamaan tegas | H | < | P ( H ) | {\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|} {\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|} untuk setiap himpunan H {\displaystyle H} {\displaystyle H}.

Oleh karena elemen x {\displaystyle x} {\displaystyle x} muncul dua kali pada ekspresi " x ∈ f ( x ) {\displaystyle x\in f\!\left(x\right)} {\displaystyle x\in f\!\left(x\right)}", maka argumen ini disebut sebagai argument diagonal. Untuk himpunan terhitung (atau berhingga), argumentasi dari pembuktian di atas dapat diilustrasikan dengan membuat tabel yang

  1. setiap barisnya dilabeli oleh suatu elemen x {\displaystyle x} {\displaystyle x} dari himpunan H = { x 1 , x 2 , x 3 , … } {\displaystyle H=\left\{x_{1},\,x_{2},\,x_{3},\,\ldots \right\}} {\displaystyle H=\left\{x_{1},\,x_{2},\,x_{3},\,\ldots \right\}} secara berurutan. Himpunan H {\displaystyle H} {\displaystyle H} diasumsikan terurut linear sehingga tabelnya dapat dikonstruksikan.
  2. setiap kolomnya dilabelkan oleh suatu elemen y {\displaystyle y} {\displaystyle y} dari himpunan P ( H ) {\displaystyle {\mathcal {P}}\!\left(H\right)} {\displaystyle {\mathcal {P}}\!\left(H\right)}. Kolomnya diurutkan berdasarkan argumen dari f {\displaystyle f} {\displaystyle f}. Dengan kata lain, kolomnya dilabeli sebagai f ( x 1 ) , f ( x 2 ) , f ( x 3 ) , … {\displaystyle f\!\left(x_{1}\right)\!,\,f\!\left(x_{2}\right)\!,\,f\!\left(x_{3}\right)\!,\,\ldots } {\displaystyle f\!\left(x_{1}\right)\!,\,f\!\left(x_{2}\right)\!,\,f\!\left(x_{3}\right)\!,\,\ldots } dengan urutan ini.
  3. perpotongan dari setiap baris x {\displaystyle x} {\displaystyle x} dan kolom y {\displaystyle y} {\displaystyle y} berisi nilai benar/salah dari pernyataan x ∈ y {\displaystyle x\in y} {\displaystyle x\in y}. Dengan kata lain, setiap baris berisi nilai fungsi indikator dari himpunan pada masing-masing kolom.

Diberikan suatu urutan yang dipilih untuk label baris dan kolom, diagonal utama D {\displaystyle D} {\displaystyle D} dari tabel ini berisi nilai kebenaran dari pernyataan x ∈ f ( x ) {\displaystyle x\in f\!\left(x\right)} {\displaystyle x\in f\!\left(x\right)} untuk setiap x ∈ H {\displaystyle x\in H} {\displaystyle x\in H}. Salah satu tabelnya dapat dilihat sebagai berikut: f ( x 1 ) f ( x 2 ) f ( x 3 ) f ( x 4 ) ⋯ x 1 B B S B ⋯ x 2 B S S S ⋯ x 3 S S B B ⋯ x 4 S B B B ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ {\displaystyle {\begin{array}{c|ccccc}&f(x_{1})&f(x_{2})&f(x_{3})&f(x_{4})&\cdots \\\hline x_{1}&{\color {red}B}&B&S&B&\cdots \\x_{2}&B&{\color {red}S}&S&S&\cdots \\x_{3}&S&S&{\color {red}B}&B&\cdots \\x_{4}&S&B&B&{\color {red}B}&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}} {\displaystyle {\begin{array}{c|ccccc}&f(x_{1})&f(x_{2})&f(x_{3})&f(x_{4})&\cdots \\\hline x_{1}&{\color {red}B}&B&S&B&\cdots \\x_{2}&B&{\color {red}S}&S&S&\cdots \\x_{3}&S&S&{\color {red}B}&B&\cdots \\x_{4}&S&B&B&{\color {red}B}&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}} Himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}} pada paragraf sebelumnya dikonstruksikan berdasarkan negasi dari nilai kebenaran pada diagonal utama D {\displaystyle D} {\displaystyle D} (yang pada contoh di atas, diwarnai dengan merah), yaitu menukar "benar" dan "salah".[1] Akibatnya, fungsi indikator dari himpunan H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}} akan berbeda dengan setiap kolom pada setidaknya satu entri, sehingga tidak ada kolom yang mewakili H {\displaystyle {\cancel {H}}} {\displaystyle {\cancel {H}}}.

Lihat juga

[sunting | sunting sumber]
  • Teorema Schröder–Bernstein
  • Artikel teori himpunan pertama Cantor
  • Kontroversi atas teori Cantor

Referensi

[sunting | sunting sumber]
  1. ^ a b Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. hlm. 118–119. ISBN 978-0-19-925405-7.
  • Halmos, Paul, Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Dicetak ulang oleh Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (edisi Springer-Verlag). Dicetak ulang oleh Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (edisi Paperback).
  • Jech, Thomas (2002), Set Theory, Springer Monographs in Mathematics (Edisi 3rd millennium), Springer, ISBN 3-540-44085-2

Pranala luar

[sunting | sunting sumber]
  • Hazewinkel, Michiel, ed. (2001) [1994], "Cantor theorem", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
  • (Inggris) Weisstein, Eric W. "Cantor's Theorem". MathWorld.
  • l
  • b
  • s
  • Metalogika
  • Metamatematika
  • Fondasi matematika
  • Independensi
  • Interpretasi
  • Kekukuhan
  • Kepuasan
  • Ketetapan
  • Konsistensi
  • Metateorema
  • Metode efektif
  • Pemenuhan
  • Perbedaan guna-penggunaan
  • Perbedaan tipe-token
  • Teorema Cantor
  • Teorema Church
  • Teorema Löwenheim–Skolem
  • Tesis Church
  • Teorema kelengkapan Gödel
  • Teorema ketidaklengkapan Gödel
  • l
  • b
  • s
Teori himpunan
Umum
  • Himpunan (matematika)
Diagram Venn irisan himpunan
Aksioma
  • Adjungsi
  • Batas ukuran
  • Determinasi
  • Gabungan
  • Himpunan kuasa
  • Keberaturan
  • Kebisadibangunan (V=L)
  • Perluasan
  • Pasangan
  • Pemilihan
    • tercacah
    • terikat
    • global
  • Takhingga
  • Aksioma Martin
  • Skema aksioma
    • penggantian
    • spesifikasi
Operasi
  • Gabungan
  • Gabungan lepas
  • Himpunan kuasa
  • Hukum De Morgan
  • Irisan
  • Komplemen
  • Produk Kartesius
  • Selisih himpunan
  • Beda setangkup
  • Konsep
  • Metode
  • Argumen diagonal
  • Bilangan kardinal (besar)
  • Bilangan ordinal
  • Diagram Venn
  • Elemen
    • pasangan terurut
    • rangkap
  • Hipotesis kontinum
  • Induksi lintas-hingga
  • Kardinalitas
  • Kelas
  • Keluarga
  • Korespondensi satu-ke-satu
  • Pemaksaan
  • Semesta yang bisa dibangun
Jenis himpunan
  • Himpunan bagian · Superhimpunan
  • Berhingga (turun-temurun)
  • Takhingga (takhingga Dedekind)
  • Kabur
  • Kosong
  • Rekursif
  • Semesta
  • Tercacah
  • Tak tercacah
  • Transitif
Teori
  • Aksiomatik
  • Alternatif
  • Naif
  • Teorema Cantor
  • Zermelo
    • Umum
  • Principia Mathematica
    • New Foundations (NF, NFU)
  • Zermelo–Fraenkel (ZFC)
    • von Neumann–Bernays–Gödel (NBG)
      • Morse–Kelley
    • Kripke–Platek
    • Tarski–Grothendieck
  • Paradoks
  • Masalah
  • Paradoks Russell
  • Masalah Suslin
  • Paradoks Burali-Forti
Teoretisi himpunan
  • Abraham Fraenkel
  • Bertrand Russell
  • Ernst Zermelo
  • Georg Cantor
  • John von Neumann
  • Kurt Gödel
  • Paul Bernays
  • Paul Cohen
  • Richard Dedekind
  • Thomas Jech
  • Thoralf Skolem
  • Willard Quine
  • l
  • b
  • s
Logika matematika
Umum
  • Bahasa formal
  • Aturan formasi
  • Sistem formal
  • Sistem deduktif
  • Pembuktian formal
  • Formal semantik
  • Formula bentukan
  • Himpunan
  • Elemen
  • Kelas
  • Logika klasik
  • Aksioma
  • Deduksi alami
  • Aturan inferensi
  • Relasi
  • Teorema
  • Konsekuensi logis
  • Sistem aksiomatis
  • Teori tipe
  • Simbol
  • Sintaks
  • Teori
Logika tradisional
  • Proposisi
  • Inferensi
  • Argumen
  • Validitas
  • Meyakinkan
  • Silogisme
  • Sisi berlawanan
  • Diagram Venn
Kalkulus proposisional
Logika boolean
  • Fungsi Boolean
  • Kalkulus proposisional
  • Formula proposisional
  • Hubungan logis
  • Tabel kebenaran
Logika predikat
  • Orde-pertama
  • Pembilang
  • Predikat
  • Orde-dua
  • Kalkulus predikat Monadic
Teori himpunan
  • Himpunan
  • Himpunan kosong
  • Enumerasi
  • Ekstensionalitas
  • Himpunan terbatas
  • Fungsi
  • Subhimpunan
  • Himpinan perpangkatan
  • Himpunan terhitung
  • Himpunan rekursif
  • Domain
  • Rentang
  • Pasangan berurut
  • Himputan tak terhitung
Teori model
  • Model
  • Interpretasi
  • Model nonstandar
  • Teori model terbatas
  • Nilai kebenaran
  • Validitas
Teori pembuktian
  • Pembuktian formal
  • Sistem deduktif
  • Sistem formal
  • Teorema
  • Konsekuensi logis
  • Aturan inferensi
  • Sintaks
Teori komputabilitas
  • Rekursi
  • Himpunan rekursif
  • Himpunan rekursif terhitung
  • Permasalahan keputusan
  • Tesis Church–Turing
  • Fungsi terhitung
  • Fungsi rekursif primitif
Kategori
Diperoleh dari "https://id.wikipedia.org/w/index.php?title=Teorema_Cantor&oldid=26454451"
Kategori:
  • Teori himpunan
  • Teorema dalam fondasi matematika
  • Bilangan kardinal
  • Georg Cantor
Kategori tersembunyi:
  • Pages using the JsonConfig extension
  • Articles with hatnote templates targeting a nonexistent page

Best Rank
More Recommended Articles