22. Частично рекурсивные функционалы

Будет удобно включить множество натуральных чисел в список рассматриваемых нами пространств. Мы сделаем это, определив окрестности I просто как натуральные числа

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

Частично рекурсивный функционал, отображающий пространство X в пространство У, — это рекурсивно перечислимое отношение между окрестностями в X и окрестностями в У, удовлетворяющее следующим двум условиям.

1 Для любой окрестности есть аппроксимация в

2 Для любой окрестности есть открытое множество в

Частично рекурсивные функционалы, отображающие бэровское пространство в себя, рассматриваются Клини [3].

Эквивалентным образом мы могли бы сначала ввести окрестности в пространстве как синтаксические выражения вида

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

Существует рекурсивная нумерация частично рекурсивных функционалов.

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

Если а — аппроксимация, то -также аппроксимация.

Принадлежность означает, что для некоторой окрестности I из а. Если тоньше то так что также принадлежит

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

Рассмотрим частично рекурсивный функционал, отображающий пространство X в пространство У, и пусть две окрестности в У, причем тоньше Образуем объединение всех окрестностей I, таких, что или для некоторой отделенной от Взяв пересечение всех открытых множеств, полученных таким способом при варьировании мы имеем внутреннее предельное множество, которое будем называть областью (определения) функционала Если окрестности в У диаметризованы, то область можно определить более обозримым способом как где объединение всех окрестностей таких, что для некоторого Область дискретнозначного функционала — открытое множество.

Если конструктивная точка а принадлежит области частично рекурсивного функционала то конструктивная точка.

Доказательство очевидно.

Точно так же, как и в классическом анализе, теорема о равномерной непрерывности — простое следствие леммы Гейне — Бореля.

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

Доказательство для отображений канторовского пространства в себя. Всюду определенность на компактном множестве означает, разумеется, что для всех где область Пусть произвольное натуральное число. Лемма Гейне — Бореля позволяет нам найти окрестности

Такие, что

и

Пусть определено соотношением

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

Последовательность частично рекурсивных функционалов

сходится к частично рекурсивному функционалу если для любой пары окрестностей таких, что мы можем найти настолько большое что для всех Если рассматривать частично рекурсивные функционалы, отображающие пространство X в пространство У, как аппроксимации в пространстве то это определение сходимости — просто частный случай определения сходимости аппроксимаций, данного в

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

Это немедленно следует из определения сходимости и теоремы о равномерной непрерывности.