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,

\{2,4,6,8,10\}

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.

\{1,2,3,\dots \}

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 $S$ dikatakan terhingga jika terdapat sebuah bijeksi

f\colon S\rightarrow \{1,\dots ,n\}

untuk suatu bilangan asli $n$ . Bilangan $n$ merupakan kekardinalan himpunan (yang dinyatakan sebagai $\left|S\right|$ ). Himpunan kosong $\{\}$ atau $\varnothing$ , dianggap terhingga, dengan kekardinalan himpunannya adalah nol.^[1]^[2]^[3]^[4]

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

{\textstyle x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).}

Sifat-sifat dasar

Setiap himpunan bagian dari suatu himpunan hingga $S$ adalah terhingga dan mempunyai yang lebih sedikit daripada himpunan $S$ sendiri. Akibatnya, tidak mungkin ada sebuah bijeksi antara sebuah himpunan hingga $S$ dan sebuah himpunan bagian wajar $S$ . 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

\left|S\cup T\right|\leq \left|S\right|+\left|T\right|.

Bahkan, menurut prinsip inklusi–enklusi:

\left|S\cup T\right|=\left|S\right|+\left|T\right|-\left|S\cap T\right|.

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

\left|S\times T\right|=\left|S\right|\times \left|T\right|.

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

Setiap subhimpunan dari suatu himpunan hingga adalah terhingga. Himpunan dari nilai suatu fungsi ketika diterapkan ke anggota suatu himpunan hingga adalah terhingga, dengan kekardinalan $2^{\left|S\right|}$ .

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:^{[butuh rujukan]}

$S$ merupakan himpunan hingga. Dalam artian, $S$ dapat diletakkan menjadi sebuah padanan satu-ke-satu dengan himpunan bilangan bulatnya lebih kecil dari suatu bilangan asli spesifik.
(Kazimierz Kuratowski) $S$ 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) $S$ dapat diberikan sebuah urutan total yang terurut rapi di depan dan di belakang. Yaitu, setiap himpunan bagian takkosong $S$ memiliki sebuah elemen terkecil dan terbesar dalam himpunan bagian.
Setiap fungsi satu-ke-satu dari ${\mathcal {P}}({\mathcal {P}}(S))$ menjadi sendirinya adalah pada, Yaitu, himpunan kuasa dari himpunan kuasa $S$ adalah hingga-Dedekind (lihat di bawah).^[5]
Setiap fungsi surjektid dari ${\mathcal {P}}({\mathcal {P}}(S))$ pada sendirinya adalah satu-ke-satu.
(Alfred Tarski) Setiap keluarga himpunan takkosong $S$ memiliki sebuah elemen minimal yang berkenaan dengan inklusi.^[6] (Sebenarnya, setiap keluarga himpunan takkosong $S$ memiliki sebuah elemen maksimal yang berkenaan dengan inklusi.)
$S$ dapat terurut rapi dan dua urutan rapi apapun padanya merupakan isomorfik urutan. Dengan kata lain, urutan-rapi pada $S$ memiliki tepatnya satu tipe urutan.

Jika aksioma pemilihan juga diasumsi (aksioma pemilihan tercacahkan cukup^[7]^{[butuh rujukan]}), maka syarat-syarat berikut adalah setara semua:

