Діагональний метод Кантора

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

Ілюстрація діагонального аргументу  Кантора існування незліченних множин. Послідовність s не може входити у наведений перелік послідовностей.

Бієкція f(x) = 2x із натуральних у парні числа показує, що нескінченна множина може мати однакову потужність із точною підмножиною себе самої. Однак, діагональний метод Кантора показує, що  існують нескінченні множини різних потужностей.

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

Незліченна множина

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

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

Доведення починається із перелічення усіх елементів із 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 будують, вибираючи 1-шу цифру оберненою до 1-ї цифри s₁ (замінюючи 0 на 1 і навпаки), 2-гу цифру оберненою до 2-ї цифри s₂, 3-тю цифру оберненою до 3-ї цифри s₃, і загалом для кожного n, n-та цифра s є оберненою до n-тої цифри s_n. Для прикладу вище отримаємо:

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 відрізняється від кожного s_n, оскільки їхні n-ті цифри відрізняються (виділені у прикладі). Тому s не може бути в переліку.

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

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

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

Дійсні числа

Незліченність дійсних чисел вже була встановлена першим доведенням незліченності Кантора^[en], але вона також випливає із попереднього результату. Для доведення цього будується ін'єкція f з множини T нескінченних двійкових рядків у множину R дійних чисел. Оскільки T є незліченною, то образ цієї функції f, який є підмножиною R, теж незліченний. Отже, множина R теж є незліченною. Також Кантор запропонував спосіб побудови бієкції між T і R. Отже, T і R мають однакову потужність, яка називається "потужністю континууму" і зазвичай позначається ${\displaystyle {\mathfrak {c}}}$${\displaystyle 2^{\aleph _{0}}}$.

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