Teorema Cantor

teorema dalam teori himpunan

Dalam teori himpunan, teorema Cantor merupakan hasil fundamental yang menyatakan bahwa, untuk setiap himpunan , himpunan seluruh himpunan bagian dari (yang dikenal sebagai himpunan kuasa dari , dan ditulis sebagai ) memiliki kardinalitas yang lebih dari itu sendiri. Secara simbolis, jika notasi menyatakan kardinalitas dari himpunan , maka teorema Cantor menyatakan bahwa

Kardinalitas dari himpunan adalah , sedangkan terdapat delapan elemen pada himpunan kuasanya (), yang diurutkan berdasarkan relasi himpunan bagian.

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 elemen memiliki himpunan bagian, dan teoremanya bernilai benar sebab untuk setiap bilangan cacah .

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").

Kasus khusus

sunting

Bagian ini akan menggunakan kasus spesifik ketika   merupakan himpunan terhitung tak terhingga. Tanpa mengurangi keumuman, akan digunakan himpunan  , yaitu himpunan semua bilangan asli.

Misalkan himpunan   sama banyaknya dengan himpunan kuasanya,  . Himpunan   memuat tak terhingga banyaknya himpunan bagian dari  , seperti himpunan bilangan genap positif   dan himpunan kosong  . Beberapa himpunan yang termuat pada   antara lain:  

Oleh karena   diasumsikan sama banyaknya dengan  , maka setiap elemen dari   dapat melabeli setiap elemen dari  , dengan syarat tidak ada elemen dari kedua himpunan yang tidak terlabeli. Salah satu cara pelabelannya adalah sebagai berikut:   Diberikan suatu proses pelabelan, beberapa bilangan asli melabelkan himpunan bagian yang memuat dirinya sendiri. Misalnya, pada contoh di atas, bilangan   melabelkan himpunan  , yang memuat   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   melabelkan himpunan  , yang tidak memuat   sebagai anggotanya.

Dengan menggunakan ide ini, maka dapat dikonstruksikan suatu himpunan bilangan asli yang istimewa. Himpunan ini akan memberikan kontradiksi yang sedang diincar. Misalkan   adalah himpunan semua bilangan yang tidak egois. Berdasarkan definisi, himpunan kuasa   memuat semua himpunan bilangan asli, yang mengakibatkan  . Jika pemetaannya bersifat bijektif, maka   harus dilabelkan dengan suatu bilangan asli, misalnya  . Akan tetapi, hal ini menimbulkan masalah.

  1. Jika  , maka   merupakan bilangan egois, dan hal ini bertentangan dengan definisi dari  .
  2. Jika  , maka   adalah bilangan yang tidak egois, sehingga   seharusnya menjadi anggota dari  .

Akibatnya, tidak mungkin ada elemen   yang dipetakan ke  .

Oleh karena tidak ada bilangan asli yang melabelkan himpunan  , maka pengandaian di awal bernilai salah, yaitu terdapat bijeksi antara   dan  .

Perhatikan bahwa himpunan   mungkin saja kosong. Hal ini mengakibatkan setiap bilangan asli   dipetakan ke himpunan bagian yang memuat  . Dengan kata lain, setiap bilangan asli melabelkan suatu himpunan tak kosong dan tidak ada bilangan yang melabelkan himpunan kosong. Akan tetapi,  , sehingga pemetaannya tetap tidak meliput  .

Berdasarkan pembuktian melalui kontradiksi ini, terbukti bahwa  . Selain itu,   juga tidaklah mungkin, sebab berdasarkan definisi,   memuat semua singleton, dan singleton-singleton ini membentuk "salinan" dari   di dalam  . Akibatnya, hanya tersisa satu kemungkinan, yaitu  

Kasus umum

sunting

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

Teorema Cantor — Jika   adalah pemetaan dari himpunan   ke himpunan kuasanya,  , maka   tidak surjektif. Lebih lanjut, berlaku pertidaksamaan   untuk sembarang himpunan  .

Bukti —

