استدلال قطری کانتور: تفاوت میان نسخه‌ها

جز
تمیزکاری، + ماژول ابرابزار با استفاده از AWB
جز (←‏top: تمیزکاری. با استفاده از AWB)
جز (تمیزکاری، + ماژول ابرابزار با استفاده از AWB)
[[پرونده:Diagonal argument 01 svg.svg|چپ|بندانگشتی|325x325پیکسل|یک تصویر از استدلال قطری کانتور (در مبنای ۲) برای اثبات وجود مجموعه هایمجموعه‌های غیرقابل شمارش. دنباله پایین (s) نمی‌تواند در هیچ یکهیچ‌یک از توالی هایتوالی‌های بالا رخ دهد.]]
[[پرونده:Aplicación 2 inyectiva sobreyectiva02.svg|بندانگشتی|یک [[مجموعه نامتناهی]] ممکن است دارای همان کاردینالیتی باشد که [[زیرمجموعه|زیر مجموعه]] مناسب آن دارد. مثلاً مجموعه اعداد طبیعی با مجموعه اعداد زوج مس تواند تناظر یک به یک برقرا نماید. با این وجود بی نهایت هاییبی‌نهایت‌هایی با کاردینالیتی هایکاردینالیتی‌های متفاوت وحو دارندکه '''استدلال قطری کانتور '''وجود آنها را اثبات می نمایدمی‌نماید.]]
در [[نظریه مجموعه‌ها|نظریه مجموعه]] ها٬ها، '''استدلال''' '''قطری کانتور''' در سال ۱۸۹۱ توسط [[گئورگ کانتور]] به عنوان یک [[برهان (ریاضی)|اثبات ریاضی]] ارایه گردید و نشان داد مجموعه هایمجموعه‌های [[مجموعه نامتناهی|بی نهایتیبی‌نهایتی وجود دارند]] قادر نیستیم اعضای آنها را در تناظر یک به یک با محموعه اعداد طبیعی قرار دهیم.<ref>{{Cite journal|title=Ueber eine elementare Frage der Mannigfaltigkeitslehre|last=Georg Cantor|journal=Jahresbericht der Deutschen Mathematiker-Vereinigung 1890–1891|year=1891|volume=1|pages=75–78 (84–87 in pdf file)}}</ref><ref name="Simmons1993">{{Cite book|url=https://books.google.com/books?id=wEj3Spept0AC&pg=PA20|title=Universality and the Liar: An Essay on Truth and the Diagonal Argument|last=Keith Simmons|date=30 July 1993|publisher=Cambridge University Press|isbn=978-0-521-43069-2|pages=20–}}</ref><ref name="Rubin1976">{{Cite book|title=Principles of Mathematical Analysis|last=Rudin|first=Walter|date=1976|publisher=McGraw-Hill|isbn=00708561330-07-085613-3|edition=3rd|location=New York|page=30}}</ref>
چنین مجموعه ایمجموعه‌ای در حال حاضر  به عنوان غیر قابلغیرقابل شمارش  شناخته می شوندمی‌شوند.
 
== مجموعه غیر قابلغیرقابل شمارش ==
او در سال ۱۸۹۱ مقاله کانتور در نظر گرفت مجموعه ''T'' شامل همه بی نهایتهایبی‌نهایتهای بدی آمده از [[دنباله|توالی]] [[بیت (رایانه)|رقم هایرقم‌های دودویی]] (یعنی هر رقم صفر یا یک) در یک دنباله باشد.
او با یک اثبات سازنده از قضیه زیر اثبات خود را شروع می کندمی‌کند:
: اگر s1, s2, … , sn شامل تمامی شمارشهای ممکن از T باشد آنگاه همواره عضوی از T وجود خواهد داشت که در بین s1,S2,... نخواهد بود.{{سخ}}
برای اثبات این٬این، محموعه هاییمحموعه‌هایی از T را به شکل زیر انتخاب می نماییممی‌نماییم:
: {| style="margin-bottom: 10px;"
| ''s''<sub>1</sub> =
| (0۰,
| 0۰,
| 0۰,
| 0۰,
| 0۰,
| 0۰,
| 0۰,
| ...)
|-
| ''s''<sub>2</sub> =
| (1۱,
| 1۱,
| 1۱,
| 1۱,
| 1۱,
| 1۱,
| 1۱,
| ...)
|-
| ''s''<sub>3</sub> =
| (0۰,
| 1۱,
| 0۰,
| 1۱,
| 0۰,
| 1۱,
| 0۰,
| ...)
|-
| ''s''<sub>4</sub> =
| (1۱,
| 0۰,
| 1۱,
| 0۰,
| 1۱,
| 0۰,
| 1۱,
| ...)
|-
| ''s''<sub>5</sub> =
| (1۱,
| 1۱,
| 0۰,
| 1۱,
| 0۰,
| 1۱,
| 1۱,
| ...)
|-
| ''s''<sub>6</sub> =
| (0۰,
| 0۰,
| 1۱,
| 1۱,
| 0۰,
| 1۱,
| 1۱,
| ...)
|-
| ''s''<sub>7</sub> =
| (1۱,
| 0۰,
| 0۰,
| 0۰,
| 1۱,
| 0۰,
| 0۰,
| ...)
|-
| ...
|}
او ساختار توالی ''s'' را با انتخاب مکمل اولین رقم در s1 انتخاب نمود (جایگزینی صفر به جای یک و برعکس)٬، برای انتخاب دومین رقم S به سراع رقم دوم در s2 رفت و مکمل آنرا انتخاب نمد و به همین ترتیب ادامه داد. در مثال فوق به نتایج زیر میرسیممی‌رسیم:
: {|
| ''s''<sub>1</sub>
| =
| (<u>'''0'''</u>,
| 0۰,
| 0۰,
| 0۰,
| 0۰,
| 0۰,
| 0۰,
| ...)
|-
| ''s''<sub>2</sub>
| =
| (1۱,
| <u>'''1'''</u>,
| 1۱,
| 1۱,
| 1۱,
| 1۱,
| 1۱,
| ...)
|-
| ''s''<sub>3</sub>
| =
| (0۰,
| 1۱,
| <u>'''0'''</u>,
| 1۱,
| 0۰,
| 1۱,
| 0۰,
| ...)
|-
| ''s''<sub>4</sub>
| =
| (1۱,
| 0۰,
| 1۱,
| <u>'''0'''</u>,
| 1۱,
| 0۰,
| 1۱,
| ...)
|-
| ''s''<sub>5</sub>
| =
| (1۱,
| 1۱,
| 0۰,
| 1۱,
| <u>'''0'''</u>,
| 1۱,
| 1۱,
| ...)
|-
| ''s''<sub>6</sub>
| =
| (0۰,
| 0۰,
| 1۱,
| 1۱,
| 0۰,
| <u>'''1'''</u>,
| 1۱,
| ...)
|-
| ''s''<sub>7</sub>
| =
| (1۱,
| 0۰,
| 0۰,
| 0۰,
| 1۱,
| 0۰,
| <u>'''0'''</u>,
| ...)
|-
|-
|-
| ''s''
| =
| (<u>'''1'''</u>,
| <u>'''0'''</u>,
| <u>'''1'''</u>,
| <u>'''1'''</u>,
| <u>'''1'''</u>,
| <u>'''0'''</u>,
| <u>'''1'''</u>,
| ...)
|}
با ساخت s به روش فوق به مجموعهمجموعه‌ای ای میرسیممی‌رسیم که با تمامی مجمه هایمجمه‌های بالا متفاوت است زیرا عنصر n ام آن با عنصر n ام تمام مجموعه هایمجموعه‌های بالا تفاوت دارد.
 
بر اساس این قضیه کانتور با استفاده از یک [[برهان خلف|اثبات با تناقض]] نشان می دهدمی‌دهد که:
: مجموعه ''T'' غیر قابلغیرقابل شمارش است.
او برای اثبات تناقض در ابتدا فرض می کندمی‌کند ''T'' شمارا است. پس همه عناصر آن به شکل s1,s2,...sn قابل نمایش هستند.
با اعمال قضیه قبلی به این شمارشها به توالی ''s'' می رسیممی‌رسیم که در شمارش هاشمارش‌ها موجود نیست.
اما ''s'' عنصری از T بود و بنابراین باید در شمارش هاشمارش‌ها باشد.
این تضاد فرض اصلی را زیر سوالسؤال میبردمی‌برد بنابراین ''T'' غیر قابلغیرقابل شمارش است.
 
== منابع ==