23. Максимальные рекурсивные функционалы

Как уже отмечено, частично рекуреивные функционалы, отображающие пространство X в пространство У, можно рассматривать как аппроксимации в пространстве Среди них мы выделим теперь максимальные.

Говорят, что частично рекурсивный функционал есть максимальный рекурсивный функционал, если для любых пар окрестностей в У, таких, что тоньше тоньше либо имеет место либо для некоторой I, более тонкой, чем и I, отделенной от

Если частично рекурсивный функционал всюду определен на евклидовом или канторовом пространстве, то он максимален.

Это утверждение — следствие локальной компактности и не имеет места для бэровского пространства.

Доказательство для функционалов, отображающих канторовское пространство в себя. Пусть всюду определен, и пусть произвольные окрестности. По теореме о равномерной непрерывности мы имеем

Так как то либо тоньше либо отделена от Если тоньше для всех то . В противном случае для некоторого такого, что тоньше отделена от Это показывает, что максимален.

Вещественные рекурсивные функционалы, которые всюду определены, совпадают с рекурсивными вещественными функциями Шпеккера [1] (если заменить там примитивно рекурсивные функции общерекурсивными), Гжегорчика [1] и Лакомба [1].

Область максимального рекурсивного функционала плотна.

Рассмотрим максимальный рекурсивный функционал отображающий Допустим, что окрестности в У, такие, что тоньше и выберем окрестность Взяв тоньше I, мы имеем или или для некоторой более тонкой, чем отделенной от Это показывает, что открытые множества, пересечение которых составляет область все плотны. Следовательно, область плотна.

Применяя теорему Бэра, мы видим, что в любой окрестности I пространства X имеется конструктивная точка а, такая, что конструктивная точка.

Чтобы продемонстрировать полезность понятия максимального рекурсивного функционала, мы докажем конструктивный вариант теоремы Рисса о представлении. Максимальный вещественный рекурсивный функционал называется неубывающей функцией, если из соотношений вместе с следует

Под полигоном (рис. 1) мы будем понимать кусочно линейную функцию, исчезающую вне конечного интервала, вершины которой имеют рациональные координаты. Точнее, полигон — это синтаксическое выражение вида где — рациональные числа.

Рис. 1.

Интеграл полигона относительно неубывающей функции

определяется обычным образом как предел сумм Стильтьеса

Единственное нововведение состоит в том, что мы должны позаботиться о выборе точек разбиения из области Это всегда возможно, так как область плотна согласно вышеприведенной теореме. Интеграл очевидно, имеет свойства

Обратно, мы покажем, что если рекурсивная функция, сопоставляющая каждому полигону

некоторое вычислимое действительное число таким образом, что эти условия выполнены, то мы можем найти неубывающую функцию такую, что

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

Для данной определим как объединение всех окрестностей таких, что для какого-либо полигона имеющего вид, изображенный на рис. 2.

Рис. 2.

Тогда плотное открытое множество для любого так что теорема позволяет нам найти точку Неопределим рекурсивно перечислимое отношение между рациональными интервалами требованием, чтобы тогда и только тогда, когда

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

Определенный таким образом очевидно, является частично рекурсивным функционалом. Основная трудность — доказать его максимальность.

Пусть тоньше тоньше Нам нужно доказать, что либо

либот для некоторой более тонкой, чем отделенной от

Рис. 3.

С этой целью выберем как показано на рис. 4.

Рис. 4.

Вычисляя с достаточной точностью, мы можем доказать

и

Если имеют место то согласно определению Если то мы можем найти тоньше такую, что при откуда следует, что отделена от Аналогично, если Следовательно, максимален. Неубывание прямое следствие Предположения, что если

Проверка соотношения

а также того обстоятельства, что однозначно определяется нормализующим условием стандартна и завершает доказательство.

Область совпадает с внутренним предельным множеством, которое определено в начале доказательства, и интуитивно может быть представлена как множество точек, не несущих массы.

Пусть

и

— интегралы. Применяя теорему о категории, найдем конструктивную точку принадлежащую областям для всех а также области Нормализуем весовые функции, полагая для всех Тогда

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