У теорії множин, діагональний метод Кантора або діагональний аргумент Кантора, також відомий як метод діагоналізації - опубліковане 1891 року Георгом Кантором математичне доведення того, що існують нескінченні множини, для котрих не існує взаємно однозначної відповідності з нескінченною множиною натуральних чисел. Англійський переклад: Такі множини тепер називають незліченними множинами, і розміри незліченних множин вивчає започаткована Кантором теорія кардинальних чисел.

1874 року Кантор  незліченність дійсних чисел іншим методом. Однак діагональний метод є потужним і універсальним способом, що був відтоді використаний у широкому діапазоні доведень, як от у першій теоремі Геделя про неповноту і тезі Черча — Тюрінга. Аргументи діагоналізації також часто є джерелом суперечностей, таких як парадокс Рассела і парадокс Рішара.

Незліченна множина У статті 1891 року Кантор розглянув множину T усіх нескінченних послідовностей двійкових чисел (тобто чисел, кожна цифра яких є нулем або одиницею). Він почав із конструктивного доведення такої теореми:

Якщо s1, s2, … , sn, … - довільний перелік елементів із T, то завжди існує елемент s із T якому не відповідає жоден елемент sn у переліку.

Доведення починається із перелічення усіх елементів із T, наприклад:

|s1 = |(0, |0, |0, |0, |0, |0, |0, |...) |- |s2 = |(1, |1, |1, |1, |1, |1, |1, |...) |- |s3 = |(0, |1, |0, |1, |0, |1, |0, |...) |- |s4 = |(1, |0, |1, |0, |1, |0, |1, |...) |- |s5 = |(1, |1, |0, |1, |0, |1, |1, |...) |- |s6 = |(0, |0, |1, |1, |0, |1, |1, |...) |- |s7 = |(1, |0, |0, |0, |1, |0, |0, |...) |- |...

Далі, послідовність s будують, вибираючи цифру оберненою до цифри s1 (замінюючи 0 на 1 і навпаки), цифру оберненою до цифри s2, цифру оберненою до цифри s3, і загалом для кожного n,  цифра s є оберненою до  цифри sn. Для прикладу вище отримаємо:

|s1 |= |(0, |0, |0, |0, |0, |0, |0, |...) |- |s2 |= |(1, |1, |1, |1, |1, |1, |1, |...) |- |s3 |= |(0, |1, |0, |1, |0, |1, |0, |...) |- |s4 |= |(1, |0, |1, |0, |1, |0, |1, |...) |- |s5 |= |(1, |1, |0, |1, |0, |1, |1, |...) |- |s6 |= |(0, |0, |1, |1, |0, |1, |1, |...) |- |s7 |= |(1, |0, |0, |0, |1, |0, |0, |...) |- |...

|s |= |(1, |0, |1, |1, |1, |0, |1, |...)

За побудовою, s відрізняється від кожного sn, оскільки їхні n-ті цифри відрізняються (виділені у прикладі). Тому s не може бути в переліку.

На основі цієї теореми, використовуючи доведення від супротивного Кантор показує, що:

Множина T є незліченною.

Доведення починається із припущення, що T зліченна. Тоді всі її елементи можна записати як перелік s1, s2, … , sn, … . Використання попередньої теореми до цього переліку дає елемент s, який не належить до переліку. Але, це суперечить тому, що s є елементом T і тому належить до переліку. Із суперечності випливає, що первісне припущення хибне. Отже, T незліченна.

Дійсні числа Незліченність дійсних чисел вже була встановлена , але вона також випливає із попереднього результату. Для доведення цього будується ін'єкція 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. Розглянемо таку множину:

T = { s ∈ S: s ∉ f(s) }.

Для кожного 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 приводить до  узагальненої континуум-гіпотези.

Примітки

Зовнішні посилання

Cantor's Diagonal Proof на MathPages