Himpunan hingga

Dalam matematika (khususnya teori himpunan); sebuah himpunan hingga atau himpunan berhingga merupakan sebuah himpunan hingga yang mempunyai jumlah anggota yang terhingga (terbatas). Secara informal, sebuah himpunan hingga merupakan sebuah himpunan yang salah satunya dapat dalam pencacahan prinsip dan selesai mencacahkan. Sebagai contoh,

merupakan sebuah himpunan hingga dengan lima elemen. Jumlah elemen dari sebuah himpunan hingga merupakan sebuah bilangan asli (sebuah bilangan bulat taknegatif) dan disebut kekardinalan dari himpunan. Sebuah himpunan yang tidak terhingga disebut takhingga. Sebagai contoh, himpunan semua bilangan bulat positif adalah takhingga.

Himpunan hingga secara khusus penting dalam kombinatorika, cabang matematika yang mempelajari pencacahan. Banyak argumen melibatkan himpunan hingga yang mengandalkan prinsip rumah burung, yang mengatakan bahwa tidak mungkin ada sebuah fungsi injektif suatu himpunan hingga yang lebih besar ke sebuah himpunan hingga yang lebih kecil.

Definisi dan terminologi 

Secara umum, sebuah himpunan  dikatakan terhingga jika terdapat sebuah bijeksi

untuk suatu bilangan asli . Bilangan  merupakan kekardinalan himpunan (yang dinyatakan sebagai ). Himpunan kosong  atau , dianggap terhingga, dengan kekardinalan himpunannya adalah nol.

Jika himpunan adalah terhingga, maka anggotanya dapat ditulis — dalam banyak cara — dalam sebuah barisan:

Sifat-sifat dasar 
Setiap himpunan bagian dari suatu himpunan hingga  adalah terhingga dan mempunyai yang lebih sedikit daripada himpunan  sendiri. Akibatnya, tidak mungkin ada sebuah bijeksi antara sebuah himpunan hingga  dan sebuah himpunan bagian wajar . Setiap himpunan dengan sifat ini disebut hingga-Dedekind. Menggunakan aksioma ZFC standar untuk teori himpunan, setiap himpunan hingga-Dedekind juga terhingga, tetapi implikasi ini tidak dapat dibuktikan dalam ZF (aksioma Zermelo–Fraenkel tanap aksioma pemilihan) sendiri. Aksioma pemilihan tercacahkan, sebuah versi yang lemah dari aksioma pemilihan, cukup untuk membuktikan kesetaraan ini.

Setiap fungsi injektif diantara dua himpunan hingga dari kekardinalan yang sama juga merupakan sebuah fungsi surjektif. Dengan cara yang sama, setiap fungsi surjektif antara dua himpunan hingga dari kekardinalan yang sama juga merupakan sebuah injeksi.

Gabungan dari dua himpunan hingga adalah terhingga, dengan

Bahkan, menurut prinsip inklusi–enklusi:

Lebih umum lagi, gabungan dari setiap jumlah hingga dari himpunan hingga adalah terhingga. Darab Kartesius dari himpunan hingga juga terhingga dengan:

Dengan cara yang sama, darab Kartesius dari banyaknya himpunan hingga adalah terhingga. Himpunan hingga dengan elemen  mempunyai  himpunan bagian yang berbeda. Dalam artian, himpunan kuasa sebuah himpunan hingga adalah terhingga, dengan kekardinalan .

Setiap subhimpunan dari suatu himpunan hingga adalah terhingga. Himpunan dari nilai suatu fungsi ketika diterapkan ke anggota suatu himpunan hingga adalah terhingga, dengan kekardinalan .

Semua himpunan hingga adalah tercacahkan, namun tidak semua himpunan tercacahkan adalah terhingga.

Semikekisi bebas pada sebuah himpunan hingga merupakan himpunan dari subhimpunan kosongnya, dengan operasi sambungan telah diberikan oleh gabungan himpunan.

