27. Неперечислимость второго числового класса

Ординальные числа, согласно нашему определению, — это некоторые рекурсивно перечислимые множества в двухбуквенном алфавите Мы знаем, что существует рекурсивная нумерация всех рекурсивно перечислимых множеств слов в данном алфавите. Следовательно, конструктивные ординалы второго числового класса счетны в теоретико-множественном смысле слова. Тем не менее они не являются эффективно перечислимыми. Борель [2] и Брауэр [2] понимали это, а Тьюринг [2] доказал для ординалов Чёрча — Клини.

Если дана последовательность ординалов то мы можем найти ординал а, такой, что а для всех

Построим ординал Тогда следовательйо, для всех что и требовалось доказать.

Заметим, что это доказательство использует рассуждение, которое привело Кантора к выводу о том, что второй числовой класс имеет мощность, которая больше и в действительности равна второму по величине трансфинитному ординальному числу Именно введение понятия эффективной перечислимости вместо теоретико-множественного понятия счетности позволяет нам вывести из рассуждения Кантора совсем иные следствия.