/
Tags: анализ
Text
NOTES ON
CONSTRUCTIVE MATHEMATICS
PER MARTIN-LOF
Almqvlst & Wiksell
Stockholm
1970
БИБЛИОТЕКА СБОРНИКА «МАТЕМАТИКА»
П. Мартин-Лёф
ОЧЕРКИ
ПО КОНСТРУКТИВНОЙ
МАТЕМАТИКЕ
Перевод с английского
Г. Е. Минца
Под редакцией
А. Г. Драгалина
ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1975
УДК 517.11; 510.50
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Эта книга представляет собой введение в кон-
конструктивную математику и рассчитана на математи-
математиков, желающих уточнить свои интуитивные представ-
представления о конструктивности; она позволяет без особых
технических усилий ознакомиться с точными резуль-
результатами в этой области. В книге излагается найден-
найденный автором конструктивный вариант некоторых пер-
первоначальных идей Брауэра из области конструктиви-
зации математического анализа.
Книга доступна математикам всех специально-
специальностей, начиная со студентов младших курсов. Она
представляет интерес также для всех лиц, интересую-
интересующихся основаниями математики.
Редакция литературы по математическим наукам
20203*016
М —. j _— 16-75 © Перевод на русский язык, «Мир», 1975
Последние десятилетия характеризуются бурным
развитием конструктивных подходов в математике.
Вычислительная тенденция в современной математике
вызвала устойчивый интерес к выяснению общей
роли алгорифмических процессов. В частности, появи-
появилось настойчивое стремление построить главные раз-
разделы математики на строго эффективной основе, без
привлечения актуально бесконечных множеств и за-
закона исключенного третьего, нарушающих вычис-
вычислимость. Идея такого построения, восходящая к ин-
интуиционистской концепции Брауэра [1], [2], получила
дальнейшее развитие в работе Тьюринга [1] (в кото-
которой, в частности, описано точное понятие алгоритма)
и в работе Банаха и Мазура [1*].
В настоящее время конструктивная математика до-
довольно детально и глубоко разработана с различных
позиций.
В Советском Союзе плодотворно работает большая
школа конструктивной математики. Со взглядами этой
школы на основания математики читатель может
ознакомиться по статьям Маркова [1*] и Шанина [1*].
Основные факты конструктивного математического
анализа в стиле школы Маркова систематически из-
изложены в книге Кушнера [1*]. Другие подходы к по-
построению конструктивной математики описаны в мо-
монографиях Бишопа [1*], Гудстейна [1*].
Эта небольшая книга принадлежит перу известного
шведского специалиста по математической логике
П. Мартин-Лёфа. Она представляет собой блестяще
написанный сжатый очерк основных идей и мето-
методов конструктивной математики. Для чтения книги
6
Предисловие редактора перевода
необходимо лишь знание основ математического ана-
анализа и некоторая общая математическая культура,
поэтому она может служить для первого ознакомле-
ознакомления с предметом.
В первых двух своих главах книга содержит сжа-
сжатое изложение самых характерных результатов кон-
конструктивной математики. Выбор в качестве уточнения
интуитивного понятия алгорифма канонических си-
систем Поста позволил автору удивительно кратко из-
изложить громоздкие конструкции теории алгорифмов
(см., например, п. 7, п. 9). Этот выбор привел автора
к трактовке открытых и замкнутых множеств (п. 17),
при которой удалось доказать конструктивную версию
теоремы Гейне — Бореля (п. 18) и теорему Бэра о ка-
категории (п. 21). Значительный интерес представляет
также оригинальное построение теории борелевских
множеств и теории меры (гл. 3 и 4). Автор привлекает
для построения этих теорий так называемые обобщен-
обобщенные индуктивные определения (в терминологии авто-
автора— определения по трансфинитной индукции). Эта
идея, восходящая к Брауэру, позволяет Мартин-Лёфу
придать рассматриваемым конструктивным теориям
такое же изящество, которое присуще их классиче-
классическим прообразам. Специалист, несомненно, оценит и
два применения конструктивной теории борелевских
множеств к математической логике (п. 31 и п. 32).
Русский перевод книги снабжен несколькими при-
примечаниями переводчика и редактора. Введение автора,
содержащее более специальное обсуждение методоло-
методологических установок монографии, перенесено в конец
книги.
Можно надеяться, что предлагаемая книга будет
полезна для широкого круга математиков и логиков,
студентов, аспирантов, интересующихся конструктив-
конструктивностью в математике.
А. Г. Драгалин
ПРЕДИСЛОВИЕ
Эта монография выросла из лекций, которые я чи-
читал в университетах Орхуса и Стокгольма в 1966—
1968 годах. Целью этих лекций было ввести математи-
математиков, не имеющих логической подготовки, в круг идей,
известных как интуиционистские или конструктивные,
а также представить некоторые из моих собственных
работ. Я добавил приложение, где описываю в логи-
логических терминах занятую мной конструктивную по-
позицию.
Чикаго, октябрь 1968
Пер Мартин-Лёф
ГЛАВА 1
РЕКУРСИВНЫЕ ФУНКЦИИ
1. Конструктивные объекты
Мы попытаемся установить границы понятия кон-
конструктивного объекта. Простейшие примеры таких
объектов получаются с помощью сочетания букв, зна-
знаков или символов из конечного алфавита в цепочки
или слова. В частности, если взять алфавит, состоя-
состоящий из единственной буквы — черточки |, то мы по-
получаем натуральные числа
? ими... ниш....
Здесь и всюду в дальнейшем, когда возникает опас-
опасность недоразумений, присутствие пустого слова ука-
указывается с помощью символа П. Целые числа
— это слова в двухбуквенном алфавите | —. Добав-
Добавляя знак/, мы можем строить рациональные числа
Несколько более сложные примеры дают нам фор-
формулы аксиоматической теории, например арифметики
первого порядка
Мы можем также рассматривать конструктивные объ-
объекты, устроенные нелинейным образом, например ко-
конечные деревья
10
Гл. 1. Рекурсивные функции
2. Канонические системы
И
целочисленные матрицы
I II
-I -I
и релейно-контактные схемы
ЕВ
Можно не вводить общее понятие конструктивного
объекта, так как каждый, кто ясно понимает, что это
такое, вероятно, согласится, что конструктивный объ-
объект всегда можно закодировать словом в подходящем
алфавите. Например, конечные деревья, приведенные
выше, легко закодировать в виде цепочек скобок
а целочисленные матрицы — в виде слов в четырех-
четырехбуквенном алфавите | —, ;
Эту редукцию можно провести еще дальше, так как
слова в конечном алфавите могут быть перенумеро-
перенумерованы, например путем использования лексикографиче-
лексикографического, упорядочения, как показано ниже для случая
трехбуквенного алфавита ару:
? а р y аа ар ау ...
? I II III НИ IIIII ПИИ-..
Таким образом, достаточно было бы рассматривать
только натуральные числа. Однако необходимость все
время линейно упорядочивать символы причиняет не-
некоторые неудобства, а необходимость нумеровать все
рассматриваемые объекты приводила бы к еще боль-
большей громоздкости. Вот почему мы предпочитаем ра-
работать с более общим понятием конструктивного объ-
объекта.
По-видимому, несущественно, предпочитаем ли мы
считать конструктивные объекты мысленными кон-
конструкциями или материально существующими объек-
объектами. Следует, однако, заметить, что в последнем
случае мы позволяем себе оперировать с этими объ-
объектами таким образом, как будто не существует ни-
никаких ограничений в пространстве и во времени. На-
Например, если наши конструкции — это отметки черни-
чернилами на листе бумаги, то мы предполагаем, что запас
чернил и бумаги не ограничен. Эта абстракция позво-
позволяет нам, в частности, сложить любые два натураль-
натуральных числа, приписав одно к другому. Бесконечное по-
появляется здесь лишь потенциально, не приводя, по-
видимому, ни к одной из трудностей, порождаемых
классическим понятием актуальной бесконечности.
Важность конструктивных объектов определяется
тем фактом, что это единственные объекты, которые
мы можем сообщить друг другу во всех деталях.
В частности, если нужна уверенность, что два мате-
математика, рассматривающие некоторый математический
объект, имеют в виду один и тот же объект, то этот
объект должен быть конструктивно определен. В со-
соответствии с этим все конкретные математические
объекты, которые мы будем рассматривать, такие, как
вещественные числа, открытые множества, веществен-
нозначные функции вещественной переменной, орди-
ординальные числа, измеримые множества и т. д., будут
конструктивными объектами, т. е. в конечном счете
натуральными числами.
2. Канонические системы
Канонические системы были изобретены Постом в
1941 году при попытке найти наиболее общий вид
формальных систем, таких, например, как Principia
Mathematica.
Будем предполагать, что дан список знаков и дру-
другой список символов, называемых переменными, и
!2
Гл. 1. Рекурсивные функции
3. Рекурсивно перечислимые множества и отношения 13
отличных от знаков. Терм— это любая цепочка зна-
знаков и переменных, а производящая схема (короче,
схема) — это фигура вида
... tn
где все t, ti} .,., tn (n > 0) суть термы. Термы
t\, ..., /„ называются посылками, а / — заключением
схемы. Схема без посылок (п = 0) называется
аксиомой.
Каноническая система, или система Поста, состоит
из списка знаков, списка переменных и конечного мно-
множества схем. Знаки образуют алфавит канонической
системы.
Применение схемы получается из схемы путем под-
подстановки цепочек знаков вместо всех переменных,
причем вместо всех вхождений одной н той же пере-
переменной подставляется одна и та же цепочка.
Если дана каноническая система, то определим по
индукции понятие доказательства некоторого слова,
т. е. цепочки знаков.
1. Применение аксиомы — доказательство этого
применения.
2. Если Р\, Р2, .... Рп — доказательства соответ-
соответственно слов а.\, а2, ..., ап и
а2
а-п
— применение некоторой схемы, то
Pi Р2 ... Рп
— доказательство слова а.
Слово доказуемо в канонической системе, если мы
можем найти его доказательство.
Пример. Слова, доказуемые в следующей системе
Поста, — это в точности четные числа.
знак
переменная
схемы
I
?
*1Г
Пример. Альтернирующие цепочки знаков аир.
знаки а E
переменные х
схемы (ф Ра —J-.
3. Рекурсивно перечислимые множества и отношения
Интуитивно множество конструктивных объектов
эффективно перечислимо, если мы можем дать пред-
предписание, указывающее нам, как порождать элементы
этого множества один за другим чисто механическим
путем. Понятие рекурсивно перечислимого множества
задумано как точная математическая формулиров-
формулировка этого несколько расплывчатого интуитивного
понятия.
Рекурсивно перечислимое множество слов в дан-
данном алфавите — это система Поста, алфавит которой
является расширением данного алфавита. Знаки рас-
расширенного алфавита, не принадлежащие данному
алфавиту, будут называться вспомогательными зна-
знаками.
Пусть а обозначает слово в данном алфавите, и
пусть Е и F — рекурсивно перечислимые множества
слов в том же алфавите. Введем следующие опреде-
определения.
яе? (читается «а принадлежит Е» или «а яв-
является элементом множества ?»), если а доказуемо
в системе Поста Е.
афЕ, если а не принадлежит Е, т. е. если любое
доказательство в системе Поста Е оканчивается сло-
словом, отличным от а.
Е = F, если любое слово в данном алфавите, дока-
доказуемое в системе Поста Е, доказуемо также в Р.
Е = F, если Е = F и F s ?.
Два примера рекурсивно перечислимых множеств
были уже приведены в предыдущем пункте. Добавим
к ним следующие чуть менее тривиальные примеры.
14
Гл. 1. Рекурсивные функции
3. Рекурсивно перечислимые множества и отношения 15
Пример. Множество чисел, не являющихся про-
простыми.
знак |
вспомогательные N • =
знаки
переменные х у г
Nx Nx x-y=z \\х • у\\ = г
— —
схемы
N
-гг-т -
Nx | х • ¦= х ¦ у
xz
Пример. Выводимые формулы интуиционистского
исчисления высказываний в бесскобочной записи
знаки
вспомогательные знаки
переменные
схемы
Р \ Л V -> —
AFT
х у z
АР
Ах Ах FxFy FxFy
Ах\ Fx F sxy F v xy
Fx
Fx Fy
Fx Fy Fz
F — x T ->x->yx T ->
Fx Fy Fx Fy
Т-+х->улху Т
Fx Fy Fz
• xy -> -> x -> у г -> xz
Fx Fy Fx Fy
¦hxyx T ¦
T
Tx
x
¦ кхуу Т ~> xv xy
Fx Fy
:-y-z
Fx Fy
F ->xy
Tx T ->xy
Ту
Fx Fy
T ->yv xy T -> -> xz ->• -*¦ yz -*¦ v xyz
Fx Fy
T -> — x -> xy
Мы часто будем использовать следующий прием.
К каждому члену каждой схемы данной системы По-
Поста приписывается один и тот же знак, не содержа-
содержащийся в алфавите этой системы. Эта операция будет
называться нанесением метки.
Пусть Е и F — рекурсивно перечислимые множе-
множества слов в алфавите оц ... аР.
Е U F, объединение множеств Е и F, определяется
как система Поста, схемами которой являются схемы
первого множества, отмеченные знаком Е, схемы вто-
второго, отмеченные знаком F, и новые схемы
л Ах Ах Ах Ex Ax Fx
'" Ахйв х х *
Здесь мы не стали явно выписывать знаки, вспомога-
вспомогательные знаки и переменные определяемых нами си-
систем Поста. Мы часто будем допускать такого рода
неточности, если не будет опасности путаницы. Непо-
Непосредственно видно, что если а — слово в алфавите
си ... ар, то а е Е U F тогда и только тогда, когда
а^Е или aeF, Этим оправдывается наше опреде-
определение.
Заменяя последние две схемы из определения
E[}F на
Ах Ex Fx
мы получаем EOF, пересечение Е и F, обладающее
тем свойством, что ае.Е [] F тогда и только тогда,
когда aefnflEf.
Рекурсивно перечислимое множество Е слов в дан-
данном алфавите рекурсивно или разрешимо, если можно
найти рекурсивно перечислимое множество F, такое,
что Е П F пусто, а Е U F равно множеству всех слов
в данном алфавите. Хотя мы и не будем этого дока-
доказывать, все рекурсивно перечислимые множества, при-
приведенные в наших примерах, в действительности раз-
разрешимы. Утверждение о существовании рекурсивно
перечислимого неразрешимого множества — это одна
из основных теорем теории рекурсивных функций, ко-
которая будет доказана позднее.
Предположим теперь, что даны два алфавита
он ... ар и Pi ... pq. Рекурсивно перечислимое отно-
отношение— это рекурсивно перечислимое множество слов
вида а, Ь в алфавите1) а\ ... ар, Pi ... pq, где а и
b — слова в соответствующих алфавитах (т. е. а есть
слово в алфавите а\ ... аР, Ъ — слово в алфавите
Pi ... pq). Мы будем использовать запись aRb, чтобы
выразить тот факт, что a, b принадлежит отноше-
отношению R.
Если рекурсивно перечислимое отношение обла-
обладает свойством функциональности, т. е. из того, что
a, b и а, с принадлежат ему, следует, что b = с, то мы
') Запятая является буквой этого алфавита. — Прим. перев.
Гл. 1, Рекурсивные функции
будем называть это отношение частично рекурсивной
функцией или алгорифмом. Обычная функциональная
запись F(a) = 6 будет использоваться для выражения
того, что а, Ь принадлежит частично рекурсивной
функции F. Мы приводим ниже несколько примеров
алгорифмов, в которых мы позволили себе чуть изме-
изменить символику по сравнению с используемой в мате-
математической практике.
Пример. Сложение натуральных чисел,
знаки | + =
вспомогательный знак N
переменные
схемы
N
Nx
Nx\
Nx Ny
Пример. Умножение натуральных чисел.
знаки | • «=
вспомогательный знак N
переменные х у z
Nx Nx х- у-
Nx\ х- = х-у | =
схемы
N
xz
Пример. Факториал,
знаки | I i
вспомогательные знаки N *
переменные х у я
схемы !'
х\ — у x\-y*=*z
вместе со схемами из предыдущего примера.
Пример. Лексикографически следующий.
знаки
вспомогательный А
знак
переменные х у
... ар F
схемы
i ''' Ахар
Fat
Ах
Ах
хпр-iFxap
xFy
3. Рекурсивно перечислимые множества и отношения 17
Пример. Лексикографическая гёделевская нуме-
нумерация.
знаки
вспомогательные
переменные
схемы
знаки
1
А
X
G
«1
F
У
z
xGy
х\
ар G
yFz
Gz
вместе со схемами из предыдущего примера.
Область определения рекурсивно перечислимого
отношения между словами в ai ... ар и словами в
Pi • ¦. Р? — это рекурсивно перечислимое множество,
получаемое с помощью нанесения метки R на схемы
рассматриваемого отношения и добавления новых
схем
Ах
Аха,
Ах
АхаП
В
Вх
Ах Rx,y By
Аналогичным образом мы получаем область зна-
значений, заменяя последнюю схему на
Ах Rx,y By
- .
Если область определения частично рекурсивной
функции, перерабатывающей слова в щ ... ар в сло-
слова в Pi ... pg, есть множество всех слов в ai, ..., аР,
то эта функция называется общерекурсивной функ-
функцией или всюду определенным алгорифмом.
Образ рекурсивно перечислимого множества слов
в ai ... ар относительно рекурсивно перечислимого
отношения между словами в oi ... ар и словами в
Pi ... р? определяется схемами
Ах
Аха„
В
Вх
~BxJ
Вх
Ах Ex Rx,y By
у
вместе со схемами отображаемого множества, от-
отмеченными символом Е, и схемами рассматривае-
рассматриваемого отношения, отмеченными символом R. Прообраз
18
Гл. 1. Рекурсивные функции
4. Исчисление равенств
19
получается тем же способом, только последняя схема
заменяется на
Ах Rx,y By Еу
х
Пусть R— рекурсивно перечислимое отношение
между словами в а\ ... ар и словами в Pi ... fa и
5 — рекурсивно перечислимое отношение между сло-
словами в pi ... рд и словами в yi • • • Уг- Композиция
отношений R и S определяется схемами
Ах
Сх
СхУ1
Ах
Ахар
Сх
Схух
Вх
Вх
в
Ах Rx,y By Sy,z Cz
x, z
вместе с отмеченными схемами R и 5.
Наконец, обращение рекурсивно перечислимого от-
отношения R — это рекурсивно перечислимое отношение,
получаемое добавлением схем
Ax n Bx Bx
AxaD D Bx&, ' * ' Bx&n
к схемам, отмеченным символом R.
Ах Rx,y By
4. Исчисление равенств
Первое точное определение эффективно вычисли-
вычислимой функции принадлежит Эрбрану и Гёделю [3]. Их
идея состояла в попытке найти наиболее общий вид
рекурсивных определений теоретико-числовых функ-
функций.
Пример. Сложение ф и умножение г|) натуральных
чисел могут быть определены через 0 и функцию сле-
следования а посредством следующих равенств, написан-
написанных в бесскобочной символике
1 №0 = О
Здесь ? и т) — переменные, пробегающие множество
натуральных чисел.
В общем случае мы рассматриваем список функ-
функциональных символов
Фо == 0 ф, = а ф2 • •. Фт = Ф.
с каждым из которых связано неотрицательное число,
называемое числом мест
А> = 0 р,= 1 р2 ... рт = р.
Как уже отмечено, всегда должен присутствовать
функциональный символ 0 с числом мест нуль и одно-
одноместный функциональный символ а для функции сле-
следования. Последний функциональный символ ф с чис-
числом мест р называется главным функциональным сим-
символом.
Цифры определяются следующими индуктивными
пунктами.
1 0 — цифра.
2 Если п — цифра, то и an — цифра.
Далее предположим, что дан список переменных
l! 12 ... In-
Из них и из функциональных символов мы индуктив-
индуктивно строим термы.
1 Переменная есть терм.
2 Если t\, ?2 tp — термы, то ф;Мг • • • tp — терм
@<i<m).
В частности, все цифры являются термами. Если t и
и — термы, то t — u — равенство. Список функцио-
начьных символов и список переменных вместе с ко-
конечным множеством равенств называется исчислением
равенств.
Для исчисления равенств имеется два правила вы-
вывода.
1 От данного равенства можно перейти к новому
равенству, полученному подстановкой некоторой циф-
цифры вместо всех вхождений одной и той же перемен-
переменной.
2 От равенства Е и равенства (pinin2 ... пр = п,
где п, пи п2, ..., nPi—цифры, можно перейти к
20
Гл. 1. Рекурсивные функции
5. Машины Тьюринга
21
равенству, полученному из Е заменой некоторого
вхождения терма (p,nin2 • • • nPi на п.
Эти правила называются подстановкой и заменой.
Равенство выводимо, если его можно получить из дан-
данных равенств с помощью правил вывода.
Если фИ1«2 • • • пр = п выводимо не более чем для
одной цифры п при любом выборе цифр п\, "г. • • •
..., пр, то мы будем говорить, что рассматриваемое
исчисление равенств определяет частично рекурсив-
рекурсивную функцию в смысле Эрбрана и Геделя. Мы пока-
покажем, что это понятие частично рекурсивной функции
не является более общим, чем то, которое мы ввели
с помощью канонических систем Поста.
Если дано исчисление равенств, мы можем найти
рекурсивно перечислимое множество, элементы кото-
которого— это в точности выводимые равенства вида
(рщп2 ... пр = п, где п, пи ..., пР — цифры и <р —
главный функциональный символ.
Доказательство достигается путем построения сле-
следующей канонической системы.
знаки
0 о
вспомогательные знаки фг
переменные
производящие
/ и
схемы WO
Nx
(fiStPiSt/Sx
Nx
tfixSljSx
Nx
liSliSliSx
Nx
= S =a Sl-jSX
¦ ф =
• ¦ • <Pm-
V W X
1 = 0, .
A/- I:
'*=/
tSvSxSy uSwSxSy
tuSvwSxSy
1 ll ¦.. 1
Xt Xt ...
Nx
Nax
.., m
.., n
.., re
n N S E
У *
равенства данного исчисления равенств, перед, кото-
которыми вставлена буква Е:
Et tSuSxSy
Ей
х Eytfixl ... xpfz Nx
E<fXl ..
Eyxz
1 = 0 m
xp = x Nx Nx\ ... Nxp
<fX\
5. Машины Тьюринга
Непосредственный анализ человеческих воможно-
стей в области вычисления привел Поста [1] и Тью-
Тьюринга [1] к введению определенного типа машин, кото-
которые должны имитировать действия человека-вычис-
человека-вычислителя.
Представим себе ленту, разделенную на ячейки и
продолжимую в обоих направлениях сколь угодно да-
далеко. Мы можем печатать на ней знаки а\ ... аР,
возможно оставляя некоторые ячейки пустыми:
«2
Далее, представим себе машину, которая в любой
момент находится в одном из своих состояний Pi ...
... pg, обозревая одну из ячеек ленты. На рисунке
это указывается посредством подписывания состояния
машины под обозреваемой ячейкой. Если обозревае-
обозреваемый символ есть а4 (мы пишем ао вместо пустого сим-
символа) и машина находится в состоянии Pj, она выпол-
выполняет инструкцию, имеющую один из четырех видов?
1 Напечатать ahiO^k^p) и перейти в состоя-
состояние р,A </<?).
2 Сдвинуться на одну ячейку влево и перейти в со-
состояние Рг.
22
Гл. 1. Рекурсивные функции
5. Машины Тьюринга
23
3 Сдвинуться на одну ячейку вправо и перейти в
состояние р*.
4 Остановиться.
Машина начинает работу в состоянии Pi с началь-
начальными данными, напечатанными на ленте, и работает
шаг за шагом в соответствии с приведенными прави-
правилами до тех пор, пока не остановится. Результат вы-
вычисления — это надпись, оставшаяся на ленте после
того, как машина остановилась. Может случиться, что
она никогда не остановится.
Мы говорим, что лента обозревается в стандарт-
стандартной позиции, если машина обозревает самый правый
символ, напечатанный на ленте. Лента, изображенная
выше, обозревается в стандартной позиции
1
1
1
1
1
1
л
Машина только что описанного типа называется
машиной Тьюринга. Она следующим образом опреде-
определяет частичную теоретико-числовую функцию (при не
уменьшающем общности предположении, что cci =» |).
Запустим машину, обозревающую в начальном со-
состоянии р число m в стандартной позиции.
Если машина в конце концов останавливается, обо-
обозревая некоторое натуральное число в стандартной
позиции, то это натуральное число и есть значение,
принимаемое рассматриваемой функцией для аргу-
аргумента т. Мы покажем, что вычисление, осуществляе-
осуществляемое машиной Тьюринга, может быть с тем же успехом
выполнено в канонической системе.
Если дана машина Тьюринга, мы можем найти ча-
частично рекурсивную функцию F, такую, что F(m) a n
тогда и только тогда, когда рассматриваемая машина
Тьюринга, запущенная в стандартной позиции, где она
обозревает натуральное число пг, в конце концов оста-
останавливается, обозревая натуральное число п в стан-
стандартной позиции.
Следующая система Поста определяет искомую
частично рекурсивную функцию:
знаки
вспомогательные знаки
переменные
производящие схемы
а0 а2 ..
х у z
N NX
N
х,У
х,уаа
х,у
Nx\
х,уаа
х,у
Nx
х,аоу
х,у
Для каждой конструкции первого типа мы добавляем
схему
Аналогично инструкция второго типа порождает схему
инструкция третьего типа — схемы
инструкция четвертого типа — схемы
x,at
или
x,ya{
в зависимости от того, равно ли I нулю или единице.
Для / = 2, ..., р инструкция типа 4 вообще не по-
порождает схем.
Мы закончим этот пункт, приведя некоторые со-
соображения в пользу того, что все возможные виды
механических вычислений могут быть выполнены на
машинах Тьюринга.
Должно быть ясно, что мы не наложим суще-
существенных ограничений, допустив, что производим на-
наши вычисления обычным образом с помощью записей
чернилами на листах бумаги. Эти листы мы берем на-
настолько большими, чтобы те части наших вычислений,
которые мы можем окинуть взглядом, умещались на
24
Гл. 1. Рекурсивные функции
6. Тезис Чёрча
25
одном листе бумаги, лежащем перед нами. Резуль-
Результаты наших предшествующих усилий мы складываем
в стопку около стола. Для числа конфигураций на бу-
бумаге, находящейся перед нами, которые мы способны
отчетливо различить, должна иметься конечная гра-
граница, так как иначе нашлись бы сколь угодно мало
различающиеся конфигурации. Наше действие в лю-
любой определенный момент должно определяться кон-
конфигурацией на бумаге перед нами и нашим состоя-
состоянием ума. В расчет нужно принимать лишь конечное
число состояний ума, так как в противном случае
среди этих состояний были бы сколь угодно близкие,
и это привело бы нас в замешательство. Далее, чтобы
не запутаться в стопке бумаг, находящейся рядом с
нами, мы пользуемся закладкой для указания поло-
положения в стопке того листа, который лежит перед на-
нами. В зависимости от того, что написано на бумаге,
лежащей перед нами, и состояния нашего ума мы
предпринимаем действия двух возможных типов. Либо
мы пишем что-нибудь на бумаге перед нами, либо мы
кладем эту бумагу назад в стопку на место закладки
и вынимаем из стопки другой лист для исследования.
Снизу и сверху стопки подкладывается чистая бумага.
Расстояние от закладки до листа, который мы соби-
собираемся вынуть, должно определяться конфигурацией
на листе, лежащем перед нами, и нашим состоянием
ума и тем самым имеет конечную границу. Сделав
размер листов достаточно большим, мы можем допу-
допустить, что, меняя лист, лежащий перед нами, мы все-
всегда кладем на его место один из соседних листов. Та-
Таким образом, ход вычисления разбит на последова-
последовательность элементарных действий того типа, который
способна выполнять машина Тьюринга.
6. Тезис Чёрча
Чёрч [1] выдвинул тезис о том, что интуитивное по-
понятие эффективности равнообъемно с точным мате-
математическим понятием рекурсивности, которое мы вве-
ввели. Этот тезис, известный как тезис Чёрча, можно
рассматривать либо как гипотезу относительно ин-
интуитивного понятия эффективности, либо как точную
формулировку понятия, которому до сих пор не хва-
хватало математической строгости. Используя выражение
Поста [1], можно сказать, что оно является фундамен-
фундаментальным открытием относительно границ математиче-
математических способностей Homo Sapiens.
Мы попытаемся привести некоторые подтвержде-
подтверждения тезиса Чёрча. Во-первых, можно спросить, реаль-
реально ли вообще интуитивное понятие эффективности,
так как иначе этот тезис был бы бессмысленным.
Психологический факт состоит в том, что многие ма-
математики способны развить сильное ощущение поня-
понятия эффективности. Например, задолго до зарождения
теории рекурсивных функций понятие эффективности
использовалось с большой точностью Борелем [1] и
Брауэром [2], который основывал на нем многие не-
нетривиальные математические рассуждения.
Одна половина тезиса Чёрча утверждает, что ре-
рекурсивно перечислимые множества эффективно пере-
перечислимы также в интуитивном смысле. (Мы выбираем
понятие рекурсивно перечислимого множества вместо
рекурсивной функции в качестве основного понятия
рекурсивности.) Это несомненно так: если дано ре-
рекурсивно перечислимое множество, то мы можем по-
порождать его элементы один за другим чисто механи-
механическим путем, систематически перебирая все доказа-
доказательства. Один из способов сделать это будет весьма
подробно описан в п. 8.
Вторая половина тезиса Чёрча — основная. Она
утверждает, что множество, эффективно перечисли-
перечислимое в интуитивном смысле, также и рекурсивно пере-
перечислимо. Эффективно перечислимое множество задано
предписанием, содержащим конечное число слов и со-
сообщающим нам, как порождать элементы. Мы ут-
утверждаем, что такое предписание всегда можно запи-
записать в виде канонической системы, которую можно
считать чем-то вроде формализованного языка. Мы
уже несколько раз демонстрировали, как неформаль-
неформальные предписания, написанные по-русски, могут быть
переведены в соответствующим образом построенные
канонические языки, и в следующем пункте будет
26
Гл. t. Рекурсивные функции
7. Универсальная система
27
дано важнейшее применение этой техники. Это долж-
должно сделать правдоподобным утверждение о том, что
канонические системы достаточно мощны для выраже-
выражения всех возможных видов эффективных определений.
Другой более формальный тип подтверждений
дается тем фактом, что многие сильно различающиеся
подходы к понятию вычислимости, например
исчисление равенств
црекурсивные функции
Яопределимость
вычислительные машины
канонические системы
нормальные алгорифмы
Эрбран и Гёдель
Кляни
Чёрч
Тьюринг
Пост
Марков
оказались эквивалентными. Это сильное свидетель-
свидетельство в пользу тезиса Чёрча. Мы не показали ни одной
из этих эквивалентностей, а установили только, что
исчисление равенств и машины Тьюринга могут быть
сведены к каноническим системам Поста. Это иллю-
иллюстрирует технику, нужную для таких доказательств,
а также позволяет нам, для подтверждения общности
принятого нами определения рекурсивности, опираться
на тьюринговский анализ вычислительных возможно-
возможностей человека, намеченный в предыдущем пункте.
Наконец, имеется эмпирическое подтверждение: за
38 лет, прошедших с тех пор, как был выдвинут тезис
Чёрча, не была получена никакая процедура, эффек-
эффективная по общему признанию, но оказавшаяся нере-
нерекурсивной.
7. Универсальная система
Точно так же, как мы говорили об исчислении ра-
равенств и машинах Тьюринга внутри соответствующим
образом построенных канонических систем, мы начнем
сейчас говорить о самих канонических системах вну-
внутри системы того же самого типа. Эта возможность,
автоссылок, впервые использованная Гёделем [2] в его
знаменитой работе о неразрешимости аксиоматиче-
аксиоматических теорий, составляет само ядро теории рекурсив-
рекурсивных функций.
Мы рассмотрим все рекурсивно перечислимые мно-
множества слов в данном алфавите <xi ... ар, т. "е. си-
системы Поста, алфавиты которых являются расшире-
расширениями данного алфавита. Чтобы о них можно было
говорить внутри канонической системы, мы должны
закодировать их словами в фиксированном алфавите.
Оказывается, что подходит алфавит
а,
. ар
, ... ар
Заменим каждый вспомогательный знак словом из
списка
aip ... а„р а,рр ...
и переменные — словами
Таким образом термы станут словами в сц .. Р(
Код определяющей схемы получается, если написать
рядом коды всех посылок и код заключения, отделен-
отделенный знаком ->. Наконец, приписывая друг к другу
коды схем, разделенные *, мы получим код всей си-
системы. Этот код называется базисом рассматривае-
рассматриваемого рекурсивно перечислимого множества.
Пример. Базис множества чисел, не являющихся
простыми, определенного в п. 3:
* г ill т» ill mm -»m-
Здесь Вспомогательные знаки N-= были заменены на
IP IPP IPPP и переменные xyz — соответственно на
I U ЕРР-
Гёделевский номер рекурсивно перечислимого мно-
множества — это лексикографический номер его базиса.
Если рекурсивно перечислимое множество задано
в виде своего базиса, то неудобно сначала произво-
производить все подстановки, а затем размещать применения
схем в форме дерева. Поэтому мы чуть иначе опре-
определим понятие доказуемости. В следующих трех
индуктивных пунктах мы, говоря о знаках, перемен-
переменных, термах и схемах, имеем в виду коды этих объ-
объектов.
28
Гл. 1. Рекурсивные функции
7. Универсальная система
29
1 Схема, встречающаяся в базисе, доказуема.
2 Если некоторая схема доказуема, то доказуема
и схема, получающаяся из нее подстановкой некото-
некоторой цепочки знаков вместо переменной.
3 Если доказуемы t и t -*¦ м, причем t — терм, то
и доказуемо.
Непосредственно проверяется, что слово принад-
принадлежит рекурсивно перечислимому множеству тогда и
только тогда, когда оно доказуемо из его базиса по
этим правилам. Мы готовы теперь к доказательству
следующей фундаментальной теоремы.
Существует рекурсивно перечислимое отношение II
между натуральными числами и словами в данном
алфавите, такое, что mUa тогда и только тогда, когда
m есть гёделевский номер рекурсивно перечислимого
множества, которому принадлежит а.
Это отношение II будет называться универсальным
для рекурсивно перечислимых множеств слов в дан-
данном алфавите.
Для облегчения чтения мы будем перемежать схе-
схемы канонических систем, которые мы собираемся
строить, семантическими интерпретациями синтакси-
синтаксических выражений.
знаки | , а, ... ар
вспомогательные знаки 0 g -» « ABC EFGLPSTVW
переменные t и v w х у z
схемы
Ах
Lx
Vx
Wx
Тх
Рх
Вх
X ¦
х-
А
X
X
X
X •
х-
— СЛОВО В Cti ... ар
— знак или вспомогательный знак
Ах Ах .
Axat '" Ахар
— переменная
— цепочка знаков
— терм
Vx Wx Ly
Vx$ Wxy
— схема
— базис
Тх Тх Ру в
Рх Рх->у
tit ... ар
т Тх Ly
Тху
Вх Ру
Вх*у '
Lx
Lx$
Тх Vy
Тху
tSuSvSw — схема и получена из схемы t в результате подста-
подстановки цепочки знаков w вместо переменной о
Lx Vy Wz
xSxSySz
Vx Vxfiy Wz
Vx Wy Vx
Wz
xSySxSy
Vx Wy
xSxSxfiySz
tSvSxSy uSwSxSy
tuSvwSxSy
хСц
Ex
E
xFy
xGy
Fat
-*S->SxSy
у доказуемо из базиса х
Вх Ру Вг xCt tSuSvSw xCy xCy -> z Ту
х * yzCy xCu xCz
X — СЛОВО В d[ ... ОрР* -> *
Ex Ex Ex Ex _ Ex Ex
Ex\
Exap
Ex-> Ex*
у лексикографически непосредственно следует
за х
х —лексикографический гёделевский номер у
Ex Ex Ex Ex Ex
x->Fx*
xFy
x * Fyat
xGy yFz
x\Gz
xGy yGz Az
x, z
Доказательство закончено.
Рассмотрим теперь частный случай, когда р
си = |. Добавляя новую схему
1 И
х,х
к схемам, приведенным выше, мы получаем рекур-
рекурсивно перечислимое множество D натуральных чисел,
которое назовем диагональным множеством. Оно со-
содержит натуральное число п тогда и только тогда, ко-
когда ft принадлежит рекурсивно перечислимому множе-
множеству с номером п. В частности, если е — гёделевский
номер рекурсивно перечислимого множества Е, то
esfl тогда и только тогда, когда es?, т. е. ее
е D U Е влечет за собой eeflflfi. Отсюда мы за-
заключаем, что не может случиться так, что D П Е пу-
пусто, и в то же время D О Е равно множеству всех
30
Гл. I. Рекурсивные функции
8. Теорема о перечислении
натуральных чисел. Следовательно, диагональное
множество неразрешимо.
Мы построили рекурсивно перечислимое множество
натуральных чисел, которое неразрешимо.
Это важное следствие принадлежит Черчу [1]. За-
Заметим, что в доказательстве скрыто рассуждение, при-
приводящее к парадоксу Рассела. Действительно, если
мы отождествим рекурсивно перечислимое множество
с его гёделевым номером, то диагональное множество
состоит из всех множеств, которые содержат самих
себя. Чтобы доказать разрешимость диагонального
множества, мы должны были бы указать рекурсивно
перечислимое множество, элементы которого — это в
точности те множества, которые не содержатся в себе.
Рассуждение Рассела показывает, что допущение су-
существования такого множества ведет к противоре-
противоречию.
Рассмотрим утверждение
для всех п либо яеД либо пф-D,
которое истинно классически, так как оно немедленно
следует из закона исключенного третьего. Интуицио-
Интуиционистская интерпретация этого утверждения такова.
Мы нашли метод, позволяющий нам доказать либо
пей, либо пфЬ, какое бы натуральное п ни было
нам дано. При такой интерпретации это утверждение
ведет к противоречию, если принять тезис Чёрча. Мы
видим, таким образом, что если логическим связкам
придан их конструктивный смысл, то закон исключен-
исключенного третьего больше неприменим. Это фундамен-
фундаментальное обстоятельство было открыто Брауэром [1].
Теорема Чёрча — плод работ двадцатых и тридца-
тридцатых годов, вызванных уверенностью Гильберта в раз-
разрешимости всех математических проблем. Брауэр с
самого начала отвергал это утверждение Гильберта.
Теперь, если разрешимость понимается в смысле су-
существования эффективной процедуры для доказатель-
доказательства или опровержения любого математического ут-
ьерждения и если принят тезис Чёрча, то теорема
Чёрча усиливает возражение Брауэра до настоящего
опровержения.
8. Теорема о перечислении для частично
рекурсивных функций
На основную теорему предыдущего пункта мы бу-
будем ссылаться как на теорему о перечислении для ре-
рекурсивно перечислимых множеств. В дальнейшем нам
понадобятся .несколько других теорем о перечислении.
Все они будут выведены из усиленного варианта тео-
теоремы, которую мы уже доказали.
Рассмотрим базис рекурсивно перечислимого мно-
множества слов в данном алфавите. Последовательность
схем, к которым спереди приписана *, считается
по определению кодом доказательства из этого ба-
базиса, если каждая из этих схем может быть получена
из предыдущих с помощью одного из трех правил вы-
вывода, приведенных в предыдущем пункте. Номер до-
доказательства определяется как лексикографический
гёделевский номер его кода.
Пример. Множество четных чисел, определенное в
п. 2, имеет базис
**1-1||*-Ч1*1Ы1Н*11*1111
является кодом доказательства того, что четыре —
четное число.
Имеется разрешимое отношение V между нату'
ральными числами и общерекурсивная функция W,
переводящая натуральные числа в слова в данном
алфавите, такие, что mVn тогда и только тогда, когда
m есть гёделевский номер некоторого рекурсивно пе-
перечислимого множества и п есть номер доказатель-
доказательства некоторого элемента а этого множества, причем
в этом случае W(n) = а.
82
Гл. 1. Рекурсивные функции
8. Теорема о перечислении
33
Эту теорему можно считать аналогом теоремы
Клини о нормальной форме. Она представляет уни-
универсальное отношение U в виде композиции раз-
разрешимого отношения V и общерекурсивной функ-
функции W.
Мы не будем выписывать явно системы Поста,
определяющие V и W. Это потребовало бы около сот-
сотни схем и не было бы особенно ценно. Вместо этого
мы неформально укажем, как узнавать, верно ли
tnVn, и как вычислять W(n). Сила канонических
систем продемонстрирована теперь до такой степени,
что перевод наших неформальных инструкций в кано-
каноническую форму должен быть чисто рутинным делом.
Это не значит, что мы полагаемся на тезис Чёрча.
Мы только приводим менее детальные доказательства,
чем раньше.
Доказательство теоремы. Пусть он ... аР — дан-
данный алфавит. Сначала проверяем, имеют ли слова в
он ... аРр?->*, соответствующие данным тип, пра-
правильную синтаксическую структуру, т. е. являются ли
они последовательностями схем, к каждой из которых
приписана впереди звезда. Это так в том и только в
том случае, если они начинаются со звезды и никакое
р не следует за стрелкой или звездой. Далее мы по-
последовательно проверяем для каждой из схем в по-
последовательности, соответствующей числу п, может ли
она быть получена из предыдущих применением од-
одного из трех правил вывода из предыдущего пункта.
Если все эти испытания дают положительный резуль-
результат и если последняя схема последовательности есть
слово в ai ... аР, то mVn. Иначе неверно mVn.
Это предписание определяет разрешимое отноше-
отношение V.
Построение общерекурсивной функции W даже
проще. Если п — лексикографический гёделевский
номер слова в ai ... apP?->*, оканчивающегося на
*а, где а — слово в ai ... ap, то W(n)=a. Иначе
полагаем, например, W(n) = П.
Эта теорема важна по той причине, что, как указы-
указывается ниже, она позволяет для всякого т порождать
в определенном порядке элементы рекурсивно пере-
перечислимого множества, гёделевский номер которого
есть т
п mVnf
По
Я|
нет
нет
да
да
У(п.)
Очень простое применение этой техники влечет сле-
следующий конструктивный принцип выбора.
Если дано рекурсивно перечислимое отношение R,
мы можем найти частично рекурсивную функцию F
с той же областью, такую, что Р(а) = Ь влечет за со-
собой aRb.
Достаточно порождать элементы ait Ъи принадле-
принадлежащие R, 1 = 0, 1, ..., описанным выше способом и
определить F(ai) = Ьи если а< Ф а} для всех / < L
Более важна теорема о перечислении для частично
рекурсивных функций, преобразующих слова в одном
алфавите ai... ар в слова в другом алфавите
Pi... р,.
Существует частично рекурсивная функция
U (m, а), такая, что если m есть гёделевский номер ча-
частично рекурсивной функции F, то U(m, a) =b тогда
и только тогда, когда F(a) = b.
Частично рекурсивная функция рассматриваемого
нами типа есть по определению рекурсивно перечис-
перечислимое множество слов в ai... ap, Pi.. р„ имеющее
определенные свойства. Мы уже доказали теорему
о перечислении для класса всех рекурсивно перечис-
перечислимых множеств слов в этом алфавите. Затруднение
34
Гл. 1. Рекурсивные 'функций
10. Рекурсивная неотделимость
35
в том, что не все они — функции. Пусть дано произ-
произвольное натуральное число пг, и мы порождаем после-
последовательно элементы с0, с\, ..., с,- ... того множе-
множества, гёделевский номер которого равен пг, если такие
имеются. Если ct имеет вид аи Ь{, где а( и bt— слова
в ai... ар и Pi... pg соответственно, и свойство функ-
функциональности еще не нарушено, т. е. щ = а,- для не-
некоторых / < i влечет bt = b}, мы полагаем U(m, с4) =
= Ь{. Так определенное U — очевидным образом ча-
частично рекурсивная функция, и если пг уже было гё-
делевским номером некоторой частично рекурсивной
функции F, то U(m,a) = b тогда и только тогда, ко-
когда F(a) ='b. Доказательство закончено.
Построенная функция U называется универсаль-
универсальной для частично рекурсивных функций рассматривае-
рассматриваемого нами типа.
9. Теоремы об итерации
Мы докажем, что произвольная рекурсивная нуме-
нумерация рекурсивно перечислимых множеств может
быть в определенном смысле сведена к универсальной
нумерации.
Пусть R — рекурсивно перечислимое отношение
между натуральными числами и словами в данном ал-
алфавите. Тогда можно найти общерекурсивную функ-
функцию S, такую, что R равно композиции S и универ-
универсального отношения U.
Эту теорему мы назовем теоремой об итерации для
рекурсивно перечислимых множеств.
Доказательство. Рассмотрим алфавит ai... ар и
запишем схемы данного отношения, отмеченные зна-
знаком R, и, кроме того, схемы
m
Ах
Аха.1
Ах
Ахаа
Р\\\-.\\,х Ах
х
Пусть S(tn)—гёделевский номер этого рекурсивно
перечислимого множества. Тогда S — общерекурсив-
общерекурсивная функция, удовлетворяющая условиям теоремы.
Действительно, если S (пг) = п, то mRa тогда и толь-
только тогда, когда nUa, что как раз и означает, что R
равно композиции S и U.
Теорема об итерации для частично рекурсивных
функций столь же проста.
Если дана частично рекурсивная функция F(m,a),
то мы можем найти общерекурсивную функцию S, та-
такую, что F(пг, а) = U(S (пг) ,а), где U — универсаль-
универсальная функция.
По аналогии с доказательством предыдущей тео-
теоремы мы полагаем S(m) равным гёделевскому номе-
номеру сечения F в точке т.
10. Рекурсивная неотделимость
Говорят, что два рекурсивно перечислимых мно-
множества А и В рекурсивно отделимы, если можно най-
найти рекурсивное множество С, такое, что A s С и В Л С
пусто.
Существует пара дизъюнктных рекурсивно пере-
перечислимых множеств натуральных чисел, которые не
могут быть рекурсивно отделены.
Если два дизъюнктных рекурсивно перечислимых
множества не могут быть рекурсивно отделены, то ни
одно из них не рекурсивно. Поэтому приведенная
выше теорема усиливает теорему Чёрча о существо-
существовании рекурсивно перечислимого множества, которое
не рекурсивно.
Доказательство. Допустим, что уже доказано су-
существование рекурсивной нумерации всех пар
дизъюнктных рекурсивно перечислимых множеств на-
натуральных чисел,
Ап,Вп, п = 0, 1
Пусть А а В — рекурсивно перечислимые множества,
элементами которых являются соответственно те чис-
числа п, для которых яеЛ„, пеВл. Так как Ап и Вп
36
Гл. 1. Рекурсивные функции
П. Теорема Клини о неподвижно/! точке
дизъюнктны для любого п, то А и В также дизъюнкт-
дизъюнктны. Мы покажем, что Л и В не могут быть рекурсивно
отделены. Действительно, допустим, что А = С и
D э В, где С и D — дизъюнктные рекурсивно пере-
перечислимые множества, объединение которых есть мно-
множество всех натуральных чисел. Так как D, С — пара
дизъюнктных рекурсивно перечислимых множеств, мы
можем найти п, такое, что Ап = D и Вп = С. Теперь
яеС = Вп влечет п^В<=Ь, и п е Z) = Лп влечет
«E/IeC. Так как либо п <= С, либо /isD и С Л D
пусто, мы пришли к противоречию.
Остается построить рекурсивную нумерацию всех
пар дизъюнктных рекурсивно перечислимых множеств
натуральных чисел. Мы уже доказали теорему о ну-
нумерации для рекурсивно перечислимых множеств."
С помощью рекурсивного взаимно однозначного соот-
соответствия между натуральными числами и парами на-
натуральных чисел мы получаем отсюда рекурсивную
нумерацию всех пар (не обязательно дизъюнктных)
рекурсивно перечислимых множеств. Теперь мы сде-
сделаем их дизъюнктными с помощью рекурсивной про-
процедуры модификации, которая не трогает те пары,
которые были дизъюнктны с самого начала.
Пусть А и В образуют произвольную пару рекур-
рекурсивно перечислимых множеств. Порождаем последо-
последовательно их элементы методом, указанным в п. 8, так
что
UQ, 0|, . . . , О{
Ьо, blt ..., bjn
— элементы, полученные из доказательств с номера-
номерами ss; га. Мы поступаем так, пока имеет место at Ф 6,-
для всех i tg; in и / ^ /п. Если это условие нарушено
для некоторого значения п, то процедура модифика-
модификации заканчивается, и модифицированные А и В со-
состоят из -элементов, полученных к этому моменту.
Ясно, что если А к В дизъюнктны с самого начала, то
они остаются неизменными после модификации. До-
Доказательство закончено.
11. Теорема Клини о неподвижной точке
Для доказательства рекурсивности некоторых опе-
операций в теории конструктивных ординалов Клини [1]
доказал важную теорему, которую обычно называют
теоремой о рекурсии или теоремой Клини о неподвиж-
неподвижной точке.
Рассмотрим два алфавита, и пусть U — универ-
универсальна для частично рекурсивных функций, переводя-
переводящих слова из первого алфавита в слова из второго,
т. е. U(n, a)=b, если функция с гёделевским номе-
номером п, будучи применена к аргументу а, дает значе-
значение Ь.
Для данной частично рекурсивной функции F(n, a)
мы можем найти натуральное число f, называемое не-
неподвижной точкой, такое, что F(f, a)= b тогда и толь-
только тогда, когда U(f, а) = Ь.
Рассмотрим сначала вопрос о нахождении какой-
нибудь функции U, имеющей свойство, сформулиро-
сформулированное в теореме. Очевидный путь решения состоит
в рассмотрении универсальной функции V для частич-
частично рекурсивных функций от двух переменных и извле-
извлечении диагональной функции. Таким образом,
V(m, га, а)=Ь, если функция с гёделевским номером
m и аргументами га, а принимает значение Ь, и мы
утверждаем, что V(ra, га, а) подходит в качестве функ-
функции U из формулировки теоремы. Действительно, вы-
вычислим гёделевский номер f функции F. Тогда
Г(п,а)= V(f,n,a), так что F(f,a)=V(f,f,a), что и
требовалось.
Остается показать, что и сама U обладает этим
свойством. Пусть S (m, га) есть гёделевский номер
сечения функции V в т, га, так что V(m, га, а) =.
= U(S (m, п) ,а). Существование такой общерекурсив-
общерекурсивной функции S следует из теоремы об итерации, кото-
которая несколько отлична от уже сформулированных
нами, но доказывается точно тем же путем. Рассмот-
Рассмотрим вспомогательную функцию G(ra, a) = F(S(n, га), а)
и вычислим ее гёделевский номер g. Тогда f = S(g, g)
38
Гл. 1. Рекурсивные функции
ГЛАВА 2
и есть искомая неподвижная точка, так как
F (/, а) - F (S (g, g), a) = G (g, a) = V (g, g, a) =
= U(S(g, g), a) = U(f, a).
Теорему о неподвижной точке можно понимать
следующим образом. Допустим, что при определении
значения, которое некоторая частично рекурсивная
функция должна принять для некоторого аргумента,
мы ссылаемся не только на этот аргумент, но и на
гёделевский номер функции, которую собираемся оп-
определить. Точнее, величина функции для аргумента а
будет равна F(n, а), где п — гёделевский номер самой
функции, a F — данная частично рекурсивная функ-
функция. Такое определение имеет непредикативный ха-
характер, и не сразу ясно, что можно заставить некото-
некоторую частично рекурсивную функцию удовлетворять
ему. Теорема Клини о неподвижной точке говорит
нам, что это тем не менее так. Действительно", при
несколько некорректной записи функция f(a) =
= F(f,a) = U(f,a) имеет все требуемые свойства.
Соответствующая теорема для рекурсивно перечис-
перечислимых множеств известна как теорема Майхилла о
неподвижной точке.
Для данного рекурсивно перечислимого отношения
R между натуральными числами и словами в данном
алфавите мы можем найти неподвижную Точку f, та-
такую, что fRa тогда и только тогда, когда fUa, где U —
универсальное отношение.
Доказательство во всех деталях аналогично толь-
только что приведенному.
Пример. Чтобы найти натуральное число f, кото-
которое является гёделевским номером рекурсивно пере-
перечислимого множества с единственным элементом f,
достаточно применить теорему Майхилла о неподвиж-
неподвижной точке к отношению равенства R между натураль-
натуральными числами. Заметим, что уже в этом простом слу-
случае не ясно, как найти / без обращения к теореме о
неподвижной точке.
ЭЛЕМЕНТАРНЫЙ КОНСТРУКТИВНЫЙ АНАЛИЗ
12. Окрестности, аппроксимации
и конструктивные точки
Окрестности на вещественной прямой будут син-
синтаксическими выражениями вида а, Ь, где а и b —
рациональные числа, такие, что а <.Ь. (Арифметика
и отношения порядка между рациональными числами
разрешимы, и мы будем их использовать без дальней-
дальнейших пояснений.) Например,
-I/Ill. II/IIIII
есть окрестность. Окрестность I = а,Ь тоньше, чем
окрестность / = c,d, если с <а<.Ь <. d. /и/ отде-
отделены, если b < с или d <Са.
Если аи Ь{ является окрестностью на веществен-
вещественной прямой для i = 1, ..., п, то Oi, b\ X ... Хап, Ьп —
окрестность в п-мерном евклидовом пространстве.
I = аи Ь\ X • • • X #п, Ь„ тоньше, чем J = с\, diX---
... X сп, dn, если С{ < п{ < bi < di для любого i =
г= 1, ..., п. I отделена от /, если аи Ь{ отделена от
с,-, di для некоторого t = 1, ..., п.
В пространстве Кантора мы берем в качестве
окрестностей все конечные цепочки знаков 0 и |.
/ = d[d2 ... dft тоньше, чем / = 6162... ей если k ^ I
и d\ = в\, ..., di = ей I и / отделены, если dt=?e{
для некоторого i *C min (k, I).
Окрестность в бэровском пространстве — это ко-
конечная последовательность натуральных чисел, пи п2,
..., щ, разделенных запятыми. Натуральное число /
называется длиной этой окрестности. ? — единствен-
единственная окрестность, для которой 1 = 0. Отношения отде-
ленности и «быть тоньше» определяются в бэровском
пространстве точно так же, как в канторовском.
40
Гл. 2. Элементарный конструктивный анализ
12. Окрестности и аппроксимации
41
В канторовском и бэровском пространствах любые
две окрестности либо отделены, либо одна из них
тоньше другой.
Применяя терминологию Лакомба [1], мы будем
называть рекурсивно перечислимое множество а
окрестностей аппроксимацией, если оно удовлетворяет
следующим двум условиям. Мы предпочитаем гово-
говорить, что / есть окрестность (аппроксимации) а, вме-
вместо того чтобы говорить, что / принадлежит рекурсив-
рекурсивно перечислимому множеству а.
1 Если / тоньше / и / есть окрестность а, то / есть
окрестность а.
2 Если / и / — окрестности а, то мы можем найти
окрестность а, которая тоньше / и /.
Окрестности погружаются в аппроксимации путем
сопоставления окрестности / множества всех окрест-
окрестностей /, таких, что / тоньше /.
Аппроксимации могут быть рекурсивно перечис-
перечислены.
Точнее, мы построим рекурсивно перечислимое от-
отношение О между натуральными числами и окрестно-
окрестностями, такое, что для любого п сечение U числом п
есть аппроксимация и любая аппроксимация может
быть получена таким образом.
Доказательство для вещественной прямой. Аппрок-
Аппроксимация — это по определению рекурсивно перечисли-
перечислимое множество слов в четырехбуквенном алфавите
| — /, удовлетворяющее двум приведенным выше ус-
условиям. Мы уже построили рекурсивную нумерацию
всех перечислимых множеств слов в этом алфавите.
Таким образом, достаточно описать рекурсивную про-
процедуру, превращающую любое такое множество в ап-
аппроксимацию и оставляющую неизменными те рекур-
рекурсивно перечислимые множества, которые уже удовле-
удовлетворяют этим двум условиям.
Итак, возьмем произвольное рекурсивно перечис-
перечислимое множество слов в рассматриваемом алфавите
и будем порождать его элементы /о, h /„,... в
определенном порядке. Для любого натурального п,
если . /о, 1\, ..,, 1п все являются окрестностями и
/= /о Л Л Л ... Л /п непусто, то модифицированное
множество должно содержать все окрестности /, та-
такие, что / тоньше, чем /. Если модифицированное мно-
множество определено таким образом, то ясно, что оно —
аппроксимация и что множество, которое уже удовле-
удовлетворяет определяющим условиям для аппроксимации,
не изменяется процедурой модификации. Доказатель-
Доказательство закончено.
Аппроксимация а называется максимальной, если
для любой пары окрестностей / и /, таких, что / тонь-
тоньше /, либо / отделена от некоторой окрестности а,
либо / есть окрестность а. Максимальные аппрокси-
аппроксимации образуют конструктивные точки рассматривае-
рассматриваемого пространства.
Пространства, введенные до сих пор, допускают
естественное вычисление диаметров окрестностей.
Обозначая диаметр окрестности / через d(l), мы по-
полагаем
1 = а,Ь
I = al,bl X •• • Х^иА
d(I)= max (bi— at)
et
Пи
Щ
Аппроксимация максимальна тогда и только то-
тогда, когда она содержит окрестности произвольно ма-
малого диаметра.
Доказательство для вещественной прямой. Доста-
Достаточность. Пусть I — а,Ь тоньше I = c,d. Найдем
окрестность рассматриваемой аппроксимации с диа-
диаметром, меньшим min(a — с, d — b). Она должна быть
либо отделена от /, либо быть тоньше /.
Необходимость. Максимальная аппроксимация на-
наверняка имеет хотя бы одну окрестность. Поэтому до-
достаточно показать, что если a, b — такая окрестность,
то такова же a,(a-j-2b)/3 или Ba-\-b)/3,b. Во-пер-
Во-первых, мы можем найти окрестность с, d нашей аппро-
аппроксимации, которая тоньше а, Ь. Затем мы можем при-
применить условие максимальности к с, Bа-\-ЗЪ)/Ъ и
42
Гл. 2 Элементарный конструктивный анализ
13. Парадокс Ришара и чеперечислимость континуума 43
а, (а + 26)/3, а также к (За + 26)/5, d и Bа + Ь)/3, Ь.
Обе окрестности с,Bа + 36)/5 и (За+ 26)/5, d не мо-
могут быть отделены от некоторых окрестностей из ап-
аппроксимации, так как отсюда следовало бы то же
для с, d. Следовательно, либо а, (а + 26)/3, либо
Bа + 6)/3, 6 является окрестностью нашей аппрокси-
аппроксимации.
Пусть а и 6 — две конструктивные точки. Введем
следующие определения.
а = 6, если любая окрестность а налегает на лю-
любую окрестность 6.
аФ 6, если можно найти окрестность а и окрест-
окрестность Ь, которые отделены.
Мы покажем, что две конструктивные точки рав-
равны в смысле приведенного определения тогда и толь-
только тогда, когда они равны как рекурсивно перечисли-
перечислимые множества.
Две конструктивные точки равны тогда и только
тогда, когда они имеют одни и те же окрестности.
Доказательство для канторовского и бэровского
пространств. Необходимость. Допустим, что а = 6, и
пусть / — окрестность а. Так как а — максимальная
аппроксимация и / не отделена от окрестности 6, то /
является в действительности окрестностью 6. По сим-
симметрии, любая окрестность 6 есть также окрестность
а. Достаточность этого условия очевидна.
Под последовательностью аппроксимаций мы по-
понимаем рекурсивно перечислимое отношение А ме-
между натуральными числами и окрестностями, такое,
что сечение А в п есть аппроксимация (которую мы
обозначим через ап) для любого п = 0, 1, ... .
Последовательность аппроксимаций
а0, а1( ..., а„, ...
сходится к аппроксимации а, если для любой окрест-
окрестности / аппроксимации а мы можем найти настолько
большое N, что / есть окрестность а„ для всех n ^ N.
Любая последовательность аппроксимаций сходится
к пустой аппроксимации. Если последовательность
сходится к двум максимальным аппроксимациям, то
они обязательно равны. Последовательность аппро-
аппроксимаций называется сходящейся, если мы-можем
найти максимальную аппроксимацию, к которой она
сходится.
Мы будем говорить, что последовательность ап-
аппроксимаций
а0, Oj, ..., ап, ...
есть последовательность Коши, если для любых
окрестностей / и /, таких, что / тоньше /, мы можем
найти N и доказать, либо что / есть окрестность ап
для всех n ^ N, либо что / отделена от некоторой
окрестности, общей для всех ап при п ^ N. Так как
мы провели диаметризацию окрестностей в рассмат-
рассматриваемых пространствах, определение последователь-
последовательности Коши можно несколько упростить. Достаточно
потребовать, чтобы для любого m мы могли найти
окрестность / и натуральное число N, такие, что
d(I)*g: 2~m и / есть окрестность ап для всех n ^ N.
Последовательность аппроксимаций сходится то-
тогда и только тогда, когда она — последовательность
Коши.
Доказательство для канторовского и бэровского про-
пространства. Необходимость этого условия очевидна,
поэтому допустим, что ао, ci\ ... — последователь-
последовательность Коши. Это значит, что для любой окрестности
/ мы можем найти # и доказать, что либо / есть
окрестность а„ для всех n > N, либо / отделена от
окрестности, общей всем ап для п > N. Пусть а со-
состоит из всех окрестностей /, для которых решено,
что имеет место первый случай. Тогда, как легко про-
проверить, а — максимальная аппроксимация, к которой
последовательность сходится.
13. Парадокс Ришара
и неперечислимость континуума
Рассмотрим вещественные числа, которые могут
быть определены конечным множеством слов русско-
русского языка. Определение такого числа — это цепочка
44
Гл 2. Элементарный конструктивный анализ
13. Парадокс Ришара и неперечислимость континуума 45
букв из алфавита
а,б,...,я, . ! ? 1 2 ... 9,
содержащего около пятидесяти букв. Все такие це-
цепочки могут быть перечислены одна за другой, на-
например, в лексикографическом порядке. Удалим из
этого списка каждую цепочку, не являющуюся осмыс-
осмысленным предложением русского языка, определяю-
определяющим вещественное число. Пусть ао, а\, ... обозначают
числа, определяемые остающимися предложениями,
взятыми в том порядке, в котором они стоят. Каждое
из них может быть разложено в десятичную дробь
5, если dkk^4,
4, если
Теперь положим
и определим вещественное число а разложением
a = Q.dadi ... dk ... .
Это число было определено конечным числом слов, а
именно теми словами из этого пункта, которые были
до сих пор написаны. Тем не менее оно не содержит-
содержится в приведенной выше нумерации всех чисел, опре-
определимых конечным множеством слов. Это парадокс
Ришара [1].
Этот парадокс был частично объяснен самим Ри-
Ришаром, который заметил, что определение критиче-
критического числа а носит непредикативный характер. Дей-
Действительно, определяя а конечным числом слов, мы
ссылаемся на совокупность всех чисел, определимых
конечным числом слов. Более глубокий анализ был
дан Борелем [1]. Он указал, что процесс выбрасыва-
выбрасывания тех цепочек символов, которые не определяют
вещественных чисел, не может быть проведен эффек-
эффективно и множество всех вещественных чисел, опре-
определимых конечным числом слов, не является эффек-
эффективно перечислимым, хотя оно и счетно в теоре-
теоретико-множественном смысле, будучи подмножеством
счетного множества всех слов в конечном алфавите.
Этот пример показывает, как заметил Борель, что
классическая теорема о счетности подмножества счет-
счетного множества не имеет места, если счетность заме-
заменить эффективной перечислимостью.
Мы сейчас используем рассуждение из парадокса
Ришара для доказательства того, что конструктивные
точки континуума не могут быть эффективно пере-
перечислены. Это конструктивная версия знаменитой тео-
теоремы Кантора.
Если дана последовательность конструктивных то-
точек ао, а\, ..., as, ..., мы можем найти конструктив-
конструктивную точку а, такую, что а^Ф а для всех k = 0, 1, ... .
Допустим, что
а0
— последовательность конструктивных точек канто-
ровского пространства. Полагая е\ = 1 — е^ъ мы по-
получаем конструктивную точку
а = eoet ... е* ... ,
которая отличается от а?, для всех k = 0, 1, ... .
46
Гл. 2. Элементарный конструктивный анализ
14. Вычислимые вещественные числа
47
В бэровском пространстве для данной последова-
последовательности конструктивных точек
мы строим новую точку
где nh = nhh+ 1.
Наконец допустим, что дана последовательность
конструктивных точек а0, а\, ..., аи, ... на вещест-
вещественной прямой. Пусть /о — окрестность а0, и выберем
/о, отделенную от Jo, такую, что d(/o)^ 1. Допустим,
что уже определена h-i- Найдем окрестность /* точ-
точки aft с d(Jh)<. d(Jh-i), а затем /ft, более тонкую, чем
Ih-u и такую, что d(Ih) < 2~ft и U отделена от /*,. По-
Последовательность /о, 1\, ..., /л сходится к конструк-
конструктивной точке а, которая обладает искомым свойством
аиФ а для всех k. Для многомерного евклидова про-
пространства доказательство то же самое.
14. Вычислимые вещественные числа
Конструктивная точка на вещественной прямой
будет называться вычислимым вещественным чи-
числом.
Рациональные числа можно естественным обра-
образом вложить в конструктивные вещественные числа.
Рациональному числу г = plq мы сопоставляем ре-
рекурсивно перечислимое множество всех окрестностей
I = а,Ь, таких, что а < г < 6. Вычислимое вещест-
вещественное число называется рациональным, если мы мо-
можем найти равное ему рациональное число. Оно ир-
иррационально, если для любого рационального числа
г = plq мы можем найти его окрестность / = а, Ь,
такую, что г <а или b <.г.
Примерами вычислимых иррациональных чисел
являются У% е и п. Y2 можно определить как рекур-
рекурсивно перечислимое множество всех рациональных
интервалов I = а,Ь, таких, что или а < 0 или а2 < 2
и b > 0 и Ь2 > 2. Чтобы определить е и п, можно ис-
использовать обычные разложения в ряды
р— 1_|_ — U — U— U
е~1Т II Т21 Т31 т '" *
Эти ряды имеют смысл, так как частичные суммы
являются даже рациональными числами, и легко про-
проверить, что они конструктивно сходятся.
Отношения порядка между вычислимыми веще-
вещественными числами вводятся следующим образом.
а <Ь, если мы можем найти окрестность / точки
а и окрестность / точки Ь, такие, что правый конец /
меньше левого конца /.
а ^ Ь, если для всех окрестностей / точки аи/
точки b левый конец / меньше, чем правый конец /.
Теперь очевидны следующие эквивалентности:
афЬ тогда и только тогда, когда а<Ь или а > Ь.
а = Ь тогда и только тогда, когда а^.Ь и а^ Ь.
Первое определение понятия вычислимого веще-
вещественного числа было дано Тьюрингом [2]. Согласно
ему, вещественное число вычислимо, если оно может
быть представлено в виде
г=1
где бинарная последовательность
/ II ¦ • • 1 0 с, с2 ... сг ...
п
вычислима на машине Тьюринга. Разумеется, с кон-
конструктивной точки зрения вычислимое вещественное
число есть не что иное, как сама машина Тьюринга.
48
Гл. 2. Элементарный конструктивный анализ
15. Результаты о неразрешимости
49
Если последовательность i ||... | ОС1С2... сг... вы-
вычислима на машине Тьюринга, то она рекурсивна
и потому определяет вычислимое вещественное число
в смысле нашего определения. Обратно, данное вы-
вычислимое вещественное число нетрудно представить
в указанном выше виде посредством рекурсивной би-
бинарной последовательности. Чтобы завершить доказа-
доказательство эквивалентности нашего и тьюринговского
определений, достаточно таким образом показать, что
любая рекурсивная бинарная последовательность вы-
вычислима на машине Тьюринга. Как замечено в связи
с тезисом Чёрча, это действительно так, хотя мы и не
прилагали усилий, чтобы доказать это.
15. Результаты о неразрешимости
для вычислимых вещественных чисел
Тьюринг [1] сначала ввел определение вычисли-
вычислимого вещественного числа как такого числа, для ко-
которого на машине Тьюринга вычислимо двоичное
разложение его дробной части. Но, как он скоро по-
понял, нет способа вычислять двоичное разложение лю-
любого конструктивного вещественного числа в смысле
нашего определения. Именно этот факт заставил за-
заменить исходное определение на приведенное в пре-
предыдущем пункте и использующее налегающие интер-
интервалы вместо прилегающих. Невозможность вычисле-
вычисления десятичного разложения любого вещественного
числа была впервые осознана Брауэром [4], и исполь-
использование налегающих интервалов восходит к нему.
Мы докажем сначала несколько более слабый ре-
результат, имеющий место для всех рассматриваемых
нами пространств.
Невозможно распознать для любых двух кон-
конструктивных точек а и Ь, верно ли а = Ь или аФЬ.
Доказательство для канторовского пространства.
Рассмотрим диагональное множество D, которое ре-
рекурсивно перечислимо, но не рекурсивно, и положим
^ = 0 или 1 в зависимости от того, является ли п
номером доказательства пг в D, т. е. в символике п. 8.
Г 1, если mVn и W(ri) = m,
mn I 0 в противном случае.
Пусть 0 обозначает точку канторовского простран-
пространства, все знаки которой равны нулю, и положим
ат == етФт\ • • • ^тп • • •
для т = 0, 1 Тогда meD или т ф. D в зависи-
зависимости от того, что имеет место: ат Ф О или ат = 0.
Поэтому если бы мы могли решить для любого т,
что имеет место ат Ф 0 или ат = 0, то D было бы
разрешимо, что дает противоречие.
Нет алгорифма, который для любого вычислимого
вещественного числа а говорит нам, что имеет место:
а^.0 или а > 0.
По аналогии с предыдущим доказательством мы
полагаем
m 2j тп ,
так что ат ^ 0 или ат > 0 в зависимости от того,
тфй или neD, Таким образом, мы имели бы раз-
разрешающую процедуру для D, если бы могли дока-
доказать либо a ssc 0, либо а > 0 для любого вычислимого
вещественного числа.
Невозможен алгорифм, вычисляющий необрываю-
щееся десятичное разложение любого вычислимого
вещественного числа.
Разумеется, эта теорема, принадлежащая Тью-
Тьюрингу [2], имеет место также, если выбрать любое
основание системы счисления, отличное от 10. До-
Допустим, что имеется алгорифм разложения любого
вычислимого вещественного числа в десятичную
дробь:
ft=0
\ n = 0, ±1
= 0, 1, ...,
50
Гл. 2. Элементарный конструктивный анализ
15. Результаты о неразрешимости
такую, что dh > 0 для бесконечно многих k. Тогда
а ^ О или а > 0 в зависимости от того, п ^ —1 или
п^О, так что мы имеем противоречие с предыдущей
теоремой.
Теперь мы покажем, что невозможно вычисление
какого бы то ни было обрывающегося или нет деся-
десятичного разложения любого вычислимого веществен-
вещественного числа. Это — простое следствие теоремы, кото-
которую можно найти, например, у Цейтина [1].
Нет рекурсивной процедуры, которая доказыва-
доказывала бы либо а ^ 0, либо а ^ 0 для любого вычисли-
мого вещественного числа а.
Пусть А и В — два дизъюнктных рекурсивно пере-
перечислимых множества натуральных чисел, которые не
могут быть рекурсивно отделены. Свяжем с А обще-
общерекурсивную функцию /, определенную соотношением
( 1, если п есть номер доказательства tn в А,
1 0 в противном случае.
Соответствующим образом В определяет общере-
общерекурсивную функцию g. Допустим теперь, что сущест-
существует общерекурсивная процедура, упомянутая в тео-
теореме, и применим ее к вычислимым вещественным
числам
— fmnJ~n, m = 0, 1,... .
n=0
Пусть C(D) состоит из тех чисел т, для которых мы
решили, что ат ^ 0 (ат ^ 0). Тогда С и D образуют
рекурсивное отделение для А н В, так как изтеД
(т^В) следует ат < 0 (ат>0), так что те. С
(т е D). Мы пришли к противоречию.
Не существует алгорифма, вычисляющего деся-
десятичное разложение любого вычислимого веществен-
вещественного числа.
Если бы мы могли вычислить десятичное разло-
разложение
любого вычислимого вещественного числа а, то, оп-
определив п^—1 или tt ^ 0, мы могли бы доказать
либо а ^ 0, либо а ^ 0. Это противоречит предыду-
предыдущей теореме.
Рассмотрим следующее рассуждение, использую-
использующее закон исключенного третьего. Пусть дано про-
произвольное вычислимое вещественное число. Если оно
десятично рационально, то оно очевидным образом
имеет десятичное рекурсивное разложение. Далее,
если оно не является десятично рациональным, то мы
можем определить любой знак его десятичного раз-
разложения, просто вычисляя его с достаточной точ-
точностью. Так как вычислимое вещественное число
либо является десятично рациональным, либо не яв-
является, мы заключаем отсюда, что любое вычислимое
вещественное число имеет рекурсивное десятичное
разложение. С другой стороны, мы только что дока-
доказали, что это утверждение ложно, если его интерпре-
интерпретировать конструктивно. Это показывает, что (как
было впервые отмечено в п. 7) неосторожное исполь-
использование закона исключенного третьего может вести
к заключениям, не являющимся конструктивно
истинными.
Брауэр [4] и [8] классифицировал вычислимые ве-
вещественные числа согласно возможности установить
их положение относительно рациональных чисел, из
которых они получены пополнением.
Вычислимое вещественное число без всякой даль-
дальнейшей информации называется элементом (попол-
(пополнения) нулевого порядка.
Если, кроме того, для любого рационального чис-
числа г может быть доказано либо г ^ а, либо г ^ а, то
а называется элементом первого порядка.
Элемент а первого порядка, для которого г ^ а
может быть доказано или опровергнуто при любом
рациональном г, называется элементом второго по-
порядка.
Если мы можем решить для любого рационально-
рационального г, верно ли г<о или г > а, то а называется эле-
элементом третьего порядка.
Гл. 2. Элементарный конструктивный анализ
17 Открытые и замкнутые чножества
53
Наконец, если для любого рационального г мы
можем решить, верно ли г < а, г = а или г > а, то а
называется элементом четвертого порядка, или, в
терминологии Гейтинга [1], респектабельным веще-
вещественным числом.
Когда мы погружаем рациональное число в вы-
вычислимые вещественные числа, мы, очевидно, полу-
получаем элемент четвертого порядка. Также и иррацио-
иррациональное число автоматически имеет четвертый по-
порядок.
Мы показали выше, что нет рекурсивного метода,
позволяющего хотя бы доказывать а ^ 0 или а ^ О
для любого вычислимого вещественного числа а, и
поэтому мы никогда не сможем сказать, что любое
вычислимое число есть элемент первого порядка.
Всегда будут числа вроде эйлеровой константы С,
о которых мы сможем сказать лишь, что они нуле-
нулевого порядка. В процессе развития математики, разу-
разумеется, может случиться, что мы сможем доказать,
что некоторые из них имеют более высокий порядок,
но всегда можно будет найти новые, для которых это
еще не показано.
16. Последовательность Шпеккера
Шпеккер [1949] построил пример, показывающий,
что теорема о монотонной сходимости ложна при
конструктивной интерпретации.
Существует рекурсивная последовательность ра-
рациональных чисел
0<а0<а1< ... <а„< ... < I,
которая не сходится.
Пусть / — общерекурсивная функция, перечисляю-
перечисляющая без повторений диагональное множество D. По-
Полагая
мы, очевидно, имеем
<ап<
Допустим, что ап сходится при п->оо. Это значит,
что мы нашли общерекурсивную функцию N(m), та-
такую, что
-,—m—l
n>N(m).
/№=0
Это последнее соотношение влечет за собой f(n) > m
для п > N(m). Следовательно, яей тогда и только
тогда, когда f(m)=n для некоторого п = 0, 1, ...
..., N(m). Таким образом, мы имели бы разрешаю-
разрешающую процедуру для D, что невозможно. Эта кон-
конструкция принадлежит Раису [1].
Ограниченная монотонная последовательность вы-
вычислимых вещественных чисел, которая не сходится,
будет называться шпеккеровой последовательностью.
Конструктивная точка а называется точкой сгу-
сгущения последовательности конструктивных точек по,
аи ..., ап, ..., если для любой окрестности / точки а
и любого натурального N мы можем найти п^ N,
такое, что / есть окрестность ап.
Последовательность Шпеккера доставляет нам
также контрпример к теореме Больцано — Вейер-
штрасса. Действительно, если бы мы могли найти
точку сгущения шпеккеровой последовательности, то
эта последовательность обязательно сходилась бы к
ней, что невозможно.
17. Открытые и замкнутые множества
Открытое множество (Брауэр [3] использует тер-
термин Bereich) — это рекурсивно перечислимое множе-
множество G окрестностей, удовлетворяющее следующим
двум условиям.
1 Если / тоньше / и / принадлежит G, то / при-
принадлежит G.
2 Если / принадлежит G, то мы можем найти /
в G, такое, что / тоньше /.
54
Гл. 2. Элементарный конструктивный анализ
18. Теорема Гейне — Бореля о покрытиях
55
Среди открытых множеств имеется пустое множв'
ство 0 и множество всех окрестностей, которое мы
обозначим через X и назовем всем пространством.
Окрестности погружаются в открытые множества
путем сопоставления окрестности / множества всех
окрестностей /, которые тоньше /.
aeG, где а — конструктивная точка и G — от-
открытое множество, если некоторая окрестность а при-
принадлежит рекурсивно перечислимому множеству G.
аф G, если любая окрестность а не принадлежит
рекурсивно перечислимому множеству G.
Если А и В — открытые множества, то Л Л В и
A U В определяются просто как пересечение и объеди-
объединение А и В, рассматриваемых как рекурсивно пере-
перечислимые множества.
Последовательность открытых множеств — это ре-
рекурсивно перечислимое отношение между натураль-
натуральными числами и окрестностями, такое, что для лю-
любого п = 0, 1, ... сечение этого отношения в п есть
открытое множество Gn. Объединение \jGn — это
объединение Go, G\, ..., Gn, ¦ • •, рассматриваемых
как рекурсивно перечислимые множества, т. е. об-
область значений этого отношения.
Существует рекурсивная нумерация открытых
множеств.
Это значит, разумеется, что мы можем построить
последовательность открытых множеств, обладаю-
обладающую свойством, что всякое открытое множество
встречается в этой последовательности. Доказатель-
Доказательство параллельно доказательству теоремы о перечис-
перечислении для аппроксимаций.
В евклидовом пространстве (в частности, на ве-
вещественной прямой] и в канторовом пространстве мы
можем, ввиду локальной компактности, нормализо-
нормализовать определение открытого множества, наложив еще
одно условие чисто комбинаторного характера.
3 Если / тоньше, чем I\ U h U . .. U ln и 1\, /2, ...
..., /„ принадлежат G, то / принадлежит G.
В канторовском пространстве это условие можно
сформулировать проще, сказав, что если две окрест-
окрестности /О и /| принадлежат G, то / должна принад-
принадлежать G '). Заметим, что соответствующее условие
для бэровского пространства требовало бы, что-
чтобы / принадлежала G, если /, п принадлежит G для
всех п = О, 1, ... . Это уже не комбинаторное усло-
условие, а правило с бесконечным числом посылок, чем
и объясняется тот факт, что экстенсиональная интер-
интерпретация открытых множеств в бэровском простран-
пространстве требует трансфинитной индукции и должна быть
отложена до следующей главы.
После наложения третьего условия мы можем
определить отношения включения и равенства между
двумя открытыми множествами Л и Б в евклидовом
или канторовском пространстве.
A s В, если А содержится в В, когда они рас-
рассматриваются как рекурсивно перечислимые множе-
множества.
А = В, если ЛдВиВеД.
Если G — открытое множество, заданное, скажем,
своим гёделевским номером, то CG — замкнутое мно-
множество2) (Брауэр [4] говорит Bereichkomplement).
Теоретико-множественные операции и отношения ме-
между замкнутыми множествами определяются по
двойственности. Остается определить только отноше-
отношение включения между двумя множествами, одно из
которых открыто, а другое замкнуто, причем случай
бэровского пространства все еще исключается.
А = СВ, где А и В открыты, означает, что А Л В =
= 0 СЛ д= В, если A U В = X.
18. Теорема Гейне—Бореля о покрытиях
Замкнутое множество F на вещественной пря-
прямой ограничено, если мы можем найти натуральное
') При наложении условия 3 следует естественным образом
изменить определение объединения открытых множеств, чтобы
обеспечить выполнение этого условия у суммы множеств: именно
,.„ хО х\Вх п
поэтому в таблице на стр. 56 добавлена схема !—. — Прим.
ред.
2) Здесь С следует рассматривать не как обозначение опера-
операции, а как формальный символ, поставленный перед гёделевским
номером G. — Прим. ред.
66
Гл. 2. Элементарный конструктивный анализ
19. Локализованные замкнутые множества
57
число п, такое, что F содержится в замкнутом интер-
интервале от — п до п. Определение для евклидова про-
пространства аналогично. Ограниченное замкнутое мно-
множество в евклидовом пространстве, а также любое
замкнутое множество в канторовском пространстве
называются компактными.
Пусть F — компактное множество, и допустим, что
F<=()Gn,
П=0
где Go, G\, ... — последовательность открытых мно-
множеств. Тогда можно найти натуральное N, такое, что
U
Л=0
Доказательство для канторового пространства. По
предположению, F = С G, где G открыто и
U
п=0
Система Поста, определяющая левый член, со-
состоит из отмеченных схем для G, схем для последо-
последовательности Go, Gi, .... отмеченных, например, сим-
символом S, и новых схем
N
Nx
Nx\
В
Вх
ВхО
Вх
Вх Gx
хО х\ Вх Sxy Nx By
X ' У
Любая окрестность, в частности П, порождается
этой системой Поста. Пусть N — максимум натураль-
натуральных чисел, подставленных вместо х в тех примене-
применениях последней схемы, которые входят в доказатель-
доказательство D. Тогда, очевидно,
U
так что
U
что и требовалось доказать.
Конструктивная форма теоремы Гейне — Бореля
была найдена Брауэром в [9]. Он доказал ее как след-
следствие теоремы о веерах для так называемых локали-
локализованных компактных видов (Katalogisiertkompakte
Species). Предположение локализованности (понятие
локализованности будет введено в следующем раз-
разделе) излишне, по крайней мере в случае, если при-
принята наша интерпретация интуиционистских понятий.
19. Локализованные замкнутые множества
Пусть G — открытое множество в канторовом про-
пространстве. Мы скажем, что замкнутое множество CG
локализовано и что G дополнительно локализовано,
если мы можем решить для любой окрестности /, вер-
верно ли, что / принадлежит G.
Для евклидова пространства определение лишь
технически сложнее. CG локализовано, если мы мо-
можем найти рекурсивно перечислимое множество
окрестностей F, которое дизъюнктно с G и таково,
что для любой пары окрестностей / и /, если / тонь-
тоньше /, то либо / принадлежит G, либо / принадлежит
F. Без ограничения общности можно считать, что F
удовлетворяет следующим двум условиям, двой-
двойственным условиям, определяющим открытое, мно-
множество.
1 Если / тоньше / и / принадлежит F, то / при-
принадлежит F.
2 Если / принадлежит F, то мы можем найти
в F окрестность /, более тонкую, чем /.
Наконец, замкнутое множество CG в бэровском
пространстве локализовано, если мы можем найти
рекурсивно перечислимое множество окрестностей F,
дизъюнктное с G и такое, что любая окрестность /
принадлежит либо F, либо G, и если / принадлежит
58
Гл 2 Элементарный конструктивный анализ
20. Внутренние и внешние предельные множества
59
F, то мы можем найти натуральное число п, такое,
что /, п также принадлежит F. Локализованное замк-
замкнутое множество в бэровском пространстве опреде-
определяет закон потока в терминологии Рейтинга [1]. Эле-
Элементы F и G называются соответственно допустимы-
допустимыми и недопустимыми относительно закона потока.
Если замкнутое локализованное множество непу-
непусто, то мы можем найти в нем конструктивную точку.
Доказательство для канторовского пространства.
Локализованность CG означает разрешимость G.
Пусть F — множество всех окрестностей, не принад-
принадлежащих G. Сначала мы можем найти во = 0 или |
в F, так как если бы и 0 и | принадлежали G, то П
тоже принадлежала бы G, и F было бы пусто. Тем же
рассуждением мы можем определить е\, такое, что
еое\ принадлежит F, и так далее. Таким образом, мы
последовательно определяем знаки некоторой кон-
конструктивной точки в CG.
Объединение двух локализованных множеств ло-
локализовано.
Мы должны доказать, что пересечение двух до-
дополнительно локализованных открытых множеств
снова дополнительно локализовано. Это непосред-
непосредственно очевидно в канторовом пространстве, напри-
например, ввиду того что пересечение двух открытых мно-
множеств — это просто пересечение этих двух открытых
множеств, рассматриваемых как рекурсивно перечис-
перечислимые множества, а пересечение двух разрешимых
множеств разрешимо.
Существуют два локализованных множества, пе-
пересечение которых не локализовано.
Положим етп = 0 или 1 в зависимости от того,
является ли п номером доказательства т в диаго-
диагональном множестве D, и определим следующую по-
последовательность вычислимых вещественных чисел:
Для любого т пусть Um есть открытый интервал от
Ът — 3 до Ът + ат и Vm— открытый интервал от
Ът — ат до Ът + 3. Легко проверить, что два откры-
открытых множества
i = 2j Zmn*
n=0
Л-п-\
, т — О, 1, ... .
И V=\JVm
дополнительно локализованные. Допустим теперь, что
G = U U V — дополнительно локализованное. Тогда
мы можем для любого т доказать либо
Вт — 1, Вт + 1 принадлежит G,
либо
Вт — 2, Вт + 2 принадлежит F,
где F — то рекурсивно перечислимое множество
окрестностей, которое фигурирует в определении ло-
локализованное™. Но если Ът— 1, 5т + 1 принадле-
принадлежит G, то ат > 0 и m^D, а если Ът — 2, Ът -f 2
принадлежит F, то ат = 0 и т ф. D, так что D было
бы разрешимо. Мы достигли противоречия.
Две последние теоремы в применении к бэров-
скому пространству объясняют, почему, как утвер-
утверждал Брауэр [2] и {7], объединение двух потоков (Men-
gen) есть снова поток, в то время как пересечение
двух потоков — не обязательно поток.
Понятие локализованности замкнутого множества
(katalogisiertes Bereichkomplement) и дополнитель-
дополнительно локализованного открытого множества (komple-
mentar katalogisierter Bereich) принадлежат Брауэру
[3]. Брауэр [2]. и [7] ввел также понятие Gebiet, но
трудно усмотреть различие между понятием Gebiet и
понятием дополнительно локализованного открытого
множества. Сам Брауэр [3] считал, что Gebiet всегда
есть дополнительно локализованное открытое множе-
множество, но не утверждал обратное.
20. Внутренние и внешние предельные множества
Если Go, G\, ..., Gn, ... — последовательность
открытых множеств, то
60
Гл 2 Элементарный конструктивный анализ
20. Внутренние и внешние предельные множества
61
есть внутреннее предельное множество (innere Grenz-
species в терминологии Брауэра [3]), и
есть внешнее предельное множество (aussere Grenz-
species). В данный момент мы должны удовольство-
удовольствоваться рассмотрением C\Gn и \jCGn как чисто сим-
символических выражений, поскольку экстенсиональная
интерпретация внутренних и внешних предельных
множеств требует трансфинитной индукции.
Открытые множества можно тривиально погру-
погрузить во внутренние предельные множества, сопостав-
сопоставляя открытому множеству G внутреннее предельное
множество f\Gn, где Gn = G для всех п = 0, 1
Аналогично замкнутые множества погружаются во
внешние предельные множества. Пусть /0, Л, ...
..., /„, ... — перечисление окрестностей открытого
множества G. Тогда G можно отождествить с внеш-
внешним предельным множеством \jCGn, где Gn — объ-
объединение всех окрестностей., отделенных от /„, и CG
можно отождествить с ПО„.
Внутренние (внешние) предельные множества
очевидным образом замкнуты относительно счетных
(конечных) пересечений и конечных (счетных) объ-
объединений.
не C\Gn, где а — конструктивная точка, если для
любого п мы можем найти окрестность а, которая
принадлежит Gn.
Крайзель и Лакомб [1], а также Заславский и
Цейтин [1] дали пример внутреннего предельного
множества, показывающий, грубо говоря, что кон-
конструктивные точки континуума могут быть покрыты
произвольно малым открытым множеством. Кон-
Конструкция похожа на хорошо известное доказатель-
доказательство того, что множество рациональных чисел имеет
лебегову меру 0. Но в то время, как рациональные
числа могут быть рекурсивно перечислены, это не-
неверно для конструктивных точек. Для доказатель-
доказательства достаточно того, что имеется рекурсивное пере-
перечисление аппроксимаций.
Существует внутреннее предельное множество
ПО„ в канторовском пространстве, которое содержит
все конструктивные точки и обладает тем свойством,
что мера объединения любого конечного числа
окрестностей из Gn меньше 2~п.
Под мерой здесь имеется в виду обычная лебегова
мера, которая сопоставляет любой окрестности
/ = 0||0 ... 0|
п
меру 2~п.
В п. 12 мы построили рекурсивную нумерацию
всех аппроксимаций
Пусть Gn есть объединение всех окрестностей /, та-
таких, что / — окрестность ат и d(I) ^2-m~n-1 для не-
некоторого m = 0, 1, ...'). Конструктивная точка —
это аппроксимация, имеющая окрестности произволь-
произвольно малого диаметра, следовательно, конструктивная
точка должна обязательно принадлежать Gn для
всех л. Кроме того, объединение любого конечного
числа окрестностей из Gn имеет меру
Это завершает доказательство.
Открытое множество G = Go содержит все кон-
конструктивные точки. С другой стороны, G не равно X,
всему пространству. Действительно, из G = X сле-
следовало бы по лемме Гейне — Бореля, что уже конеч-
конечное число окрестностей, объединением которых яв-
является G, покрывало бы X. Это противоречит тому
факту, что мера объединения любого конечного чис-
числа окрестностей из G меньше 1. Мы доказали сле-
следующую теорему, принадлежащую Клини [2].
') Подразумевается, что / включается в Gn с «анализом», от
какого ат она произошла, и для каждого m в Gn имеется не
более одной окрестности с анализом ат. — Прим. перев.
62
Гл. 2. Элементарный конструктивный анализ
22. Частично рекурсивные функционалы
63
Существует открытое множество G ф X, содер-
содержащее все конструктивные точки, и двойственным об-
образом замкнутое множество F Ф 0, не содержащее ни
одной конструктивной точки.
В качестве побочного результата мы получаем
пример замкнутого множества, которое не локализо-
локализовано. Действительно, если бы замкнутое множество
F ф0, упоминаемое в теореме, было локализовано,
то мы могли бы найти в нем конструктивную точку.
В классической математике континуум восприни-
воспринимается как совокупность своих точек. Поэтому можно
было бы попытаться, как Марков и его школа, кон-
структивизировать теорию континуума, рассматривая
его как совокупность его конструктивных точек. Это
ведет, как показывает теорема Клини, к теории, ра-
радикально отличной от теории Брауэра.
21. Теорема Бэра о (множествах первой) категории
Открытое множество G плотно, если для любой
окрестности / мы можем найти более тонкую окрест-
окрестность /, принадлежащую G. Внутреннее предельное
множество C\Gn плотно, если Gn плотно при лю-
любом п.
Пусть f\Gn— плотное внутреннее предельное мно-
множество. Тогда любая окрестность содержит конструк-
конструктивную точку, принадлежащую C\Gn.
Классическое доказательство уже конструктивно
и не требует модификации. Пусть / — произвольная
окрестность. Так как Go плотно, мы можем найти /о
в Go, которая тоньше / и удовлетворяет d(I0) г?1 1.
Допустим теперь, что /о, h /n-i уже определены,
п~^\. Так как Gn плотно, мы можем найти /„ в Gn,
которая тоньше 1п-\ и удовлетворяет d(In) <; 2~п.
Последовательность /о, h In, ¦•¦ сходится к
конструктивной точке а, которая принадлежит Gn
при любом п. Кроме того, / есть окрестность а.
Приведенное доказательство напоминает доказа-
доказательство неперечислимости конструктивных точек, и
действительно, последний результат — простое след-
следствие теоремы о категории. Точнее, пусть
^0> ^1> • • • i ^Л1 • • •
— вычислимая последовательность конструктивных
точек, и для любого п удалим из всего пространства
точку ап, получая таким образом открытое и плотное
множество Gn. По теореме Бэра, в любой окрестно-
окрестности / мы можем найти конструктивную точку а е
е П Gfy, что и означает в точности а ф ап для всех п.
Другое применение таково. Пусть f]Gn — внутрен-
внутреннее предельное множество на вещественной прямой,
содержащее все рациональные точки. Тогда в любой
окрестности / мы можем найти иррациональное вы-
вычислимое вещественное число aeflGn. Чтобы уста-
установить это, зафиксируем нумерацию рациональных
чисел
Л)> ^1) • • • I ^Л> • • • I
и пусть Нп получится из Gn выбрасыванием точки гп.
Нп все еще открыто и плотно при п = 0, 1 и по-
поэтому в силу теоремы Бэра мы находим в любой
окрестности / вычислимое вещественное число а е
е Г)Нп. Очевидно, что а иррационально и принадле-
принадлежит f]Gn.
22. Частично рекурсивные функционалы
Будет удобно включить множество натуральных
чисел в список рассматриваемых нами пространств.
Мы сделаем это, определив окрестности / просто как
натуральные числа
и положив d(I) = 0. О множестве натуральных чи-
чисел говорят, что оно дискретно.
Частично рекурсивный функционал, отображаю-
отображающий пространство X в пространство У, — это рекур-
рекурсивно перечислимое отношение между окрестностями
в X и окрестностями в У, удовлетворяющее следую-
следующим двум условиям.
64
Гл. 2. Элементарный конструктивный анализ
22. Частично рекурсивные функционалы
65
1 Для любой окрестности / в X /(/) есть аппро-
аппроксимация в У.
2 Для любой окрестности / в У f~l (/) есть откры-
открытое множество в X.
Частично рекурсивные функционалы, отображаю-
отображающие бэровское пространство в себя, рассматриваются
Клини [3].
Эквивалентным образом мы могли бы сначала
ввести окрестности в пространстве X—> У как синтак-
синтаксические выражения вида
где /ь ...,/„ и /ь ...,/„ — окрестности соответ-
соответственно в X и У. Введя также необходимые отноше-
отношения между окрестностями (тонкость и отделенность),
мы могли бы затем определить частично рекурсивный
функционал как аппроксимацию в пространстве
X -*¦ У. С использованием этой формулировки теоре-
теорема о нумерации для частично рекурсивных функцио-
функционалов становится частным случаем теоремы о нуме-
нумерации для аппроксимаций.
Существует рекурсивная нумерация частично ре-
рекурсивных функционалов.
Доказательство совершенно аналогично доказа-
доказательству теоремы о нумерации для аппроксимаций,
данному в п. 12.
Если а — аппроксимация, то f(a)—также аппро-
аппроксимация.
Принадлежность / к f(a) означает, что IfJ для
некоторой окрестности / из а. Если / тоньше J\, то
JfJi, так что /i также принадлежит f(a).
Пусть /i и /г принадлежат f(a). Тогда hfJi и
hfh для некоторых окрестностей 1\ и /2 из а. Так
как а — аппроксимация, имеется окрестность / из а,
которая тоньше 1\ и 1%. Так как f~l(Ji) и /"'(/г) —
открытые множества, то IfJ\ и ///г, а так как /(/) —
аппроксимация, мы можем найти /, более тонкую,
чем /i и /2, такую, что ///. Окрестность /, очевидно,
принадлежит /(а).
Рассмотрим частично рекурсивный функционал,
отображающий пространство X в пространство У,
и пусть /i и /г — две окрестности в У, причем /г
тоньше 1\. Образуем объединение всех окрестностей /,
таких, что IfJ\ или /// для некоторой /, отделенной
от /г. Взяв пересечение всех открытых множеств, по-
полученных таким способом при варьировании J\ и /2,
мы имеем внутреннее предельное множество, которое
будем называть областью (определения) функциона-
функционала f. Если окрестности в У диаметризованы, то об-
область можно определить более обозримым способом
как f]Gn, где Gn—объединение всех окрестностей /,
таких, что /// для некоторого / с d(J) < 2~п. Область
дискретнозначного функционала — открытое множе-
множество.
Если конструктивная точка а принадлежит обла~
сти частично рекурсивного функционала f, то f(a) —-
конструктивная точка.
Доказательство очевидно.
Точно так же, как и в классическом анализе, тео-
теорема о равномерной непрерывности — простое след-
следствие леммы Гейне — Бореля.
Частично рекурсивный функционал, всюду опре-
определенный на компактном множестве, равномерно не-
непрерывен на этом множестве.
Доказательство для отображений канторовского
пространства в себя. Всюду определенность / на ком-
компактном множестве F означает, разумеется, что
F<=<Зп для всех п, где f]Gn — область f. Пусть п —
произвольное натуральное число. Лемма Гейне — Бо-
Бореля позволяет нам найти окрестности I\, h, ..., h,
такие, что
Пусть m определено соотношением
min
66
Гл. 2. Элементарный конструктивный анализ
23. Максимальные рекурсивные функционалы
Тогда для вычисления первых п знаков значения f
на F достаточно знать первые m знаков аргумента.
Последовательность частично рекурсивных функ-
функционалов
/о> /и • • • > /« • • •
сходится к частично рекурсивному функционалу /,
если для любой пары окрестностей / и /, таких, что
If}, мы можем найти настолько большое N, что IfnJ
для всех п^ N. Если рассматривать частично рекур-
рекурсивные функционалы, отображающие пространство
X в пространство У, как аппроксимации в простран-
пространстве X -* У, то это определение сходимости — просто
частный случай определения сходимости аппроксима-
аппроксимаций, данного в п. 12.
Если последовательность частично рекурсивных
функционалов сходится к частично рекурсивному
функционалу, который всюду определен на компакт-
компактном множестве, то сходимость равномерна на этом
множестве.
Это немедленно следует из определения сходимо-
сходимости и теоремы о равномерной непрерывности.
23. Максимальные рекурсивные функционалы
Как уже отмечено, частично рекурсивные функ-
функционалы, отображающие пространство X в простран-
пространство У, можно рассматривать как аппроксимации в
пространстве X-*Y. Среди них мы выделим теперь
максимальные.
Говорят, что частично рекурсивный функционал f
есть максимальный рекурсивный функционал, если
для любых пар окрестностей 1\ и /2 в X и /i и /2 в У,
таких, что /i тоньше h и /г тоньше /ь либо имеет
место 1\]1\, либо //7 для некоторой /, более тонкой,
чем 7г. и /, отделенной от /г-
Если частично рекурсивный функционал всюду
определен на евклидовом или канторовом простран-
пространстве, то он максимален.
Это утверждение — следствие локальной компакт-
компактности и не имеет места для бэровского пространства.
Доказательство для функционалов, отображаю-
отображающих канторовское пространство в себя. Пусть f всю-
всюду определен, и пусть / и / — произвольные окрест-
окрестности. По теореме о равномерной непрерывности мы
имеем
/=/,и/2и ... и//.
Так как d(/ft) ^d(J), то либо /ft тоньше /, либо /ft
отделена от /. Если /ft тоньше / для всех k, I ^ k ^ /,
то IfJ. В противном случае /л//Л для некоторого k, та-
такого, что /л тоньше / и /Л отделена от /. Это показы-
показывает, что / максимален.
Вещественные рекурсивные функционалы, которые
всюду определены, совпадают с рекурсивными веще-
вещественными функциями Шпеккера [1] (если заменить
там примитивно рекурсивные функции общерекурсив-
общерекурсивными), Гжегорчика [1] и Лакомба [1].
Область максимального рекурсивного функциона-
функционала плотна.
Рассмотрим максимальный рекурсивный функ-
функционал f, отображающий X в У. Допустим, что J\ и
h — окрестности в У, такие, что h тоньше J\, и вы-
выберем окрестность I в X. Взяв h тоньше /, мы имеем
или IifJi или J2fJ для некоторой h более тонкой, чем /
и /, отделенной от /г. Это показывает, что открытые
множества, пересечение которых составляет область f,
все плотны. Следовательно, область / плотна.
Применяя теорему Бэра, мы видим, что в любой
окрестности / пространства X имеется конструктив-
конструктивная точка а, такая, что /(а) —конструктивная точка.
Чтобы продемонстрировать полезность понятия
максимального рекурсивного функционала, мы дока-
докажем конструктивный вариант теоремы Рисса о пред-
представлении. Максимальный вещественный рекурсивный
функционал F называется неубывающей функцией,
если из соотношений аи b\Fc\, d\ и а2, b2Fc%, fife вместе
с а\ < 4>2 следует С\ < fife.
68
Гл. 2. Элементарный конструктивный анализ
23. Максимальные рекурсивные функционалы
69
Под полигоном (рис. 1) мы будем понимать ку-
кусочно линейную функцию, исчезающую вне конеч-
конечного интервала, вершины которой имеют рациональ-
рациональные координаты. Точнее, полигон — это синтакси-
синтаксическое выражение вида r0, s0; rh s,; ; /¦„, sn, где
Рис. 1.
/"о<С П"< • • • '< г„, и «о = 0, «ь ..., sn = 0 — рацио-
рациональные числа.
Интеграл полигона / относительно неубывающей
функции М,
определяется обычным образом как предел сумм
Стильтьеса
2/(
п=1
Единственное нововведение состоит в том, что мы
должны позаботиться о выборе точек разбиения а<> ¦<
,< ai < ... < aN из области М. Это всегда возмож-
возможно, так как область М плотна согласно вышеприве-
вышеприведенной теореме. Интеграл ц(Л» очевидно, имеет свой-
свойства
, если/>0,
Обратно, мы покажем, что если ц —рекурсивная
функция, сопоставляющая каждому полигону неко?
торое вычислимое действительное число таким обра-
образом, что эти условия выполнены, то мы можем най-
найти неубывающую функцию М, такую, что
lx(f)=j fdM,
причем весовая функция М однозначно определяется
функцией ц с точностью до аддитивной константы.
Для данной ц определим Gn как объединение
всех окрестностей / = а, Ь, таких, что ц(/)<2~" для
какого-либо полигона /, имеющего вид, изображен-
изображенный на рис. 2. Тогда С„ — плотное открытое множе-
множество для любого п, так что теорема Бэра позволяет
нам найти точку х е П^п-
Определим рекурсивно перечислимое отношение М
между рациональными интервалами a, b и с, d тре-
требованием, чтобы а, ЬМс, d тогда и только тогда, когда
для некоторых функций fug того типа, который
изображен на рис. 3. В действительности f и g уже
не являются полигонами, но выбор точки х позволяет
нам определить \x(f) и n{g) очевидным предельным
переходом.
Определенный таким образом М, очевидно, яв-
является частично рекурсивным функционалом. Основ-
Основная трудность — доказать его максимальность.
Пусть 1\ = аи bi тоньше /2 = аг, Ь2 и /2 = c2, d%
тоньше / = С\, d\. Нам нужно доказать, что либо
70 Гл. 2. Элементарный конструктивный анализ
hMJ\, либо* IMJ для некоторой /, более тонкой, чем
12, и /, отделенной от /2.
С этой целью выберем fug, как показано на
рис. 4.
J •
az a b
Рис. 4.
6,
Вычисляя ц(/) и n(g) с достаточной точностью,
мы можем доказать
ц(/)>с, или n(f)<c2,
и
</, или \i(g)>d2.
Если имеют место ц(/) > Ci и ц(§) < d2, то
согласно определению М. Если ц(/)<Сг, то мы мо-
можем найти а, Ъ тоньше а2, Ь2, такую, что а, ЬМс, d при
d < сг, откуда следует, что с, d отделена от Гг, d2.
Аналогично, если ii(g)>d2. Следовательно, М макси-
максимален. Неубывание М — прямое следствие предполо-.
жения, что ц(/)^.0, если /^,0.
24 Две теоремы из классической теории функций 71
Проверка соотношения
а также того обстоятельства, что М однозначно опре-
определяется нормализующим условием М(х) = 0, стан-
стандартна и завершает доказательство.
Область М совпадает с внутренним предельным
множеством, которое определено в начале доказа-
доказательства, и интуитивно может быть представлена
как множество точек, не несущих массы.
Пусть
J л = 0, 1, ....
VL(f)=jfdM
— интегралы. Применяя теорему о категории, найдем
конструктивную точку х, принадлежащую областям
Мп для всех п, а также области М. Нормализуем ве-
весовые функции, полагая Afn(O) = O для всех п и
Af(O) = O. Тогда
Pn(f)-+P(f) при и-*оо
для всех полигонов / тогда и только тогда, когда
Мп-*М согласно определению сходимости, данному
в предыдущем разделе. Это соответствует классиче-
классическому понятию поточечной сходимости в каждой точ-
точке непрерывности предельной функции.
24. Две теоремы из классической теории функции
Если вещественный частично рекурсивный функ-
функционал всюду определен на некотором локализован-
локализованном компактном множестве, то мы можем вычислить
его максимум на этом множестве. Чтобы усмотреть
это, пусть / — отображение (например) канторовского
пространства в вещественную прямую, и предполо-
предположим, что / всюду определено на локализованном
компактном множестве F. Теорема о равномерной
72
Гл. 2. Элементарный конструктивный анализ
24. Две теоремы из классической теории функций 73
непрерывности позволяет нам найти для каждого п
окрестности 1и /2, ..., /,, такие, что
F?=/,u/2u... и л,
hfh. d(Jk)<2-n, 1<?</.
Так как F = С G локализовано, мы можем ре-
решить для каждой окрестности 1р, содержится ли она
в G. Если да, выбрасываем ее. Сделав это, найдем
тот рациональный интервал Д = ah, bh, для которо-
которого bh наибольшее из возможных. Этот интервал яв-
является окрестностью максимума / на F.
Следующий пример показывает, что предположе-
предположение локализованности действительно необходимо для
того, чтобы можно было вычислить максимум всюду
определенной функции на этом множестве. Рассмот-
Рассмотрим Шпеккерову последовательность 0 < а0 < а\ <
< ... < ап < ... < 1, и пусть Fn — замкнутый про-
промежуток от й„ до 1. Тогда F=[\Fn замкнуто и
ограничено. Если бы мы могли вычислить минимум
тождественной функции f(x) = х на F, то последо-
последовательность Шпеккера сходилась бы к этому мини-
минимальному значению, что невозможно.
Хотя мы можем вычислить максимум действи-
действительной функции на локализованном компактном
множестве, может случиться, что нет конструктивной
точки, в которой достигается это максимальное зна-
значение. Это было обнаружено Лакомбом [2], Заслав-
Заславским [1] и Шпеккером [2].
Существует действительный рекурсивный функ-
функционал f, который всюду определен, хотя
f(a) < max f(x)
0<<l
для любой конструктивной точки 0 ^ а ^. 1.
Пусть /0, /ь ,.., /„, ... — рекурсивная последова-
последовательность рациональных интервалов, такая, что \jln
N
содержит все конструктивные точки, но 2 d (/„) < 1
/1=0
для всех N. Такая последовательность была построе-
построена для канторовского пространства в п. 20, но кон-
конструкция работает столь же хорошо и для веществен-
вещественной прямой. С 1п = ап, Ъп мы свяжем функцию
Тогда
х — ¦
— 1, если an
0, если х ^ ап или х ^ Ьп.
определена всюду на вещественной прямой
max / (я) = 0,
0<<1
хотя
f(a)<0
для любой конструктивной точки а. Это доказатель-
доказательство было дано Лакомбом [3].
Используя существование открытого множества,
которое содержит все конструктивные точки, но не
равно всему пространству, мы можем построить раз-
различные функции, области определения которых со-
содержат все конструктивные точки, но которые тем не
менее ведут себя очень плохо. Например, как пока-
показано Клини [2], функция может быть определена во
всех конструктивных точках канторова пространства,
не будучи равномерно непрерывной, а в этом случае
она не может быть продолжена до всюду определен-
определенной функции. Чтобы усмотреть это, допустим, что
/0, 1\, ..., /п, ... — дизъюнктные окрестности, покры-
покрывающие все конструктивные точки, но не покрываю-
покрывающие всего пространства. Положим / = 0 и 1 на
окрестностях /п0 и /п | соответственно, п = 0, 1, ... .
Тогда / — дискретнозначный частично рекурсивный
функционал, принимающий только значения 0 и 1,
который обладает нужными свойствами.
Другой пример классической теоремы, которая
проваливается конструктивно, — это теорема о сред-
среднем значении.
74
Гл. 2. Элементарный конструктивный анализ
24. Две теоремы из классической теории функций
Нет алгорифма, вычисляющего корень любого
вещественного рекурсивного функционала, который
всюду определен и меняет знак в единичном интер-
интервале.
Эта, а также следующая теорема упомянута
Крайзелем [2] и доказана Цейтиным [1].
Сопоставим каждому вычислимому действитель-
действительному числу а функцию, изображенную на рис. 5.
1
Рис. 5.
Если бы в нашем распоряжении был алгоритм со
свойствами, указанными в теореме, то мы могли бы
найти точку, в которой эта функция исчезает. Для
этой точки b можно решить b > 7з или b < 2/3, про-
просто вычисляя ее с достаточной точностью. В первом
случае а ^ О, во втором а ^ 0. Таким образом, мы
имели бы рекурсивный метод доказательства а ^ 0
или а ^ 0 для любого вычислимого действительного
числа а. Однако мы знаем из п. 15, что такого ме-
метода нет.
Невозможно, чтобы вещественный рекурсивный
функционал, который всюду определен и меняет
знак в единичном интервале, принимал ненулевое
значение в любой конструктивной точке.
Действительно, допустим, что / всюду определен
на единичном интервале /@)<0, /A) >0. Поло-
Положим /о = а0, bo = 0, 1 и определим индуктивно
«Я+1»
bn,
Здесь мы использовали тот факт, что если вы-
вычислимое действительное число b Ф 0, то мы можем
решить b < 0 или b > 0. Когда п -> оо, окрестность
/п = о.п, Ьп сходится к конструктивной точке, где f
исчезает. Мы достигли противоречия.
ГЛАВА 3
25. Определение ординалов второго числового класса 77
ОРДИНАЛЬНЫЕ ЧИСЛА И БОРЕЛЕВСКИЕ МНОЖЕСТВА
25. Определение ординалов второго
числового класса
Канторовская теория ординальных чисел второго
числового класса получила конструктивное обоснова-
обоснование с использованием рекурсивных функций в рабо-
работах Черча и Клини [1], Черча [2] и Клини [1]. Другой
подход принадлежит Марквальду [1] и Спектору [1],
который ввел так называемые рекурсивные вполне
упорядочения. Мы будем ближе следовать изложе-
изложению Брауэра [2] и [10].
Ординалы в нашем смысле можно изобразить как
фундированные деревья, ветви которых, исходящие
из данной точки, нумеруются натуральными числами
0, 1, ... в нужном количестве. См. рис. 6. Из каждой
точки ветвлений может исходить конечное или беско-
бесконечное число ветвей. Точка ветвления, из которой не
исходит ветвей, называется вершиной. Фундирован-
ность дерева означает, что, как бы мы ни взбирались
вверх по дереву, мы доберемся до вершины за ко-
конечное число шагов.
Формально мы определяем ординальное число
второго числового класса как рекурсивно перечисли-
перечислимое множество а конечных последовательностей
, щ, Пг И/ натуральных чисел, которое может
быть получено повторными применениями следующе-
следующего индуктивного пункта.
Если осо. он, ... (возможно, пустая или конеч-
конечная) — рекурсивно перечислимая последовательность
ординальных чисел, то рекурсивно перечислимое мно-
множество ос, элементами которого являются ? и мно-
множество всех ,п, Пь ..., tii, таких, что , И] ,,., щ при-
принадлежит осп> — ординальное число.
Если последовательность осо. он, • •. пуста, подра-
подразумевается, что условие этого индуктивного опреде-
определения выполнено тривиально, так что рекурсивно
перечислимое множество, состоящее только из D, яв-
является ординальным числом, называемым нулем и
обозначаемым через 0.
Рис. 6.
Ординальное число ос, получаемое применением
индуктивного пункта к последовательности ордина-
ординалов осо> ось •¦•» называется супремумом этой после-
последовательности, и мы пишем
a = sup<xn.
Если ос— это единственный ординал, то sup a назы-
называется также наследником (или непосредственно сле-
следующим за) ос. Используя стандартную запись, мы
78 Гл. 3. Ординальные числа и борелевские множества
26. Равенство и отношения порядка
79
вводим последовательно
О, l = supO, 2 = supl, 3 = sup2, ...
со = sup п, со -f 1 в sup со, со + 2 = sup (со + 1), ...
со2 = sup (со + я), со2 + 1 = sup со2, ...
со2 = sup сои
supcu2«, ...
чтобы говорить, что }П\,п% ..., П| принадлежит рекур-
рекурсивно перечислимому множеству а. Верхний узел—¦
это такой узел, никакое собственное продолжение ко-
которого не принадлежит а.
Если , ni ..., /is — узел ординального числа а, то
множество всех , nu+i ,.., Щ, таких, что , П\ ..., пк,
nk+\ ..., iti также есть узел а, называется подордина-
лом k-го порядка ординала а и будет обозначаться
через
со» = sup со", ..., (йи<0 = sup со10", ...
е0 = sup со J
Индуктивный пункт, определяющий ординальные
числа, разрешает нам получать из бесконечного чис-
числа посылок
<х„ — ординальное число для любого я=«0, 1, ...
заключение
<x = supan— ординальное число.
Мы выражаем это, говоря, что задано определение
по трансфинитной индукции.
Если мы можем доказать, что ординальное число
a = sup an обладает некоторым свойством, как толь-
только an обладает этим свойством для любого п = О,
1, ..., то мы разрешаем себе заключить отсюда, что
все ординалы второго числового класса также обла-
обладают этим свойством. На такое рассуждение мы бу-
будем ссылаться как на доказательство по (с по-
помощью) трансфинитной индукции.
Мы будем говорить, что ,П\, Пг ..., щ — точка
ветвления {узел) ординального числа а, вместо того
(Брауэр [2] применял название konstruktive Unter-
species й-ter Ordnung).
Трансфинитной индукцией с использованием со-
соотношения
(a«l)n ... п ==ап п ... я
доказывается, что подординал действительно яв-
является ординалом.
26. Равенство и отношения порядка
между ординальными числами
Мы введем сначала отношения порядка < и <,
в терминах которых легко определяется отношение
равенства =.
Конечное множество выражений вида a < Р или
а ^ р, где аир — ординальные числа, будет назы-
называться секвенцией'). Секвенции будут обозначаться
через Г, А и в.
Мы будем рассматривать следующие два правила
вывода:
Г, ап < Р для всех п Г, a < ftn для некоторого п
Г, а<р Г, о<р
Доказательство — это бесконечное дерево секвен-
секвенций, в котором каждое разветвление является приме-
применением одного из правил вывода. В частности, верх-
верхние секвенции должны иметь вид Г, 0 ^ р. Они
') Приблизительное истолкование* секвенции А\, ,.,, Лп
дается формулой А\ V... УАп. — Прим. перев.
80 Гл. 3. Ординальные числа и борелевскив множества
26. Равенство и отношения порядка
81
выводятся посредством первого правила вывода, ко-
когда а есть нуль, так что посылка выполнена автома-
автоматически. Говоря точнее, мы понимаем под бесконеч-
бесконечным деревом секвенций ординальное число вместе с
частично рекурсивной функцией, которая сопоставляет
некоторую секвенцию каждому узлу этого ординаль-
ординального числа. Полагаем а<Р (или as^P), если вы-
выводима соответствующая секвенция.
а=^р, тогда и только тогда, когда ап<Р для всех п.
Достаточность — просто применение первого пра-
правила выбора, а необходимость — следствие того фак-
факта, что обращение этого правила
Г, а<р
Г, ап < р для всех п
имеет место как допустимое правило вывода. Мы до-
доказываем это трансфинитной индукцией по длине до-
доказательства посылки. Следует различать несколько
случаев в зависимости от последнего применения
правила в данном доказательстве секвенции Г, a ^ р.
Если Г = A, y ^ б и это применение есть
A, Vm<6, О<1Р для всех m
A,
то мы получаем по предположению индукции
A, Ym < б, an < Р для всех man. Отсюда по пер-
первому правилу вывода заключаем A, y ¦«=* б, ап < Р «=«,
= Г, ап < Р для всех п, что и требовалось доказать,
Аналогично если Г = А, у <.Ь, и последнее примене-
применение правила есть
А, у<6т. <*<Р для некоторого m
Остается рассмотреть случаи
Г, an<P для всех я
Г, а<р
и
Г, а<Р, ап<Р Для всех п
Г, а<Р
в первом из которых все получается сразу, а во
втором можно применить предположение индукции к.
Г, а ^ р, ап <С Р, получая тем самым Г, ап < $ для
всех п. Доказательство окончено.
а^а для любого ординального числа а.
Доказательство — трансфинитной индукцией по а,
Допустим, что ап ^ ап для всех п. Тогда по второму
правилу вывода ап < а для всех /г, так что по пер-
первому правилу вывода а ^ а, что и требовалось дока-
доказать.
Если а < р м Р ^ Y> го а < y«
.Если а ^ р и р < y. го а < Y-
Мы докажем чуть больше, а именно что
Г, а<р в, р<у Г, а<р в, Р<у
Г, в, а<у Г, в,
имеют место как допустимые правила вывода. Это
делается кратной трансфинитной индукцией. Индук-
Индукционное предположение состоит в том, что первое
правило справедливо для всех подординалов первого
порядка ординалов а и y и что второе правило спра-
справедливо для всех подординалов первого порядка ор-
ординала р. Внутри индукционного перехода нам снова
приходится применять трансфинитную индукцию, на
этот раз предполагая, что правила справедливы,
если уменьшилась длина вывода хотя бы одной из по-
посылок.
Рассмотрим для начала первое правило. Следует
различать несколько случаев в зависимости от по-
последних применений правил в доказательствах по-
посылок.
Основной случай возникает, когда они имеют вид
Г, a<Pa<pn для некоторого п
Г, а<р
в, Р<у, Рп<У для всех п
е,
82 Гл. 3. Ординальные числа и борелевские множества
26. Равенство и отношения порядка
83
соответственно. В этом случае доказательство завер-
.шается следующими применениями правил:
Г, а<р, а<Р» в, р<у Г, а<р в, Р<у, Р»<у
Г, в, а<у, а<Р„ Г, в, а<у, Р»<у
Г, 9, а<у
Здесь верхние применения правил допустимы со-
согласно предположению индукции по длинам доказа-
доказательств посылок, а нижнее — согласно предположе-
предположению индукции по р.
Второе правило рассматривается во многом тем
же способом. Ограничимся случаем, когда последние
применения правил в доказательствах посылок имеют
вид
Г, а<Р, ат<Р для всех m
Г, а<р
в, Р<у, Р^Уп для некоторых п
в, Р<у
соответственно. Искомое заключение получается так:
Г, а<р, ат<Р 6, р<у Г, а<Р в, Р<у, Р<у„
Г, в, а<у, аст<р Г, в, а<у,
Г, в, а<у, ат<уп
Г, в, а < у, а < у„
Г, в, а<у"
Здесь верхние применения правил допустимы со-
согласно предположению индукции по длинам выво-
выводов посылок, а следующее применение —согласно
предположению индукции по а и у. Последние два
применения — просто применения постулированных
правил вывода. Доказательство окончено.
Если а
и
. Т0
Если а <: р, то а„ < р для всех п. Из ап < Р и
Р ^ Y следует ап < у. Таким образом, ап < у для
всех п, так что a ^ у, что и требовалось доказать.
Транзитивность отношения < следует из уже до-
доказанного и того факта, что отношение < сильнее4
чем отношение <;.
Если а < р, то a
Достаточно доказать, что а„ ^ а для всех п, так
как тогда мы получим а„ < р для всех п, что экви-
эквивалентно а ^ р. Соотношение <хп ^ а доказывается
трансфинитной индукцией по а с индукционным пред-
предположением amn ^ am для всех тип. Отсюда мы
получаем amn < a no второму правилу вывода для
любых m и п, а затем am <; а по первому правилу
вывода, что и требовалось доказать.
Следующую теорему можно рассматривать как
конструктивный вариант теоремы о сравнимости ор-
ординальных чисел, которая в классической формули-
формулировке утверждает, что для любой пары ординальных
чисел а, р имеет место либо а < р, либо р ^ а.
Для любых ординалов а и р доказуема секвенция
а < р, р < а.
Мы докажем одновременной трансфинитной ин-
индукцией, что две секвенции
а<р, р<а а<р, р<а
доказуемы. Индукционное предположение состоит в
том, что первая секвенция доказана для всех подор-
диналов первого порядка ординала а, а вторая сек-
секвенция— для всех подординалов первого порядка ор-
ординала р. Отсюда мы получаем
a < Рд| Рд < в ДДя всех п
а < р, р„ < а для всех п
а<Р, р<а
и
Р Р< для всех п
ап < р, р < а для всех п
р, р<а
что и требовалось доказать.
Отношения a < р и р ^ а исключают друг друга,
Для того чтобы эта теорема имела место, необхо-
необходимо и достаточно, чтобы a < а было невозможно
для любого ординала а. Учитывая непротиворечи-
непротиворечивость нашего исчисления, т. е. недоказуемость пустой
84 Гл. 3. Ординальные числа и борелевские множества
28. Открытые множества в бэровском пространстве 85
секвенции, достаточно доказать выводимое правило
Г, а<а
что мы сделаем трансфинитной индукцией по а. Вну-
Внутри индукционного перехода нам придется использо-
использовать трансфинитную индукцию по длине доказатель-
доказательства посылки. Если Г = Д, р ^ у и последнее приме-
применение правила в этом доказательстве есть
А, рп < у, а < а для всех п
Д.
то мы получаем Д, р„ < у для всех п и, следова-
следовательно, А, р ss: у = Г по первому правилу вывода.
Аналогично и если Г = Д, р < у. Остается рассмот-
рассмотреть случаи
Г, а ^ ап для некоторого п
Г, а<а
И
Г, а < а, а <1 ап для некоторого п
Г, а < а
из которых более трудное — второе. Согласно пред-
предположению индукции по длине доказательства посыл-
посылки мы получаем Г, а^Сап для некоторого п, что вле-
влечет Г, ап < ап. Предположение индукции по а дает
нам теперь искомое доказательство Г.
Отношения равенства и неравенства между орди-
ординальными числами определяются следующим об-
образом:
а = Р, если а^Р и
аф р, если доказуемо а < р,Р < а.
Рефлексивность, симметричность и транзитивность
отношения = следует из рефлексивности и транзи-
транзитивности ^. Далее, тот факт, что отношения а < р,
а = р и р < а взаимно исключают друг друга, яв-
является непосредственным следствием несовместимости
а < р и р < а.
Заметим, наконец, что если ао, аи ... — возможно,
пустая или конечная последовательность ординалов,
то а = sup an — это наименьший ординал а, такой,
что ап<а для всех п. А именно допустим, что
ап < Р для всех п. Тогда по первому правилу вывода
а г?1 р, как и утверждалось.
27. Неперечислимость второго числового класса
Ординальные числа, согласно нашему определе-
определению,— это некоторые рекурсивно перечислимые мно-
множества в двухбуквенном алфавите , I . Мы знаем, что
существует рекурсивная нумерация всех рекурсивно
перечислимых множеств слов в данном алфавите.
Следовательно, конструктивные ординалы второго
числового класса счетны в теоретико-множественном
смысле слова. Тем не менее они не являются эффек-
эффективно перечислимыми. Борель [2] и Брауэр [2] пони-
понимали это, а Тьюринг [2] доказал для ординалов Чёр-
ча — Клини.
Если дана последовательность ординалов ао,
аь ..., ап. ..-, то мы можем найти ординал а, та-
такой, что ап Ф а для всех п.
Построим ординал а = sup сс„. Тогда ап < а и,
следовательно, ап Ф а для всех п, что и требовалось
доказать.
Заметим, что это доказательство использует рас-
рассуждение, которое привело Кантора к выводу о том,
что второй числовой класс имеет мощность, которая
больше Ко и в действительности равна второму по
величине трансфинитному ординальному числу Кь
Именно введение понятия эффективной перечисли-
перечислимости вместо теоретико-множественного понятия счет-
иости позволяет нам вывести из рассуждения Кантора
совсем иные следствия.
28. Открытые множества в бэровском пространстве
До сих пор мы еще не ввели отношений равен-
равенства и включения между открытыми множествами
в бэровском пространстве. Чтобы сделать это, мы
?6 Л». 3 Ординальные числа и борелевские множества
28. Открытые множества в бэровском пространстве
87
определим сначала по трансфинитной индукции от-
отношение: окрестность / заперта открытым множе-
множеством G (или множество G запирает /) в бэровском
пространстве.
1 Если/ принадлежит G, то G запирает /.
2 Если G запирает /, п для любого натурального
числа п, то G запирает /.
Введем следующие определения, в которых А и В
обозначают открытые множества в бэровском про-
пространстве.
А^В, если В запирает любую окрестность, при-
принадлежащую А.
А = В, если ЛдВиВдЛ.
Обозначим через X все бэровское пространство,
т. е. множество всех конечных последовательностей
целых чисел ,п\, п2 ..., щ. Из данного нами опреде-
определения мы заключаем, что G = X, где G — открытое
множество, тогда и только тогда, когда G запирает
пустую последовательность П.
Пример. Пусть G состоит из всех окрестностей
,щ, «2 •.•, tit, для которых rti < I. Согласно перво-
первому пункту, G запирает , 0 и G запирает , 1, Пч для лю-
любого П2, так что по второму пункту G запирает , 1.
Снова по первому пункту G запирает , 2, пъ, п3 для
любых п2 и Пз, откуда второй пункт позволяет нам
заключить, что G запирает , 2, Пг для любого Пч, а за-
затем, что G запирает , 2. Продолжая тем же способом,
мы доказываем, что G запирает , п\ для любого п\.
Следовательно, по второму пункту G запирает П,
так что G = X.
В определении открытого подмножества G бэров-
ского пространства мы могли бы потребовать, чтобы
рекурсивно перечислимое множество G было разре-
разрешимым. Это не привело бы к ограничению общности.
Пусть А — открытое множество в бэровском про~
странстве. Тогда А = В для открытого множества В,
которое, если его рассматривать как рекурсивно пе~
речислимое множество, разрешимо и содержится в А.
Если п — номер доказательства / в постовской си-
системе А, то В будет содержать все окрестности /t
более тонкие, чем /, для которых d(J) ^ 2~п. Для,
любой окрестности / можно решить, принадлежит ли
она В, проверяя, является ли / более тонкой, чем
одна из окрестностей, принадлежащих А и имеющих
доказательство с номером ^.п, где d(I) =2~n. Сле-
Следовательно, рекурсивно перечислимое множество В
содержится в рекурсивно перечислимом множестве А.
С другой стороны, наша конструкция такова, что В
запирает любую окрестность из А, откуда А = В,
что и требовалось доказать.
Напомним, что в определении открытого множе-
множества G в канторовом пространстве мы требовали не
только того, чтобы /0 и / | принадлежали G вместе
с /, но и обратного соотношения. Мы всегда можем
достичь этого, отмечая производящие схемы G и до-
добавляя новые схемы:
В
Вх
Вх
~ВхТ
Вх Gx хО х I Bx
ВхО Вх\ х х
В бэровском пространстве это не срабатывает, так
как схема, соответствующая последней из только что
приведенных, должна была бы иметь бесконечное
множество посылок. Следующий пример, приведен-
приведенный Клини [4], показывает, что мы действительно
существенно ограничили бы общность, потребовав,
чтобы окрестность / принадлежала открытому мно-
множеству G в бэровском пространстве, если /, п при-
принадлежит G для всех п.
Пусть А — открытое множество, состоящее из всех
окрестностей , п\, п?. ..., щ, таких, что п2 не яв-
является номером доказательства щ в диагональном
множестве D. Допустим, что А = В, где В обладает
свойством: если для всех п окрестность /, п принадле-
принадлежит В, то / принадлежит В. Тогда пфБ тогда и
только тогда, когда , п принадлежит В. Так как по-
последнее отношение рекурсивно перечислимо, это про-
противоречит неразрешимости D.
Брауэр работал с понятием свободно становя-
становящейся последовательности (choice sequence) нату-
натуральных чисел
,п1 ,п2... ,п{... ,
88 Гл. 3. Ординальные числа и борелевские множества
последовательные элементы которой определяются
произвольным образом, путем свободного выбора, а
не обязательно математическим законом. Бесконечно
продолжающаяся последовательность принадлежит
по определению открытому множеству В в бэровском
пространстве, если для некоторого / ее начальный от-
отрезок , «|, пч ..., щ есть окрестность из G. Примем
на минуту понятие бесконечно продолжающейся по-
последовательности. В дополнение к данному выше
определению G = X (G запирает ?) мы получаем
другое определение, потребовав, чтобы все бесконеч-
бесконечно продолжающиеся последовательности принадле-
принадлежали G. Эквивалентность этих двух определений со-
составляет содержание брауэровской бар теоремы. Ра-
Разумеется, она имеет лишь интуитивный смысл, если
не принято понятие бесконечно продолжающейся по-
последовательности. Бар теорема и теорема о веерах из
следующего пункта весьма тщательно обсуждены
Клини и Весли [1].
29. Теорема Брауэра о веерах
С каждой рекурсивной последовательностью на-
натуральных чисел
мы можем связать дополнительно локализованное от-
открытое множество А в бэровском пространстве, со-
состоящее из всех окрестностей ,п\ ,п% ..., щ, таких,
что nh> Сь. для некоторого k^CL В = СА является
тогда локализованным замкнутым множеством, кото-
которое мы назовем ограничивающим множеством. Зам-
Замкнутое множество F в бэровском пространстве огра-
ограничено, если мы можем найти ограничивающее мно-
множество В, такое, что F Е В. Ограниченное замкнутое
множество в бэровском пространстве называется ком-
компактным.
Следующая лемма содержит основную сущность
теоремы Брауэра о веерах.
29. Теорема Брауэра о веерах
89
Если G — открытое множество, покрывающее все
бэровское пространство, и ,С\ ,с2 ... ,Ci — рекурсивная
последовательность натуральных чисел, мы можем
найти настолько большое I, что ,п\ ,п2 ... ,Щ принад-
принадлежит G для всех niKcu п2Кс2, .... n^Ci.
Сначала мы с помощью обычной индукции опре-
определим некоторое рекурсивно перечислимое отноше-
отношение R между окрестностями в бэровском простран-
пространстве и натуральными числами.
1 Если окрестность / принадлежит G, то пола-
полагаем IRQ.
2 Если /, nRl для всех п ^ cft.H, где k есть длина
IRl
Очевидно, IRI означает, что / ,nh+\ ,nh+2 • • ¦ ,+
принадлежит G для всех nk+iKck+i, nh+2-^cft+2, ...
..., tik+i-*Cck+u где k означает длину /. Таким обра-
образом, утверждение теоремы имеет место тогда и толь-
только тогда, когда мы можем найти такое /, что HRI,
т. е. тогда и только тогда, когда ? принадлежит об-
области R.
Мы сейчас покажем, что область R содержит все
окрестности /, которые заперты множеством G, и,
значит, в частности, пустую последовательность П.
Мы сделаем это трансфинитной индукцией по длине
доказательства того, что G запирает /. Базис. Если /
принадлежит G, то IR0, так что / принадлежит об-
области R. Шаг индукции. Допустим, что /, п принадле-
принадлежит области R для любого п, т. е. для любого п мы
можем найти /„, такое, что /, nRln. Положим
/= max /„,
где k обозначает длину /. Тогда I,nRL для всех
п -<Cft+i, так что в силу второго пункта выше IRI + 1.
Следовательно, / принадлежит области R. Доказа-
Доказательство закончено.
Теорема Гейне — Бореля о покрытиях для бэров-
ского пространства — простое следствие только что
доказанной леммы.
90 Гл. 3. Ординальные числа и борелевские множества
30. Борелевские множества
91
Если F — компактное множество в бэровском про-
пространстве и
j
п=а
где Со, G\, ... — последовательность открытых мно-
о/сеств, то можно найти настолько большое N, что
Fs=(jGn.
0
л=0
Компактность F означает, что F — CG, где G от-
открыто и FsB, где В —С А—ограничивающее мно-
множество, определяемое рекурсивной последователь-
последовательностью натуральных чисел
оо
Далее, F^ (JOn означает, что открытое множество
оо
G\j[jGn покрывает все бэровское пространство.
л=0
Применяя приведенную выше лемму, находим I, та-
00
кое, что ,П\ ,п2 ... ,щ принадлежит G U (J Gn Для
всех п\ ^ си Щ*^.С2, ..., Щ^. С;. Так как имеется
лишь конечное число таких окрестностей, мы можем
найти настолько большое N, что все они содержатся
N
уже в G\j \jGn. Теперь объединение этих окрестно-
л=0
стей и А равно всему пространству и FeJ5, значит
Л е G. Следовательно,
сии0»-*
а это и есть определение отношения
л=0
Если f — дискретнозначный частично рекурсивный
функционал, который всюду определен на компактном
.множестве F в бэровском пространстве, то можно
найти натуральное число I, такое, что значение f на F
определяется уже знанием первых I знаков аргу-
аргумента.
Эта обычная форма теоремы о веерах, доказан-
доказанная Брауэром [5], [6], [И] и [12] при дополнительном
предположении, что компактное множество F лока-
локализовано.
Доказательство. По предположению F содержится
в области /, которая определена как объединение
всех окрестностей /, таких, что 1\п для некоторого
натурального числа п. Согласно предыдущей теореме,
уже конечное число этих окрестностей покрывает F.
Пусть / — максимум их длин. Тогда для вычисления
значений / на f достаточно знать первые / знаков
аргумента.
30. Борелевские множества
Мы возвращаемся теперь к задаче о конструктив-
конструктивной интерпретации теоретико-множественных отноше-
отношений между внутренними и внешними предельными
множествами, которая осталась нерешенной в п. 20.
Оказывается, что эта задача для полной иерархии
борелевских множеств не труднее, чем для внутрен-
внутренних предельных множеств, так что мы рассмотрим
непосредственно этот более общий случай.
Для упрощения наше рассмотрение борелевских
множеств будет ограничено канторовским простран-
пространством. Остальные пространства можно рассмотреть
похожим образом.
Простое множество в канторовском простран-
пространстве— это синтаксическое выражение вида
где /i, h, ..., In — окрестности. Интуитивно говоря,
множество в канторовском пространстве простое,
если оно налагает условия лишь на конечное число
92 Гл. 3. Ординальные числа и борелевские множества
30. Борелевские множества
координат. Используя теорему Гейне — Бореля о по-
покрытиях, мы видим, что простые множества—это в
точности те, которые одновременно и открыты, и за-
замкнуты. Если дано простое множество, то можно най-
найти другое простое множество, являющееся его допол-
дополнением. Аналогично мы можем найти объединение и
пересечение любых двух простых множеств. Отноше-
Отношения включения и равенства между простыми множе-
множествами очевидным образом разрешимы.
Сейчас мы определим трансфинитной индукцией
понятие борелевского множества.
1 Если А — простое множество, то Л — борелев-
ское множество.
2 Если Ло, Аи ...— возможно, пустая или конеч-
конечная рекурсивно перечислимая последовательность бо-
релевских множеств, то \JAn и f]An — борелевские
множества.
Точнее, борелевское множество А — это ординаль-
ординальное число, каждому узлу которого некоторая частич-
частично рекурсивная функция сопоставляет либо простое
множество, либо один из знаков U. П. причем про-
простые множества сопоставлены только вершинам. Если
а — это лежащий в основе ординал, то мы говорим,
что А имеет бэровский класс а. А имеет аддитивный
или мультипликативный класс а в зависимости от
внешнего знака А, т. е. от того, какой знак, U или
(™|. сопоставляет рассматриваемая частично рекурсив-
рекурсивная функция узлу D.
Когда ординал равен 0 и узлу ? сопоставлено U
или (™|> мы получаем два борелевских множества, на-
называемых пустым множеством и всем пространством
и обозначаемых соответственно через 0 и X.
Дополнение СА борелевского множества А полу-
получается заменой любого простого множества на его
дополнение и взаимной заменой (J и (™|- Для объеди-
объединения двух борелевских множеств мы будем исполь-
использовать обычную неформальную запись A U В. Анало-
Аналогично для пересечения. Разность двух борелевских
множеств А и В определяется соотношением
а симметрическая разность — соотношением
ААВ = {А — B)\j{B — A).
Чтобы определить отношение включения между
борелевскими множествами, мы построим формаль-
формальную систему генценовского типа, правила вывода ко-
которой имеют бесконечное число посылок. Формула'
ми нашей системы являются борелевские множества,
а конечная последовательность формул
"t» > • • • > "rtt
где п ^ 0, называется секвенцией. Чтобы избежать
структурных правил вывода, мы будем отождествлять
секвенции, которые равны, если их рассматривать
как конечные множества. Буквы Г, Д и в будут ис-
использоваться для обозначения секвенций.
Аксиома — это секвенция, состоящая целиком из
простых множеств, которые вместе покрывают все
пространство. Ясно, что если зафиксирована запись
простых множеств, то множество, аксиом разрешимо.
Наша формальная система имеет два правила вы-
вывода. Формула, указанная явно в заключении прави-
правила вывода, называется главной формулой этого пра-
правила.
Г, Ап для некоторого п
Г, U Ап
Г, Ап Для всех я
U-введение
Л -введение
Г, п Ля
В случае пустого объединения посылка LJ-введе-
ния выполнена, если доказана Г, а для пустого пере-
пересечения подразумевается, что посылка |~)"ввеДения
выполнена тривиально.
Мы полагаем по определению, что борелевское
множество А содержится в борелевском множестве В,
и пишем
A SB,
если секвенция
сд в
может быть выведена из аксиом с использованием
приведенных выше правил вывода.
94 Гл. 3. Ординальные- числа и борелевские множества
30. Борелевские множества
Равенство определяется соотношением
затем А, С А, что и требовалось. Аналогично, если
л пл
= В, если Лг
и Bs
Остается показать, что определенное нами отно-
отношение включения имеет все обычные свойства или,
что сводится к тому же, доказать достаточное число
выводимых правил для сформулированной нами фор-
формальной системы. Будет достаточно следующих пра-
правил:
закон исключенного третьего А, С А
утончение -p-J
П-УДаление г, л/^tex п
сечение
Г, А 6,0 А
г. в
Именно сечение является основным среди этих
выводимых правил. .Оно играет ту же роль для нашей
системы, что основная теорема Генцена [1] для клас-
классической логики предикатов первого порядка. Дока-
Доказательства следуют тому же образцу.
Закон исключенного третьего выражает рефлек-
рефлексивность отношения включения, т. е. тот факт, что
А еЛ для любого борелевского множества А.
Транзитивность отношения включения — это про-
простое следствие правила сечения. Действительно, от-
отношения A s В и В<=С означают, что обе секвенции
С А, В и С В, С
доказуемы, а тогда доказуема и
С Л, С,
т. е. в точности ЛеС, что и требовалось доказать.
Доказательство закона исключенного третьего.
Трансфинитной индукцией по бэровскому классу А.
Базис. Если А — простое множество, то А, С А — ак-
аксиома. Шаг индукции. Допустим, что A— \JAn и Ап,
САп уже доказано для всех п. По (J-введению мы
получаем тогда А, САЯ для всех п, ("|-введение дает
п„
Доказательство утончения. Рассмотрим данный
вывод секвенции Г и добавим формулу А к каждой
секвенции, входящей в этот вывод. При этом преоб-
преобразовании каждое применение правила переходит в
применение того же правила, так что достаточно до-
доказать возможность утончения аксиом. Это делается
трансфинитной индукцией по бэровскому классу А.
Если А — пустое множество, утончение очевидным об-
образом допустимо. Допустим, что А = \JAn и что
утончение уже доказано для всех А„. Это значит, что
для любого п мы построили вывод Г, Ап. По U"BBe-
дению мы получаем Г, А. Аналогично если А = f\An.
Доказательство П-удаления. Мы используем
трансфинитную индукцию по длине данного вывода
Г, Г]Л„ и должны рассмотреть ряд случаев в зависи-
зависимости от правила, примененного на последнем шаге
вывода, и от того, является ли |"| Ап главной форму-
формулой этого правила.
Если Г = A, f\Bm и последнее применение пра-
правила в данном выводе имеет вид
А. Вщ, П Ап для некоторого т,
Г, U Bm, n Ап
то предположение индукции дает А, Вт, Ап для всех
п. Применяя то же самое правило вывода, мы полу-
получаем отсюда A, \JBm, Ап для всех п, т. е. Г, Ап для
всех п, что и требовалось доказать. Аналогично если
Г = А, Г[Вт.
Если f[An — главная формула последнего приме-
применения правила в доказательстве Г, [)Ап, то это при-
применение— либо
Г, Ап для всех п
либо
Г, n An, Ап для всех п
В первом случае мы непосредственно получаем Г, Ап
для всех п, а во втором индукционное предположение
позволяет нам вывести то же заключение. Это за-
завершает доказательство П-удаления.
9f} Гл. 3. Ординальные числа и борелевские множества
31. Конструктивный вариант теоремы Гёделя о полноте 97
Доказательство сечения. Доказательство полу-
получается индукцией по бэровскому классу формулы А.
Базис. Если А — простое множество, мы используем
непосредственную трансфинитную индукцию по дли-
длинам выводов посылок. В этом месте не возникает
трудностей, так как А не может быть главной форму-
формулой последнего применения правила в выводе по-
посылки. Кроме того, сечение тривиально имеет место,
когда посылки являются аксиомами.
Индукционный переход. Так как сечение симмет-
симметрично относительно своих посылок, достаточно рас-
рассмотреть случай, когда А = \JAn и утверждение до-
доказано для всех Ап. Мы снова должны использовать
трансфинитную индукцию, на этот раз по длинам вы-
выводов посылок. Если А не является главной форму-
формулой последнего применения правила в выводе Г, А
или СЛ не является таковой в выводе 0, СА, то рас-
рассуждение протекает по следующему образцу. Пусть
Г = А, Г\Вп и последнее применение правила в вы-
выводе Г, А есть
Л, ВпА для всех п.
Д, П Вп, А
Предположение индукции позволяет нам выпол-
выполнить сечение
А, Вп, А в, С А
д, вп, в
для всех п, а затем Г, в получается ("|"ввеДением-
Если А = |_|ЛП есть главная формула последнего
применения правила в выводе секвенции Г, Л, то это
применение имеет вид
Г, Ап для некоторого t Г, А, Ап для некоторого п
и аналогично, когда СА= f)CAn есть главная фор-
формула последнего применения правила в выводе сек-
секвенции в, СЛ, это применение имеет вид
Таким образом, нужно рассмотреть четыре случая.
В первом случае сечение
Г, Ап в,САп
Г, в
допустимо согласно соответствующему индукцион-
индукционному предположению. Во втором случае мы произво-
производим два сечения
Г, А, Ап в, С А
Г, в, Ап в, С Ап
Г, в
верхнее из которых обосновывается предположением
индукции по длинам доказательств посылок, а ниж-
нижнее— индукционным предположением, касающимся
бэровского класса формулы сечения. Аналогично в
третьем случае. В четвертом случае мы производим
следующие три сечения:
Г, А, Ап в, С А Г, А 8, С А, С Ап
Г, в, Ап Г, в, С Ап
в, САп для всех п
в, С Д
или
в, С Л, С Ап для всех п
в, О А
Г, в
Предположение индукции по длинам доказательств
посылок позволяет нам выполнить два верхних сече-
сечения, а предположение индукции по бэровскому клас-
классу формулы сечения оправдывает нижнее сечение.
Доказательство окончено.
31. Конструктивный вариант теоремы Гёделя
о полноте
Множество всех оценок (т. е. распределений
истинностных значений) атомарных формул, выпол-
выполняющих данную формулу классического исчисления
предикатов первого порядка, — это борелевское мно-
множество конечного бэровского класса в канторовом
пространстве. Конструктивизация теории борелевских
множеств, предпринятая в предыдущем пункте, поз-
позволяет нам дать конструктивный вариант теоремы
Гёделя [1] о полноте.
98 Гл. 3. Ординальные числа и борелевские множества
31, Конструктивный вариант теоремы Гёделя о полноте 99
Мы будем рассматривать формулы, построенные
обычным образом из предикатных символов, функ-
функциональных символов, свободных и связанных пере-
переменных и логических связок и кванторов — , V, л, V
и Д. Знак 'отрицания может стоять только перед
атомарными формулами, а отрицание произволь-
произвольной формулы определяется индуктивно по законам
де Моргана.
Конечная последовательность формул
^1» F2 Рп
будет называться секвенцией. Мы отождествляем
секвенции, если они равны как конечные множества.
Аксиома — это секвенция, построенная из атомар-
атомарных формул и их отрицаний и содержащая как F,
так и —F для некоторой атомарной формулы F. Пра-
Правила вывода следующие:
формул F мы определяем F индукцией по числу логи-
логических знаков в F:
v-введение
л-введение
V-введение
Л-введение
Г, F Г, G
Г, F v G Г, F v G
Г, F Г, G
Г, Fa G
Г, FI
Г, V* F*
Г, Fa
Г, Д* F*
Для правила Л'ввеДения имеется обычное усло-
условие: свободная переменная а не должна входить в
заключение.
Зафиксируем теперь взаимно однозначную рекур-
рекурсивную нумерацию атомарных формул
Используя 0 и | для обозначения истинности и лож-
ложности соответственно, мы сопоставим каждой атомар-
атомарной формуле F = Fn множество F всех оценок ато-
атомарных формул, при которых F истинна, т. е. множе-
множество всех бесконечных бинарных последовательностей,
п-я координата которых равна |. Это простое множе-
множество в канторовском пространстве. Для неатомарных
-F=*CF,
=\J Ftn AxFx=C\ Ftn.
Здесь мы предположили, что
'0> Mi • ¦ • > 'Bi • • •
— фиксированная взаимно однозначная нумерация
всех термов. Если Г — секвенция, то мы будем обо-
обозначать через Г секвенцию борелевских множеств, по-
полученную из Г заменой каждой формулы F на F.
Так как в формуле F есть лишь конечное число
логических знаков, то бэровский класс F конечен.
Формула F называется логически истинной, если
она истинна для всех оценок атомарных формул, т. е.
если F = X, где X обозначает все канторовское про-
пространство. Мы готовы теперь сформулировать наш
вариант теоремы Гёделя о полноте.
Формула доказуема тогда и только тогда, когда
она логически истинна.
Заменим временно правило Л~ввеДения> сформу-
сформулированное выше, на бесконечное правило
Г, Ft для всех t
Г, д х Fx '
Выводы в модифицированном таким образом исчис-
исчислении предикатов изоморфны выводам в формаль-
формальной системе для борелевских множеств, построенной
в предыдущем пункте, если мы сопоставим каждой
формуле F борелевское множество F. С другой сто-
стороны, приведенное выше бесконечное правило, экви-
эквивалентно обычному правилу Л'введения. Действи-
Действительно, если Г, Ft доказуемо для всех термов t, то,
в частности, доказуемо Г, Fa, где а — свободная пе-
переменная, не входящая в Г,Л*^*> так как свободная
переменная является термом. Обратно, если даны
произвольный терм t и вывод секвенции Г, Fa, где
а — свободная переменная, не входящая в Г, ^F
100 Гл. 3. Ординальные числа и борелевские множества
32. Полнота логики второго порядка с сечением
101
то позаботимся сначала о том, чтобы переменные,
связываемые при Д-введениях в доказательстве Г, Fa,
не входили бы в t. Затем мы можем заменить а на i
во всем доказательстве, получая тем самым вывод
Г, Ft. Доказательство закончено.
Основная теорема Генцена утверждает, что пра-
правило сечения имеет место для исчисления предикатов
как производное правило вывода:
T,F в.-F
сечение
Г, в
Это утверждение оказывается непосредственным
следствием справедливости правила сечения для ис-
исчисления борелевских множеств (через теорему о пол-
полноте). Действительно, если Г, F и в, —F, то по одной
половине теоремы о полноте мы получаем Г, F и
в, CF. Отсюда правило сечения для борелевских мно-
множеств позволяет нам заключить Г, в, а другая поло-
половина теоремы о полноте дает Г, в, что и требовалось.
Хотя это доказательство основной теоремы и кон-
конструктивно, оно, в отличие от доказательства Генцена
[1], не финитно в строгом гильбертовском смысле.
32. Полнота логики второго порядка с сечением
Мы будем теперь рассматривать логику второго
порядка, получаемую из логики первого порядка
(предыдущий раздел) добавлением замкнутых пре-
предикатных переменных к списку символов и разреше-
разрешением применять в формулах кванторы по предика-
предикатам.
К аксиомам и правилам вывода для первого по-
порядка мы добавляем кванторные правила второго
порядка и правило сечения
Г FT
V-введение '
Д-введение
сечение
Г, V XFX
T,FA
Г, л XFX
T,Fr,—F
Здесь Т обозначает предикатный терм, А — сво-
свободную предикатную переменную, не входящую в Г,
AXFX.
Зафиксируем взаимно однозначную рекурсивную
нумерацию
Fo, Fx, ..., Fn, ...
всех формул, а не только атомарных, как в предыду*
щем пункте. Для произвольной формулы F = Fn мы
будем обозначать через F простое множество в кан-
торовом пространстве, определяемое условием, что
и-я координата равна |.
Мы переходим к определению внутреннего пре-
предельного множества V в канторовом пространстве,
которое образует множество всех полных оценок. V —
это пересечение следующих открытых множеств:
1 Для любой формулы F — открытые множества
j^F и СРЦС^.
2 Для любой формулы JFvG — открытые множе-
множества CFUFvG, CGUfvG и F[}G[}CF\G.
3 Для любой формулы FaG — открытые множе-
множества fucIZg, gucfagTh cfucguJKg.
4 Для любой формулы V*^* открытые множе-
множества [JFt\)CyxFx, где объединение берется по всем
предметным термам t, и открытое множество CFt\j
U \/xFx для любого предметного терма t.
5 Для любой формулы /\xFx — открытое мно-
жество ЦCFt U Л*^* и открытое множество Ft\j
Для любого предметного терма t.
бй ф \/XFX
A р р
6 Для любой формулы \/XFX — открытое множе-
множество [JFT U CS/XFX, где объединение берется по всем
предикатным термам от подходящего числа перемен-
переменных, и открытое множество CFT\)\/XFX для каждого
предикатного терма Т.
7 Для любой формулы /{XFX открытое множе-
множество \JCFT\J hXFX и открытое множество FT\j
для любого предикатного терма Т.
102 Гл. 3. Ординальные числа и борелевские множества
Формула F истинна для всех полных оценок, если
FsF, т. е. если CV, F выводима в исчислении боре-
левских множеств. Мы докажем следующий кон-
конструктивный вариант теоремы Генкина [1] о полноте
для логики второго порядка с сечением.
Формула истинна для всех полных оценок тогда
и только тогда, когда она доказуема в логике вто-
второго порядка с сечением.
Достаточность. Заменим правила Л'ввеДения бес-
бесконечными правилами
Г, Ft для всех t Г, FT для всех Т
Г, \xFx ' Г, Л XFX
Как и в случае логики первого порядка, секвенция
выводима посредством этих бесконечных правил то-
тогда и только тогда, когда она выводима в обычной
логике второго порядка.
Непосредственным следствием построения V яв-
является доказуемость следующих семи типов борелев-
ских секвенций:
32. Полноту логики второго порядка с сечением
103
1 CV, F, -F и CV, CF, C—F
2 CF, CF, FyG и CF, CG,
3 CF, CF, CG,
4 CF, С Ft, VxFx
5 CF, CC\F~t, l\xFx
6 CF, CFT, S/XFX
7 CV, CflFT,
Для секвенции Г, состоящей из формул второго по-
порядка, обозначим через Г секвенцию, состоящую из
простых множеств, полученную путем замены ка-
каждой формулы F из Г на F.
Мы докажем индукцией по длине доказательства
Г, что если Г выводима в логике второго порядка, то
CF, Г выводима в исчислении борелевских множеств.
Базис. Если Г — аксиома, то CV, Г получается из
CV, F, —F утончением. Шаг индукции. Допустим,
например, что Г = Д, A%FX и чт0 последнее приме-
применение правила в доказательстве Г есть
A, FT для всех Т
Д, л XFX
По индукционному предположению мы имеем CF,
Л/Т для всех Т. П -введение дает CF, Д, П^"- Да-
Далее, мы знаем, что CF, СП^Г, Л-^7-^ выводима
в исчислении борелевских множеств. Сечение, приме-
ненное к_этим двум посылкам, дает CF, Д, ДХ^=
= CV, Г, что и требовалось. Остальные правила
вывода рассматриваются аналогично.
Необходимость. Допустим, что формула F истин-
истинна для всех полных оценок, т. е. что мы имеем вывод
CV, F в исчислении борелевских множеств. Мы пре-
преобразуем этот вывод в вывод формул F в логике вто-
второго порядка с сечением.
Так как борелевское исчисление не содержит се-
сечения, то имеет место принцип подформульности. Та-
Таким образом, любая секвенция из доказательства
CV, F имеет вид
А Ат, В, Вп, CF, F,
где В и ..., Вп — некоторые из замкнутых множеств,
объединением которых является CV, а А\ Ат —
некоторые из атомарных мйожеств (т. е. множеств,
ограничивающих лишь одну координату), пересече-
пересечениями которых являются упомянутые замкнутые мно-
множества. Некоторые из множеств Ль ..., Ат, В и ...
..., Вп, CV могут, разумеется, отсутствовать.
Множество Л,- имеет вид G или CG, где G — не-
некоторая формула. В первом случае заменим Л,- на G,
во втором — на —G. Сделаем это для всех i= 1, ...
..., т. Далее мы просто вычеркнем множества
fii, ..., Вп, CV и, наконец, заменим F на F. Таким
образом мы преобразуем каждую секвенцию из дан-
данного вывода CV, F в секвенцию, состоящую из фор-
формул второго порядка. Конечная секвенция CV, F пе-
104 Гл. 3. Ординальные числа и боре.гевские множества
ГЛАВА 4
реходит в F. Мы получили вывод F, в котором ка-
каждая аксиома и применение правила является част-
частным случаем следующих аксиом и правил вывода.
Аксиомы — это секвенции (не обязательно состоя-
состоящие из атомарных формул), содержащие как F, так
и —F для некоторой формулы F, а правила вывода —
это
Г, F Г, —F
Г
Г, -F Г, -G r.fvG
Г, - F Г, F л О Г, - О Г, F л G
Г, — Ft для всех / Г, V xFx
Г, — FT для всех Г Г, V XFX
Г, — Ft Г, л xFx
Г
Г, -FT Г, л XF X
Г
Так как аксиомы легко могут быть выведены в ло-
логике второго порядка с сечением, а правила вывода
справедливы как выводимые правила, мы видим, что
формула F выводима в логике второго порядка с се-
сечением. Доказательство закончено.
В действительности в ходе доказательства мы по-
получили больше, чем нам было нужно, а именно неко-
некоторую нормальную форму выводов в логике второго
порядка с сечением.
ТЕОРИЯ МЕРЫ
33. Продолжение меры и ее основные свойства
Рассмотрим канторовское пространство и сопо-
сопоставим любой окрестности
/ == 0100 ... |0
п
меру цA) = 2~п. Эта мера ц будет называться мерой
Лебега. Более общо, мы можем рассмотреть любую
общерекурсивную функцию ц, которая сопоставляет
любой окрестности / некоторое вычислимое веще-
вещественное число таким образом, что
С точностью до порядка слагаемых представле-
представление простого множества
р=или/»... и/.
однозначно, если мы потребуем, чтобы окрестности
Л, h, .. •, In были дизъюнктны и п минимально. Ме-
Мера Р тогда однозначно определена, если положить
Очевидно, что
и что
для любого простого множества Р. Далее, нетрудно
доказать теорему сложения
для простых множеств Р и Q.
106
Гл. 4. Теория меры
Мы скажем, что открытое множество U ограниче-
ограничено вычислимым действительным числом е, если
ц(Р)<е
для любого простого множества Р s ?Л Заметим, что
ввиду открытости U содержащиеся в нем простые
множества образуют рекурсивно перечислимое мно-
множество.
Следующая лемма, являющаяся простым след-
следствием теоремы Гейне — Бореля о покрытиях, оказы-
оказывается фундаментальной. Действительно, вне зависи-
зависимости от рассматриваемого пространства основные
теоремы переносятся без изменений, как только дока-
доказана эта лемма.
Если Uo, U\, ...— последовательность открытых
множеств, ограниченных соответственно числами ео,
N
ei и 2е»^е для всех N, то \JUn ограничено
о
числом е.
Пусть Р — простое множество =U^ По лемме
Гейне —Бореля мы можем найти простые множества
Ль Pi Рп, такие, что
P<=P0UP,U ...
Следовательно,
что и требовалось доказать.
Борелевское множество А измеримо, если для лю-
любого вычислимого действительного числа е > 0 (ра-
(разумеется, достаточно брать числа вида 2~п, например)
мы можем найти простое множество Р и открытое
множество U, такие, что
AAPs=U
и U ограничено числом е. Мы покажем, что суще-
существует единственное вычислимое действительное чис-
чис33. Продолжение меры и ее основные свойства 107
ло ц(Л), называемое мерой множества А, со свой-
свойством
при любом выборе е >• 0, простого множества Р и от-
открытого множества U. Действительно, предположим,
что
AAP<=U, AAQ<=V,
где Р и Q — простые, а открытые множества U и V
ограничены соответственно числами е и и\. Тогда
Р Д Q s (Л Д Р) U (Л Д Q) с С/ U К,
так что
так как PAQ — простое множество, г U [} V ограни-
ограничено числом е -f tj согласно фундаментальной лемме.
Это показывает существование и единственность
Только что введенная мера — это продолжение
меры, введенной ранее только для простых множеств.
Действительно, если А — простое множество, то мы
можем положить Р = А и U = 0, так что ?/ ограни-
ограничено числом е = 0. Следовательно, новая мера мно-
множества А совпадает с его первоначальной мерой.
В частности,
ц@) = О, ц(Х)=1.
Далее,
для любого измеримого множества А, так как \i(A)
может быть сколь угодно хорошо аппроксимирована
числами ц.(Р), где Р — простое множество, а выше
отмечено, что ц(Р) ^ 0.
Если А — измеримое множество, то СМ — тоже
измеримое и
Пусть дано произвольное вычислимое действи-
действительное число е >• 0. Так как А измеримо, можно
!08
Гл. 4. Теория меры
33. Продолжение меры и ее основные свойства
109
найти простое множество Р и открытое множество U,
такое, что
AAPs=U
и U ограничено числом е. Тогда
и, так как СР— простое и
СЛ ДСР=ЛДР<=?/,
мы получаем
что вместе с \i(P) -\-\i(CP) = 1 и произвольностью
е дает искомое соотношение
Если А и В — измеримые множества, то А[) В и
А П В — тоже измеримые и
Пусть е > 0 произвольно. Так как А и В измери-
измеримы, мы можем найти простые множества Р и Q и
открытые множества U и V, ограниченные числом е,
такие, что
А АР ?U, BAQ<=V.
Тогда
(A U В) А (Р U Q) ? (А А Р) [} (В A Q) <= С/ U К,
где Р U Q, PDQ — простые и U [} V ограничено
числом 2е согласно фундаментальной лемме. Следо-
Следовательно, Лив a A f] В измеримы и
\]i(A[iB)-\i(P\jQ)\<2e,
Так как е > 0 произвольно и теорема сложения вер-
верна для простых множеств Р и Q, она следует отсюда
также и для измеримых множеств А и В.
?сли Ло, Ль ...—рекурсивная последовательность
оо
дизъюнктных измеримых множеств «2|i (Лп) сходит-
о
ОО
ся, го L/Лп измеримо и
Пусть е > 0 произвольно. Для любого п мы мо-
можем приблизить Ап простым множеством Рп таким
образом, что
где Un открыто и ограничено числом е2~"~!. Далее,
оо
так как 2 V- {An) по предположению сходится, мы мо-
о
жем найти столь большое N, что
N+1
N
О
N оо
и
О
Г=й^ий(^и^),
Полагая
мы получаем
где Р — простое, U — открытое, ограниченное числом
N+1
по
Гл. 4. Теория меры
Это доказывает измеримость \jAn. Теперь
N
\
J An 1 — \i (Р)
о 1
N
<
^ 2 e2
и
N oo
"V .. i * \ "V .. / л \
A
N W
где второе неравенство следует из (J Ап Д Р ? (J Un
о о
и фундаментальной леммы. По предыдущей теореме
N \ N
так что
и, так как выбор числа е был произвольным, мы по-
получаем искомое соотношение
?слм Ло, Лtt ... — рекурсивная последовательность
IN \
измеримых множеств и ^\\}Ап) сходится при N-*¦ оо,
00
то \jAn измеримо и ц(
(J)= ^m V- fL
О \ о / N-X» \ о
Это следствие получается применением предыду-
предыдущей теоремы к последовательности
Bq=Aq, Вп==Л„ПСЛ„_,П ... ПСЛ0, «=1, 2
34. Измеримые и неизмеримые открытые множества II!
По двойственности мы видим, что следствие также
справедливо, если повсюду заменить (J на П-
Если А — борелевское множество и
В<=А<=С,
где В и С измеримы и имеют одинаковую меру, то А
измеримо и ц(Л) = \i(B) = \i(C).
Так как Л = (Л — В) U В, А — В s С — В, С —В
измеримо и ц,(С — В) = ц(С) —[х(В) =0, то доста-
достаточно доказать, что борелевское подмножество любо-
любого множества меры нуль само имеет меру нуль. Это
будет сделано в п. 35.
Борелевское множество А измеримо тогда и толь-
только тогда, когда мы можем найти измеримое внешнее
предельное множество В и измеримое внутреннее пре-
предельное множество С, такие, что
(),()
Достаточность немедленно следует из предыду-
предыдущей теоремы. Обратно, предположим, что А измери-
измеримо. Тогда для любого п мы можем найти простое
множество Рп, такое, что
Л Д/>„ = ?/„,
где Un открыто и ограничено числом 2~п. Множества
являются соответственно внешним и внутренним пре-
предельным множеством и
В<=Л<=С; ВДР„<=?/„; СДРЙ<=?/„,
откуда следует, что В и С измеримы и имеют ту же
меру, что и Л.
34. Измеримые и неизмеримые открытые множества.
Теорема Брауэра
По определению А есть непустое открытое множе-
множество, если
112
Гл. 4. Теория меры
где h, h, ... — рекурсивная последовательность окре-
окрестностей. Мы покажем, что А измеримо тогда и только
/ N \
то1да, когда n((J/n] сходится при N-*oo, и в этом
случае
/Л \
ц{А) = lim ц I \JIn] •
ЛГ-»°о \ о /
Пусть А измеримо, и пусть дано произвольное
е > 0. Тогда мы можем найти такое простое множе-
множество Р и такое открытое множество U, ограниченное
числом е, что
Л Л/><=?/.
Отсюда мы заключаем
так что теорема Гейне — Бореля позволяет нам найти
столь большое N, что
Ps=[Jln{}U.
о
N
Теперь PA^Jln — простое множество s6' и, следо-
следовательно,
N
0
что вместе с
дает
Это завершает доказательство необходимости усло-
условия, а достаточность следует из предыдущего пункта.
Брауэр [3] вводил измеримость открытого множе-
множества (Bereich) посредством вышеприведенного усло-
34. Измеримые и неизмеримые открытые множества ИЗ
вия. Мы получаем, что для открытых множеств его
определение совпадает с нашим.
Теперь легко построить неизмеримое открытое
множество. Пусть f — общерекурсивная функция, пе-
перечисляющая без повторений нерекурсивное множе-
множество натуральных чисел. Окрестности
/„ = 000... 0|, я = 0, 1, ...,
f (п)
дизъюнктны, так что
1 N
1*(
N
V n-t(n-l
Ъ2
где ц — мера Лебега. Как показано в п. 16, правая
часть равенства не сходится при N -> оо и, следова-
следовательно,
— неизмеримое открытое множество.
Мы переходим к доказательству важной теоремы
Брауэра [3] (содержащейся также в книге Рейтинга),
не имеющей классического аналога.
Если А — измеримое множество, то для любого
е > 0 мы можем найти измеримое открытое множе-
множество В, дополнительно локализованное и такое, что
А<=В, ц(В)^ц(А) + е.
Для любой окрестности
мы можем решить, что имеет место
(i (/ — А) ^ е2~п~
или
вычисляя ц(/ — А) с достаточной точностью. Ясно,
что мы можем дать эффективную процедуру, которая
114
Гл. 4. Теория меры
34. Измеримые и неизмеримые открытые множества МП
всегда выбирает один определенный из этих двух слу-
случаев. Пусть В„ — простое множество, являющееся
объединением тех из окрестностей длины п, для ко-
которых мы остановились на первом случае. Мы пока-
покажем, что открытое множество
удовлетворяет условиям теоремы.
Пусть / — произвольная окрестность ? А. Тогда
ц(/— Л) =0, так что необходимо /sBnsS, где
п обозначает длину /. Мы заключаем, что As В.
Далее мы покажем, что В измеримо. Из определе-
определения В„ мы видим, что
ц (Вп - Л) < г2~2п-12п = е2"п-'.
Так как ряд, общий член которого дается правой
частью равенства, суммируем, мы заключаем из пре-
оо оо
дыдущего пункта, что \J(Bn — A) = {jBn — A = B — А;
о о
тем самым В = A U (В — А) измеримо и
ц (В)- ц (А) = ц (В - А) < 2
е.
Мы покажем, наконец, что если / — окрестность
длины п, то /sB тогда и только тогда, когда /?
? Во U Bi U ... U Вп. Так как очевидным образом
можно решить, верно ли это включение, отсюда сле-
следует, что В дополнительно локализовано. Возьмем
производящие схемы, которые порождают окрестно-
окрестности всех В„, п = 0,1, ..., и отметим их, скажем, сим-
символом В. Добавим новые схемы
А
Ах
Ах Ах Вх х Ах х Ах
/4*0 Ax\ x xO x\
Мы покажем, что если обе окрестности / 0 и / |
доказуемы в этой системе Поста, то это же верно для
окрестности /. Это очевидно, если какая-либо из / 0,
/ | получена по одной из двух последних схем, по-
этому предположим, что /0 и /|—окрестности из
В„+1, где п обозначает длину /. Тогда обязательно
ц (/0 - А) < е2-2"-\ ц (/1 — Л) < е2-2п~3,
так что
что вынуждает / быть одной из окрестностей из Вп.
Теперь /sB означает, что / доказуемо в приведен-
приведенной выше системе Поста и тогда уже / ? Во и В4 U ...
... U В„, где п — длина /. Это завершает доказатель-
доказательство.
Мы знаем, что непустота замкнутого множества,
вообще говоря, недостаточна для того, чтобы оно со-
содержало конструктивную точку. Однако, как отме-
отмечено Брауэром [3], из только что доказанной теоремы
следует, что если замкнутое множество измеримо и
имеет положительную меру, то мы можем найти в
нем конструктивную точку. Это следствие было пе-
переоткрыто Крайзелем и Лакомбом [1], а также Зас-
Заславским и Цейтиным [1].
По данному замкнутому множеству положитель-
положительной меры мы можем найти содержащуюся в нем кон-
конструктивную точку.
Согласно предыдущей теореме, мы можем найти
локализованное замкнутое измеримое подмножество
данного множества, все еще имеющее положитель-
положительную меру. Следовательно, оно непусто и, будучи ло-
локализованным, содержит конструктивную точку.
Теперь мы можем обсудить различие между брау-
эровским и принятым нами определением измеримо-
измеримости. Как уже отмечено, эти два определения эквива-
эквивалентны, если мы ограничимся множествами, которые
открыты или замкнуты. Однако для внутренних и
внешних предельных множеств это уже не так.
Точечный вид А измерим, по Брауэру [3], если для
любого е > 0 мы можем найти простое множество Р
и открытое измеримое множество U, такие, что
AAP^U и ц,(?/)-<е. Если забыть, что мы пред-
предпочли понятие борелевского множества брауэров-
скому понятию вида, то единственная разница между
116
Гл. 4. Теория меры
35. Множества меры нуль
117
этими двумя определениями измеримости в том, что
Брауэр требует, чтобы U было измеримым и ц(?/)г=;е,
в то время как мы удовлетворяемся тем, что U огра-
ограничено числом е.
Рассмотрим построенное в п. 20 внутреннее пре-
предельное множество А = f\Gn, которое содержит все
конструктивные точки, хотя при любом п множество
С ограничено числом 2~" относительно меры Лебега.
Согласно нашему определению, А очевидным образом
измеримо и ц(А)=0. Следовательно, если F — изме-
измеримое замкнутое подмножество множества А, то
(х (F) = 0. Допустим теперь, что G — измеримое от-
открытое множество, такое, что A s G. Тогда G содер-
содержит все конструктивные точки и мы можем заключить
из теоремы Брауэра, что \i(G)= 1. Это показывает,
что А не может быть измеримо по Брауэру, так как
точечный вид измерим в смысле Брауэра тогда и
только тогда, когда для любого е > 0 мы можем
найти измеримые открытое и замкнутое множества G
и F соответственно, такие, что F s A s G и
)n() n()<
Имеется несколько причин, по которым мы приня-
приняли более широкое определение измеримости, чем
Брауэр. Прежде всего, проблема всегда состояла в на-
нахождении непротиворечивого и возможно более ши-
широкого продолжения меры, определенной сначала
лишь для простых множеств. Наше продолжение, хотя
оно идет дальше брауэровского, не влечет отхода от
конструктивной точки зрения. Во-вторых, тот факт,
что наше определение позволяет нам построить вну-
внутреннее предельное множество меры нуль, содержа-
содержащее все конструктивные точки, хотя оно и обеспокоит
тех, чей континуум состоит только из конструктивных
точек, находится в полном согласии с интуиционист-
интуиционистской концепцией континуума как среды свободного
становления. В-третьих, принятое определение дает
нам возможность доказать новую теорему, которая
может служить оправданием понятия случайной по-
последовательности, задуманного фон Мизесом и разра-
разработанного Вальдом и Чёрчем (см. Чёрч [3]). Это будет
показано в следующем пункте.
35. Множества меры нуль
Удобно использовать следующее несколько упро-
упрощенное определение множества меры нуль, или, как
мы будем иногда говорить, нулевого множества.
Борелевское множество А измеримо и имеет меру
нуль тогда и только тогда, когда для любого е > 0
мы можем найти открытое множество U, такое, что
и U ограничено числом е.
Чтобы увидеть это, допустим, что А измеримо и
ц(А)= 0. Тогда для данного е > 0 мы можем найти
простое множество Р и открытое множество U, такие,
что
AAPsU
и U ограничено числом е. V = Р U V открыто,
и мы покажем, что V ограничено числом е. Пусть Q —¦
простое множество s V. Тогда
AA{P[)Q)s{AAP)[){Q-P)s=U,
так что
что и требовалось доказать. Достаточность »того ус«
ловия очевидна.
После этой переформулировки определения мно-
множества меры нуль непосредственно ясно, что борелев-
борелевское подмножество нулевого множества — снова нуле-
нулевое множество.
Если А — борелевское множество и A s= В, где В
измеримо и цE) = 0, то А измеримо и р(А)= 0.
Отсюда и из результатов п. 23 мы получаем след-
следствие.
Если Ао, Аи ... — рекурсивная последовательность
нулевых множеств, то \JAn — нулевое множество.
118
Гл. 4. Теория меры
35. Множества меры нуль
119
Мы переходим к доказательству того, что понятие
измеримости, с которым мы имеем дело, позволяет
построить внутреннее предельное множество, макси-
максимальное в том смысле, что в нем содержится любое
другое нулевое множество. Этот результат был полу-
получен Мартин-Лёфом [1].
Мы уже знаем, что открытые множества могут
быть рекурсивно перенумерованы. Учитывая это, мы
покажем, что для каждого вычислимого в > 0 (доста-
(достаточно брать его в виде 2~") мы можем рекурсивно
перечислить все открытые множества U, такие, что
для всех простых множеств Р s U. Выберем произ-
произвольное открытое множество U, и пусть /о, Л, ... —
рекурсивная нумерация составляющих его окрестно-
окрестностей. Модифицируем U, взяв объединение лишь тех
In, для которых ц(/0 U ... U/n)< е. Так как послед-
последнее отношение рекурсивно перечислимо (в этом при-
причина того, что мы выбрали < вместо <:, несколько
отклонившись от определения ограниченности), то мо-
модифицированное U — открытое множество, удовлетво-
удовлетворяющее вышеприведенному условию. Далее, те откры-
открытые множества U, для которых это условие уже вы-
выполнено, остаются неизменными после модификации.
Мы показали, что для любого п мы можем рекур-
рекурсивно перечислить открытые множества, удовлетво-
удовлетворяющие указанному условию при е = 2~п. Но тогда
мы можем также рекурсивно перечислить внутренние
предельные множества
Г\иа,
которые таковы, что ц(Р)<2гп для всех простых
множеств Р s Un. Очевидно, что все эти внутренние
предельные множества измеримы и имеют меру нуль.
Их объединение, скажем А, является, следовательно,
множеством меры нуль.
Пусть В — произвольное множество меры нуль.
Тогда, по определению нулевого множества, мы мо-
можем найти открытые множества ?/„, такие, что
и ц(Р)<2~" для всех простых множеств Р s Un,
n = 0,1. ... . Следовательно, В s А, так что А — ма-
максимальное множество меры нуль. Далее, будучи
само нулевым множеством, А содержится в некотором
внутреннем предельном множестве меры нуль, кото-
которому оно должно быть равно из-за максимальности.
Следовательно, А — внутреннее предельное множе-
множество.
Мы построили внутреннее предельное множество
меры нуль, содержащее любое множество меры нуль.
Переходя к дополнениям, мы видим, что мы могли
сопоставить любой мере ц некоторое внешнее пре-
предельное множество, являющееся минимальным мно-
множеством меры 1. Его естественно назвать конструк-
тивным носителем ц.
Мы хотели бы сделать следующее замечание от-
относительно классического понятия носителя. Он опре-
определяется как дополнение объединения всех окрестно-
окрестностей /, для которых |i(/)=0. Классически это
замкнутое множество. Однако легко построить вычис-
вычислимую меру ц, для которой множество окрестностей /,
таких, что ц.(/)= 0, не является рекурсивно перечис-
перечислимым. Таким образом, мы не можем в общем случае
получить классический носитель как конструктивное
замкнутое множество, а вынуждены довольствоваться
внутренним предельным множеством П^п, где Gn —
объединение окрестностей / длины я, для которых
ц(/)>0. Будучи множеством меры один, оно навер-
наверняка содержит конструктивный носитель, но в общем
случае более объемисто. Например, классический но-
носитель меры Лебега равен всему пространству, в то
время как конструктивный носитель не содержит ни
одной конструктивной точки. Далее, за исключением
случая дискретного пространства, классический носи-
носитель не имеет никакого отношения к понятиям абсо-.
лютной непрерывности и сингулярности. С другой сто*
роны, две конструктивные меры являются, например,
сингулярными тогда и только тогда, когда их кон«
структивные носители дизъюнктны.
120
Га 4. Теория меры
Наконец, отметим следствие, усиливающее послед»
нюю теорему из п. 33.
Если дано измеримое множество А, то мы можем
найти измеримое внешнее предельное множество В и
измеримое внутреннее предельное множество С, такие,
что В^А^С, [i(C — В)=»0, и, далее, любое изме*
римое множество, которое отличается от А не более
чем на нулевое множество, также содержится между
В и С.
Возьмем В и С, построенные в конце п. 33, и
модифицируем их, вычтя максимальное нулевое мно-
множество из В и добавив максимальное нулевое множе-
множество к С. Модифицированные таким образом В и С
очевидно удовлетворяют условиям теоремы.
ПРИЛОЖЕНИЕ
Цель этого приложения — коротко объяснить
смысл, который мы придаем термину конструктивный.
Все рассматриваемые нами объекты должны быть
конструктивными объектами, т. е. конечными конфи-
конфигурациями знаков. Эти знаки, которые могут быть не-
непосредственно распознаны как равные или различные,
рассматриваются как далее неразложимые атомы.
Конструктивные объекты должны рассматриваться
как конкретные объекты, т. е. в конечном счете как
существующие во времени и пространстве. Например,
формулы и доказательства в формальной системе яв-
являются конструктивными объектами в этом смысле, а
произвольные осмысленные утверждения и нефор-
неформальные доказательства не являются. Также и мно-
множества в обычном интуитивном смысле, безусловно,
не являются конструктивными объектами.
Мы принимаем анализ оперирования над кон-
конструктивными объектами по механическим правилам,
данный Постом [1] и Тьюрингом [1]. В соответствии с
этим анализом правила вычислений, так же как и
сами вычисления, снова являются конструктивными
объектами и оказывается разрешимым вопрос о кор-
корректности вычисления по данным правилам. Точнее,
имеется разрешимый предикат Т(е,пг,п), выражаю-
выражающий, что п — корректное вычисление по правилу е с
начальными данными т, и в этом случае мы можем
считывать результат U(n) вычисления п. Так как кон-
конструктивные объекты — это просто конфигурации зна-
знаков, их можно закодировать натуральными числами.
Мы скажем, что е применимо к т, если суще-
существует п, такое, что Т(е, т, п);
УпТ(е, ш,п).
J22
Приложение
Приложение
123
Отсюда немедленно получается, что не может быть
правила, которое позволило бы нам решать для лю*
бого правила га, применимо ли оно к самому себе.
Действительно, тогда имелось бы правило е, приме-
применимое к га тогда и только тогда, когда га не приме-
применимо к самому себе:
V tiT(e, га, п)-*-»- — V пТ(т, га, п).
В частности, е применимо к себе тогда и только
тогда, когда е не применимо к себе:
V пТ(е, е, п) *-> — У пТ(е, е, п),
что противоречиво.
Любая теорема конструктивной математики, после
того как она до конца проанализирована, имеет ут-
утвердительную форму: найден конструктивный объект
с определенным свойством. Критический вопрос со-
состоит в том, какие свойства мы собираемся считать
конструктивно осмысленными.
Простейший случай представляет разрешимое
свойство Р(п). Это просто правило, позволяющее нам
вычислять истинностное значение для любого нату-
натурального п. В применении к таким свойствам класси-
классические пропозициональные связки Д (и), V (или),
— (не),-»- (влечет) имеют четкий вычислительный
смысл, который задается обычными таблицами истин*
ности, и применима классическая логика высказыва*
ний. Например, Р(п)У —Р(п)— разрешимое свой-
свойство, которое имеет место для всех натуральных п.
Классически произвольные логические формулы,
построенные из разрешимых предикатов с помощью
пропозициональных связок и кванторов Д (для вся-
всякого) и V (существует) по числовым переменным,
считаются осмысленными в терминах классического
понятия истинности, и законы классической логики
предикатов истинны при такой интерпретации. Напри-
Например, формула
Д еV га Дп(Г(е, е, ra>v — Т(е, е, п))
истинна в классическом смысле.
Конструктивно произвольные формулы, построен-
построенные из разрешимых предикатов с помощью v, a-, —,
—*¦» Л и V» не считаются осмысленными без дальней-
дальнейшего анализа, и только после того, как такой анализ
проведен, имеет смысл спрашивать, какие законы ло-
логики верны.
Начнем с того, что будем считать конструктивно
осмысленными свойствами вида Пг
/\m\JnP(га, п),
где Р разрешимо. Частными случаями являются П?,
т. е. /\пР(п) и 2?, т. е. УпР(п). Самый типичный
пример Пг-свойства — это применимость правила е
ко всем числам га:
t\m\lnT(e, m,n).
Утверждая. f\,m\/nP(m, n), мы имеем в виду,
что мы нашли метод, позволяющий нам каждый раз,
когда нам дано натуральное число т, найти такое на-
натуральное п, что верно Р(пг,п). Заметим, что подра-
подразумеваемый смысл Иг утверждения — тот же самый
и при классической интерпретации. Действительно,
если /\m\/nP(m, n) истинно классически, то мы дей-
действительно имеем метод нахождения для каждого m
натурального числа п, такого, что истинно P(m,ri).
Мы просто вычисляем одно за другим истинностные
значения
Р(га, 1), Я(га, 2), ....
пока не обнаружим п, для которого верно Р(пг,п).
Таким образом, между классической и конструктив-
конструктивной интерпретациями Пг утверждений нет разницы в
отношении подразумеваемого смысла. Разница за-
заключается в допускаемых методах доказательства^
Например, пусть Р(п) —утверждение, что п есть
гёделевский номер некоторого доказательства в
аксиоматической теории множеств (или даже в ариф-
арифметике второго порядка) с последней формулой 0 = 1.
Тогда Р — разрешимый предикат, а утверждение
Ап-Р(п),
124
Приложение
Приложение
125
выражающее непротиворечивость этой формальной
системы, имеет место классически, хотя в настоящее
время мы не обладаем его конструктивным доказа-
доказательством.
Рассмотрим теперь произвольную предваренную
формулу
Л «1V «1 ... Л /"/ V п,Р (т„ п, т}, п,)
с разрешимым Р. Мы скажем, что эта формула кон-
конструктивно истинна, если мы нашли правила fi, fz, .. *
..., fj, такие, что ft применима ко всем i-членным си-
системам натуральных чисел, i= 1, ...,/, и
Атх ... «/?(«„/,(«,), ..., m,, f,(mx m,)).
В полной записи это значит, что мы нашли правила
U, h> • • •, f], такие, что
Ащ ... myV«i ... n,(T(flt тищ)л ...
... л f(f/,(/?*! т^.п^лр^, и(щ) mJtU (n;))).
Это свойство считается конструктивно осмысленным,
так как оно имеет вид П<>.
Формула
AeV тЛп(Т(е, е, т)м - Т(е, е, п))
не является конструктивно истинной, хотя она истинна
классически. Действительно, предположим, что f—
правило, применимое ко всем натуральным числам и
удовлетворяющее
Aen(T(e,e,f(e))w — T(e,e,n)).
Тогда
T(e,e,f(e))++VnT(e,e,n),
так что мы имели бы разрешающую процедуру для
предиката \/пТ(е,е,п), что невозможно. Этот при-
пример показывает, что законы классической логики, в
частности закон исключенного третьего, могут вести
к заключениям, не являющимся конструктивно истин-
истинными.
Первые две главы основаны на некритическом при-
принятии Пг- - утверждений как конструктивно осмыслен-
осмысленных, а нужные рудименты логики можно понижать в
терминах конструктивной истинности.
Мы уже видели, что классическое понятие истины
отличается от понятия конструктивной истинности.
Тем не менее оказывается, что понятие арифметиче-
арифметической истины может быть конструктивно понято со-
совершенно иным способом, с помощью интерпретации
отсутствием контрпримера (которая была намечена
Эрбраном [1] для случая логики предикатов и рас-
распространена на теорию чисел Крайзелем [1]; послед-
последнему принадлежит и терминология). Рассмотрим сно-
снова предваренную формулу
A«iV«i ... Aml\/nlP(mbnb .... m,, n,),
которую мы обозначим через А. Тогда
... f/A«i ... n,—
— P(fu Пи .... fj(nlt .... rty-,), Яу),
где область значений fi — все теоретико-числовые
функции от i—1 аргумента, i=\ /. Следова-
Следовательно,
A^-Afi ... ft V«i ... rijPi.fi, "i. •••• M»i. -. n/-i). »/).
причем последняя формула называется *) интерпрета-
интерпретацией отсутствием контрпримера для А. Кодируя
fi, ..., fj в виде единой бесконечной последователь-
последовательности натуральных чисел и П|, ..., п,- в виде одного
натурального числа, мы видим, что интерпретация от-
отсутствием контрпримера имеет вид III,
Amym2... ntn ... V tiP (mym2 ... tnn),
') Здесь автор неточен. Интерпретацией отсутствием контр-
контрпримера для А Крайзель называет не правую часть последней
эквивалентности, а формулу
VAf, .. .W/Af, ...f,P (A, Nu ...,fi (JV, NM), If,), (.)
где N{ Nj — переменные для функционалов и Ni обозна-
обозначает Ni (f i, ..., fj). Кандидатами на роль конструктивного
истолкования доказанной классически формулы А являются, по
Крайзелю, эффективные функционалы Ni Nj, удовлетворяю-
удовлетворяющие условию, стоящему в (*) после кванторов при любых финит-
финитных функциях U fj.
126
Приложение
Приложение
127
где Р — разрешимое свойство конечных последова-
последовательностей натуральных чисел. Наиболее типичным
примером ITi- свойства является свойство быть орди-
ординалом конструктивного второго числового класса.
Мы определим сейчас отношение: тутг... гпп за-
заперта для Р. Во-первых, если Р{т\т2...тп) верно,
то т^тг... тп заперта для Р. Во-вторых, если
rtiiniz... тпт заперта для Р при всех натуральных т,
то /П1/П2... тп заперта для Р. Трансфинитные индук-
индуктивные определения этого рода будут считаться кон-
конструктивно осмысленными, и мы будем говорить, что
nj-утверждение указанной выше формы имеет место,
если пустая последовательность ? заперта для Р.
Как легко видеть, эквивалентность
Д тхтг ... тпУ пР(т{т2 ¦.. тп)-*-+ ? заперта для Р
имеет место классически. Таким образом, подразуме-
подразумеваемый смысл П{ утверждения один и тот же как для
принятой нами конструктивной интерпретации, так и
для классической интерпретации. Разница только в
принимаемых методах доказательства. Это полностью
аналогично рассмотренной ранее ситуации для Иг-ут-
Иг-утверждений.
В интуиционистской математике обе части приве-
приведенной выше эквивалентности считаются осмыслен-
осмысленными. При этом считается, что область изменения пе-
переменной, связанной левым квантором всеобщности,—
это все свободно становящиеся последовательности
натуральных чисел. Тот факт, что эта эквивалентность
справедлива интуиционистски, является содержанием
бар теоремы Брауэра. Мы рассматриваем рассужде-
рассуждение Брауэра [11] в доказательстве бар теоремы скорее
как интуитивный анализ, оправдывающий наше опре-
определение истинности П{-утверждения.
Из того, что мы только что сказали, вытекает, что
если ограничиться П'-утверждениями, мы можем по-
понимать брауэровский континуум интуиционистски
эквивалентным образом, не используя свободно ста-
становящихся последовательностей. Совершенно иной
путь избавления от свободно становящихся последо-
последовательностей — истолкование кванторов по теоретико-
числовым функциям как кванторов по правилам,
определяющим такие функции, т. е. по числам е, та-
таким, 4ToA'"Vre T(e,m, /г). Это путь, избранный кон-
конструктивистской школой Маркова, а также Бишо-
Бишопом [1] в его недавней книге (которая не была
доступна автору в процессе работы над рукописью).
В случае Бишопа при помощи подходящих предпо-
предположений о непрерывности удается избежать патоло-
патологий, порожденных этой концепцией.
Интерпретация отсутствием контрпримера вместе
с нашим анализом И| утверждений позволяет нам по-
понимать конструктивно классическое понятие истины в
применении к арифметическим формулам. Так как
этот способ понимания арифметической истины клас-
классически эквивалентен классическому способу, то не
удивительно, что законы классической логики оказы-
оказываются истинными при этой интерпретации.
В действительности, как только мы соглашаемся
признавать Hi-утверждения конструктивно осмыслен-
осмысленными, мы можем понимать конструктивно гораздо
больше, чем понятие арифметической истинности.
Большая часть анализа, включая теорию ординалов
второго числового класса, борелевских множеств и
меры Лебега, может быть рассмотрена с использова-
использованием этих абстракций. Это показано в последних двух
главах. Однако для конструктивного анализа теоремы
Кантора — Бендиксона (Крайзель [2]) нужны более
сильные методы, и то же верно для аналитических и,
в еще большей мере, проективных множеств.
Более мощные средства, достаточные по крайней
мере для рассмотрения теоремы Кантора — Бендиксо-
Бендиксона, получаются введением более высоких конструк-
конструктивных числовых классов.
Список литературы
129
СПИСОК ЛИТЕРАТУРЫ
Этот список литературы содержит только работы, действи-
действительно упомянутые в тексте. Более полная библиография имеется
в Клини [3] и Клини и Весли II] (а также Б. А. Кушнер. Лекции
по конструктивному анализу, «Наука», М., 1973. — Перев.).
Банах и Мазур (Banach, Masur)
[1*] Sur les fonctions calculables, Ann. Soc. Pologne de Mathe-
matiques, 16 A937), 223.
Бишоп (Bishop E.)
[1] Foundations of constructive analysis, McGraw-Hill, New York,
1967.
Борель (Borel E)
[1] Les "Paradoxes" de la theorie des ensembles, Ann Sci Ecolt
Norm Sup., 25 A908), 443—448
[2] Lemons sur la theorie des fonctions, 2nd ed., Gauthier-Villars,
Paris, 1914.
Брауэр (Brouwer L. E. J)
[1] De onbetrouwbaarheid der logische principes, Tijdschrift voor
wijsbegeerte 2 A908), 152—158.
[2] Begrflndung der Mengenlehre unabhangig vom logischen
Satz vom ausgeschlossenen Dritten, Erster Teil, Verh Nederl
Akad Wetensch Afd Natuurk, Sect. 1, 12 A918), 5, 3—43.
[3] Begriindung der Mengenlehre unabhangig vom logischen
Satz vom ausgeschlossenen Dritten, Zweiter Teil, Verh Ne-
Nederl Akad Westensch Afd Natuurk, Sect. 1, 12 A919), 7,
3—33.
[4] Besitzt jede reelle Zahl eine Dezimalbruchentwicklung? Math.
Ann, 83 A920), 201—210.
[5] Begrflndung der Funktionenlehre unabhangig vom logischen
Satz vom ausgeschlossenen Dritten, Verh Nederl Akad We-
Wetensch Afd Natuurk, Sect 1, 13 A923), 2, 3—24.
[6] Beweis, dass jede voile Funktion gleichmassig stetig ist,
Nederl Akad Wetensch Proc, Ser. A, 27 A924), 189—193.
[7] Zur Begrundung der intuitionistischen Mathematik. I, Math.
Ann., 93 A925), 244—257.
[8] Zur Begriindung der intuitionistischen Mathematik. II, Math.
Ann., 95 A926), 453—472.
* Звездочкой отмечены работы, добавленные редактором.
[9] Die intuitionistische Form des Heine—Borelschen Theo-
Theorems, Nederl Akad Wetensch Proc, Ser. A, 29 A926),
866—867.
[10] Zur Begrundung der intuitionistischen Mathematik III, Math.
Ann., 96 A927), 451—488.
[11] Ober Definitionsbereiche von Funktionen, Math. Ann., 97
A927), 60—75.
[12] Points and spaces, Canad J. Math, 6 A954), 1—17.
Гедель (Godel K.)
[1] Die Vollstandigkeit der Axiome des logischen Funktionenkal-
kuls. Monatshefte fur Mathematik und Physik, 37 A930),
349—360.
[2] Ober formal unentscheidbare Satze der Principia Mathema-
tica und verwandter Systeme. I, Monatshefte }iir Mathematik
und Physik, 38 A931), 173—198.
[3] On undecidable propositions of formal mathematical systems,
Напечатано в Девис [1].
Гейтинг (Heyting A.)
[1] Intuitionism. An introduction, North — Holland, Amsterdam
A956). [Русский перевод: Гейтинг А., Интуиционизм, М.,
1965.]
Генкип (Henkin L.)
[1] Completeness in the theory of types, /. Symbolic Logic, 15
A950) 81—91.
Генцен (Gentzen G.)
[1] Untersuchungen fiber das logische Schliessen, Math. Z., 39
A934), 176—210, 405—431. [Русский перевод: Генцен Г.,
Исследование логических выводов, в кн. «Математическая
теория логического вывода», М, 1967, «Наука»]
Гжегорчик (Grzegorczyk A)
[1] Computable functional, Fund. Math., 42 A955), 168—202.
Гудстейн Р. Л. (Goudstein R. L.)
[1*] Рекурсивный математический анализ, «Наука», М, 1970.
Девис (Davis M.)
[1] The undecidable, Raven Press, Hewlett N. Y., 1965.
Заславский И. Д.
[1] Опровержение некоторых теорем классического анализа в
конструктивном анализе, Успехи Математических Наук, 10
A956), 209—210.
Заславский И. Д, Цейтин Г. Е.
[1] Сингулярные покрытия и связанные с ними свойства кон-
конструктивных функций, Труды МИ АН, 67 A962), 458—502.
Клини (Kleene S. С.)
[1] On notation for ordinal numbers, /. Symbolic Logic, 3 A938),
150-155
[2] Recursive functions and intuitionistic mathematics, Procee-
Proceedings of the International Congress of Mathematicians 1
A950), 679—685. Amer. Math. Soc, Providence R. I.
[3] Введение в метаматематику, ИЛ, М., 1957.
[4] Countable functionals, Constructivity in mathematics, 81—100,
North-Holland, Amsterdam, 1959,
130
Список литературы
Список литературы
131
Клини и Весли (Kleene S. С, Vesley R. Е.)
[1] The foundations of intuitionistic mathematics, North-Holland,
Amsterdam, 1965.
Крайзель (Kreisel G.)
[1] On the interpretation of non-finitist proofs.— Part I, /. Sym-
Symbolic Logic, 16 A951), 241—267.
[2] Analysis of the Cantor—Bendixson theorem by means of
the analytic hierarchy, Bull Acad. Polon. Sci., 7 A959),
621—626.
[3] Interpretation of analysis by means of constructive functio-
nals of finite types, Constructivity in mathematics, 101—128,
North-Holland, Amsterdam, 1959.
Крайзель и Лакомб (Kreisel G, Lacombe D.)
[1] Ensembles recursivement mesurables et ensembles recursive-
ment ouverts ou fermes, С R. Acad. Sci. Paris, 245 A957),
1106—1109.
Кушнер Б. А
[1*] Лекции по конструктивному математическому анализу,
«Наука», М., 1973.
Лакомб (Lacombe D.)
[1] Extension de la notion de fonction recursive aux foncti-
ons d'une ou plusieurs variables reelles, С R. Acad.
Sci. Paris, 240 A955), 2478—2480, 241, 13—14,
151-153.
[2] Remarques sur les operateurs recursifs et sur les fonctions
recursives d'une variable reelle, С R. Acad. Sci. Paris, 241
A955), 1250—1252.
[3] Les ensembles recursivement ouverts ou fermes, et leurs ap-
applications a I'analyse recursive, C. R. Acad. Sci. Paris, 245
A957), 1040—1043, 246, 28—31.
[4] Quelques procedes de definition en topologie recursive, Con-
Constructivity in mathematics, 129—158, North-Holland, Amster-
Amsterdam, 1959.
Марквальд (Markwald W.)
[1] Zur Theorie der konstruktiven Wohlordnungen, Math. Ann.,
127 A954), 135—149
Марков A. A.
[1*] О конструктивной математике, Тр. МИ АН СССР им. Стек-
лова, 67 A962). 8—14
Мартин-Лёф (Martin-Lof P.)
[1] The definition of random sequences, Information and Control,
9 A966), 602—619.
Пост (Post E. L.)
[1] Finite combinatory processes—formulation I, /. Symbolic
Logic, 1 A936), 103—105.
[2] Absolutely unsolvable problems and relatively undecidable
propositions, Account of an anticipation, 1941. Напечатано
в Девис [1].
Райе (Rice H. G.)
[1] Recursive real numbers, Proc. Amer. Math. Soc, 5 A954),
784-791,
Ришар (Richard J)
[1] Les principes des mathematiques et le probleme des ensemb-
ensembles. Ada Math., 30 A905), 295—296.
Спектор (Spector C.)
[1] Recursive well-orderings, /, Symbolic Logic, 20 A955),
151—163.
Тьюринг (Turing A. M.)
[1] On computable numbers, with an application to the Ent-
scheidungsproblem, Proc. London Math. Soc, ser. 2, 42
A936/37), 230—265.
[2] A correction, Proc. London Math. Soc, 43 A937), 544—546.
[3] Systems of logic based on ordinals, Proc. London Math.
Soc, 45 A939), 161-228.
Цейтин Г. С.
[1] Теоремы о среднем в конструктивном анализе, Труды
МИ АН, 67 A962), 362—384.
[21 Чёрч (Church A.)
[1] An unsolvable problem of elementary number theory, Amer,
J. Math., 58 A936), 345—363.
[2] The constructive second number class, Bull. Amer. Math. Soc,
44 A938), 224—232,
[3] On the concept of a random sequence, Bull. Amer. Math.
Soc, 46 A940), 130—135.
Чёрч и Клини (Church A., Kleene S. C.)
[1] Formal definitions in the theory of ordinal numbers, Fund.
Math., 28 A937), 11-21.
Шанин Н. A.
[1*] Конструктивные вещественные числа и конструктивные функ-
функциональные пространства, Тр. МИАН СССР им. Стеклова,
67 A962), 15—294.
Шпеккер (Specker E.)
[1] Nicht konstruktiv beweisbare Satze der Analysis, /. Symbolic
Logic, 14 A949), 145—158.
[2] Der Satz vom Maximum in der rekursiven Analysis, Construc-
Constructivity in mathematics, 254—265, North-Holland, Amsterdam,
1959.
Эрбран (Herbrand J.)
[1] Recherches sur la theorie de la demonstration. (Thesis), Uni-
University of Paris, 1930,
Указателе
133
УКАЗАТЕЛЬ
Аддитивный класс 92
Аксиома 12, 93, 98
Алгорифм 9, 12
Аппроксимация 40
Базис 30
Бар теорема 88, 126
Бишоп 127
Борелевское множество 91
Борель 25, 45, 85
Брауэр 25, 30, 48, 51, 53, 55, 57,
59, 62, 76. 85. 88,91. 111, 112.
113, 115
Буква 9
Бэровский класс 92
Бэровское пространство 39, 85
Вальд 116
Верхний узел 79
Весли 88, 128
Вещественная прямая 39
Внешнее предельное множество
60
Внутреннее предельное множе-
множество 60
Все пространство 54, 92
Вспомогательный знак 13
Всюду определенный алгорифм
Выводимое правило 94
Выводимый 20
Вычисление 121
Вычислимое вещественное чи-
число 46
Вычислительная машина 26
Гёделевский номер 27
Гёдель 18, 26, 97
Гейтинг 52, 58. 113
Генкин 888
Генцен 94, 100
Гжегорчик 67
Гильберт 30, 100
Главная формула 93
Главный функциональный сим-
символ 19
Диагональное множество 33
Диаметр 41, 63
Дискретный 63
Доказательство 12, 79
Доказуемый 12
Дополнение 92
Дополнительно локализованное
открытое множество 57, 58
Евклидово пространство 39
Заключение 12
Закон исключенного третьего
94
— потока 58
Замена 20
Замкнутое множество 55
Запирание 86, 126
Заславский 60, 72, 115
Знак 9, 11, 21
Измеримое множество 106
Инструкция 21
Интеграл 68
Интерпретация отсутствием
контрпримера 125
Иррациональный 46
Истинность 99
Исчисление равенств 19, 26
Каноническая система 17, 29
Кантор 45, 85
Канторово пространство 39
Клини 26, 32, 37, 61, 62. 64, 73,
76, 128
Компактный 56, 88
Конструктивная истинность 124
— точка 41
Конструктивный носитель 119
— объект 9, 121
•— принцип выбора 33
Лакомб 40, 60, 67, 72, 73, 115
Лексикографический гёделев-
гёделевский номер 17
Локализованное замкнутое
множество 57, 59
Локализованный компактный
вид 57
Майхилл 38
Максимальная аппроксимация
41
Максимальный рекурсивный
функционал 66
Марквальд 76
Марков 26, 62, 127
Мартин-Лёф 118
Машина Тьюринга 21
Мера 107
— Лебега 61, 105
Метка 14
Мизес 116
Мультипликативный класс 95
Наследник 77
Натуральное число 9
Неубывающая функция 67
Нормальный алгорифм 26
Нуль 77
Область 17, 65
— значений 17
Образ 17
Обращение 18
Общекурсивная функция 17
Объединение 14
Ограниченный 55, 88, 106
Ограничивающее множество 88
Окрестность 40
Ординальное число 76
Основная теорема 94, 100
Отделепность 39
Открытое множество 53, 85
Оценка 98
Переменная 11, 19
Пересечение 15
Плотный 57
Подординал 79
Подстановка 24
Полигон 68
Полная оценка 101
Последовательность аппрокси-
аппроксимаций 42
— Коши 43
— открытых множеств 54
— Шпеккера 52, 72
Пост 11,21.25, 26, 121
. Посылка 12
Поток 59
Правила введения 87, 93, 98,
— удаления 94
Правило вывода 19, 79, 93, 98
Применение схемы 12
Применимость 121
Продолжение меры 107
Прообраз 17
Простое множество 91
Пустое множество 54, 92
— слово 9
Равенство 19
Разность 92
Разрешимый 15
Райе 53
Рассел 30
Рациональное число 15
Рациональный 46
134
Указатель
Рекурсивная неотделимость 35
— вещественная функция 67
— функция 26
Рекурсивно перечислимое мно-
множество 15
отношение 15
Рекурсивный 15
Ришар 43
Свободно становящаяся после-
последовательность 87, 126
Секвенция 79, 93, 98
Сечение 94, 100
Слово 9
Символ 9
Симметрическая разность 93
Система Поста 11
Состояние 21
Спектор 76
Стандартное положение 22
Супремум 77
Схема 12
Сходимость 42, 66
Сходящийся 43
Тезис Чёрча 24, 31
Теорема Больнано — Вейер-
штрасса 53
— Бэра о категории 62
— Гейне — Бореля 56, 90
— о веерах 89, 91
— о нормальной форме 32
— о полноте 99, 102
— о равномерной непрерывно-
непрерывности 65
— о среднем значении 73
•— Рисса о представлении 67
Теоремы об итерации 34, 35
— о неподвижной точке 38, 39
— о перечислении 28, 33, 40, 54,
64
Терм 12, 19
Тоньше 39
Точка сгущения 53
Трансфинитная индукция 78
Тьюрииг 21, 26, 47. 48, 49, 85,
121
Узел 78
Универсальный 28, 34
Утончение 94
Формула 93
Функциональный символ 19
Цейтин 50, 60, 74, 115
Целое число 9
Цепочка 9
Цифра 19
Частично рекурсивная функция
16
— рекурсивный функционал 63
Чёрч 24, 25, 30, 31, 76, 116
Число мест 19
Шпеккер 52, 67, 72
Эйлерова константа 52
Эрбраи 18, 26, 125
Я. определимость 26
ц определимость 26
ОГЛАВЛЕНИЕ
Предисловие редактора перевода Б
Предисловие 7
ГЛАВА 1. РЕКУРСИВНЫЕ ФУНКЦИИ , 9
1 Конструктивные объекты 9
2. Канонические системы Ц
3. Рекурсивно перечислимые множества и отношения . 13
4. Исчисление равенств 18
5; Машины Тьюринга 21
6. Тезис Чёрча 24
7. Универсальная система 26
8. Теорема о перечислении для частично рекурсивных
функций 31
9. Теорема об итерации 34
10. Рекурсивная неотделимость 35
11. Теорема Клини о неподвижной точке 37
ГЛАВА 2. ЭЛЕМЕНТАРНЫЙ КОНСТРУКТИВНЫЙ АНАЛИЗ s ... 39
12. Окрестности, аппроксимации и конструктивные точки 39
13. Парадокс Ришара и неперечислимость континуума , 43
14. Вычислимые вещественные числа 46
15. Результаты о неразрешимости для вычислимых веще-
вещественных чисел 48
16. Последовательность Шпеккера 52
17. Открытые и замкнутые множества 53
18. Теорема Гейне — Бореля о покрытиях 55
19. Локализованные замкнутые множества 57
20. Внутренние и внешние предельные множества ... 59
21. Теорема Бэра о (множествах первой) категории . . 62
22. Частично рекурсивные функционалы 63
23. Максимальные рекурсивные функционалы 66
24. Две теоремы из классической теории функций ... 71
!3б Оглавление
ГЛАВА 3. ОРДИНАЛЬНЫЕ ЧИСЛА И БОРЕЛЕВСКИЕ МНОЖЕСТВА 76
25. Определение ординалов второго числового класса . . 76
26. Равенство и отношения порядка между ординальными
числами 79
27. Неперечислимость второго числового класса .... 85
28. Открытые множества в бэровском пространстве . . 85
29. Теорема Брауэра о веерах 88
30. Борелевские множества 91
31. Конструктивный вариант теоремы Гёделя о полноте 97
32. Полнота логики второго порядка с сечением .... 100
ГЛАВА 4. ТЕОРИЯ МЕРЫ 105
33. Продолжение меры и ее основные свойства . . . .105
34. Измеримые и неизмеримые открытые множества. Тео-
Теорема Брауэра 111
35. Множества меры нуль 117
ПРИЛОЖЕНИЕ .,«,,...,.. 121
СПИСОК ЛИТЕРАТУРЫ 128
Указатель 132
П. МАРТИН-ЛЕФ
ОЧЕРКИ ПО КОНСТРУКТИВНОЙ МАТЕМАТИКЕ
Редактор А А. Бряндииская
Художник В. М. Новоселова Художественный редактор В. И. Шаповалов
Технический редактор 3. И. Резник Корректор Т. С Лаврова
Сдано в набор 30/Х 1974 г. Подписано к печати 26/11 1975 г.
Бумага № 2 84ХЮ87м=2.13 бум. л. 7,14 усл. печ. л. Уч.-изд. л. 5,73
Изд. № 1/8013. Цена 40 коп. Зак. 406
ИЗДАТЕЛЬСТВО сМИР» Москва, 1-й Рижский пер., 2
Ордена Трудового Красного Знамени Ленинградская типография № 2
имени Евгении Соколовой Союзполиграфпрома при Государственной
комитете Совета Министров СССР по делам издательств, полиграфии
и книжной торговли. 198052, Ленинград, Л-52, Измайловский проспект, 29