Канторова теорема

Кардиналност скупа {x, y, z} је три, док постоји осам елемената у његовом партитивном скупу (3 < 2³ = 8), овде уређених у односу на инклузију.

У елементарног теорији скупова, Канторова теорема је фундаментални резултат који тврди да је за било који скуп $A$, скуп свих подскупова од $A$ (партитивни скуп од $A$, означен са ${\mathcal {P}}(A)$) има строго већу кардиналност од самог $A$. За коначне скупове, може се видети да је Канторова теорема тачна путем једноставног набрајања броја подскупова. Рачунајући празан скуп као подскуп, скуп са $n$ чланова има укупно $2^{n}$ подскупова, тако да ако је ${\rm {card}}(A)=n,$ онда је ${\rm {card}}({\mathcal {P}}(A))=2^{n}$, и теорема важи јер је $2^{n}>n$ истинито за све ненегативне бројеве.

Много је значајније Канторово откриће аргумента који је применљив на било који скуп, чиме је показано да теорема важи за бесконачне скупове, бројиве или небројиве, као и за коначне. Као посебно важна последица, партитивни скуп скупа природних бројева, пребројиво бесконачног скупа с кардиналношћу ℵ₀ = card(ℕ), непребројиво је бесконачан и има исту величину као и скуп реалних бројева, кардиналност већа од оне за скуп природних бројева која се често назива кардиналност континуума: 𝔠 = card(ℝ) = card(𝒫(ℕ)). Однос између ових кардиналних бројева често се симболично изражава једнакошћу и неједнакошћу ${\mathfrak {c}}=2^{\aleph _{0}}>\aleph _{0}$.

Ова теорема је названа по немачком математичару Георгу Кантору, који ју је први објавио и доказао крајем 19. века. Канторова теорема је имала непосредне и важне последице за филозофију математике. На пример, итеративним узимањем партитивног скупа бесконачног скупа и применом Канторове теореме, добија се бескрајна хијерархија бесконачних кардинала, сваки строго већи од оног пре њега. Сходно томе, теорема имплицира да не постоји највећи кардинални број (колоквијално, „нема највеће бесконачности”).

Доказ

Канторов аргумент је елегантан и изузетно једноставан. Комплетан доказ представљен је у наставку, са детаљним објашњењима која следе.

Теорема (Кантор). Нека је $f$ мапа из скупа $A$ на његов партитивни скуп ${\mathcal {P}}(A)$. Онда $f:A\to {\mathcal {P}}(A)$ није сурјективно. Консеквентно, $\mathrm {card} (A)<\mathrm {card} ({\mathcal {P}}(A))$ важи за сваки скуп $A$.

Доказ: Размотримо скуп $B=\{x\in A\,|\,x\notin f(x)\}$. Претпоставимо супротно да $f$ је сурјективно. Онда постоји $\xi \in A$ такво да је $f(\xi )=B$. Међутим по конструкцији, $\xi \in B\iff \xi \notin f(\xi )=B$. Ово је контрадикција. Стога, $f$ не може да буде сурјективно. С друге стране, $g:A\to {\mathcal {P}}(A)$ дефинисано са $x\mapsto \{x\}$ јесте ињективна мапа. Консеквентно, мора бити $\mathrm {card} (A)<\mathrm {card} ({\mathcal {P}}(A))$.$\ \blacksquare$

По дефиницији кардиналности важи да је цард(X) < цард(Y) за свака два сета X и Y ако и само ако постоји ињективна функција али не и бијективна функција од X до Y. Довољно је да се покаже да нема сурјекције од X до Y. Ово је суштина Канторове теореме: не постоји сурјективна функција од било ког скупа А до његовог партитивног скупа. Да би се то успоставило, довољно је да се покаже да ниједна функција f која пресликава елементе из А у подскупове од А не може да досегне сваки могући подскуп, тј. само се мора доказати постојање подскупа А који није једнак f(x) за било које x ∈ А. (Треба имати у виду да је свако f(x) подскуп А.) Такав подскуп даје следећа конструкција, која се понекад назива и Канторов дијагонални скуп f:

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

