استدلال قطری کانتور - ویکیپدیا، دانشنامهٔ آزاد
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Diagonal_argument_01_svg.svg/250px-Diagonal_argument_01_svg.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Aplicaci%C3%B3n_2_inyectiva_sobreyectiva02.svg/220px-Aplicaci%C3%B3n_2_inyectiva_sobreyectiva02.svg.png)
در نظریه مجموعهها، استدلال قطری کانتور در سال ۱۸۹۱ توسط گئورگ کانتور به عنوان یک اثبات ریاضی ارائه گردید و نشان داد مجموعههای نامتناهی وجود دارند که اعضای آنها در تناظر یک به یک با مجموعه اعداد طبیعی نیستند.[۱][۲][۳] چنین مجموعههایی را «مجموعه ناشمارا» مینامند.
مجموعه غیرقابل شمارش
[ویرایش]کانتور، در مقالهی خود در سال ۱۸۹۱، مجموعه T را مطالعه کرد که شامل همه دنبالههای رقمهای دودویی (یعنی هر رقم صفر یا یک) باشد. او با اثباتی ساختی از قضیه زیر شروع میکند:
- اگر s1, s2, … , sn شامل تمامی شمارشهای ممکن از T باشد، آنگاه همواره عضوی از T وجود خواهد داشت که در بین s1,S2,... نخواهد بود.
برای اثبات این، مجموعههایی از T را به شکل زیر انتخاب مینماییم:
s1 = (۰, ۰, ۰, ۰, ۰, ۰, ۰, ...) s2 = (۱, ۱, ۱, ۱, ۱, ۱, ۱, ...) s3 = (۰, ۱, ۰, ۱, ۰, ۱, ۰, ...) s4 = (۱, ۰, ۱, ۰, ۱, ۰, ۱, ...) s5 = (۱, ۱, ۰, ۱, ۰, ۱, ۱, ...) s6 = (۰, ۰, ۱, ۱, ۰, ۱, ۱, ...) s7 = (۱, ۰, ۰, ۰, ۱, ۰, ۰, ...) ...
او ساختار توالی s را با انتخاب مکمل اولین رقم در s1 انتخاب نمود (جایگزینی صفر به جای یک و برعکس)، برای انتخاب دومین رقم S به سراغ رقم دوم در s2 رفت و مکمل آن را انتخاب نمود و به همین ترتیب ادامه داد. در مثال فوق به نتایج زیر میرسیم:
s1 = (۰, ۰, ۰, ۰, ۰, ۰, ۰, ...) s2 = (۱, ۱, ۱, ۱, ۱, ۱, ۱, ...) s3 = (۰, ۱, ۰, ۱, ۰, ۱, ۰, ...) s4 = (۱, ۰, ۱, ۰, ۱, ۰, ۱, ...) s5 = (۱, ۱, ۰, ۱, ۰, ۱, ۱, ...) s6 = (۰, ۰, ۱, ۱, ۰, ۱, ۱, ...) s7 = (۱, ۰, ۰, ۰, ۱, ۰, ۰, ...) ... s = (۱, ۰, ۱, ۱, ۱, ۰, ۱, ...)
با ساخت s به روش فوق به مجموعهای میرسیم که با تمامی مجموعههای بالا متفاوت است زیرا عنصر n ام آن با عنصر n ام تمام مجموعههای بالا تفاوت دارد.
بر اساس این قضیه کانتور با استفاده از یک اثبات با تناقض نشان میدهد که:
- مجموعه T غیرقابل شمارش است.
او برای اثبات تناقض در ابتدا فرض میکند T شمارا است. پس همه عناصر آن به شکل s1,s2,...sn قابل نمایش هستند. با اعمال قضیه قبلی به این شمارشها به توالی s میرسیم که در شمارشها موجود نیست. اما s عنصری از T بود و بنابراین باید در شمارشها باشد. این تضاد فرض اصلی را زیر سؤال میبرد بنابراین T غیرقابل شمارش است.
منابع
[ویرایش]- ↑ Georg Cantor (1891). "Ueber eine elementare Frage der Mannigfaltigkeitslehre". Jahresbericht der Deutschen Mathematiker-Vereinigung 1890–1891. 1: 75–78 (84–87 in pdf file).
- ↑ Keith Simmons (30 July 1993). Universality and the Liar: An Essay on Truth and the Diagonal Argument. Cambridge University Press. pp. 20–. ISBN 978-0-521-43069-2.
- ↑ Rudin, Walter (1976). Principles of Mathematical Analysis (3rd ed.). New York: McGraw-Hill. p. 30. ISBN 0-07-085613-3.