$S$ adalah sebuah himpunan hingga.
(Richard Dedekind) Setiap fungsi satu-ke-satu dari $S$ ke sendirinya merupakan pada.
Setiap fungsi surjektif dari $S$ pada sendirinya merupakan satu-ke-satu.
$S$ adalah kosong setiap urutan parsial $S$ 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^{[butuh rujukan]} 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 $S$ sebagai terhingga jika $S$ diterima sebuah bijeksi untuk suatu himpunan bilangan asli dari bentuk $\{x\mid x<n\}$ . 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 $S$ disebut takhingga Dedekind jika terdapat sebuah fungsi injektif, taksurjektif $f:S\to S$ . Seperti sebuah fungsi menunjukkan sebuah bijeksi diantara $S$ , yaitu citra $f$ . Diberikan sebuah himpunan takhingga Dedekind $S$ , sebuah fungsi $f$ , dan sebuah unsur $x$ yang tidak ada di citra $f$ , kita dapat membentuk sebuah barisan takhingga dari unsur $S$ yang berbeda, yaitu $x,f(x),f(f(x)),\dots$ . Sebaliknya, diberikan sebuah barisan dalam $S$ yang terdiri dari unsur $x_{1},x_{2},x_{3},\dots$ yang berbeda, kita dapat didefinisikan sebuah fungsi $f$ sehingga pada unsur dalam barisan $f(x_{1})=x_{i+1}$ dan $f$ 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 $S$ , operasi biner memberikan himpunan kuasa ${\mathcal {P}}(S)$ dengan struktur semikekisi. Menulis $K(S)$ untuk semikekisi bagian dihasilkan oleh himpunan kosong dan himpunan satuannya, disebut himpunan $S$ takhingga Kuratowski jika $S$ sendiri menjadi milik $K(S)$ .^[8] Secara intuitif, $K(S)$ terdiri dari himpunan bagian terhingga $S$ . Yang terpenting, salah satunya tidak membutuhkan induksi, rekuris atau sebuah definisi bilangan asli untuk mendefinisikan dihasilkan oleh karena salah satunya dapat memperoleh $K(S)$ 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 $S$ terletak di himpunan $K(S)$ , dibangun sebagai berikut. Tulis $M$ untuk himpunan semua himpunan bagian $X$ dari ${\mathcal {P}}(S)$ sehingga:

$X$ berisi himpunan kosong;
Untuk setiap himpunan $T$ dalam ${\mathcal {P}}(S)$ , jika $X$ berisi $T$ maka $X$ juga berisi gabungan $T$ dengan setiap himpunan satuan.

Maka $K(S)$ dapat didefinisikan sebagai irisan $M$ .

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 $S$ adalah berbeda. Mereka disusun dalam orde jumlah anggota yang menurun sempurna, yaitu jika sebuah himpunan $S$ bertemu sebuah kriteria dalam daftar maka $S$ 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.^[9] (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 $\omega$ .)

Terhingga-I. Setiap himpunan takhingga dari himpunan bagian $S$ 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 $S$ menjadi dua himpunan, setidaknya salah satu dari dua himpunan merupakan terhingga-I.
Terhingga-II. himpunan monoton-⊆ takkosong dari himpunan bagian $S$ memiliki sebuah unsur maksimal-⊆.
Terhingga-III. Himpunan kuasa ${\mathcal {P}}(S)$ merupakan terhingga Dedekind.
Terhingga-IV. $S$ merupakan terhingga Dedekind.
Terhingga-V. $\left|S\right|=0$ atau $2\cdot \left|S\right|>\left|S\right|$ .
Terhingga-VI $\left|S\right|=0$ atau $\left|S\right|=1$ atau $\left|S\right|^{2}>\left|S\right|$ .
Terhingga-VII. $S$ 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.^[10]

Hampir definisi-definisi keterhinggaan ini dan nama-namanya dianggap sebagai Tarski 1954 oleh Howard & Rubin 1998, hlm. 278. Namun, definisi I, II, III, IV, dan V dipresentasikan di Tarski 1924, hlm. 49, 93, 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

Catatan

^ (Apostol 1974, hlm. 38)
^ (Cohn 1981, hlm. 7)
^ (Labarre 1968, hlm. 41)
^ (Rudin 1976, hlm. 25)
^ The equivalence of the standard numerical definition of finite sets to the Dedekind-finiteness of the power set of the power set was shown in 1912 by Whitehead & Russell 2009, hlm. 288. This Whitehead/Russell theorem is described in more modern language by Tarski 1924, hlm. 73–74.
^ Tarski 1924, hlm. 48–58, demonstrated that his definition (which is also known as I-finite) is equivalent to Kuratowski's set-theoretical definition, which he then noted is equivalent to the standard numerical definition via the proof by Kuratowski 1920, hlm. 130–131.
^ Canada, A.; Drabek, P.; Fonda, A. (2005-09-02). Handbook of Differential Equations: Ordinary Differential Equations (dalam bahasa Inggris). Elsevier. ISBN 9780080461083.
^ The original paper by Kuratowski 1920 defined a set S to be finite when
^ This list of 8 finiteness concepts is presented with this numbering scheme by both Howard & Rubin 1998, hlm. 278–280, and Lévy 1958, hlm. 2–3, although the details of the presentation of the definitions differ in some respects which do not affect the meanings of the concepts.
^ Lévy 1958 found counter-examples to each of the reverse implications in Mostowski models. Lévy attributes most of the results to earlier papers by Mostowski and Lindenbaum.

