23.160. Диагональная аргументация
Несчетность 
опять была показана поразительно простым способом Кантором (1891). Его аргументация почти непосредственно применяется к множеству 
всех подмножеств 
но есть варианты, которые работают подобным же образом на множестве 
целых функций и на 
(которое можно идентифицировать с множеством целых функций различными способами). Для того чтобы показать, что существует несчетное число подмножеств 
показывают, что любая счетная совокупность 
множеств 
неполная, построив новое множество 
отличное от каждого 
это так называемое диагональное множество 
которое очевидным образом отлично от 
относительно числа 
Что и требовалось доказать!
«Диагональную» природу 
можно увидеть, представив таблицу 0-й и 
в которой
Другими словами, 
строка состоит из значений характеристической функции 
Характеристическая функция 
это просто диагональ таблицы, со всеми обращенными значениями. Последовательность 
действительных чисел можно привести к диагональному виду, образовав таблицу, 
строка которой состоит из десятичных цифр 
Подходящий способ «обратить» цифры на диагонали — изменить любую 1 на 2 и любую другую цифру на 1. (Результирующая последовательность 
после десятичной точки, определяет тогда действительное число х, разложение на десятичные дроби которого однозначно. Следовательно, х не только отлично от каждого 
в разложении на десятичные дроби, но определенно другое число.)
В более общем смысле, для любой таблицы строк целых чисел, то есть, любой последовательности целых функций 
можно построить целую функцию 
неравную каждой 
изменяя значения вдоль диагонали таблицы. Диагональная аргументация, фактически, была первой, данной в этом контексте дю Буа-Реймондом (1875), для того чтобы
построить 
с бблыней скоростью роста, чем все функции в последовательности 
Ретроспективно, можно даже увидеть диагональное построение в первой аргументации Кантора (1874) для несчетности R (упражнение 23.5.2).
Диагональная аргументация важна в теории множеств, потому что она без труда обобщает доказательство того, что любое множество имеет больше подмножеств, чем элементов (упражнение 23.5.3), и, следовательно, что наибольшего множества не существует. Сначала не было замечено как раз то, что диагональная аргументация также имеет следствия на более конкретном уровне. Это происходит потому, что диагональ таблицы вычислима, если таблица в целом вычислима. Следовательно, аргументация не просто показывает, как прибавлять новую функцию 
к списку 
она показывает, как прибавить новую вычислимую функцию к вычислимому списку. Другими словами, невозможно вычислить список всех вычислимых функций. И, конечно, то же самое относится к спискам вычислимых действительных чисел. Этот замечательный результат прошел незамеченным в первое время существования диагональной аргументации, потому что вычислимость не считали тогда интересным понятием, или, в самом деле, математическим понятием вообще. Споры об аксиоме о выборе, однако, помогли обострить осознание разницы между конструктивными и неконструктивными функциями. В 1920-х гг. логики начали исследовать понятие вычислимости серьезнее, и «почти что чудом», как позже выразил это Гёдель (1946), вычислимость оказалась математически точным понятием.
Упражнения
(см. скан)
