Kantorova teorema

U elementarnog teoriji skupova, Kantorova teorema je fundamentalni rezultat koji tvrdi da je za bilo koji skup $A$, skup svih podskupova od $A$ (partitivni skup od $A$, označen sa ${\mathcal {P}}(A)$) ima strogo veću kardinalnost od samog $A$. Za konačne skupove, može se videti da je Kantorova teorema tačna putem jednostavnog nabrajanja broja podskupova. Računajući prazan skup kao podskup, skup sa $n$ članova ima ukupno $2^{n}$ podskupova, tako da ako je ${\rm {card}}(A)=n,$ onda je ${\rm {card}}({\mathcal {P}}(A))=2^{n}$, i teorema važi jer je $2^{n}>n$ istinito za sve nenegativne brojeve.

Kardinalnost skupa {x, y, z} je tri, dok postoji osam elemenata u njegovom partitivnom skupu (3 < 2³ = 8), ovde uređenih u odnosu na inkluziju.

Mnogo je značajnije Kantorovo otkriće argumenta koji je primenljiv na bilo koji skup, čime je pokazano da teorema važi za beskonačne skupove, brojive ili nebrojive, kao i za konačne. Kao posebno važna posledica, partitivni skup skupa prirodnih brojeva, prebrojivo beskonačnog skupa s kardinalnošću ℵ₀ = card(ℕ), neprebrojivo je beskonačan i ima istu veličinu kao i skup realnih brojeva, kardinalnost veća od one za skup prirodnih brojeva koja se često naziva kardinalnost kontinuuma: 𝔠 = card(ℝ) = card(𝒫(ℕ)). Odnos između ovih kardinalnih brojeva često se simbolično izražava jednakošću i nejednakošću ${\mathfrak {c}}=2^{\aleph _{0}}>\aleph _{0}$.

Ova teorema je nazvana po nemačkom matematičaru Georgu Kantoru, koji ju je prvi objavio i dokazao krajem 19. veka. Kantorova teorema je imala neposredne i važne posledice za filozofiju matematike. Na primer, iterativnim uzimanjem partitivnog skupa beskonačnog skupa i primenom Kantorove teoreme, dobija se beskrajna hijerarhija beskonačnih kardinala, svaki strogo veći od onog pre njega. Shodno tome, teorema implicira da ne postoji najveći kardinalni broj (kolokvijalno, „nema najveće beskonačnosti”).

Dokaz

Kantorov argument je elegantan i izuzetno jednostavan. Kompletan dokaz predstavljen je u nastavku, sa detaljnim objašnjenjima koja slede.

Teorema (Kantor). Neka je $f$ mapa iz skupa $A$ na njegov partitivni skup ${\mathcal {P}}(A)$. Onda $f:A\to {\mathcal {P}}(A)$ nije surjektivno. Konsekventno, $\mathrm {card} (A)<\mathrm {card} ({\mathcal {P}}(A))$ važi za svaki skup $A$.

Dokaz: Razmotrimo skup $B=\{x\in A\,|\,x\notin f(x)\}$. Pretpostavimo suprotno da $f$ je surjektivno. Onda postoji $\xi \in A$ takvo da je $f(\xi )=B$. Međutim po konstrukciji, $\xi \in B\iff \xi \notin f(\xi )=B$. Ovo je kontradikcija. Stoga, $f$ ne može da bude surjektivno. S druge strane, $g:A\to {\mathcal {P}}(A)$ definisano sa $x\mapsto \{x\}$ jeste injektivna mapa. Konsekventno, mora biti $\mathrm {card} (A)<\mathrm {card} ({\mathcal {P}}(A))$.$\ \blacksquare$

