قضیه کانتور برنشتاین
قضیهٔ کانتور ــ برنشتاین، یا شِرُدِر ــ برنشتاین، بیانگر این است که اگر formula_1 و formula_2 دو مجموعه باشند و نگاشتی یک‌به‌یک از formula_1 به formula_4 و نگاشتی یک‌به‌یک از formula_4 به formula_6 موجود باشد، آنگاه formula_7 و formula_8 همتوانند؛ یعنی نگاشتی یک‌به‌یک و پوشا از formula_7 به formula_8 موجود است. به بیان کاردینالی، اگر formula_11 دو کاردینال باشند، و داشته باشیم formula_12 و formula_13، آنگاه formula_14.
این قضیه را نخستین بار کانتور در ۱۸۸۸ میلادی بدون ارائهٔ اثبات منتشر کرده است. اثباتی که بعدها خودِ کانتور در ۱۸۹۵ میلادی ارائه کرده است، بر «اصل انتخاب» استوار است. در ۱۸۹۸ اثباتی توسط ارنست شِرُدر برای این قضیه منتشر می‌شود، ولی معلوم می‌شود که اثبات یادشده ناکامل است. شردر در ۱۹۱۱ تصحیح‌شدهٔ اثبات خود را منتشر می‌کند. از این رو، نخستین اثبات بدون اشتباه و نه بر پایهٔ اصل انتخاب برای این قضیه، اثباتی است که فلیکس برنشتاین ارائه کرده و در کتابی از بورل در سال ۱۸۹۸ منتشر شده است.
اثبات پیش‌رو نه بر اصل انتخاب و نه بر اصل وجود مجموعه‌ای نامتناهی استوار است.
فرض کنید formula_7 و formula_8 دو مجموعه باشند و formula_17 و formula_18 نگاشتهایی یک به یک باشند. آنگاه نگاشتی یک‌به‌یک و پوشا از formula_7 به formula_8 موجود است.
کافی است مجموعهٔ formula_21 چُنان یافت شود که formula_22. دراین‌صورت با تعریف تابع یک‌به‌یک و پوشای formula_23 به گونهٔ زیر، اثبات قضیه به پایان می‌رسد.
formula_24
در ادامهٔ اثبات، مجموعهٔ formula_25 را با ویژگی یادشده، خواهیم یافت.
قرار دهید formula_26 به بیان دیگر formula_27 داریم formula_28 و از این رو formula_29. قرار می‌دهیم formula_30 و نشان می‌دهیم که formula_25 ویژگی موردنظر را داراست.
برای آسان‌تر شدن بحث، می‌گیریم formula_32. بنابراین formula_33 پس باید نشان دهیم که formula_34 (به بیان دیگر، ماهیت بحث تبدیل می‌شود به یافتن نقطه‌ای ثابت برای تابعِ formula_35).
توجه می‌کنیم که اگر formula_36 آنگاه formula_37. نیز به‌آسانی می‌توان نشان داد که formula_38. تنها چیزی که مانده، این است که نشان دهیم که formula_39. برای این منظور، کافی است نشان دهیم که formula_40؛ به بیان دیگر formula_41. این نیز به آسانی با اعمال formula_35. بر دو طرف رابطهٔ formula_38 و توجه به آنچه در آغاز این بند آمده است ثابت می‌شود.
قضیهٔ کانتور برنشتاین، معادل قضیهٔ زیر است. در اثبات زیر از استقراء (و در نتیجه از اصل وجود مجموعه‌ای نامتناهی) کمک گرفته شده است.
فرض کنید formula_44 و نگاشتی یک‌به‌یک و پوشا از formula_45 به formula_46 موجود باشد. آنگاه نگاشتی یک‌به‌یک و پوشا از formula_45 به formula_48 موجود است.
قرار می‌دهیم formula_49، formula_50 و formula_51. نیز با استقراء تعریف می‌کنیم formula_52، formula_53 و formula_54. توجه کنید که formula_55. تابعِ formula_56 که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا: formula_57.
اثبات ارائه‌شده در زیر، در حقیقت بیان دیگری است از اثبات بالا.
فرض کنید formula_58 و formula_59 یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از formula_48 به formula_45 یافت می‌شود.
قرار دهید formula_62، formula_63، formula_64. نیز بگیرید formula_65، formula_66 و formula_67. تابعِ formula_56 که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا: formula_69.
اثبات چهارم نیز بیان بهتری است از اثباتهای دوم و سوم.
فرض کنید formula_58 و formula_59 یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از formula_48 به formula_45 یافت می‌شود.
برای آسانتر شدن بحث فرض می‌کنیم formula_74 نگاشت همانی باشد و formula_75. قرار دهید formula_76. تابعِ formula_77 که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا: formula_78.
اثبات ارائه‌شده در زیر، توسط «کونیگ» ارائه شده است.
فرض کنید formula_17 و formula_18 یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از formula_7 به formula_8 یافت می‌شود.
برای هر عنصر formula_83 (یا برای هر formula_84) دنباله‌های زیر را در نظر بگیرید:
formula_85
توجه کنید که دنباله‌های این‌چنین اگر با هم اشتراکی داشته باشند، با هم برابرند؛ بنابراین این دنباله‌ها مجموعهٔ formula_86 را افراز می‌کنند. برای اثبات قضیه، کافی است هر یک از این دنباله‌ها را جداگانه در نظرگرفته میان عناصری از آن که از formula_48 آمده‌اند و عناصری از آن که از formula_45 آمده‌اند تناظر برقرار کنیم. اگر دنبالهٔ یادشده از سمت چپ در formula_48 متوقف شود، نگاشت formula_90 را برای برقرار کردن تناظر میان اعضای آن در نظر می‌گیریم، و اگر از سمت چپ در formula_8 متوقف شود از نگاشت formula_92 استفاده می‌کنیم. در غیر این دو صورت، هم می‌توان از نگاشت formula_90 استفاده کرد و هم از formula_92.
با استفاده از اصل انتخاب می‌توان ثابت کرد که وجود یک نگاشت یک‌به‌یک از formula_7 به formula_8 معادل وجود نگاشتی پوشا از formula_8 به formula_7 است. قضیهٔ کانتور برنشتاین از این گفته به آسانی نتیجه می‌شود.