Диагонализация

Р - множество натуральных чисел.

Назовем Р^* - множество всех множеств натуральных чисел. Множество Р^* - несчетно.

Доказательство:

Предположим, что нам удалось перенумеровать все множества натуральных чисел.

Сопоставим каждому i-тому множеству характеристическую последовательность s_i(1),s_i(2),...,s_i(j),..., j-ый элемент которой равен 1 если j принадлежит множеству номер i и 0, если не принадлежит. Рассмотрим новое множество М, характеристическая последовательность которой 1-s₁(1), 1-s₂(2),..., 1-s_k(k),... - антидиагональное множество. Множество М представляет собой множество натуральных чисел, следовательно (по предположению) оно имеет свой номер в нумерации всех множеств натуральных чисел. Пусть этот номер k. Рассмотрим k-ый элемент характеристической последовательности этого множества. По определению множества М s_k(k)=1-s_k(k), откуда 0=1 - противоречие.

Следовательно, наше предположение неверно.

Этот метод называется «метод диагонализации».

С помощью диагонализации можно доказать, что к любому счетному множеству множеств натуральных чисел может быть добавлено новое (отличное от всех, содержащихся в нем) множество.

Утверждение: Множество всех функций с натуральными значениями, определенных всюду или частично на множестве натуральных чисел, несчетно.

Доказательство: Пусть вычислимая последовательность f₁,f₂,... - нумерует все такие функции. Определим «антидиагональную» функцию u так: u(n)=1, если f_n(n) не определено, u(n)=f_n(n)+1 в противном случае. Функция u всюду определена на множестве натуральных чисел и принимает натуральные значения. Следовательно u находится в вычислимой последовательности. Пусть ее номер m. Тогда имеем: f_m(m)=1, если f_m(m) не определено, или f_m(m)= f_m(m)+1 в противном случае. Так или иначе - противоречие.

Дата добавления: 2013-12-13