То значи, по дефиницији, да за свако x у А, x ∈ Б ако и само ако x ∉ ф(x). За свако x скупови B и f(x) не могу да буду исти јер је B конструисано из елемената A чије пресликавање (под f) није обухватало њих саме. Специфичније ако се размотри свако x ∈ А, онда било x ∈ f(x) или x ∉ f(x). У првом случају, f(x) не може да буде једнако B, јер x ∈ f(x) по претпоставци, а x ∉ B по конструкцији B. У потоњем случају, f(x) не може бити једнако Б, јер x ∉ ф(x) по претпоставци и x ∈ B конструкцијом B.

Еквивалентно, и донекле формалније, доказује се да постојање ξ ∈ А такво да f(ξ) = B подразумева следећу противречност:

${\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}}$

Стога, према reductio ad absurdum, претпоставка мора бити погрешна. Произилази да не постоји ξ ∈ А такво да је f(ξ) = B; другим речима, B није у пресликавању ф и ф се не мапира у сваки елемент партитивног скупа од А, и.е., f није сурјективно.

Коначно, да се комплетира доказ неопходно је да се покаже ињективна функција из A у његов партитивни скуп. Налажење такве функције је тривијално: само се мапира x у синглтонски скуп {x}. Аргумент је сада потпун и утврђена је строга неједнакост за било који скуп A да је card(A) < card(𝒫(A)).

Другачији начин да се размишља о доказу је да је B, празан или непразан, увек у партитивном скупу од A. Да би f била укључена, неки елемент A се мора пресликати у B. Али то доводи до контрадикције: ни један елемент B се не може пресликати на B, јер би то било у супротности са критеријумом чланства у B, те стога елемент који се пресликава у B не може да буде елемент B, што значи да задовољава критеријум за чланство у B, још једна контрадикција. Дакле, претпоставка да се елемент A пресликава у B мора бити лажна; и f не може бити укључено.

Због двоструке појаве x у изразу „x ∉ f(x)”, ово је дијагонални аргумент. За бројив (или коначан) скуп, аргумент горе наведеног доказа може се илустровати конструкцијом табеле у којој је сваки ред означен јединственим x из А = {x₁, x₂, ...}, у том редоследу. Претпоставља се да A прихвата линеарни редослед, тако да се таква табела може конструисати. Свака колона табеле је означена јединственим y из партитивног скупа A; колоне су поређане аргументом за f, тј. ознаке колона су f(x₁), f(x₂), ..., у том редоследу. Пресек сваког реда x и колоне y бележи истински/лажни бит да ли x ∈ y. С обзиром на редослијед изабран за ознаке редова и колона, главна дијагонала D ове табеле бележи да ли је x ∈ f(x) за свако x ин A. Скуп B изграђен у претходним параграфима се подудара са ознакама редова за подскуп уноса на тој главној дијагонали D, где табела бележи да је x ∈ f(x) лажно. Свака колона бележи вредности индикаторске функције скупа која одговара колони. Индикаторска функција за B подудара се са логички негираним (истинито ↔ лажно) записима главне дијагонале. Стога се индикаторска функција за B не слаже ни са једном колоном у бар једном уносу. Према томе, ниједна колона не представља B.

За коначни скуп, доказ исто тако може да буде илустрован користећи прозаичнију презентацију познату као парадокс берберина.

Упркос једноставности горњег доказа, прилично је тешко да се произведе аутоматизованим доказивачем теорема. Главна потешкоћа лежи у аутоматизованом откривању Канторовог дијагоналног скупа. Лоренс Полсон је напоменуо 1992. године да Otter то није могао учинити, док је Isabelle могла, иако с одређеним бројем упутстава у смислу тактике, што се можда може сматрати варањем.

Литература

• Халмос, Паул, Наиве Сет Тхеорy. Принцетон, Њ: D. Ван Ностранд Цомпанy, 1960. Репринтед бy Спрингер-Верлаг, Неw Yорк, 1974. ISBN 0-387-90092-6 (Спрингер-Верлаг едитион). Репринтед бy Мартино Фине Боокс, 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.