Po definiciji kardinalnosti važi da je card(X) < card(Y) za svaka dva seta X i Y ako i samo ako postoji injektivna funkcija ali ne i bijektivna funkcija od X do Y. Dovoljno je da se pokaže da nema surjekcije od X do Y. Ovo je suština Kantorove teoreme: ne postoji surjektivna funkcija od bilo kog skupa A do njegovog partitivnog skupa. Da bi se to uspostavilo, dovoljno je da se pokaže da nijedna funkcija f koja preslikava elemente iz A u podskupove od A ne može da dosegne svaki mogući podskup, tj. samo se mora dokazati postojanje podskupa A koji nije jednak f(x) za bilo koje x ∈ A. (Treba imati u vidu da je svako f(x) podskup A.) Takav podskup daje sledeća konstrukcija, koja se ponekad naziva i Kantorov dijagonalni skup f:

$B=\{x\in A\,|\,x\not \in f(x)\}.$

To znači, po definiciji, da za svako x u A, x ∈ B ako i samo ako x ∉ f(x). Za svako x skupovi B i f(x) ne mogu da budu isti jer je B konstruisano iz elemenata A čije preslikavanje (pod f) nije obuhvatalo njih same. Specifičnije ako se razmotri svako x ∈ A, onda bilo x ∈ f(x) ili x ∉ f(x). U prvom slučaju, f(x) ne može da bude jednako B, jer x ∈ f(x) po pretpostavci, a x ∉ B po konstrukciji B. U potonjem slučaju, f(x) ne može biti jednako B, jer x ∉ f(x) po pretpostavci i x ∈ B konstrukcijom B.

Ekvivalentno, i donekle formalnije, dokazuje se da postojanje ξ ∈ A takvo da f(ξ) = B podrazumeva sledeću protivrečnost:

${\begin{aligned}\xi \in f(\xi )&\iff \xi \in B&&{\text{(po pretpostavci da }}f(\xi )=B{\text{)}};\\\xi \in B&\iff \xi \notin f(\xi )&&{\text{(po definiciji }}B{\text{)}}.\end{aligned}}$

Stoga, prema reductio ad absurdum, pretpostavka mora biti pogrešna. Proizilazi da ne postoji ξ ∈ A takvo da je f(ξ) = B; drugim rečima, B nije u preslikavanju f i f se ne mapira u svaki element partitivnog skupa od A, i.e., f nije surjektivno.

Konačno, da se kompletira dokaz neophodno je da se pokaže injektivna funkcija iz A u njegov partitivni skup. Nalaženje takve funkcije je trivijalno: samo se mapira x u singltonski skup {x}. Argument je sada potpun i utvrđena je stroga nejednakost za bilo koji skup A da je card(A) < card(𝒫(A)).

Drugačiji način da se razmišlja o dokazu je da je B, prazan ili neprazan, uvek u partitivnom skupu od A. Da bi f bila uključena, neki element A se mora preslikati u B. Ali to dovodi do kontradikcije: ni jedan element B se ne može preslikati na B, jer bi to bilo u suprotnosti sa kriterijumom članstva u B, te stoga element koji se preslikava u B ne može da bude element B, što znači da zadovoljava kriterijum za članstvo u B, još jedna kontradikcija. Dakle, pretpostavka da se element A preslikava u B mora biti lažna; i f ne može biti uključeno.

Zbog dvostruke pojave x u izrazu „x ∉ f(x)”, ovo je dijagonalni argument. Za brojiv (ili konačan) skup, argument gore navedenog dokaza može se ilustrovati konstrukcijom tabele u kojoj je svaki red označen jedinstvenim x iz A = {x₁, x₂, ...}, u tom redosledu. Pretpostavlja se da A prihvata linearni redosled, tako da se takva tabela može konstruisati. Svaka kolona tabele je označena jedinstvenim y iz partitivnog skupa A; kolone su poređane argumentom za f, tj. oznake kolona su f(x₁), f(x₂), ..., u tom redosledu. Presek svakog reda x i kolone y beleži istinski/lažni bit da li x ∈ y. S obzirom na redoslijed izabran za oznake redova i kolona, glavna dijagonala D ove tabele beleži da li je x ∈ f(x) za svako x in A. Skup B izgrađen u prethodnim paragrafima se podudara sa oznakama redova za podskup unosa na toj glavnoj dijagonali D, gde tabela beleži da je x ∈ f(x) lažno. Svaka kolona beleži vrednosti indikatorske funkcije skupa koja odgovara koloni. Indikatorska funkcija za B podudara se sa logički negiranim (istinito ↔ lažno) zapisima glavne dijagonale. Stoga se indikatorska funkcija za B ne slaže ni sa jednom kolonom u bar jednom unosu. Prema tome, nijedna kolona ne predstavlja B.