Referensi

Apostol, Tom M. (1974), Mathematical Analysis (edisi ke-2nd), Menlo Park: Addison-Wesley, LCCN 72011473
Cohn, Paul Moritz, F.R.S. (1981), Universal Algebra, Dordrecht: D. Reidel, ISBN 90-277-1254-9, LCCN 80-29568
Dedekind, Richard (2012), Was sind und was sollen die Zahlen?, Cambridge Library Collection (edisi ke-Paperback), Cambridge, UK: Cambridge University Press, ISBN 978-1-108-05038-8
Dedekind, Richard (1963), Essays on the Theory of Numbers , Dover Books on Mathematics, Beman, Wooster Woodruff (edisi ke-Paperback), Dover Publications Inc., ISBN 0-486-21010-3
Herrlich, Horst (2006), Axiom of Choice, Lecture Notes in Math. 1876, Berlin: Springer-Verlag, ISBN 3-540-30989-6
Howard, Paul; Rubin, Jean E. (1998). Consequences of the axiom of choice . Providence, Rhode Island: American Mathematical Society. ISBN 9780821809778.
Kuratowski, Kazimierz (1920), "Sur la notion d'ensemble fini" (PDF), Fundamenta Mathematicae, 1: 129–131, doi:10.4064/fm-1-1-129-131
Labarre, Jr., Anthony E. (1968), Intermediate Mathematical Analysis, New York: Holt, Rinehart and Winston, LCCN 68019130
Lévy, Azriel (1958). "The independence of various definitions of finiteness" (PDF). Fundamenta Mathematicae. 46: 1–13. doi:10.4064/fm-46-1-1-13.
Rudin, Walter (1976), Principles Of Mathematical Analysis (edisi ke-3rd), New York: McGraw-Hill, ISBN 0-07-054235-X
Suppes, Patrick (1972) [1960], Axiomatic Set Theory , Dover Books on Mathematics (edisi ke-Paperback), Dover Publications Inc., ISBN 0-486-61630-4
Tarski, Alfred (1924). "Sur les ensembles finis" (PDF). Fundamenta Mathematicae. 6: 45–95. doi:10.4064/fm-6-1-45-95.
Tarski, Alfred (1954). "Theorems on the existence of successors of cardinals, and the axiom of choice". Nederl. Akad. Wetensch. Proc. Ser. A., Indagationes Math. 16: 26–32. doi:10.1016/S1385-7258(54)50005-3. MR 0060555.
Whitehead, Alfred North; Russell, Bertrand (February 2009) [1912]. Principia Mathematica. Volume Two. Merchant Books. ISBN 978-1-60386-183-0.

Pranala luar

(Inggris) Barile, Margherita. "Finite Set". MathWorld.

[1] (Apostol 1974, hlm. 38)

[2] (Cohn 1981, hlm. 7)

[3] (Labarre 1968, hlm. 41)

[4] (Rudin 1976, hlm. 25)

[5] The equivalence of the standard numerical definition of finite sets to the Dedekind-finiteness of the power set of the power set was shown in 1912 by Whitehead & Russell 2009, hlm. 288. This Whitehead/Russell theorem is described in more modern language by Tarski 1924, hlm. 73–74.

[6] Tarski 1924, hlm. 48–58, demonstrated that his definition (which is also known as I-finite) is equivalent to Kuratowski's set-theoretical definition, which he then noted is equivalent to the standard numerical definition via the proof by Kuratowski 1920, hlm. 130–131.

[7] Canada, A.; Drabek, P.; Fonda, A. (2005-09-02). Handbook of Differential Equations: Ordinary Differential Equations (dalam bahasa Inggris). Elsevier. ISBN 9780080461083.

[8] The original paper by Kuratowski 1920 defined a set S to be finite when

[9] This list of 8 finiteness concepts is presented with this numbering scheme by both Howard & Rubin 1998, hlm. 278–280, and Lévy 1958, hlm. 2–3, although the details of the presentation of the definitions differ in some respects which do not affect the meanings of the concepts.

[10] Lévy 1958 found counter-examples to each of the reverse implications in Mostowski models. Lévy attributes most of the results to earlier papers by Mostowski and Lindenbaum.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]