در مورد قضیه کانتور برنشتاین توضیح بده.
قضیهٔ کانتور ــ برنشتاین، یا شِرُدِر ــ برنشتاین، بیانگر این است که اگر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است. قضیهٔ کانتور برنشتاین از این گفته به آسانی نتیجه می‌شود.