Za konačni skup, dokaz isto tako može da bude ilustrovan koristeći prozaičniju prezentaciju poznatu kao paradoks berberina.

Uprkos jednostavnosti gornjeg dokaza, prilično je teško da se proizvede automatizovanim dokazivačem teorema. Glavna poteškoća leži u automatizovanom otkrivanju Kantorovog dijagonalnog skupa. Lorens Polson je napomenuo 1992. godine da Otter to nije mogao učiniti, dok je Isabelle mogla, iako s određenim brojem uputstava u smislu taktike, što se možda može smatrati varanjem.

Literatura

• Halmos, Paul, Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).
• Jech, Thomas (2002), Set Theory, Springer Monographs in Mathematics (3rd millennium изд.), Springer, ISBN 3-540-44085-2 
• Arkhangel'skii, A. V.; Fedorchuk, V. V. (1990), „The basic concepts and constructions of general topology”, Ур.: Arkhangel'skii, A. V.; Pontryagin, L. S., General Topology I, New York, Berlin: Springer-Verlag, стр. 1—90, ISBN 978-0-387-18178-3 .
• Audin, Michèle (2011), Remembering Sofya Kovalevskaya, London: Springer, ISBN 978-0-85729-928-4 .
• Bell, Eric Temple (1937), Men of Mathematics, New York: Simon & Schuster, ISBN 978-0-671-62818-5 .
• Birkhoff, Garrett; Mac Lane, Saunders (1941), A Survey of Modern Algebra, New York: Macmillan, ISBN 978-1-56881-068-3 .
• Burton, David M. (1995), Burton's History of Mathematics (3rd изд.), Dubuque, Iowa: William C. Brown, ISBN 978-0-697-16089-8 .
• Cantor, Georg (1874), „Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen”, Journal für die Reine und Angewandte Mathematik (на језику: German), 1874 (77): 258—262, doi:10.1515/crll.1874.77.258 CS1 одржавање: Непрепознат језик (веза).
• Cantor, Georg (1878), „Ein Beitrag zur Mannigfaltigkeitslehre”, Journal für die Reine und Angewandte Mathematik (на језику: German), 1878 (84): 242—258, doi:10.1515/crll.1878.84.242 CS1 одржавање: Непрепознат језик (веза).
• Cantor, Georg (1879), „Ueber unendliche, lineare Punktmannichfaltigkeiten. 1.”, Mathematische Annalen (на језику: German), 15: 1—7, doi:10.1007/bf01444101 CS1 одржавање: Непрепознат језик (веза).
• Chowdhary, K. R. (2015), Fundamentals of Discrete Mathematical Structures (3rd изд.), Dehli, India: PHI Learning, ISBN 978-81-203-5074-8 .
• Cohen, Paul J. (1963), „The Independence of the Continuum Hypothesis”, Proceedings of the National Academy of Sciences of the United States of America, 50 (6): 1143—1148, Bibcode:1963PNAS...50.1143C, PMC 221287 , PMID 16578557, doi:10.1073/pnas.50.6.1143 .
• Dasgupta, Abhijit (2014), Set Theory: With an Introduction to Real Point Sets, New York: Springer, ISBN 978-1-4614-8853-8 .
• Dauben, Joseph (1979), Georg Cantor: His Mathematics and Philosophy of the Infinite, Cambridge, Mass.: Harvard University Press, ISBN 978-0-674-34871-4 .
• Dauben, Joseph (1993), „Georg Cantor and the Battle for Transfinite Set Theory” (PDF), 9th ACMS Conference Proceedings .
• Edwards, Harold M. (1989), „Kronecker's Views on the Foundations of Mathematics”, Ур.: Rowe, David E.; McCleary, John, The History of Modern Mathematics, Volume 1, New York: Academic Press, стр. 67–77, ISBN 978-0-12-599662-4 .
• Ewald, William B., ур. (1996), From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2, New York: Oxford University Press, ISBN 978-0-19-850536-5 .
• Ferreirós, José (1993), „On the relations between Georg Cantor and Richard Dedekind”, Historia Mathematica, 20 (4): 343—363, doi:10.1006/hmat.1993.1030 .
• Ferreirós, José (2007), Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought (2nd revised изд.), Basel: Birkhäuser, ISBN 978-3-7643-8349-7 .
• Fraenkel, Abraham (1930), „Georg Cantor”, Jahresbericht der Deutschen Mathematiker-Vereinigung (на језику: German), 39: 189—266 CS1 одржавање: Непрепознат језик (веза).
• Grattan-Guinness, Ivor (1971), „The Correspondence between Georg Cantor and Philip Jourdain”, Jahresbericht der Deutschen Mathematiker-Vereinigung, 73: 111—130 .
• Gray, Robert (1994), „Georg Cantor and Transcendental Numbers” (PDF), American Mathematical Monthly, 101 (9): 819—832, JSTOR 2975129, MR 1300488, Zbl 0827.01004, doi:10.2307/2975129 .
• Hardy, Godfrey; Wright, E. M. (1938), An Introduction to the Theory of Numbers, Oxford: Clarendon Press, ISBN 978-0-19-921985-8 .
• Havil, Julian (2012), The Irrationals, Princeton, Oxford: Princeton University Press, ISBN 978-0-691-16353-6 .
• Hawkins, Thomas (1970), Lebesgue's Theory of Integration, Madison, Wisconsin: University of Wisconsin Press, ISBN 978-0-299-05550-9 .
• Jarvis, Frazer (2014), Algebraic Number Theory, New York: Springer, ISBN 978-3-319-07544-0 .
• Kanamori, Akihiro (2012), „Set Theory from Cantor to Cohen” (PDF), Ур.: Gabbay, Dov M.; Kanamori, Akihiro; Woods, John H., Sets and Extensions in the Twentieth Century, Amsterdam, Boston: Cambridge University Press, стр. 1—71, ISBN 978-0-444-51621-3 .
• Kaplansky, Irving (1972), Set Theory and Metric Spaces, Boston: Allyn and Bacon, ISBN 978-0-8284-0298-9 .
• Kelley, John L. (1991), General Topology, New York: Springer, ISBN 978-3-540-90125-9 .
• LeVeque, William J. (1956), Topics in Number Theory, I, Reading, Mass.: Addison-Wesley, ISBN 978-0-486-42539-9 . (Reprinted by Dover Publications, 2002.)
• Noether, Emmy; Cavaillès, Jean, ур. (1937), Briefwechsel Cantor-Dedekind (на језику: German), Paris: Hermann CS1 одржавање: Непрепознат језик (веза).
• Perron, Oskar (1921), Irrationalzahlen (на језику: German), Leipzig, Berlin: W. de Gruyter, OCLC 4636376 CS1 одржавање: Непрепознат језик (веза).
• Sheppard, Barnaby (2014), The Logic of Infinity, Cambridge: Cambridge University Press, ISBN 978-1-107-67866-8 .
• Spivak, Michael (1967), Calculus, London: W. A. Benjamin, ISBN 978-0914098911 .
• Stewart, Ian (2015), Galois Theory (4th изд.), Boca Raton, Florida: CRC Press, ISBN 978-1-4822-4582-0 .
• Stewart, Ian; Tall, David (2015), The Foundations of Mathematics (2nd изд.), New York: Oxford University Press, ISBN 978-0-19-870644-1 .
• Weisstein, Eric W., ур. (2003), „Continued Fraction”, CRC Concise Encyclopedia of Mathematics, Boca Raton, Florida: Chapman & Hall/CRC, ISBN 978-1-58488-347-0 

Spoljašnje veze

• Hazewinkel Michiel, ур. (2001). „Cantor theorem”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Weisstein, Eric W. „Cantor's Theorem”. MathWorld.