قضیهٔ کانتور ــ برنشتاین، یا شِرُدِر ــ برنشتاین، بیانگر این است که اگر
و
دو مجموعه باشند و
نگاشتی یکبهیک از
به
و نگاشتی یکبهیک از
به
موجود باشد، آنگاه
و
همتوانند؛ یعنی نگاشتی یکبهیک و پوشا از
به
موجود است. به بیان کاردینالی، اگر
دو کاردینال باشند، و داشته باشیم
و
،
آنگاه
.
این قضیه را نخستین بار کانتور در
۱۸۸۸
میلادی بدون ارائهٔ اثبات منتشر کرده است. اثباتی که بعدها خودِ کانتور در
۱۸۹۵
میلادی ارائه کرده است، بر «اصل انتخاب» استوار است. در
۱۸۹۸
اثباتی توسط ارنست شِرُدر برای این قضیه منتشر میشود، ولی
معلوم میشود که اثبات یادشده ناکامل است. شردر در
۱۹۱۱
تصحیحشدهٔ اثبات خود را منتشر میکند. از این رو، نخستین اثبات بدون اشتباه و نه بر پایهٔ اصل انتخاب برای این قضیه، اثباتی است
که فلیکس برنشتاین ارائه کرده و در کتابی از بورل در سال
۱۸۹۸
منتشر شده است.
کافی است مجموعهٔ
چُنان یافت شود که
.
دراینصورت با تعریف تابع یکبهیک و پوشای
به گونهٔ زیر، اثبات قضیه به پایان میرسد.
در ادامهٔ اثبات، مجموعهٔ
را با ویژگی یادشده، خواهیم یافت.
قرار دهید
به بیان دیگر
داریم
و از این رو
.
قرار میدهیم
و نشان میدهیم که
ویژگی موردنظر را داراست.
برای آسانتر شدن بحث، میگیریم
.
بنابراین
پس باید نشان دهیم که
(به بیان دیگر، ماهیت بحث تبدیل میشود به یافتن نقطهای ثابت برای تابعِ
).
توجه میکنیم که اگر
آنگاه
.
نیز بهآسانی میتوان نشان داد که
.
تنها چیزی که مانده، این است که نشان دهیم که
.
برای این منظور، کافی است نشان دهیم که
؛
به بیان دیگر
.
این نیز به آسانی با اعمال
.
بر دو طرف رابطهٔ
و توجه به آنچه در آغاز این بند آمده است ثابت میشود.
برای هر عنصر
(یا برای هر
)
دنبالههای زیر را در نظر بگیرید:
توجه کنید که دنبالههای اینچنین اگر با هم اشتراکی داشته باشند، با هم برابرند؛ بنابراین این دنبالهها
مجموعهٔ
را افراز میکنند. برای اثبات قضیه، کافی است هر یک از این دنبالهها را جداگانه در نظرگرفته میان عناصری از آن که
از
آمدهاند و عناصری از آن که از
آمدهاند تناظر برقرار کنیم. اگر دنبالهٔ یادشده از سمت چپ در
متوقف شود، نگاشت
را برای برقرار کردن تناظر میان اعضای آن در نظر میگیریم، و اگر از سمت چپ در
متوقف شود از نگاشت
استفاده میکنیم. در غیر این دو صورت، هم میتوان از نگاشت
استفاده کرد و هم از
.
با استفاده از اصل انتخاب میتوان ثابت کرد که وجود یک نگاشت یکبهیک از
به
معادل وجود نگاشتی پوشا از
به
است. قضیهٔ کانتور برنشتاین از این گفته به آسانی نتیجه میشود.