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

قضیه کانتور  برنشتاین
قضیه کانتور  برنشتاین، یا شردر  برنشتاین، بیانگر این است که اگر
X
و
Y
دو مجموعه باشند و
نگاشتی یک‌به‌یک از
X
به
Y
و نگاشتی یک‌به‌یک از
Y
به
X
موجود باشد، آنگاه
و
همتوانند؛ یعنی نگاشتی یک‌به‌یک و پوشا از
به
موجود است. به بیان کاردینالی، اگر
دو کاردینال باشند، و داشته باشیم
و
آنگاه
تاریخ
این قضیه را نخستین بار کانتور در
۱۸۸۸
میلادی بدون ارائه اثبات منتشر کرده است. اثباتی که بعدها خود کانتور در
۱۸۹۵
میلادی ارائه کرده است، بر «اصل انتخاب» استوار است. در
۱۸۹۸
اثباتی توسط ارنست شردر برای این قضیه منتشر می‌شود، ولی
معلوم می‌شود که اثبات یادشده ناکامل است. شردر در
۱۹۱۱
تصحیح‌شده اثبات خود را منتشر می‌کند. از این رو، نخستین اثبات بدون اشتباه و نه بر پایه اصل انتخاب برای این قضیه، اثباتی است
که فلیکس برنشتاین ارائه کرده و در کتابی از بورل در سال
۱۸۹۸
منتشر شده است.
شش اثبات برای قضیه کانتور  برنشتاین
اثبات نخست
اثبات پیش‌رو نه بر اصل انتخاب و نه بر اصل وجود مجموعه‌ای نامتناهی استوار است.
قضیه
فرض کنید
و
دو مجموعه باشند و
و
نگاشتهایی باشند یک‌به‌یک.
آنگاه نگاشتی یک‌به‌یک و پوشا از
به
موجود است.
اثبات
کافی است مجموعه
چنان یافت شود که
دراین‌صورت با تعریف تابع یک‌به‌یک و پوشای
به گونه زیر، اثبات قضیه به پایان می‌رسد.
h(x) = \left\{\begin{array{lr
f(x) - x\in Z_0\\
g^{-1(x) - x\not\in Z_0
\end{array\right.
در ادامه اثبات، مجموعه
Z_0
را با ویژگی یادشده، خواهیم یافت.
قرار دهید
\Sigma=\{Z\subseteq X| g(f(Z)^c)\subseteq Z^c\
به بیان دیگر
\Sigma=\{Z\subseteq X| Z\subseteq (g(f(Z)^c))^c\
داریم
\emptyset\in \Sigma
و از این رو
\Sigma\not=\emptyset
قرار می‌دهیم
Z_0:=\bigcup_{Z\in \sigma Z
و نشان می‌دهیم که
Z_0
ویژگی موردنظر را داراست.
برای آسان‌تر شدن بحث، می‌گیریم
H(Z):=(g(f(Z)^c))^c
بنابراین
\Sigma=\{Z\subseteq X| Z\subseteq H(Z)\.
پس باید نشان دهیم که
H(Z_0)=Z_0
(به بیان دیگر، ماهیت بحث تبدیل می‌شود به یافتن نقطه‌ای ثابت برای تابع
H
توجه می‌کنیم که اگر
A\subseteq B
آنگاه
H(A)\subseteq H(B)
نیز به‌آسانی می‌توان نشان داد که
Z_0\subseteq H(Z_0)
تنها چیزی که مانده، این است که نشان دهیم که
H(Z_0)\subseteq Z_0
برای این منظور، کافی است نشان دهیم که
H(Z_0)\in \Sigma
به بیان دیگر
H(Z_0)\subseteq H(H(Z_0))
این نیز به آسانی با اعمال
H
بر دو طرف رابطه
Z_0\subseteq H(Z_0)
و توجه به آنچه در آغاز این بند آمده است ثابت می‌شود.
اثبات دوم
قضیه کانتور برنشتاین، معادل قضیه زیر است. در اثبات زیر از استقراء (و در نتیجه از اصل وجود مجموعه‌ای نامتناهی) کمک گرفته شده است.
قضیه
فرض کنید
Z\subseteq X\subseteq Y
و نگاشتی یک‌به‌یک و پوشا از
Y
به
Z
موجود باشد. آنگاه نگاشتی یک‌به‌یک و پوشا از
Y
به
X
موجود است.
اثبات
قرار می‌دهیم
Y_0=Y
X_0=X
و
C_0=Y_0-X_0
نیز با استقراء تعریف می‌کنیم
X_n=f(X_{n-1)
Y_n=f(Y_{n-1)
و
C_n=Y_n-X_n
توجه کنید که
X_{n+1\subseteq X_n
تابع
h:Y\to X
که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا:
h(x)=\begin{cases
f(x) - x\in \bigcup_{i\in \omega C_i\\
x - \text{otherwise
\end{cases
اثبات سوم
اثبات ارائه‌شده در زیر، در حقیقت بیان دیگری است از اثبات بالا.
قضیه
فرض کنید
f:X\to Y
و
g:Y\to X
یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از
X
به
Y
یافت می‌شود.
اثبات
قرار دهید
X_0=X ، ، C_0=X_0-Y_0
نیز بگیرید
X_n=g(f(X_{n-1))
Y_n=g(f(Y_{n-1))
و
C_n=X_n-Y_n
تابع
h:Y\to X
که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا:
h(x)=\begin{cases
f(x) - x\in \bigcup_{i\in \omega C_i\\
g^{(-1)(x) - \text{ otherwise
\end{cases
اثبات چهارم
اثبات چهارم نیز بیان بهتری است از اثباتهای دوم و سوم.
قضیه
فرض کنید
f:X\to Y
و
g:Y\to X
یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از
X
به
Y
یافت می‌شود.
اثبات
برای آسانتر شدن بحث فرض می‌کنیم
f
نگاشت همانی باشد و
X\subseteq Y
قرار دهید
C=\{g^n(x)|n\in \mathbb{N,x\in Y-X\
تابع
که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا:
h(x)=\begin{cases
g(x) - x\in C\\
x - \text{ otherwise
\end{cases
اثبات پنجم
اثبات ارائه‌شده در زیر، توسط «کونیگ» ارائه شده است.
قضیه
فرض کنید
و
یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از
به
یافت می‌شود.
اثبات
برای هر عنصر
x\in X
(یا برای هر
دنباله‌های زیر را در نظر بگیرید:
\cdots \rightarrow f^{-1(g^{-1(x))\rightarrow g^{-1(x)\rightarrow a\rightarrow f(x)\rightarrow g(f(x))\rightarrow \cdots
توجه کنید که دنباله‌های این‌چنین اگر با هم اشتراکی داشته باشند، با هم برابرند؛ بنابراین این دنباله‌ها
مجموعه
X\cup Y
را افراز می‌کنند. برای اثبات قضیه، کافی است هر یک از این دنباله‌ها را جداگانه در نظرگرفته میان عناصری از آن که
از
X
آمده‌اند و عناصری از آن که از
Y
آمده‌اند تناظر برقرار کنیم. اگر دنباله یادشده از سمت چپ در
X
متوقف شود، نگاشت
را برای برقرار کردن تناظر میان اعضای آن در نظر می‌گیریم، و اگر از سمت چپ در
متوقف شود از نگاشت
استفاده می‌کنیم. در غیر این دو صورت، هم می‌توان از نگاشت
استفاده کرد و هم از
اثبات ششم
با استفاده از اصل انتخاب می‌توان ثابت کرد که وجود یک نگاشت یک‌به‌یک از
به
معادل وجود نگاشتی پوشا از
به
است. قضیه کانتور برنشتاین از این گفته به آسانی نتیجه می‌شود.