بسم الله الرحمن الرحیم
استدلال قطری کانتور
فهرست علوم
فهرست مباحث ریاضیات
مجموعه
بینهایت
بینهایت ناشمارا
استدلال قطری کانتور
بهشت کانتور
افلاطونگرائي
هوش ضعیف رفتارمحور-هوش قوی پایه محور-هوش قوی اشراق‌محور
شرح حال گئورگ کانتور(1261 - 1336 هـ = 1845 - 1918 م)
شرح حال داوید هیلبرت(1279 - 1362 هـ = 1862 - 1943 م)
شرح حال کورت گودل(1323 - 1398 هـ = 1906 - 1978 م)
شرح حال لودویگ یوزف یوهان ویتگنشتاین(1306 - 1370 هـ = 1889 - 1951 م)
Cantor's diagonal argument
استدلال قطری کانتور
از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری
پرش به جستجو
یک تصویر از استدلال قطری کانتور (در مبنای ۲) برای اثبات وجود مجموعه‌های غیرقابل شمارش. دنباله پایین (s) نمی‌تواند در هیچ‌یک از توالی‌های بالا رخ دهد.
یک مجموعه نامتناهی ممکن است دارای همان کاردینالیتی باشد که زیر مجموعه مناسب آن دارد. مثلاً مجموعه اعداد طبیعی با مجموعه اعداد زوج مس تواند تناظر یک به یک برقرا نماید. با این وجود بی‌نهایت‌هایی با کاردینالیتی‌های متفاوت وحو دارند که استدلال قطری کانتور وجود آن‌ها را اثبات می‌نماید.
در نظریه مجموعه‌ها، استدلال قطری کانتور در سال ۱۸۹۱ توسط گئورگ کانتور به عنوان یک اثبات ریاضی ارائه گردید و نشان داد مجموعه‌های بی‌نهایتی وجود دارند که قادر نیستیم اعضای آن‌ها را در تناظر یک به یک با محموعه اعداد طبیعی قرار دهیم.[۱][۲][۳] چنین مجموعه‌هایی در حال حاضر به عنوان غیرقابل شمارش شناخته می‌شوند.
مجموعه غیرقابل شمارش
او در سال ۱۸۹۱ مقاله کانتور در نظر گرفت مجموعه 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.
[نهفتن]
نبو
نظریه مجموعه‌ها
بن‌مایه ها
اصل موضوع انتخاب
countable dependent اصل موضوع گسترش Infinity اصل موضوع زوج‌سازی اصل موضوع مجموعه توانی Regularity اصل موضوع اجتماع Martin's axiom
Axiom schema
replacement اصل موضوع تصریح
Venn diagram of set intersection
مجموعه (ریاضی)
ضرب دکارتی اصل متمم (ترکیبیات) قوانین دومورگان اشتراک (مجموعه) مجموعه توانی اصل متمم (ترکیبیات) تفاضل متقارن اجتماع (مجموعه)
ConceptsMethods
کاردینالیتی عدد اصلی (large) رده Constructible universe فرضیه پیوستار استدلال قطری کانتور عنصر (ریاضیات)
زوج مرتب tuple Family Forcing تابع دوسویی عدد ترتیبی استقرای ترامتناهی نمودار ون
انواع مجموعه‌ها
مجموعه شمارا مجموعه تهی مجموعه متناهی (hereditarily) مجموعه‌های فازی مجموعه نامتناهی مجموعه بازگشتی زیرمجموعه مجموعه متعدی (نظریه مجموعه‌ها) Uncountable Universal
نظریه‌ها
Alternative نظریه مجموعه‌ها نظریه طبیعی مجموعه‌ها قضیه کانتور
Zermelo
General مبادی ریاضیات
New Foundations Zermelo–Fraenkel
von Neumann–Bernays–Gödel
Morse–Kelley Kripke–Platek Tarski–Grothendieck
ParadoxesProblems
پارادوکس راسل Suslin's problem
Set theorists
آبراهام فرنکل برتراند راسل ارنست تسرملو گئورگ کانتور جان فون نویمان کورت گودل لطفی زاده پل برنایز پل کوهن (ریاضیدان) ریچارد ددکیند Thomas Jech ویلارد کواین
رده‌ها:
اعداد کاردینالبرهان‌هابرهان‌های ریاضیاتبی‌نهایتگئورگ کانتورنظریه مجموعه‌ها