Математическая энциклопедия - конструктивное метрическое пространство

концепция метрич. пространства, используемая в конструктивной математике. Близкий смысл имеет также понятие рекурсивного метрического пространства.

Список где некоторое множество конструктивных объектов (обычно слов в том или ином алфавите), р алгоритм, переводящий любую пару элементов в конструктивное действительное число (к. д. ч., см. Конструктивный анализ), наз. К. м. п., если при любых выполняется: 1) r( Х, Х)=0,

2) r( Х, У)r(X, Z)+r(Y, Z )(здесь и ниже термин "алгоритм" употребляется в смысле одного из точных понятий алгоритма). Множество и алгоритм р наз. носителем и метрическим алгоритмом соответствующего К. м. п., а элементы точками этого К. м. п. Из аксиом 1), 2) следует, что всегда

и r( Х, Y)=r(Y, X). Две точки называются эквивалентными (различными) в К. м. п. если r( Х, У)=0 (соответственно r(X, Y) неравно 0).

Примеры К. м. п.: а) пространство натуральных чисел Н. Носителем Нявляется множество натуральных чисел (натуральные числа трактуются как слова вида О, 01, 011, ...), а метрич. алгоритм р таков, что р( т, п)=|m- п|. Аналогично определяются пространства Rи Е храциональных и конструктивных действительных чисел, соответственно; б) "-мерное евклидово пространство ЕД. Носителем Е п является множество слов вида x1* ... *х п, где х;,. есть к. д. ч., а метрич. алгоритм строится так, что в) пространство Сравномерно непрерывных на единичном сегменте конструктивных функций. Носителем Сявляется множество слов вида где fвсюду определенная на единичном сегменте конструктивная функция, а g алгоритм, переводящий всякое натуральное число в натуральное число, причем

( означает запись (код) алгоритма U). Метрнч. алгоритм р строится так, что

Сложный вид носителя пространства Собусловлен требованием эффективной вычислимости метрики; г) бэровское пространство Вобщерекурсивных функций. Носителем Вявляется множество гёделевых номеров общерекурсивных функций, а метрич. алгоритм р строится так, что если j п и jm общерекурсивные функции с номерами n и т, то р(га, т)= 0, если jn(i) = jm(i) при любом i, и r( п, m)=2^-k, если jn(i) = jm(i) при i<k и

Пусть К. м. п. Алгоритм Р наз. последовательностью точек М, если при всяком пимеем Последовательность Р наз. регулярной, если при имеем r(b(т), b(n))<2^-n. Регулярная последовательность b сходится к точке XК. м. п. М, если при любом пимеем р( Х, К. м. п. Мназ. полным, если существует алгоритм, находящий для каждой регулярной последовательности р (точек М)точку М, к к-рой сходится р. К. м. п. Мназ. сепарабельным, если существуют алгоритмы а, d такие, что а последовательность точек М, и при любом и любом пимеем: d( Х*п). есть натуральное число, причем r(a(d( Х*п)), Х)<2^-n. Все пространства Н, R, Е 1, Е п, С, В примеров а) г) сепарабельны, пространства Н, Е 1, Е п, С, кроме того, полны. Пример несепарабельного К. м. п. дает рассмотрение подпространства Н, индуцированного не рекурсивно перечислимым множеством. В терминах К. м. п. могут быть изложены многие результаты классич. теории метрич. пространств; в частности, большое значение имеет конструктивный вариант теоремы Хаусдорфа, утверждающий, что для каждого К. м. п. может быть построено его пополнение.