Syarat perlu dan cukup untuk keterhinggaan 
Dalam teori himpunan Zermelo–Fraenkel tanpa aksioma pemilihan (ZF), syarat-syarat berikut merupakan ekuivalen semua:

  merupakan himpunan hingga. Dalam artian,  dapat diletakkan menjadi sebuah padanan satu-ke-satu dengan himpunan bilangan bulatnya lebih kecil dari suatu bilangan asli spesifik.
 (Kazimierz Kuratowski)  memiliki semua sifat-sifat yang dapat dibuktikan oleh induksi matematika dimulia dengan himpunan kosong dan menambahkan satu elemen baru sekaligus. (Lihat di bawah untuk perumusan teoretis himpunan keterhinggaan Kuratowski.)
 (Paul Stackel)  dapat diberikan sebuah urutan total yang terurut rapi di depan dan di belakang. Yaitu, setiap himpunan bagian takkosong  memiliki sebuah elemen terkecil dan terbesar dalam himpunan bagian.
 Setiap fungsi satu-ke-satu dari  menjadi sendirinya adalah pada, Yaitu, himpunan kuasa dari himpunan kuasa  adalah hingga-Dedekind (lihat di bawah).
 Setiap fungsi surjektid dari  pada sendirinya adalah satu-ke-satu.
 (Alfred Tarski) Setiap keluarga himpunan takkosong  memiliki sebuah elemen minimal yang berkenaan dengan inklusi. (Sebenarnya, setiap keluarga himpunan takkosong  memiliki sebuah elemen maksimal yang berkenaan dengan inklusi.)
  dapat terurut rapi dan dua urutan rapi apapun padanya merupakan isomorfik urutan. Dengan kata lain, urutan-rapi pada  memiliki tepatnya satu tipe urutan.

Jika aksioma pemilihan juga diasumsi (aksioma pemilihan tercacahkan cukup), maka syarat-syarat berikut adalah setara semua:

  adalah sebuah himpunan hingga.
 (Richard Dedekind) Setiap fungsi satu-ke-satu dari  ke sendirinya merupakan pada.
 Setiap fungsi surjektif dari  pada sendirinya merupakan satu-ke-satu.
  adalah kosong setiap urutan parsial  berisi sebuah elemen maksimal.

Masalah-masalah yang mendasar 
Georg Cantor mengajukan teori himpunannya untuk menyediakan sebuah perawatan himpunan takhingga matematis. Dengan demikian perbedaan antara hingga dan takhingga terletak di inti teori himpunan. Landasan-landasan tertentu, finitis yang sempurna, menolak keberadaan himpunan takhingga dan demikian menganjurkan sebuah matematika berdasarkan semata-mata pada himpunan hingga. Aliran utama matematikawan menganggap finitisme yang sempuna terlalu mengikat, tetapi mengakui konsistensi relatifnya, semesta himpunan hingga secara turun-temurun mendirikan sebuah model teori himpunan Zermelo–Fraenkel dengan aksioma takhingga digantikan oleh negasinya.

Bahkan untuk para matematikawan itu yang mencakup himpunan takhingga, dalam konteks yang penting, perbedaan formal antara hingga dan takhingga dapat tinggal sebuah materi yang sulit. Akar kata kesulitannya dari teorema ketaklengkapan Gődel. Salah satunya dapat menerjemahkan teori himpunan hingga secara turun-temurun dalam aritmetika Peano (dan tentu juga sebaliknya), jadi ketaklengkapan dari teori aritmetika Peano menyiratkannya dari teori himpunan hingga secara turun-temurun. Khususnya, terdapat kebanyakan disebut model non-standar dari kedua teori. Tampak seperti sebuah paradoks adalah bahwa terdapat model standar dari teori himpunan hingga secara turun-temurun yang berisi himpunan takhingga, tetapi himpunan-himpunan takhingga ini dilihat terhingga dari dalam model. (INi dapat terjadi ketika model kekurangan himpunan-himpunan atau fungsi-fungsi yang diperlukan untuk menyaksikan ketidakterhinggaan himpunan-himpunan ini.) Pada akun dari teorema ketaklengkapan, tidak ada predikat orde-pertama, maupun bahkan setiap skema rekursif predikat orde-pertama, dapat mengkarateristik bagian standar semua seperti model. Jadi, setidaknya dari sudut pandang logika orde-pertama, salah satunya dapat berharap untuk menjelaskan keterhinggaan sekitar.

