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

قضیهٔ کانتور ــ بِرِنِشْتاین

قضیهٔ کانتور ــ برنشتاین، یا شِرُدِر ــ برنشتاین، بیانگر این است که اگر $X$ و $Y$ دو مجموعه باشند و نگاشتی یک‌به‌یک از $X$ به $Y$ و نگاشتی یک‌به‌یک از $Y$ به $X$ موجود باشد، آنگاه $X$ و $Y$ همتوانند؛ یعنی نگاشتی یک‌به‌یک و پوشا از $X$ به $Y$ موجود است. به بیان کاردینالی، اگر $\kappa ,\kappa '$ دو کاردینال باشند، و داشته باشیم $\kappa \leq \kappa '$ و $\kappa '\leq \kappa$، آنگاه $\kappa =\kappa '$.

تاریخ

این قضیه را نخستین بار کانتور در ۱۸۸۸ میلادی بدون ارائهٔ اثبات منتشر کرده است. اثباتی که بعدها خودِ کانتور در ۱۸۹۵ میلادی ارائه کرده است، بر «اصل انتخاب» استوار است. در ۱۸۹۸ اثباتی توسط ارنست شِرُدر برای این قضیه منتشر می‌شود، ولی معلوم می‌شود که اثبات یادشده ناکامل است. شردر در ۱۹۱۱ تصحیح‌شدهٔ اثبات خود را منتشر می‌کند. از این رو، نخستین اثبات بدون اشتباه و نه بر پایهٔ اصل انتخاب برای این قضیه، اثباتی است که فلیکس برنشتاین ارائه کرده و در کتابی از بورل در سال ۱۸۹۸ منتشر شده است.

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

اثبات نخست

اثبات پیش‌رو نه بر اصل انتخاب و نه بر اصل وجود مجموعه‌ای نامتناهی استوار است.

قضیه

فرض کنید $X$ و $Y$ دو مجموعه باشند و $f:X\to Y$ و $g:Y\to X$ نگاشتهایی یک به یک باشند. آنگاه نگاشتی یک‌به‌یک و پوشا از $X$ به $Y$ موجود است.

اثبات

کافی است مجموعهٔ $Z_{0}\subseteq X$ چُنان یافت شود که $g(f(Z_{0})^{c})=Z_{0}^{c}$. دراین‌صورت با تعریف تابع یک‌به‌یک و پوشای $h:X\to Y$ به گونهٔ زیر، اثبات قضیه به پایان می‌رسد.

$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$، $Y_{0}=g(Y)$، $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:Y\to X$ که به صورت زیر تعریف شده، یک‌به‌یک است و پوشا: $h(x)={\begin{cases}g(x)&x\in C\\x&{\text{ otherwise}}\end{cases}}$.

اثبات پنجم

اثبات ارائه‌شده در زیر، توسط «کونیگ» ارائه شده است.

قضیه

فرض کنید $f:X\to Y$ و $g:Y\to X$ یک‌به‌یک باشند. آنگاه تابعی یک‌به‌یک و پوشا از $X$ به $Y$ یافت می‌شود.

اثبات

برای هر عنصر $x\in X$ (یا برای هر $y\in Y$) دنباله‌های زیر را در نظر بگیرید:

$\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$ متوقف شود، نگاشت $f$ را برای برقرار کردن تناظر میان اعضای آن در نظر می‌گیریم، و اگر از سمت چپ در $Y$ متوقف شود از نگاشت $g$ استفاده می‌کنیم. در غیر این دو صورت، هم می‌توان از نگاشت $f$ استفاده کرد و هم از $g$.

اثبات ششم

با استفاده از اصل انتخاب می‌توان ثابت کرد که وجود یک نگاشت یک‌به‌یک از $X$ به $Y$ معادل وجود نگاشتی پوشا از $Y$ به $X$ است. قضیهٔ کانتور برنشتاین از این گفته به آسانی نتیجه می‌شود.