استدلال قطری کانتور

در نظریه مجموعه ها، استدلال قطری کانتور در سال ۱۸۹۱ توسط گئورگ کانتور به عنوان یک اثبات ریاضی ارائه گردید و نشان داد مجموعه های نامتناهی وجود دارند که اعضای آن ها در تناظر یک به یک با مجموعه اعداد طبیعی نیستند. [ ۱] [ ۲] [ ۳] چنین مجموعه هایی را «مجموعه ناشمارا» می نامند.
کانتور، در مقاله ی خود در سال ۱۸۹۱، مجموعه T را مطالعه کرد که شامل همه دنباله های رقم های دودویی ( یعنی هر رقم صفر یا یک ) باشد. او با اثباتی ساختی از قضیه زیر شروع می کند:
برای اثبات این، مجموعه هایی از T را به شکل زیر انتخاب می نماییم:
او ساختار توالی s را با انتخاب مکمل اولین رقم در s1 انتخاب نمود ( جایگزینی صفر به جای یک و برعکس ) ، برای انتخاب دومین رقم S به سراغ رقم دوم در s2 رفت و مکمل آن را انتخاب نمود و به همین ترتیب ادامه داد. در مثال فوق به نتایج زیر می رسیم:
با ساخت s به روش فوق به مجموعه ای می رسیم که با تمامی مجموعه های بالا متفاوت است زیرا عنصر n ام آن با عنصر n ام تمام مجموعه های بالا تفاوت دارد.
بر اساس این قضیه کانتور با استفاده از یک اثبات با تناقض نشان می دهد که:
او برای اثبات تناقض در ابتدا فرض می کند T شمارا است. پس همه عناصر آن به شکل s1, s2, . . . sn قابل نمایش هستند. با اعمال قضیه قبلی به این شمارش ها به توالی s می رسیم که در شمارش ها موجود نیست. اما s عنصری از T بود و بنابراین باید در شمارش ها باشد. این تضاد فرض اصلی را زیر سؤال می برد بنابراین T غیرقابل شمارش است.