Lebih umumnya, gagasan informal seperti himpunan, dan khususnya himpunan hingga, dapat menerima interpretasi disepanjang sebuah kisaran sistem formal beragam dalam aksiomatiknya dan aparat yang logis. Teori himpunan aksiomatik yang paling terkenal termasuk teori himpunan Zermelo–Fraenkel (ZF), teori himpunan Zermelo–Fraenkel dengan Aksioma Pemilihan, Teori himpunan von Neumann–Bernays–Gödel (NBG), teori himpunan takcukup beralasan, teori tipe Bertrand Russell dan semua teori-teori model beragamnya. Salah satunya dapat memilih diantara logika orde-pertama klasik, berbagai logika orde-tertinggi dan logika intuitionistik.

Sebuah pengikut formalisme melihat arti himpunan yang beragam dari sistem ke sistem. Beberapa jenis Platonist dapat memandang sistem formal khusus ketika mengaproksimasikan sebuah akar kenyataan.

Definisi teoretis himpunan keterhinggaan 
Dalam konteks dimana gagasan bilangan asli yang menduduki secara logis untuk setiap gagasan himpunan, salah satunya dapat mendefinisikan sebagai sebuah himpunan  sebagai terhingga jika  diterima sebuah bijeksi untuk suatu himpunan bilangan asli dari bentuk . Matematikawan lebih khusus memilih untuk gagasan dasar bilangan dalam teori himpunan, sebagai contoh mereka dapat memodelkan bilangan asli oleh tipe orde himpunan urutan rapi hingga. Pendekatan demikian membutuhkan sebuah definisi struktural keterhinggaan yang tidak bergantung pada bilangan asli.

Berbagai sifat-sifat yang memilih himpunan hingga di sekitar semua himpunan dalam teori ZFC mengeluarkan ketaksetaraan secara logis dalam sistem lemah seperti ZF atau teori-teori himpunan yang intuitionistik. Dua definisi yang menonjol dalam kepustakaan, salah satunya dikarenakan Richard Dedekind, lainnya Kazimierz Kuratowski. (Kuratowski merupakan definisi yang digunakan di atas.)

Sebuah himpunan  disebut takhingga Dedekind jika terdapat sebuah fungsi injektif, taksurjektif . Seperti sebuah fungsi menunjukkan sebuah bijeksi diantara , yaitu citra . Diberikan sebuah himpunan takhingga Dedekind , sebuah fungsi , dan sebuah unsur  yang tidak ada di citra , kita dapat membentuk sebuah barisan takhingga dari unsur  yang berbeda, yaitu . Sebaliknya, diberikan sebuah barisan dalam  yang terdiri dari unsur  yang berbeda, kita dapat didefinisikan sebuah fungsi  sehingga pada unsur dalam barisan  dan  berperilaku seperti fungsi identitas jika tidak. Dengan demikian himpunan takhingga Dedekind mengandung himpunan bagian yang padanan secara bijektif dengan bilangan asli. Tentu saja takhingga Dedekind berarti bahwa setiap injektif pemetaan diri sendiri juga surjektif.

Keterhinggaan Kuratowski didefinisikan sebagai berikut. Diberikan setiap himpunan , operasi biner memberikan himpunan kuasa  dengan struktur semikekisi. Menulis  untuk semikekisi bagian dihasilkan oleh himpunan kosong dan himpunan satuannya, disebut himpunan  takhingga Kuratowski jika  sendiri menjadi milik . Secara intuitif,  terdiri dari himpunan bagian terhingga . Yang terpenting, salah satunya tidak membutuhkan induksi, rekuris atau sebuah definisi bilangan asli untuk mendefinisikan dihasilkan oleh karena salah satunya dapat memperoleh  menyederhanakan dengan mengambil irisan semua semikekisi bagian berisi himpunan kosing dan himpunan satuannya.

Para pembaca tidak mengenal dengan semikekisi dan gagasan lainnya mengenai aljabar abstrak dapat lebih memilih sebuah rumusan elementer secara keseluruhan. Terhingga Kuratowski berarti  terletak di himpunan , dibangun sebagai berikut. Tulis  untuk himpunan semua himpunan bagian  dari  sehingga:

  berisi himpunan kosong;
 Untuk setiap himpunan  dalam , jika  berisi  maka  juga berisi gabungan  dengan setiap himpunan satuan.

