قضیه کانتور
در نظریه مجموعه‌های مقدماتی، قضیه کانتور نتیجه بنیادینی است که بیان می دارد: برای هر مجموعه formula_1، مجموعه تمام زیر مجموعه های formula_1 (به آن مجموعه توانی formula_1 گفته می شود و با formula_4 نمایش داده می شود) به طور اکید کاردینالی بزرگتر از خود formula_1 دارد. برای مجموعه های متناهی می توان با شمردن تعداد زیر مجموعه ها، درستی قضیه کانتور را مشاهده کرد. با در نظر گرفتن تهی به عنوان یک زیر مجموعه، کل زیرمجموعه های یک مجموعه formula_6 عضوی برابر formula_7 خواهد بود، بنابر این اگر formula_8، آنگاه formula_9، و قضیه برقرار است چون برای تمام اعداد صحیح نامنفی داریم formula_10.
کشف مهم کانتور این بود که گزاره اخیر برای هر مجموعه ای درست است، یعنی علاوه بر مجموعه های متناهی برای مجموعه های نامتناهی، چه شمارا یا ناشمارا نیز درست است. به طور خاص، یکی از پیامدهای مهم قضیه کانتور این است که اعداد طبیعی که یک مجموعه شمارا با کاردینال formula_11 است، برابر یک مجموعه ناشمارا می باشد که کاردینال آن با اعداد حقیقی برابر بوده و این کاردینال از کاردینال اعداد طبیعی بزرگتر است و به آن کاردینال پیوستار گویند: formula_12. رابطه بین این کاردینال ها را به این صورت نمایش می دهند: formula_13.
این قضیه به افتخار ریاضیدان آلمانی گئورگ کانتور نامگذاری کردند، او اولین کسی بود که این قضیه را در انتهای قرن نوزدهم میلادی بیان و اثبات کرد. قضیه کانتور پیامدهای فوری و مهمی در فلسفه ریاضیات داشت. به عنوان مثال، با تکرار عمل ساخت مجموعه توانی از یک مجموعه نامتناهی و اعمال قضیه کانتور، به سلسله مراتب نامتناهی از کاردینال‌های نامتناهی می رسیم که هر کدام از قبلی به طور اکید بزرگتر است. در نهایت، این قضیه دلالت بر این دارد که هیچ کاردینالی که از همه کاردینال‌ها بزرگتر باشد وجود ندارد (به زبان دیگر "بزرگترین بی نهایت وجود ندارد").
f یک تابع از A به مجموعه توانی A است. برای برقراری نظریه کانتور باید اثبات شود که f الزاماً پوشا نیست. برای انجام این امر، کافی است یک عنصر مجموعه توانی از A که یک زیرمجموعه از A است ارائه کرده و اثبات کنیم که در برد f وجود ندارد. چنین زیرمجموعه‌ای می‌تواند به صورت زیر ساخته شود.
این بدین معناست که بنا بر تعریف، برای هر x عضو x، A عضو B است اگر و و فقط اگر x عضو f نباشد. پس به ازای تمام xها مجموعه‌های B و(f(x فرق می‌کنند. هیچ x ای یافت نمی‌شود که f(x)=B به عبارت دیگر B در برد f نیست. به خاطر اینکه x دو بار در عبارت بالا حضور پیدا کرده،((x عضو f(x) این یک عبارت قطری است
برای یافتن تصوری از اثبات، آن را برای مورد خاص زمانی که X یک نامتناهی قابل شمارش است امتحان می‌کنیم. بدون از دست دادن کلیت، X را مساوی مجموعه اعداد طبیعی میگیریم. فرض کنید formula_15 با مجموعه توانی خود formula_16 هم ارز باشد. اجازه دهید ببینیم formula_16 به چه صورت است:
formula_16 شامل بینهایت زیرمجموعه از formula_15 است. برای مثال مجموعه تمام اعداد زوج، همچنین مجموعه تهی. حال که درکی از شمایل عناصر عضو formula_16 داریم، تصمیم میگیریم که تک تک عناصر formula_15 را با عناصری از formula_16 نظیر کنیم و به این ترتیب نشان دهیم که این دو مجموعه هم ارز هستند. به عیارت دیگر هر عنصر از formula_15 را با یک عنصر از مجموعه نامتناهی formula_16 جفت می‌کنیم به‌طوری که هیچ عنصری از هیچ‌کدام از دو مجموعه جفت ناشده باقی نماند. چنین جفت کردنی که توضیح داده شد، به صورت زیر خواهد بود:
با چنین تناظری برخی اعداد طبیعی با زیرمجموعه‌هایی جفت می‌شوند که همان عدد را شامل می‌شوند. برای مثال در نمونه‌ای که ذکر شد، ۲ با مجموعه formula_27 جفت شده‌است، که ۲ را به عنوان یک عضو در بر دارد. این اعداد را خودخواه مینامیم. سایر اعداد طبیعی با زیرمجموعه‌هایی جفت می‌شوند که شامل آن عدد نیستند. این اعداد را غیر خودپسند مینامیم. برای مثال در مثال بالا ۳ و ۴ غیر خودخواه هستند.
با بهره‌گیری از این ایده، یک مجموعه خاص از اعداد طبیعی میسازیم. این مجموعه تناقضی که به دنبال آن هستیم را فراهم میسازد. D را مجموعه تمام اعداد غیر خودخواه طبیعی در نظر میگیریم. طبق تعریف مجموعه توانی formula_16 شامل تمام محموعه‌های اعداد طبیعی هست و طبق این، مجموعه D را هم شامل می‌شود. در نتیجه D باید با یک عدد طبیعی جفت شده باشد(آن را d در نظر میگیریم.) در هر صورت این یک مشکل به بار می‌آورد. اگر d خودخواه باشد، آنگاه d نمی‌تواند عضوی از D باشد چرا که D جوری طراحی شده بود که تنها شامل اعداد غیر خودخواه باشد. اما در این صورت d غیر خودخواه خواهد بود. چون عضوی از D نیست. از سوی دیگر اگر d غیر خودخواه باشد، آنگاه... خوب آنگاه d باید در D موجود باشد(دوباره طبق تعریف D).
این یک تناقض است. چون یک عدد طبیعی نمی‌تواند در آن واحد در مجموعه D موجود باشد و در آن موجود نباشد. در نتیجه هیچ عدد طبیعی یافت نمی‌شود که با d جفت شود پس ما به تناقض با فرض اولیه خود مبنی بر این که می‌تواند یه تناظر یک به یک بین formula_15 و formula_16 برقرار کرد رسیدیم. به وسیله این اثبات، به کمک برهان خلف اثبات کردیم که کاردینال formula_15 و formula_16 نمی‌تواند مساوی باشد. همچنین می‌دانیم که کاردینال formula_16 نمی‌تواند از کاردینال formula_15 کمتر باشد چرا که formula_16 تمام مجموعه‌های تک عضوی را شامل می‌شود یعنی formula_16 یک کپی از formula_15 در خود دارد. در نتیجه تنها امکانی که باقی می‌ماند این است که کاردینال formula_16 از کاردینال formula_15 اکیداً بزرگتر باشد. این، قضیه کانتور را اثبات می‌کند.
توجه کنید که مجموعه D شاید تهی باشد. این بدان معناست که هر عدد طبیعی x به یک زیر مجموعه اعداد طبیعی که x را شامل می‌شود نظیر می‌شود. سپس هر عدد به یک مجموعه غیر تهی نظیر می‌شود و هیچ عددی به تهی نظیر نمی‌شود. اما تهی عضوی از formula_16 است، پس عملیات نظیر سازی، همچنان formula_16 را پوشش نخواهد داد.