Діагональний метод КантораУ теорії множин, Діагональний метод Кантора або діагональний аргумент Кантора, також відомий як метод діагоналізації, був опублікований у 1891 році Георгом Кантором як математичний доказ того, що існують нескінченні множини для котрих не існує взаємно однозначної відповідності з нескінченною множиною натуральних чисел[1][2][3]. Такі множини тепер називають незліченними множинами, і розміри незліченних множин вивчає теорія кардинальних чисел, започаткована Кантором. Кантор вперше довів[en] незліченність дійсних чисел у 1874 році іншим методом, відмінним від діагонального[4][5]. Однак діагональний метод є потужним і універсальним способом, що був відтоді використаний у широкому діапазоні доведень[6], включаючи першу теорему Геделя про неповноту і тезу Черча — Тюрінга. Аргументи діагоналізації також часто є джерелом суперечностей, таких як парадокс Рассела[7][8] і парадокс Рішара[en][9]. Незліченна множинаУ статті 1891 року Кантор розглянув множину T усіх нескінченних послідовностей двійкових чисел (тобто кожна цифра числа є нулем або одиницею). Він почав із конструктивного доведення такої теореми:
Доведення починається із перелічення усіх елементів із T, наприклад:
Далі, послідовність s будується вибираючи 1-шу цифру оберненою до 1-ї цифри s1 (замінюючи 0 на 1 і навпаки), 2-гу цифру оберненою до 2-ї цифри s2, 3-тю цифру оберненою до 3-ї цифри s3, і загалом для кожного n, n-та цифра s є оберненою до n-тої цифри sn. Для прикладу вище отримаємо:
За побудовою, s відрізняється від кожного sn, оскільки їхні n-ті цифри відрізняються (підсвічені у прикладі). Тому s не може бути у переліку. На основі цієї теореми, використовуючи доведення від супротивного Кантор показує, що:
Доведення починається із припущення, що T зліченна. Тоді всі її елементи можуть бути записані як перелік s1, s2, … , sn, … . Використання попередньої теореми до цього переліку дає елемент s, який не належить до переліку. Але, це суперечить тому, що s є елементом T і тому належить до переліку. Із суперечності випливає, що первісне припущення хибне. Отже, T незліченна. Дійсні числаНезліченність дійсних чисел вже була встановлена першим доведенням незліченності Кантора[en], але вона також випливає із попереднього результату. Для доведення цього будується ін'єкція f з множини T нескінченних двійкових рядків у множину R дійних чисел. Оскільки T є незліченною, то образ цієї функції f, який є підмножиною R, теж незліченний. Отже, множина R теж є незліченною. Також Кантор запропонував спосіб побудови бієкції між T і R. Отже, T і R мають однакову потужність, яка називається "потужністю континууму" і зазвичай позначається . Ін'єкція з T у R визначається відображенням рядків із T у десяткові числа, наприклад t = 0111… у число 0.0111…. ця функція визначена як f(t) = 0.t, є ін'єкцією, оскільки відображає різні рядки у різні числа. Узагальнення для множинКантор використав узагальнену форму діагонального аргументу щоби довести Теорему Кантора: для кожної множини S, булеан S — тобто, множина всіх підмножин S (позначена як P(S))—має більшу потужність ніж сама S. Доведення відбувається так: Нехай f буде будь-якою функцією із S у P(S). досить довести, що f не може бути сюр'єкцією. Це значить що деякий елемент T із P(S), тобто деяка підмножина S, не лежить в образі f. Розглянемо таку множину:
Для кожного s із S, або s належить T або ні. Якщо s належить T, то за визначенням T, s не належить f(s), тобто T не дорівнює f(s). З іншої сторони, якщо s не належить T, то за визначенням T, s належить f(s), тобто знову T не дорівнює f(s). НаслідкиІз цього випливає що поняття множини всіх множин є суперечливим. Якби S була множиною всіх множин, то P(S) була б одночасно більшою за S і підмножиною S. Парадокс Рассела показав, що наївна теорія множин, що базується на аксіомній схемі необмеженого розуміння, є суперечливою. Діагональний метод показує, що множина дійсних чисел більша за множину натуральних (і разом цілих та раціональних). Отже, можна запитати чи існує множина потужність якої посередині між потужністю цілих і дійсних чисел. Це питання приводить до континуум-гіпотези. Аналогічно, питання чи існує множина з потужністю між |S| і |P(S)| для деякої нескінченної S приводить до узагальненої континуум-гіпотези. Примітки
Зовнішні посилання
|