Didefinisikan himpunan   Himpunan   terjamin keujudannya melalui skema aksioma spesifikasi. Berdasarkan definisi, maka   sebab  .
Akan dibuktikan bahwa   tidak bersifat surjektif melalui kontradiksi. Diasumsikan   bersifat surjektif.
Berdasarkan definisi fungsi surjektif, maka terdapat suatu elemen   sedemikian sehingga berlaku   Oleh karena  , maka berdasarkan definisi dari himpunan  , diperoleh   sehingga didapatkan   yang tentunya mustahil terjadi. Akibatnya,   tidak bersifat surjektif, via reductio ad absurdum.
Di sisi lain,   dimungkinkan bersifat injektif, salah satunya ialah   yang mengakibatkan  .

Misalkan   dan   adalah sembarang himpunan. Berdasarkan definisi dari kardinalitas, maka   jika dan hanya jika terdapat suatu fungsi injektif namun tidak bijektif dari   ke  . Hal ini dapat diraih dengan menunjukkan bahwa tidak ada pemetaan surjektif dari   ke  . Inilah inti dari teorema Cantor: tidak ada fungsi surjektif dari sembarang himpunan   ke himpunan kuasanya. Untuk membuktikan ini, maka cukup dengan menunjukkan bahwa tidak ada fungsi   (yang memetakan elemen pada   ke himpunan bagian dari  ) yang dapat meraih setiap himpunan bagian yang ada. Dengan kata lain, maka cukup ditunjukkan bahwa terdapat suatu himpunan bagian dari   yang tidak sama dengan  , untuk setiap  . Ingat kembali bahwa setiap   merupakan himpunan bagian dari  . Himpunan bagian dengan sifat tersebut diberikan melalui konstruksi berikut:   Himpunan   terkadang dikenal sebagai himpunan diagonal Cantor dari  . Berdasarkan definisi dari himpunan  , maka untuk setiap  ,   jika dan hanya jika  . Akan dikaji dua kasus berikut:

  1. Jika  , maka  , sehingga  .
  2. Jika  , maka  , sehingga  .

Berdasarkan kedua kasus di atas, himpunan   untuk setiap   sebab himpunan   dikonstruksikan dari elemen pada   yang bayangan oleh fungsi   tidak memuat dirinya sendiri. Dengan kata lain, terbukti bahwa terdapat suatu elemen   sedemikian sehingga persyaratan   mengakibatkan kontradiksi berikut:   sehingga berdasarkan reductio ad absurdum, asumsi di awal bernilai salah.[1] Akibatnya, tidak ada   yang memenuhi  . Dengan kata lain, himpunan   bukanlah bayangan dari   dan fungsi   tidak memetakan setiap elemen ke himpunan kuasa dari  , yang berarti,   tidak bersifat surjektif.

Terakhir, untuk melengkapi pembuktiannya, perlu ditunjukkan bahwa terdapat suatu fungsi injektif dari   ke himpunan kuasanya. Proses mencari fungsi tersebut tidaklah sulit: petakan elemen   ke himpunan singleton  . Sekarang pembuktiannya sudah lengkap, dan berlaku ketaksamaan tegas   untuk setiap himpunan  .

Oleh karena elemen   muncul dua kali pada ekspresi " ", 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   dari himpunan   secara berurutan. Himpunan   diasumsikan terurut linear sehingga tabelnya dapat dikonstruksikan.
  2. setiap kolomnya dilabelkan oleh suatu elemen   dari himpunan  . Kolomnya diurutkan berdasarkan argumen dari  . Dengan kata lain, kolomnya dilabeli sebagai   dengan urutan ini.
  3. perpotongan dari setiap baris   dan kolom   berisi nilai benar/salah dari pernyataan  . 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   dari tabel ini berisi nilai kebenaran dari pernyataan   untuk setiap  . Salah satu tabelnya dapat dilihat sebagai berikut:   Himpunan   pada paragraf sebelumnya dikonstruksikan berdasarkan negasi dari nilai kebenaran pada diagonal utama   (yang pada contoh di atas, diwarnai dengan merah), yaitu menukar "benar" dan "salah".[1] Akibatnya, fungsi indikator dari himpunan   akan berbeda dengan setiap kolom pada setidaknya satu entri, sehingga tidak ada kolom yang mewakili  .

Lihat juga

sunting

Referensi

sunting
  1. ^ a b Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. hlm. 118–119. ISBN 978-0-19-925405-7. 

Pranala luar

sunting