قضیه کانتور

در نظریه ابتدایی مجموعه ها، قضیه کانتور بیان می‌دارد که مجموعه توانی(مجموعه تمام زیرمجموعه ها) مجموعه A، کاردینالیتی اکیدا بزرگتری از خود مجموعه A دارد. قضیه کانتور برای مجموعه‌های متناهی صادق است، اما به طور خیلی جالب برای مجموعه‌های نامتناهی نیز صادق است. این نظریه به نام جرج کانتور، کسی که آن را اثبات کرده است، به ثبت رسیده است.

توضیح دقیقی از اثبات زمانی که X، یک نامتناهی قابل شمارش است.

برای یافتن تصوری از اثبات، آن را برای مورد خاص زمانی که X یک نامتناهی قابل شمارش است امتحان میکنیم. بدون از دست دادن کلیت، X را مساوی مجموعه اعداد طبیعی میگیریم. فرض کنید N با مجموعه توانی خود(P(N هم ارز است. یک مثال از شمایل(P(N ببینید:


http://upload.wikimedia.org/wikipedi...87/Cantor2.JPG
حال که درکی از شمایل عناصر عضو(P(N داریم، تصمیم به این میگیریم که تک تک یک عنصر از N را با یک عنصر از(P(N جفت کنیم و به این ترتیب نشان دهیم که این دو مجموعه هم ارز هستند. به عیارت دیگر هر عنصر از N را با یک عنصر از مجموعه نامتناهی(P(N جفت میکنیم به طوری که هیچ عنصری از هیچ کدام از دو مجموعه جفت ناشده باقی نماند. چنین جفت کردنی که توضیح داده شد، به صورت زیر خواهد بود:

http://upload.wikimedia.org/wikipedi...f2/Cantor3.JPG

با چنین جفت کردنی. برخی اعداد طبیعی با زیرمجموعه‌هایی جفت می‌شوند که همان عدد را شامل می‌شوند. برای مثال در نمونه‌ای که ذکر شد، 2 با مجموعه 1و2و3 جفت شده است، که 2 را به عنوان یک عضو در بر دارد. این اعداد را خودخواه مینامیم. سایر اعداد طبیعی با زیرمجموعه‌هایی جفت می‌شوند که شامل آن عدد نیستند. این اعداد را غیر خودپسند مینامیم. برای مثال در مثال بالا 3 و 4 غیر خودخواه هستند.
با بهره گیری از این ایده، یک مجموعه خاص از اعداد طبیعی میسازیم. این مجموعه تناقضی که به دنبال آن هستیم را فراهم میسازد. D را مجموعه تمام اعداد غیر خودخواه طبیعی در نظر میگیریم. طبق تعریف مجموعه توانی((P(N)) شامل تمام محموعه‌های اعداد طبیعی هست و طبق این، مجموعه D را هم شامل می‌شود. در نتیجه D باید با یک عدد طبیعی جفت شده باشد(آن را d در نظر میگیریم.) در هر صورت این یک مشکل به بار می‌آورد. اگر d خودخواه باشد، آنگاه d نمی‌تواند عضوی از D باشد چرا که D جوری طراحی شده بود که تنها شامل اعداد غیر خودخواه باشد. اما در این صورت d غیر خودخواه خواهد بود. چون عضوی از D نیست. از سوی دیگر اگر d غیر خودخواه باشد، آنگاه... خوب آنگاه d باید در D موجود باشد(دوباره طبق تعریف D).

این یک تناقض است. چون یک عدد طبیعی نمی‌تواند در آن واحد در مجموعه D موجود باشد و در آن موجود نباشد. در نتیجه هیچ عدد طبیعی یافت نمی‌شود که با d جفت شود پس ما به تناقض با فرض اولیه خود مبنی بر این که می‌تواند یه تناظر یک به یک بین N و(P(N برقرار کرد رسیدیم.
به وسیله این اثبات، به کمک تناقض اثبات کردیم که کاردینالیتی N و(P(N نمی‌تواند مساوی باشد.همچنین میدانیم که کاردینالیتی(P(N نمی‌تواند از کاردینالیتی N کمتر باشد چرا که(P(N تمام مجموعه‌های تک عضوی را شامل می‌شود یعنی(P(N یک کپی از N در خود دارد.در نتیجه تنها امکانی که باقی میماند این است که کاردینالیتی (P(N از کاردینالیتی N اکیدا بزرگتر باشد. این، نظریه کانتور را اثبات می‌کند.
توجه کنید که مجموعه D شاید تهی باشد. این بدان معناست که هر عدد طبیعی x به یک مجموعه اعداد طبیعی که x را شامل می‌شود نظیر می‌شود. سپس هر عدد به یک مجموعه غیر تهی نظیر می‌شود و هیچ عددی به تهی نظیر نمی‌شود. اما تهی عضوی از (P(N است، پس عملیات نظیر سازی، همچنان (P(N را نمیپوشاند.