Диагонален метод на Кантор
В съответствие с теоремата на Кантор от раздел 4.1, множеството от всички подмножества на естествената серия има мощност, по-голяма от ℵ0, и следователно не е изброимо. Ние възпроизвеждаме доказателството (с незначителни модификации) за този случай, за да подчертаем важната идея за диагонализация, която е в основата на доказателството.
Свържете с всеки набор A⊂N неговата характерна последователност от нули и единици
така че αi=1, ако i∈A и αi=0, ако i∉A. Всяка последователност от нули и единици е характеристика на множество, чиито елементи са номерата на местата, съдържащи единици. По този начин се установява съответствие едно към едно между последователности от нули и единици и подмножества от набораN. Нека A0, A1, A2, … е произволен списък от подмножества на множествотоN. Нека покажем, че вN има подмножество, което не е включено в този списък. Разгледайте списъка от множества A0, A1, A2, ... заедно с техните характерни последователности:
Съставяме "антидиагонална" последователност
Тази последователност се различава поне по първия елемент от първата последователност на списъка, по втория елемент от втория, по третия елемент от третия и т.н. Следователно "антидиагоналната" последователност, а с нея и съответстващото й множество, не се съдържат в списъка. Горното разсъждение показва, че е невъзможно да се направи списък, който включва всички подмножества на множествотоN и, следователно, множеството от всички подмножества на множествотоN не е изброимо.
Използвайки диагоналния метод, показваме, че множеството от реални числа в интервала [0;1] не е изброимо.
Доказателство. Всяко реално число a от интервала [0;1] може да бъде записано като безкрайна десетична дроб
За числа, представени чрез крайни десетични дроби, такова означение е двусмислено. Например, записите 0,1000… и 0,0999… представляват едно и също число. Нека се съгласим да не използваме записи от втория тип, в които, започвайки от определено място, има само деветки. Тогава представянето на числата чрез десетични дроби ще бъде еднозначно. Нека a0, a1, a2, … е произволен списък от реални числа от интервала [0;1]. Нека покажем, че на сегмента [0;1] има число, което не е включено в този списък. Помислете за списък с числа a0, a1, a2, ... заедно с техните десетични представяния:
лежи на интервала [0;1] и се различава най-малко с първата цифра след десетичната запетая от първото число от списъка, с втората цифра от второто число, с третата цифра от третото и т.н. Следователно числото β не е в списъка. По този начин е невъзможно да се направи списък, който включва всички числа в сегмента [0;1] и следователно наборът от всички реални числа в сегмента [0;1] е неизброим.􀀀
Мощността на набора от числа в интервала [0;1] се нарича континуум; множествата с еднаква мощност се наричат непрекъснати. Континуум са: множеството от всички реални числа, множеството от точки на правата, множеството от точки на равнината, множеството от поредици от реални числа и много други множества, срещани в математическата практика.
Проблемът за съществуването на безброй множества, по-малки по размер от континуума (така наречената хипотеза за континуума) възниква в торите на множествата почти от момента, в който се появи тази теория. Гьодел доказва, че предположението за отрицателно решение на хипотезата за континуума не противоречи на аксиоматиката на теорията на множествата. По-късно Коен установява, че тази аксиоматика не противоречи на предположението за положително решение на хипотезата за континуума. Наличието на проблем в теорията на множествата,която, изглежда, би трябвало да има решение „да“ или „не“, но няма такова, стимулира до голяма степен формализацията на математиката, за която стана дума в предишната лекция.