Maka  dapat didefinisikan sebagai irisan .

Dalam Zermelo–Fraenkel, terhingga Kuratowski menyiratkan terhingga Dedekind, tetapi tidak sebaliknya. Dalam cara berbicara dari sebuah perumusan pedagogis yang populer, ketika aksioma pemilhan gagal dengan buruk, salah satunya dapat memiliki sebuah keluarga kaos kaki takhingga dengan tak ada cara untuk memilih satu kaos kaki lebih dari jelas banyak dari pasangan. Ini akan menjadi himpunan setiap kaos kaki terhingga Dedekind: itu dapat menjadi barisan tidak terhingganya kaos kaki, karena seperti sebuah barisan akan memungkinkan sebuah pemilihan dari satu kaos kaki untuk banyaknya pasangan dengan memiliki kaos kaki pertama dalam barisan. Namun, keterhingaan Kuratowski akan gagal untuk himpunan kaos kaki yang sama.

Konsep lainnya mengenai keterhinggaan 
Dalam teori himpunan Zermelo–Fraenkel tanpa aksioma pemilihan, konsep-konsep berikut mengenai keterhinggaan untuk sebuah himpunan  adalah berbeda. Mereka disusun dalam orde jumlah anggota yang menurun sempurna, yaitu jika sebuah himpunan  bertemu sebuah kriteria dalam daftar maka  bertemu semua dari kriteria berikut. Dalam absen dari aksioma pemilihan, implikasi yang dibalik semua tak dapat dibuktikan, tetapi jika aksioma pemilihan diasumsi maka semua konsep-konsep ini adalah setara. (Catatan bahwa tidak ada dari definisi-definisi ini membutuhkan himpunan terhingga bilangan ordinal yang didefinisikan pertama; mereka semua definisi "himpunan teoretis" murni dalam istilah dari persamaan dan hubungan keanggotaan, tidak melibatkan .)

 Terhingga-I. Setiap himpunan takhingga dari himpunan bagian  memiliki sebuah unsur maksimal-⊆. (Ini setara dengan membutuhkan keberadaan unsur minimal-⊆. Ini juga setara dengan konsep numerik standar mengenai keterhinggaan.)
 Terhingga-Ia. Untuk setiap partisi  menjadi dua himpunan, setidaknya salah satu dari dua himpunan merupakan terhingga-I.
 Terhingga-II. himpunan monoton-⊆ takkosong dari himpunan bagian  memiliki sebuah unsur maksimal-⊆.
 Terhingga-III. Himpunan kuasa  merupakan terhingga Dedekind.
 Terhingga-IV.  merupakan terhingga Dedekind.
 Terhingga-V.  atau .
 Terhingga-VI  atau  atau .
 Terhingga-VII.  merupakan terhingga-I atau takterurutan baik.

Implikasi seterusnya (dari kuat hingga lemah) merupakan teorema-teorema dalam Zermelo–Fraenkel. Contoh berlawanan menjadi implikasi terbalik (dari lemah hingga kuat) dalam Zermelo–Fraenkel dengan urelemen ditemukan menggunakan teori model.

Hampir definisi-definisi keterhinggaan ini dan nama-namanya dianggap sebagai  oleh . Namun, definisi I, II, III, IV, dan V dipresentasikan di , bersama-sama dengan bukti-bukti (atau referensi untuk pembuktian) untuk implikasi seterusnya. Pada saat itu, teori model tidak cukup maju untuk mencari contoh berlawanan.

Setiap sifat-sifat terhingga-I melalui terhingga-IV merupakan sebuah gagasan yang keteecilan dalam arti bahwa setiap himpunan bagian dari sebuah himpunan dengan sifat tersebut juga akan memiliki sifatnya. Ini tidak benar untuk terhingga-V melalui terhingga-III karena mereka dapat memiliki himpunan bagian tercacahkan.

Lihat pula 

 Himpunan Fin
 Bilangan ordinal
 Aritmetika Peano

Catatan

Referensi

Pranala luar 

 

Bilangan kardinal
Konsep dasar dalam teori himpunan