Прием "диагональной пробежки" по элементам бесконечного множ-ва с легкой руки Г.Кантора проник во все области математических доказательств. В качестве ещё одной иллюстрации приведу пример построения функции, не вычислимой на машине Поста.
Как известно, множ-во программ машины Поста(далее - МП) не более чем счетно ( док-во опускаем).
Т.е. существует последовательность P0, P1, P2, ... программ МП, содержащая все возможные программы МП.
Приступаем к построению функции f из множ-ва N в N, не вычислимой на МП:
f(n) = 0, если примен-е программы Pn к числу 'n' не приводит к результативной остановке или рез-т не есть запись натурального числа;
f(n) = k+1, если применение программы Pn к числу 'n' дает рез-т, являющийся записью числа k.
Докажем, что так построенная всюду определенная функция не вычислима на МП.
В самом деле, пусть P - любая программа МП.
Программа P встречается среди программ P0, P1, P2, ... , т.е. P=Ps при некотором s.
Что получается при применении программ Ps и функции f к числу s?
1-ый случай. Примен-е программы Ps к записи числа s приводит к результативной остановке, и рез-т есть запись натур-го числа k. Тогда f(s)=k+1 и, так как k =/= k+1 , программа Ps не вычисляет f .
2-ой случай. Примен-е программы Ps к записи числа s не приводит к результативной остановке или рез-т не есть запись никакого натур-го числа . Тогда Ps не вычисляет f уже потому, что функция f всюду определена.
Итак, в обоих случаях выясняется, что программа P(=Ps) не вычисляет функции f.
Что и треб. док-ть.
Легко увидеть прямую аналогию с процедурами "выписывания" числа, не входящего в счетный список, и построения функции, не снабженной индексом t.
______________________________________
А теперь продолжим наше частное расследование некоторых "странных" аспектов "наивной" теории множеств.
На стр. 1 этого топика было рассмотрено одно из популярных доказательств теоремы о том, что множество действительных чисел R несчетно, то бишь, неравномощно множеству натуральных чисел N.
Расследование выявило в этом док-ве логические бреши и показало, что на самом деле оно не достаточно убедительно(?).
Но может быть дело прояснит более общая теорема, в которой утверждается, что множ-во всех частей данного множества имеет мощность большую, чем мощность данного множ-ва?
Другая трактовка этой теоремы - множества с наибольшей мощностью не существует, подобно тому как не существует наибольшего натурального числа.
Когда множ-ва конечны, этот результат интуитивно понятен: образование подмножеств связано с «созданием» новых объектов «внутри множества», которых нет среди элементов исходного множ-ва поскольку область прообразов ограничена т.наз. «последним элементом».
Но когда набор элементов множества неограничен, то вывод теоремы не столь очевиден.
Самое общее доказательство, не связанное с конкретными «обозначениями» элементов множеств, проводится «методом от противного».
Допустим, что исходное множество и множ-во всех его подмнож-в равномощны.
Тогда все элементы множества с точки зрения их участия в процедуре
установления 1-1 соответствия разбиваются на два класса (прообразов):
1кл - элем-ты, входящие в соответствующее им п/множ-во(образ);
2кл - элем-ты, не входящие в соответствующее им п/множ-во.
Множество всех элем-тов 2 кл., т.е. тех прообразов, которые не входят в соответствующее им подмножество(образ), тоже образуют некоторое подмножество, построение которого некоторым образом уже завершено и оно существует "фиксированно и определенно во всех своих частях".
Это п/множ-во тоже должно иметь свой элемент-прообраз. Но неожиданно выясняется, что такой элемент не может принадлежать ни 1-му классу, ни 2-му, хотя все элементы данного множ-ва должны обязательно принадлежать одному из классов.
Этот рез-т противоречит исходному предположению о существовании 1-1 соответствия между элементами множ-ва и элементами множества всех его подмножеств.
Заметим, что в случае бесконечных множеств мы рассматриваем все бесконечные подмножества данного бесконечного множества как актуально бесконечные множества.
Следует также отметить одну особенность. При сравнении мощностей двух разных множеств между собой, нахождение образов и прообразов являются независимыми операциями. Но в нашем случае при установления 1-1 соответствия область элементов- прообразов постоянно "убывает", а область образов "растёт" - элемент, побывавший один раз в роли прообраза, уже не может им быть снова, но зато никаких ограничений на вхождение этого же элемента в подмножества (=образы) нет. При этом оба множ-ва имеют бесконечный запас элементов, т.е. в них нет "последнего элемента", на котором может остановиться "пересчёт"!
В чем же тут разгадка? ...
Заметим, что здесь мы также воспользовались диагональным методом Кантора: сначала мы предположили, что ВСЕ элементы множества всех подмножеств исходного множ-ва уже построены, а затем начали эти элементы просматривать по "диагонали" с точки зрения 1-1 соответствия и углядели в них "более мелкие части". Из этих частей мы и построили новое подмножество, т.е. новый элемент-образ, которому не нашлось соответствующего элемента-прообраза в исходном множ-ве.
Тут сразу возникает мысль о том, что завершенность актуальной бесконечности не следует понимать "традиционно", т.е. как возможность обозревать все элементы бесконечного множ-ва сразу. Мы видим лишь границы области, в пределах которой находятся элементы нашего бесконечного множ-ва, а оно в принципе не может иметь "последний элемент". Какие элементы мы можем различить, зависит от "точки зрения" на актуально бесконечное множество. Такой подход очень похож на концепцию альтернативной теории множеств (AST) П. Вопенки. Она позволяет разработать иное представление континуума. Континуум в AST появляется как "след", который некоторый класс объектов оставил за собой на "горизонте видимости-различимости".
Выделение красным цветом убрал -
Jnrty.
, а дальше строить аналогичное дерево с вершиной в 
.