قضیه کانتور برنشتاین

قضیهٔ کانتور ــ برنشتاین، یا شِرُدِر ــ برنشتاین، بیانگر این است که اگر X {\displaystyle X}  و Y {\displaystyle Y}  دو مجموعه باشند ونگاشتی یک به یک از X {\displaystyle X}  به Y {\displaystyle Y}  و نگاشتی یک به یک از Y {\displaystyle Y}  به X {\displaystyle X}  موجود باشد، آنگاه X {\displaystyle X}  و Y {\displaystyle Y}  همتوانند؛ یعنی نگاشتی یک به یک و پوشا از X {\displaystyle X}  به Y {\displaystyle Y}  موجود است. به بیان کاردینالی، اگر κ , κ ′ {\displaystyle \kappa ,\kappa '}  دو کاردینال باشند، و داشته باشیم κ ≤ κ ′ {\displaystyle \kappa \leq \kappa '}  و κ ′ ≤ κ {\displaystyle \kappa '\leq \kappa }  ،آنگاه κ = κ ′ {\displaystyle \kappa =\kappa '}  .
این قضیه را نخستین بار کانتور در۱۸۸۸میلادی بدون ارائهٔ اثبات منتشر کرده است. اثباتی که بعدها خودِ کانتور در۱۸۹۵میلادی ارائه کرده است، بر «اصل انتخاب» استوار است. در۱۸۹۸اثباتی توسط ارنست شِرُدر برای این قضیه منتشر می شود، ولیمعلوم می شود که اثبات یادشده ناکامل است. شردر در۱۹۱۱تصحیح شدهٔ اثبات خود را منتشر می کند. از این رو، نخستین اثبات بدون اشتباه و نه بر پایهٔ اصل انتخاب برای این قضیه، اثباتی استکه فلیکس برنشتاین ارائه کرده و در کتابی از بورل در سال۱۸۹۸منتشر شده است.
اثبات پیش رو نه بر اصل انتخاب و نه بر اصل وجود مجموعه ای نامتناهی استوار است.
فرض کنید X {\displaystyle X}  و Y {\displaystyle Y}  دو مجموعه باشند و f : X → Y {\displaystyle f:X\to Y}  و g : Y → X {\displaystyle g:Y\to X}  نگاشتهایی باشند یک به یک.آنگاه نگاشتی یک به یک و پوشا از X {\displaystyle X}  به Y {\displaystyle Y}  موجود است.