Министерстве высшего и среднего специального образования РСФСР
МОСКОВСКИЙ ИНСТИТУТ ЭЛЕКТРОННОГО МАШИНОСТРОЕНИЯ
Ю.И.Маш
ЛЕКЦИИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Часть I
Учебное пособив для студентов
специальности 0647
Рекомендовано Редсоветом института
в качестве учебного пособия
Москва - 1974

СОДЕРЖАНИЕ
Введение.
Литература.
Приложение.
Глава I* Язык высказываний.
§ I. Общие сведения о явыках.
§ 2. Язык высказываний: алфавит, синтаксис и интерпретация.
§ 3. Интуитивные пояснения.
§ 4. Содержательная истинность.
§ 5. Синтаксическая истинность.
§ 6. Совпадение содержательной и синтаксической истинности в
языке 1-0 ,
Глава П. Язык предикатов.
§ I. Алфавит и синтаксис.
§ 2. Интерпретация.
§ 3. Примеры интерпретаций.
§ 4. Некоторые вычисления функций истинности.
§ 5. Аксиомы к выводимость в L ^ •
§ б. Теоремы о моделях Геделя и Леввнгейма-Сколвма.
§ 7. Доказательство теорем о моделях.
§ 8. Ыатематичеокяе свойства языков Lх .
§ 9* Структура формальной математики.

Глава Ш, Проблеиа континуума.
§ I. Постановка задачи. Неформальные объяснения.
§ 2. Язык L2Rtc«*. и его стандартная интерпретация.
§ 3. Континуум-гипотеза и аксиома выбора.
§ 4. Нестандартная булева интерпретация языка Lz
основные понятия.
§ 5. Конструкция булевой интерпретации языка Lz
§ б. Континуум-гипотеза "ложна".
§ 7. Аксиомы ,L2 fo-сЛ
§ 8. Аксиома выбора "истинна".
§ 9. Аксиома полноты "истинна".
§ 10. Обсуждение.

Введение
O.I. Содержанием математической логики является изучение
языка математики.
Разумеется, забота о языке и постоянная его перестройка
для приведения в соответствие с меняющийся соотоянием знаний
характерна для любой естественной науки (ср. судьбу "флогистона"
и "мирового эфира" в физике). Тем не менее, необходимая работа
обычно осуществляется по ходу дела, и то пристальное критическое
рассмотрение, которому математика подвергла самое себя и сбои
средства выражения, представляется уникальным.
Причина этого состоит, конечно, в том, что все остальные
естественные науки имеют предмет, внеположный им, и эволюция
языка науки определяется постоянным сравнением научного описа-
описания с описываемой реальностью.
Попытка применить эту же схему к математике сразу натал-
наталкивается на принципиальную трудность, ибо совершенно не ясно,
в каком смыоле числа и множества являются реальностью. Столь
же не яоным при внимательней рассмотрении становится ответ на
вопрос, что такое истинность (математического рассуждения).
Если быть до конца последовательным, следует признать это
обстоятельство роковым.
* Действительно, до выяснения природы истинности, мы,
по-видимому, ни в состоянии сделать ни одного истинного утверж-
утверждения, и исследование должно остановиться не начавшись. *
Предыдущий абзац не является просто софизмом. Он предоп-
предопределяет две характерные черты математической логики.
1*-1877

Первая состоит в той, что строя формализмы логики, мы не-
неизбежно должны пользоваться неформализованными, интуитивными
представлениями, близкими к обычной рабочей интуиции математика.
Технический термин для этого - "метаязык", на котором идет опи-
описание "формальных изыков", в свою очередь являющихся моделями
дедуктивных, в том числе математических (в том числе метаязыковых!)
рассуждений.
Положение дел здесь можно сравнить с понятием "элементар-
"элементарности" в физике. Элементарные частицы - это не те объекты, кото-
которые являются последними кирпичиками анализа, - скорее это те
объекты, дальнейший анализ которых обнаруживает повышение уров-
уровня сложности вместо его понижения. "Элементарность" понятия
истины имеет сходные черты.
Вторан характерная черта логики состоит в том, что рас-
рассуждение, выделенное двумя звездочками в -шестом абзаце служи!
(очень грубой) моделью доказательства нетривиальных теорем о
невозможности тех или иных математических конструкций. Такие
теоремы о невозможности, сопоставимые о "принципом запрета"
в современной физике, составляют вершины современной математи-
математической логики. Чтобы убедитьои в этом, достаточно указать, что
фундаментальные результаты Геделя и других авторов называются
теоремами о неполноте, неразрешимости, независимости и т.п.
Такого типа результаты, представляющие очевидный общегу-
общегуманитарный интерео, не имеют прецедентов в развитии философской
мысли до XX века, и являются существенным вкладом естественных
наук в фонд гуманитарных. С ним можно сравнить по значению и
глубине только анализ квантовомеханических представлений о

"дополнительноети" и "неопределенности", распространенный
Нильеом Борон далеко за пределы физики иикроиира. Возможно, что
оба круга идей - логики и квантовой иеханики - имеют глубюгаую
связь. Дело в тон, что результаты о невозможности, упомянутые
выше, отяосятоя к детерминированным ("запрограммированным"
как принято говорить сейчас) мыслительным процессан, а кван-
квантовая механика как раз очерчивает границы наивного детерминизна.
Практические применения нетодов математической логики к
проектированию и эксплуатации вычислительных и управляющих
оистен сейчас хорошо известны, и ни позволим себе не останав-
останавливаться на них здесь подробно.
0.2. Для понимания генезиса и отруктуры математической
логики необходимо проследить ее иногоохроннвв овявь о теорией
множеств, "наивная" или "содержательная" ферма которой была
основана в работах Г.Кантора на рубеже нашего веха.
Прежде всего, вой современная математика ноже* бы»
построена на базе теории множеств. (Наиболее последовательное
и целостное изложение этой позиции предпринято в многотонном
труде "Основы математики" Н.Бураки). Поэтому логика как "тео-
"теория математики" вынуждена соотноситься о теорией множеств.
Далее, уже в начале века обнаружилось, что некоторые
конструкции, основанные на интуитивной представлении о тон,
что множества могут состоить из каких угодно объектов, быстро
приводят к противоречию (парадоксы Бурали-Форти, Расселла и
др.). Разные попытки устранить эти противоречия породили пер-
первые понятия и результаты современной натенатичеокой логики.
Наконец, теория множеств полухила для логики источником
нескольких важнейших идей (диагональный процесс, интерпретация)

и задач (гипотеза континуума), во многом предопределивших
направление ее развития.
Доя большей конкретности дальнейшего обсуждения кратко
опишем три теоретико-множественных конструкции.
Предполагается, что читатель знаком с понятием множества,
с первоначальными операциями над множествами и их стандартными
обозначениями. К ним относятся, в частности, понятие взаимно
однозначного соответствия, мощности и следующие конструкции:
Р(Д) - множество всех частей (подмножеств) множества;А ;
Д *В * - ¦ • * М - произведение семейства множеств А,6; - - -jH
элементы которого суть наборы (&,^> > ; ™ ) , где &&А)
11В ... *ъ ? М ) отношения эквивалентности R на мно-
жеотве А • фактор-множество ^/D , состоящее из всех
класоов эквивалентности, является частью Р(А) и т.п.
(См., например, Н.Бурбаки "Теория множеств" Сводка результатов).
0*3. Первая конструкция: диагональный процесс Кантора.
Теорема. (Г.Кантор, 1890). Не существует взаимно однознач-
однозначного соответствия между множеством N целых положительных
чисел и множеством вещественных чисел оС в интервале [ ОД С •
Доказательство. Будем представлять числа °? десятичной
записью 0) oiioiz- ¦¦ °<п,. ¦¦ , где o^i e С °; •',-ч93 •
Однозначность записи, важная для дальнейшего, может быть до-
достигнута, скажем, запретом писать подряд бесконечно много
девяток.
Предположим, что нумерация ГОД[ -взаимно однозначное
соответствие между N и f 0.1 [ - существует* Пусть

д t\ € /V
n. j
(отраховка от запрещенных разложений!). Тогда число
fl- ?. вещественное число в этой нумерации. Для каждого
выберем десятичную цифру ^ так, чтооы finj-^n.
ft . ¦ ¦ &v
принадлежит [0,1 С , но не может получить никакого номера,
ибо & отличается от о^п, в fl-M, знаке для всех It .
Противоречие. ¦ (Знак ¦ здесь и ниже означает конец
доказательства или его отсутствие).
0.3. Вторая конструкция: вещественные чиола.
Вещественные числа составляют арену для большей части клас-
оического анализа и его приложений. Проследим в общих чертах,
как они отроятся в теории множеств, начиная буквально "о
пустого места". Процесс состоит из нескольких этапов.
Натуральные числа IN и нуль. Натуральные чиола суть
мощности конечных множеств. Нуль 0 есть мощность пустого
множества ф ; единица I есть, например, мощность мно-
множества {ф} , единственным элементом которого является пуо-
тое множество ф ; двойка 2 есть мощность множества
{фЛф}} и т»п» Сложение чисел определяется
через объединение непересекающихся множеств и т.п.
Целые числа IL . Во множестве пар натуральных чисел
f\J X (\1 введем отношение эквивалентнооти R. , положив
(Х,^) <^~ (Х1,^) , воли и только если '
Определим '

Интуитивно, класс пары (У^^) mod R^ есть разность
-Х-Ч . Сложение, вычитание, умножение в Ж можно
далее определить обычным способом. Вложение /V <— L.
определяет также порядок на 21 ' ¦* ^ ^ ¦ воли Х- ^. ? (V .
Рациональные числа <& . Во множестве пар Х*B? ч
(вторые элементы ненулевые) введем отношение эквивалентности
R1 , положив (oc,f) ^ СХ'^') » если и
только если "Х.^' - зс'^ . Определим
Интуитивно, класс пары fx^Ji^odL K^ есть частное
=? . Сложение, вычитание, умножение, деление, порядок в
вводятся обычным порядком.
Последовательности Коши рациональных чисел. Последователь-
Последовательности (х1; ..,j Х^,...^ рациональных чисел суть
элементы бесконечного прризведения <Q ^< <Q K.i,X^3x.,J
Среди них выделяются последовательности Коши условием:
(х1;. ,*л.г ) последовательность Коши
для всякого т € N существует По е N
> По имеем
такое, что при всех
Пусть Cj С
вательностей
сч-
:€)'
Коши.
х
п
*
2 ^
. У
. rrj
.х
множество всех последо-
последо10

Вещественные числа IR . На множестве С< введем
отношение эквивалентности R-^ , положив
fx,, .,хЛ,.. ) (х1(...,<, )
последовательность « ( 3Ci~ ЭС* > • • * > ¦*- iv~ "»i' '
"сходится к нулю", т.е. для всякого ПХ ? /V
существует Пов N такое, что при всех Пъ-П0
Ииее« _1$оса-<$1
Определим, наконец, множество вещественных чисел /г? как
факт ор-множество
"«=с А
Замечание. Читатель, не продумывавиий этих конструкций
во всех деталях ранее, вероятно, будет обескуражен их громозд-
громоздкостью и краткостью изложения. Этот аффект до некоторой сте-
степени входил в намерение автора. Вещественное число есть
"класс последовательностей пар мощностей конечных множеств" -
нельзя ли как-нибудь попроще?
Нельзя.
В некоторых вариантах глубоко формализованной иатематикж
даже единица " J " оказывается уже чрезвычайно сложным-образо-
сложным-образованием. В формальной системе Н.Бурбакж используются всего 6
первоначальных неопределенных знаков: VaO, У,1, -j& -
Чтобы изложение имело реалистическую дину, приходится очень
быстро вводить правила сокращенной записи и новые зиага. На
II

одной из этапов единица впервые появляется как "тери"
(в сокращенной записи) вида
{
Грубый подсчетгоказывает, что это выражение, записанное
бег сокращений, должно было бы содержать несколько десятков
тысяч знаков первоначального иестибуквенвого алфавита.
0.4. Третья конструкция: парадокс РасселшA910).
Определение. Множество М называется хороший, если
оно не является сбоим собственный элекентои; не хороиие мно-
множества называются плохими.
Парадокс. Рассиотрии множество С , состоящее из
всех хороших множеств. Является ли оно хороним или плохим?
Оба предположения приводят к противоречию:
^ хорошее^ fS должно содержать себя по определению ,$
=> |S* плохое.
р плохое ^ р ве должно содержать себя по определению tS
¦=$ д хорошее.
Многие предложенные способы избавлении от этого парадокса
сводятся к тому, чтобы истолковать его жак доказательство сле-
следующей теоремы:
12

Теорема. Множество ^ не существует.
(По причинам, скорее психологическим, чем математический,
чаще всего пытаются добиться того, чтооы множество $
нельзя было даже определить).
0.5. Теперь читателю полезно будет мысленно вернуться к
конструкции вещественных чисел (R , в которой, по-видимо-
иу, обращение с множествами было гораздо более многоступенча-
многоступенчатый и сложный, чей в парадоксе Рассела; вообразять себе все
здание Анализа - с интегрированием Лебега, кривыми Пеано и
т.п., надстроенным над {R в соответствии с теоретико-
множественными принципами; и задаться вопросом:
Существуют ли вещественные числа IR ?
Различные школы в математической логике, особенно в ее мета-
матических аспектах, удобно характеризовать тем, как они отно-
относятся к этому вопросу.
Нижеследующее описание нескольких основных направлений
очень неполно и, наверняка, содержит искажения: эта тема со-
совершенно не поддается формализации.
а) Формализм в стиле Гильберта. Математика есть игра, в
ходе которой по определенным правилам пишутся значки на бумаге.
Вещественные числа ff? фигурируют в массе неформализованных
математических текстов вместе со своими свойствами. Анализируя
реальные тексты, следует составить список основных значков и
жестких правил составления из них правильных формальных мате-
математических текстов. Если, следуя этим правилам, можно составить,
скажем, текст 0 = 1, то наша "формальная математика" будет про-
противоречивой, и ничего, с чем мы в ней работаем, "не существует".
13

На саиои деле, иы надеемся, что все (или большая часть)
классических математических объектов "существует", то есть
( ->сС !), что рассуждая о них по правилам, иы не иожеи
прийти к противоречию. Мы надееися также, что это утвержде-
утверждение можно доказать, исследуя тексты и правила их составления
безотносительно к их "содержанию".
Вот грубая модель такой программы. Рассмотрим тексты,
которые являются записями шахматных партий в стандартной но-
нотации о» начальной позиции до какого-то хода. Ясно, что пра-
правила "ходов" можно сформулировать как правила последователь-
последовательного составления таких текстов Оезотносительно к реальным
деревянным олонаи, пешкам и т.д. Ясно также, что по записи
иожно подсчитать, скажем, количество фигур того или иного
цвета на доске в конечной позиции текста. При этом утвержде-
утверждение о том, что "на дооке не иожет оказаться больше двух коро?
лей" можно сформулировать и доказать, анализируя только пра-
правила составления текстов и не аппелируя к "настоящей" шах-
шахматной доске.
б) Конотр.уктивизм. "Все" вещественные числа, безусловно,
не существуют. Ииеет смысл говорить лишь о тех из* них, для
которых указан алгоритм вычислении, скажем, их последователь-
последовательных десятичных знаков (типа программы для ЭВМ). Вообще "сущест
вуют" только объекты, которые мокко построить, хотя бы в прин-
принципа. Для очень многих понятий и результатов классической мате-
математики иожно указать их конструктивные варианты. Те результаты,
которые являются по существу неконструктивными, подлежат полной
дискредитации, в той числе практичеоки вся теория множеств и
вещественного континуума и т.п. Особенно широко известен кон-

структивистский отказ от принципа исключенного третьего.
в) Интуиционизм. Концепция, близкая к конструктивизму.
Ее сторонники, однако, подчеркивают свою отделенность от
формализованной (тата)матема1ики и тяготение к философии и
сош'"лышм наукам.
г) Логицизм. Концьлция, в которой логическая система
предшествует математической; представлена, в частнооти, фун-
фундаментальным трудом Уайтхеда и Расселла " pTUlCJjOtA.TffeKWWtftyi
Согласно Клини, "логицистический тезис может быть ... под-
подвергнут сомнению по той причине, что логика уже предполагает
математические идеи в своей формулировке ... Существенное мате-
математическое ядро содержится в идее итерации, которой приходится
пользоваться, например, при описании ... выгода из данных
пооылок".
0.6. Рабочая точка зрения, которую принимает автор этих
записок, состоит г том, что математическая логика есть часть
"наивной" математики. Так она и будет излагаться, метаматема-
метаматематическое истолкование логических теорем приводится лишь в
качестве интуитивных объяснений, возможность которых, однако,
определяет эмоциональную ценность логики.
Оправдание такой точки зрения в значительной мере осно-
основано на результатах К.Геделя, лежащих в русле гильбертовского
формализма.
Эти результаты, как уже говорилось, носят отрицательный
характер.
Теорема о "неполноте" любой формализованной теории, содер-
содержащей определенную часть арифметики,шкверждает, что всегда
15

существуют содержательно истинные теоремы этой теории, кото-
которые нельзя доказать средствами этой теории.
Проблеиа непротиворечивости достаточно богатой фориальной
теории также не может быть решена только средствами, формали-
формализуемыми в этой теории.
Математику нельзя формализовать.
Попытки формализовать ее, однако, ооставляют еодержатель-
ную и интересную часть математики.
0.7. В заключение мы приведем здесь простую, но уже
нетривиальную теорему, родственную геделевским "принципам
запрета". Чтобы избежать долгих формальных объяснений, мы
аппелируем к интуиции читателя с небольшим опытом работы на
ЭВМ.
Постановка задачи. В Вычислительный центр поступают тек-
тексты, написанные на алгоритмическом языке (окажем, типа
АЛГОЛа). Транслятор - специальная программа - превращает эти
тексты в программы на машинном языке. Некоторые тексты содер-
содержат ошибки, скажем, синтаксические; транслятор реагирует на
некоторые иг ошибок остановом.
Естественно поставить задачу написания транслятора, кото-
который обнаруживал бы все больше и больше типов ошибок и, может
быть, даже и "все" ошибки в любом тексте на алгоритмическом
языке.
Уточним постановку задачи.
Фиксируем алгоритмический язык L ; его алфавит со-
состоит из конечного числа знаков. Любую конечную последователь-
последовательность этих знаков назовем текстом.
16

Текст назовем правильной програииой. если его перевод
на машинный язык возможен и если после введения в кашину,
получившаяся програмиа заставляет машину работать (потенци-
(потенциально) бесконечно долго и последовательно выпечатывать на
выходе таблицу вида
1 2 3 Ч S
S
где р (п) - некоторые натуральные числа. Иныии словами,
правильные программы вычисляют функции от натурального аргу-
иента с натуральными значениями, всюду определенные и всюду
вычиолииые.
Назовем ТРАНСЛЯТОРОМ программу, на вход которой можно
подать любой текст, и получить на выходе I, если этот текст
является правильной программой, и О б противном случае.
0.8. Теорема. ТРАНСЛЯТОР не существует.
Доказательство. Предположим, что ТРАНСЛЯТОР существует.
Пользуясь им, напишем некоторую правильную программу, которую
назовем Большой Программой (БП). БП будет работать так. Упоря-
Упорядочим как-нибудь символы языка Lj ; назовем этот порядок
алфавитным.
а) Специальная подпрограмма БП порождает по очереди все
тексты на языке L , упорядоченные по длине, а внутри тек-
текстов одинаковой длины - в словарном порядке.
б) Очередной текст подается на вход ТРАНСЛЯТОРА. Если на
выходе появляется 0, агот текст не учитывается. Если на выходе
появляется I, этот текст является правильной программой, и ему
2-1977
17

присваивается очередной ноиер (Ъ • Таким образок, мы
порождаем по очереди все правильные программы и только их,
в словарном порядке.
Пусть ft. -я правильная программа вычисляет функцию
в) Последний цикл БП вычисляет для каждого натурального
число
i подает пару ( М; J"(rt-) / на выход.
Очевидно, так определенная БП является правильной програм-
программой. Поэтом; функция J(A-) должна содержаться в списке
/а г ¦ ' /pv ¦ ¦ ) » котоРый по своей конструкции со-
содержит все функции, вычисленные правильными программами.
Противоречие: j не может содержаться в этом списке,
ибо значения ЭЧэс) ^ fn.('X-) не совпадают при JC-H.
0.9. Читатель заметит пуповину, связывающую это рассужде-
рассуждение одновременно с диагональным процессом Кантора и парадов-
сом Расселла. Последнее станет особенно ясно, если вместо
поисков j среди (fti/) попытаться отыскать БП среди
всех правильных программ.
18

Литература
Нике указаны некоторые основные книг! по лсгшке на
русской языке. Помещенная в них библиография позволяет
проследить более специальные работы*
а) Общие курсы
С.К.Клини. Введение в иетаиатеиатику. М., ИЛ, 1957.
П.С.Новиков. Элементы математической логики. П., 1959.
Ф.Гудстейн. Математическая логика. II., ИЛ, 1961.
Р.Линдон. Заметки по логике. М., МИР, 1968.
А.Тарский. Введение в логику и методологию естественных наук.
П., ИЛ, 1948.
Мендельсон. Введение в математическую логику. М., МИР, 1971»
б) Более опециальные вопросы
В.А.Успенский. Лекции о вычислимых функциях. М., физматгив, I960.
А.И.Мальцев. Алгоритмы и рекурсивные функции. М., "Наука", 1966.
А.Гейтинг. Интуиционизм. М., "мир", 1965.
П.Дж.Козн. Теория множеств и континуум-гипотеза. М., "Мир", 1969.
19

Приложение
Нике собраны некоторые любопытные неформальные
высказывания о предмете логики.
п В Копенгагенском институте, куда б те годы съезжался
для дискуссий целый ряд молодых физиков из разных стран, мы
имели обыкновение в трудных случаях утешаться шутками, среди
которых особенно любимым было старое присловье о двух родах
истины.
К одному роду относятся такие простые и ясные утвержде-
утверждения, что противоположные им очевидно неверны.
Другой род, так называемые "глубокие истины", представ-
представляют, наоборот, такие утверждения, что противоположные ии также
содержат глубокую истину." (Нильс Бор. Избранные научные
труды. Т. П, Наука, 1971, стр. 432).
(Читатель заметит, что утверждение о существовании "глу-
"глубоких истин", несомненно, является глубокой истиной, ибо
противоположное уОеждение - "всякая истина проста" - также
содержит глубок;,») истину.
Это - очень метаматематическое рассуждение. Ю.М.).
"Леви Брюль обнаружил, что мышление первобытных людей
является не логическим, а, как он его назвал, "пралогическим",
в частности, оно характеризуется безразличием к принципу исклю-
исключенного третьего, выражаемому формулой CLCL — О или
утверждениями типа "нельзя съесть пирог, сохранив его". Это
20

было очень важный и плодотворным открытием, особенно потому,
что, как указывали уже многие авторы, Леви Брюль, безусловно,
ошибался, когда находил существенное различие между "цивили-
"цивилизованным" и "первобытным" человеком. Постепенно становится
все более и более очевидным, что все мы - братья, несмотря
на различие цвета кожи, и что*-логическое мышление даже у
"цивилизованных" людей похоже скорее на танцы лошадей, то
есть на трюк, которому можно обучить некоторых, но далеко не
всех, причем он может исполняться лишь с большей затратой оил
и с разной степенью мастерства, и даже лучшие представители
ке в состоянии повторять его много раз подряд."
(Х.Ульдалль. Основы глоссематики. В сб. "Новое в линг-
лингвистике". М., ИЛ, I960).
Общее впечатление от результатов Геделя прекраоно резюми-
резюмировано в беседах Гете с Эккерманом (Гедель еще не родился,
когда эти олова были сказаны):
"Плохо то, что всякое мышление ничем не помогает самому
мышлению. Надо быть правильным от природы ... ".
Н.Бурбаки, как практически работающий математик, высказы-
высказывается на эту тему с галльским здравомыолием и терпимостью:
"Математики, кажется, сходятся на том, что между нашими "ин-
"интуитивными" представлениями о множествах м числах и призван-
призванными описывать их формализмами имеется не более чем поверхност-
поверхностное сходство. Разноглаоия относятся лишь к вопросу о выборе
между теми и другими."
2х-1977
21

ГЛАВА I
ЯЗЫК ВЫСКАЗЫВАНИЙ
"Ты пишешь на листе, и смысл,
означен и закреплен блуж-
блужданьями пера, для сведущего
до конца прозрачен: на пра-
правилах покоитоя игра."
Г.Гессе, Алфавит
I. Общие сведения о языках
I.I. Формальные языки (иначе формальные системы или ис-
исчисления) подобны физическим теориям в том отношении, что они
призваны идеализированно описывать некоторую реальность.
"Реальностью" для формального языка являются определенные
типы (математических) рассуждений или некоторые процессы ра-
работы абстрактных автоматов. Разные языки отличаются друг от
друга в первую очередь широтой охвата формализуемых типов рас-
рассуждений; во вторую очередь - ориентацией на конкретные мате-
математические меории; и в третью - отбором элементарных рассуж-
рассуждений и оформлением - выбором алфавита, то есть системы пер-
вонечальных символов.
Правила составления допустимых комбинаций из символов
алфавита образуют синтаксис языка. Правильно составленные
комбинации того или ияого вида называются термами, формулами
и т.п.
Основные математические задачи о языке состоят е выяс-
выяснении "истинности" тех или иных классов формул. Этому пред-
22

шествует формализация разных аспектов понятия истинности, в
частности, его разделение на содержательную истинность и
синтаксическую истинность (иначе доказуемость, выводимость и
т.п.) и выяснение соотношений между этими аспектами.
Содержательная истинность вводится через понятие интер-
интерпретации данного языка. В этих записках язык интерпретируется
всегда в "наивной" (или содержательной, интуитивной) теории
множеств, теории чисел и т.п.
Трехчленное отношение
(мысленный) эксперимент
физичеокая теория <¦ *- реальность
параллельно трехчленному отношению
интерпретация
язык -* *¦ содержательные рассуждения.
Интерпретация является математический понятиен, которое
для каждого языка подлежит точному определению. Бе не следует
смешивать с интуитивными пояснениями и мотивировками.
Синтаксическая истинность вводится на основе аксиом и
правил вывода и имитирует свойство "доказуемость данный; сред-
средствами".
1.2. Замечания.
а) Психологические трудности овладения новым формальным
языком близки к трудностям овладения новым человеческим языком.
На первых порах она связаны с необходимостью запомнить облик
(звуковой, графический) слов, их значения (интуитивный вариант
интерпретации) и грамматика (аналог синтаксиса).
23

б) Алгоритмические языки (типа АЛГОЛ) близки к формаль-
формальный, но имеют другое назначение: они формализуют вычислитель-
вычислительный процесс, а не теорию. Еще одно важное отличие состоит в
той, что для "формул" на этих языках, то есть программ,
имеется прагматичеокий критерий "истинности" - работает про-
программа, или нет.
1.3. Каждый математический текст в принципе может быть
"переведен" на подходящий формальный язык, хотя зачастую
процесс перевода не тривиален, а результат не однозначен и
кое-что теряет по сравнению с оригиналом. После такого пере-
перевода текст на формальном языке сам может стать предметом ма-
математического исследования. Теоремы математической логики о
"недоказуемости" или "алгоритмической неразрешимости" суть
теоремы о несуществовании текстов того или иного вида на фор-
формальных языках. При оценке оодержания таких теорем необходимо
как можно яснее представлять себе, в какой мере формальные
тексты адэкватны неформальным. Потери, связанные с бедностью
формального языка, можно компенсировать расширением его выра-
выразительных средств; один из удивительных результатов логики
состоит в том, что очень немногих средств хватает для формаль-
формального описания "всей" математики. Однако более тонкий анализ
показывает принципиальную недостаточность даже самых богатых
формальных языков для передачи интуитивного содержания во всей
его полноте и обнаруживает глубоко гуманитарный аспект матема-
математики.
Мы будем возвращаться к этим вопросам позже, по мере на-
накопления математического материала.

2. Язык высказываний: алфавит, синтаксис, интерпретация
Язык высказываний Lo являетоя в известной, мере про-
отейшим и в той или иной форме входит в качестве составной
частя во многие другие языки.
2.1. Алфавит i-o . Он состоит из следующих символов
(пояснения в скобках используются в последующих интуитивных
формулировках).
Множество Л символов атомарных Формул, элементы кото-
которого мы будем обозначать буквами р , (J , t и т.д.
Множество логических связок, элементы которого обозначаются
значками —> (влечет), V (неразделитвльное или), Л (и),
 (не). Скобки (} ).
В принципе для счетного л. можно обойтись конечным
алфавитом, обозначая элементы А , окажек, так; I II III
и т.п.
2.2. Синтаксис и формулы i-o . Форкулы i i0 - зто
некоторые конечные последовательности оимволов алфавита. Их
множество 7 описывается следующими соглашениями:
а) Атомарные формулы являются формулами.
б) Ксли Р и Q формулы, то
(P)-(Q), (r)V(Q),(P)MQ)l(P)
суть формулы.
25

в) Любая формула получается конечным числом шагов, сос-
состоящих из применения правил а) и б).
2.3. Замечание о скобках. Скобки, как в элементарной
алгебре, вводятся для обеспечения однозначности порядка
действий. Если условиться, чтосвязки -»» ,V> Л,~1
расположены в порядке "возрастания силы", то часть скобок
можно опускать, получая сокращенную запись. Например, фор-
формула
(Р)-» (n(Q)v((R)
•в сокращенной записи имеет вид
Более детальное обсуждение см. у Клини. Введение в математику.
ИЛ, 1957, § 17.
"Метаматематические утверждения о ... формулах системы
должны рассматриваться как относящиеся к несокращенным выраже-
выражениям ... , какого бы рода стенографией мы не пользовались при
записи этих выражений" (Клини, стр. 72),
Существуют варианты бесскобочной записи формул. Например,
мы могли бы сразу писать -» PQ , VPQ , APQ
вместо (P)^CQ) ; (Р) V (U) и (Р)/\(<2)
соответственно. Это обеспечивает однозначность чтения и удобнее
для метаматематики, но несколько менее удобно для "интуитивной"
математики из-за расхождения с «привычками читателя, воспитанного
на "окобочных" текстах.
26

2.4. Интерпретация Lo . Интерпретацией; называет-
называется любое отображение
(множества всех формул языка У в0 множеотво, состоящее
только из нуля и единица), которое удовлетворяет следующий
условиям:
(I) tfC
Таким образом, язык может иметь иного разных интерпретаций.
Другое название ^ - Функции истинности; в более бога-
богатых языках ее значение на атомарных высказываниях будет полу-
получаться автоматически после того, как мы придадим "смысл" дру-
другим объектам языка, то есть интерпретируем их.
2.5. Мы хотим обратить внимание на то, что алфавитом ш
называем некоторое аботрактное множество, тогда как значки
( Р)^) Л, —* и т.д.) используются только как
обозначения, или имена элементов этого множества. При опреде-
определении интерпретации (см.ниже) сами элементы алфавита отановится
к) Стрелка > в метаязыке будет использоваться для
обозначения отображений множеств, как это сейчас обще-
общепринято. Автор надеется, что во всех таких случаях кон-
контекст исключает возможность путаницы.
27

естественно рассматривать как имена элементов другого множества
(или имена операций над ними), так что р j Ц и т.д. превра-
превращаются в имена имен. Возможно еще более многоэтажное отношение
между знаком и последним обозначаемым.
В ряде традиционных изложений алфавитом наэываются сами
значки на бумаге; зто заставляет вносить в текст комментарии
о том, как писать, различать и отождествлять зти значки (ср.
первые страницы книги А.А.Маркова "Теория алгоритмов")» Автору
кажется, что зта система соглашений неудобна по двум причинам.
Во-первых, в математическом тексте приходится обсуждать вопросы,
относящиеся по существу к прикладной психологии. Во-вторых, если
уж правила отождествления и различения значков приняты, то можно
вернуться к алфавиту в нашем смысле слога, определив один его
элемент как класс отождествляемых между собой значков данного
текста.
В заключении приведем пассаж об именах из книги Россера
"Логика для математиков".
" .,. суть дела в том, что если у нас есть утверждение
типа " 3 больше 9/12" о рациональном числе 9/12, которое
содержит некоторое имя 9/12 этого рационального числа, то ш
можем заменить зто имя любым другим именем того же рациональ-
рационального 4исла, например /4". Когда же мы рассматриваем утверж-
утверждение типа  делит знаменатель "9Д2" о некотором имени
некоторого рационального числа, и наше утверждение содержит
некоторое имя этого имени, то зто имя имени можно заменить
другим именем того же имени, но вообще говоря, нельзя заменить
именем другого имени, хотя бы зто другое имя было именем того
же рационального числа".
28

Впрочем, продолкает Роосер, "отказ от скрупулезного со-
соблюдения этих тонкостей редко приводит к путанице в логике и
еще рехе в математике".
3. Интуитивные пояснения
3.1. Атомарные формулы языка |_0 интуитивно отвечают
целостным высказываниям, которые начинаются словами "Верно,
что ...": "верно, что снег белый", "верно, что 2x2 = 5",
"верно, что электрон так же неисчерпаем, как и атом". В даль-
дальнейших описаниях слова "верно, что ..." иногда опускаются,
но всегда подразумеваются.
Логические связки примерно соответствуют словам "если ...
то" ( —* ); "и" ( Д ); "или ..., или ..., или и то и
другое вместе" (V )¦ "не" A ). См., однако, ямсе заме-
замечания об —>¦ , где обнаруживается особенно большое расхож-
расхождение формализма с интуитивными привычками.
Формулы, таким образом, отвечают некоторым составным
высказываниям или цепочкам утверждений. Так, формула
г —*(Q~-? P) может читаться примерно так:
"Верно, что если Еерьо Р , то верно, что из (вер-
(верности) Q следует (верность) Р ".
3.2. Интуитивный смысл интерпретации у состоит в
том, что У описывает каждой формуле - высказыванию зна-
значение истинности A ) или ложности @). Обсудим согласован-
нооть формул (I) - E^ п. 2.3. с этим объяснением.
(I) означав*, что истинность Р равносильна ложности
отрицания р и наоборот.
29

Согласно B) высказывание " Р или Q " ложно лишь
тогда, когда оба Q и Р ложны. В этой проявляется не-
раэделительность связки V "или": Pl/Q истинно,
когда хо!я бы одно из Р , Q истинно. Аналогично обсул-
дается C). "Разделигельное или" можно представить формулой:
"верно, что Р или Q , но неверно, что Г и ц
вместе".
При нродумывании (*) следует освоиться с двуия обстоя-
обстоятельствами.
Во-первых, согласно E), если и (г)—О
( Р ложно), то f ((P)-»(Q))-1 , то
есть (Р) —*• (Q) истинно. "Из лжи следует все, что
угодно". В частности, высказывание "если 2x2=5, то 2x2=*"
(при естественной интерпретации x2=5 ложно", x2=4 истинно")
должно считаться истинным, хотя интуитивные привычки скорее
относят его к категории бессмысленных.
Во-вторых, высказывание типа "если 2x2=4, то Фишер чем-
чемпион пира 1972 года" также должно считаться кг .тинным. В языке
1_0 нет никаких средств для констатации "наличия или отсут-
отсутствия связи" между разными атомарными высказываниями, а г ин-
интерпретации нет никакого аналога категории "бессмыслицы".
Эти свойства связки —*¦ в языках более высокого уровня
ii плодят к резкому несоответствию понятия "противоречивости"
интуитивным представлениям.
5G

Множественность интерпретаций - очень важное обстоятель-
обстоятельство. Интуитивно ою связано с несколькими соображенияш.
Прежде всего, каждая формула должна быть схемой многих
равных рассуждеилй, которые получаются при подстановке вместо
атомарных формул тех или иных конкретных утверждений, нстив-
ность идж ложность которых может меняться.
Далее, в доказательство " от противного" мы можем пред-
предположить ложность Р в начале, чтобы, прндя к противоре-
противоречию, уотановить истинность Р в конце. Правильность самого
рассуждении не должна зависеть от истинности или ложности Р .
Наконец, истинность или ложность конкретных атомарных
высказываний бывает установить очень трудно ("теорема Ферма
верна", "эта позиция выигрыша для белых").
k. Содержательная нстиннооть
4.1. Определение. Формула Р языка L о называетоя
тавтологией, если У (Р) — \ для любой иитерпретат" д .
В более богатых языках понятие истинности, аппелнрутцее к
интерпретации, будет называться содержательной истинностью.
Применительно к L 0 это название было бы чересчур громким.
Тавтологии интуитивно отвечают расоуждевням, которые
правильно построены и "внутренне верны" вне зависимости от
нстиннооти или ложнооти их посылок, то есть атомарных утверж-
утверждений, входящих в рассуждение.
^•2. Алгоритм для выяснения, является ли Р тавтологией.
Пуоть р* , t р^ - все атомарные формулы, вхо-
вхов Р (оч
дящие в Р (очевидно, их конечное число). Значение У ( Р)
31

зависни только от вектора
ибо индуктивные правила (I) - D) из п. 2.3 позволяют выра-
выразить ^(Р) через tfCpj) . , . Ц (р'^) (подробно
это объяснено ниже). Вектор (
ыожет принимать всего я, разных значений. Переорав все
их, вычислим ^(г) для каждого из них и проверим, всегда
ли Зч' ' ~ ' •
4.3. Примеры. Следующие формулы являются тавтологиями
( Pi Q R - любые формулы). Ниже они будут играть
роль "схем аксиоы". Мы пишем кратко Р ** Q вместо
пары формул
А.О.
A.I.
А.%.
P-*Q ,Q-»P
P-(Q-P)
(PAQ)
А.З.
b.i. 1
В.2.
ел. IIP
C.2. IP —
C.3.
C.4.
С 5.
В.I. и В. 2. - это по существу определения связок
V через связку ^
оо
32

C.I. означает, что двойное отрицание Р равносильно
р - это закон исключенного третьего. С. 2. - механизм,
с помощью которого противоречие в систеые разрушает всю сис-
систему (подробности ниже, п. 5.6 гл. П).
4.4. Образец проверки тавтологичности.
Продемонстрируем три варианта проверки тавтологичности прос-
простой формулы A.I.
Вариант а) Цуоть ^ - некоторая интерпретация. Дваж-
да применяя E) п. 2.3, находим ^ ((Р -^(Q~
г 1 - tf (P) С4 - i t
потому что У? (Р) - V?(P) для любых |-
Вариант б) Протабулируем )$ ( Р ~?(Q -^ Р))
зависимости от
О
О
I
I
о
I
о
1
затем
О
О
1
I
I
О
I
I
(заметьте, что если г
заться, что не все пары
Например, Р
3-1977
Ь( не атомарные, то может ока-
^Р) . Ч'( Q) реализуются.
Q сами могут быть тавтологиями).
33

Вариант в) Основное свойство связки —> состоит в
том, что Р—*Q ложно, только если Р истинно, a Q
ложно.
Дэпустим, что в некоторой интерпретации Р~* (Q~^ P)
ложно. Тогда Р истинно, a Q —> Р ложно, откуда в
свою очередь Q истинно, а Р ложно - противоречие
для Р .
Читателю рекомендуется провести все три варианта про-
проверки для более сложных формул А.2., А.З., С.З., С.4. и
решить, который из них более приемлем.
Опишем в заключение множеотво всех возможных интерпре-
интерпретаций языка bo .
4.5. Предложение. Пуоть Уо - Я"—* {0, ^ 5
любое отображение множества атомарных формул в j
Тогда существует единственная интерпретация $;'J*
. совпадающая с ]р ва Д
Дэказатедьство. Назовем длиной формулы Р количество
знаков алфавита, из которых она составлена. Пусть тк
множество формул длины К
Прежде всего ?^- Ли J([);tf j- . Так как
по условию *?((?>)= О j Vp(lij =: -/ , существование и
единственность Предложения Н?о на Т очевидна.
Пусть доказано, что \?0 однозначно првдолтается
до "частички* интерпретации ^ на множестве beef формул
длвш ¦? К--\ . Покажем, что *-f ' продолжается па
; индукция по К даст трефемое. Нам п©нед»5"игся
4.6. Лемма. Вуотъ Рб J^ , к ^ 2 Тогда
34

p = ~~\ ( Q) , где Q, e TK_3 , либо существуют такие
4 ,QipL i
или P=(Q1)v(Qzf "¦ P=(QiM«k) •
Все эти альтернативы взаимоисключающие, и в каждом случае
формулы Q . Q1 t Q 2, определены однозначно.
Набросок доказательства. Существование Q или (Qt
и то, что длина их меньше длины Р , следует из опреде-
определения множества формул. В доказательстве нуждается только
единственность такого представления.
Она сводится к некоторому комбинаторному утверждению
о скобках, если исключить случай Р г: ~f (Q) , кото-
который, очевидно, не может совпасть с остальными и однозначно
определяет Q .
Это утверждение о скобках состоит в том, что в любой
формуле языка ио по каждой скобке парная ей скобка вос-
восстанавливается однозначно (доказательство см. у Клини, § 7
и § 17).
Считая, что это так, и что P^fc ~~f (Q) . дадим
рецепт для однозначного восстановления Q , и Q^ и
связки между ними. Он состоит в следующем:
а) Qj есть формула, стоящая между левой крайней
скобкой в Р и парной к ней.
б) Q^ есть формула, стоящая между правой крайней
скобкой в Р и парной к ней.
в) Связка - это та связка в р , которая стоит
между двумя найденными парными скобками.
35

Окончание доказательства 4.5» Продолжим д на 3"^ .
пользуясь формулами (I) - D) п. 2.3. Единственность продол-
продолжения следует из этих формул, а существование из леммы 4,6.
5. Синтаксическая истинность
5.1. Как было сказано, формальный язык идеализированно
описывает некоторые типы математических рассуждении. Среди
реальных типов совершенно особую роль играют доказательства-
цепочки рассуждений, которые исходят из некоторых (более или
менее явно указанных) аксиом, и выводят из них ноше утверж-
утверждения - теоремы - по определенным (также более или менее
явным) правилам.
Этим объектам интуитивно отвечает следующие конструкции
внутри формального языка L . Пусть j - множество фор-
формул L
5.2. Определение.
а) Правилом вывода RI (англ. Ъ"& of 'и^(м.К<л, )
(из l формул языка L еще одной формулы) называется
( \ + i ) - ыестное отношение между формулами языка, то есть
подмножество RlC $Х Тх ¦.. X f ( (j+4) раз);
б) если [р±г ¦ -, /у; P}r± )€ RI , то форму-
формула pL + i называется непосредственным следствием
( Pi ' ¦ • ' Р' ) по пРавЕЛУ RI- ^в соответствии с прави-
правилом, согласно правилу ...).
36

5.3. Пример. В языке высказываний Lc применяется
единственное правило вывода МР (лат. motUs ролгл-4 ):
\^1 рс Т* $ * г состоит из троек вида ( Р} P^G^Q ),
где Р , Q - любые формулы. Иными словами, Q является
непосредственным следствием из Р i P^Q
5.4. Определение. Пусть ? - некоторое множество
формул языка L , К некоторое множество правил
вывода. Ш во дом в языке L (подразумевается "из ?
в соответствии с правилами R ") называется любая конеч-
конечная последовательность формул р± - - - ,р„_ со следую-
следующими свойствами:
a)
б) Если fL>. i , то либо Рд, 6 & , либо /-\,
является непосредственным следствием части формул 0^ t ;
, р л - ± в соответствии с одним из правил из множества R
Примеры выводов в языке L 0* см. в § 6.
5.5. Определение. Пусть заданы % и гч , как в
п. 5.4. Формула г ? т называется выводимой щз Z, ,
если существует такой вывод Р ± , . р>^ , что
Утверждение " г выводима из ^ "в метаязыке
сокращенно записывается С |~~ г .
5.6. Замечания.
а) Правило вывода есть важнейшее понятие, которое
в реальных математических текстах обычно никак не формали-
формалифр
зуется. ,>W(,M/<A рс УЫ^\ отвечает простейшим рассуж-
рассуждениям, построенным пс схеме "Если верно г и верно.
37

что из Р следует Q , то верно Q ".
б) Множеотво "посылок" ^ в реальных текстах,
когда его удается выделить, обычно состоит не только из
аксиом теории, но также из некоторых выведенных ранее утвер-
утверждений, которые входят в последующие конструкции "целыми
блоками", без повторного воспроизведения их вывода. В изо-
изолированных случаях в /¦ могут входить не "истинные" ут-
утверждения, когда в доказательстве какого-нибудь факта от
противного мы принимаем его отрицание в качестве одной из
посылок.
в) Вывод есть аналог доказательства. Если в
входят только содержательно истинные формулы, и если правила
вывода сохраняют содержательную истинность, то выводимые из
? формулы можно назвать доказуемыми, или синтаксичеоки
истинными (относительно <? , R ). В достаточно богатых
языках (но не в Lо !) доказуемых формул оказывается су-
существенно меньше, чем содержательно истинных, если понимать
содержательную истинность в смысле некоторой стандартной ин-
интерпретации.
г) Реальные правила вывода обычно позволяют эффективно
распознавать, является ли данная формула 'ji-l непосред-
непосредственным следствием формул Р^ р. или нет.
Точно так же, обычно можно эффективно распознать, является
ли данная формула аксиомой или нет.
5.7. Пример-щутка. Один из главных элементов поэтичес-
поэтической системы древнеисландской поэзии составляют специальные
38

поэтические формулы, которые называют кенгашгами. Кеннинг
еотъ выражение, которое может заменить одно слово. Например,
суть кеннинги
"вьюга копий" есть кеннинг "битвы
"древо битвы"
"куст шлема"
"метатель меча"
"раздаватель золота"
"море телеги" есть кеннинг
"небо песка
"поле тюленя"
"воина"
"мужчины"
"человека"
суть кеннинги "моря" и т.п.
Простой кеннинг - это кеннинг, никакая часть которого не
является кеннингом. Приведенные выше примеры доставляют про-
простые кеннинги. Они играют роль аксиом, и создавать новые
простые кеннинги, очевидно, имеют право только великие поэты.
На долю невеликих поэтов остается создание новых кеннингов
по правилам вывода. Правило вывода нового кеннинга из уже
имеющихся: любое слово в одном из данных кеннингов может
быть заменено его кеннингом (не обязательно простым). Пример
сложного кеннинга с его расшифровкой (пример реальный):
"метатель огня вьюги ведьмы луны коня корабельных сараев".
V ч ч ".
корабль^^,^-^
копье
битва
меч
воин, мужчина, человек
39

Леонид Мартынов воспринял кеннинги как метафоры (глу-
(глубокое заблуждение, хотя и простительное. Структурные роли
кеннингов и метафор в разных поэтических системах совершенно
разные) и написал стихотворение "Песни скальдов", которое
кончается так:
... Л может быть, переводчики что-то перемудрили?
Нет! Возможно и в наши живут времена
какие-то метатели огня вьюги ведьмы луны коня
корабельных сараев или
расточители янтаря холодной земли великанского кабана?
Все возможно!
И кто утверждать может твердо,
Что и ныне нет песен, которые vc кно назвать
Прибоем дрожжей людей костей Фьорда?
Может быть, есть и нынче такие песни, как знать?
Ь.8. Задачи:
а) Восстановить простые кеннинги, входящие в вывод
двух последних кеннингов, процитированных Мартыновым.
б) itccxpoHib кеннинги максимальной длины, выводимые
из np:i«ecibiHHX в п. 5.7. Дэказать, что более длинных кен-
кеннингов вывести нельзя.
в) Щ*а,.умать кеннинг В.П.Маслова (не путать с метафо-
метафорой!).
40

6. Совпадение содержательной и синтаксической
истинности в языке Lo
6.1. В атом параграфе будет доказана следующая основ-
основная теорема о языке и0 . Обозначим через Д,Х. (аксио-
(аксиомы) множество тех формул языка Lo , которые получаются
из формул A.I., ... , С.5. пункта 4.3. подстановкой вместо
букв Р Q R любых формул ш И Я V (таким образом
АЛ С.5. это "схемы аксиом"). Определение правила
дано в п. 5.3.
6,4.2. Теорема. Любая тавтологичная ("содержательно ис-
истинная") Формула Р языка L. с выводима из Я "*- посред-
посредством МП ; наоборот, любая выведшая формула тавтологична.
Доказательство будет разбито на ряд лемм.
6.3. Лемма»
а) Все формулы из Я^ тавтологичны.
б) Если Р; P-^>Q тавтологичны, то и Q
тавтологична.
Доказательство» Упражняйтесь. ¦
6.4. Следствие. Если й~х.\- Р , то Р тавто-
тавтологична.
Доказательство. Пусть P-i j ' • • j рл. = р
вывод Р из f\yz . Проведем индукцию по РЬ . Если
тавтологична по лемме 6.3.а). Пусть у\_~?,Ъ ' и доказано.
П." 4. , то Р ~ Г' х t Я X , так что
41

что г-i , •' -1 I' л. - d тавтологии. По определению
вывода, либо Р ^ fcl Я X либо Р^ непосред-
непосредственно следует из |"\ и lj< ((Suu^. Pj -^ P,v, ) для
L . i< ^ ft-- 4. . Лемма 6.3 а) в первом случае и
6.3 б) во втором доказывает тавтологичность .
Этим доказана вторая часть теоремы 6.2. Первая тре-
требует гораздо большей работы.
6.5. Лемма о дедташи. Пусть qC. $ - любое мно-
множество формул языка J_j , содержащее все те Формулы!
которые получаются из А.О.. АЛ.. А.2. (п.4.3) подстановкой
вместо P.Q R любых формул. (В частности, можно
взять ? - Д.Х ). Пусть.далее. Р Q 6 3~
Дзказателъство. Пусть Q ^ ., . Q - Q - вывод
Q из j? Pj .(здесь = есть знак метаязыка). Индук-
Индукцией по К покажем существование вывода ( Р —* Q )
из ?
Если Ц - i .то либо Q €1 ? , либо Q - Р .
В первом случае Р —> Q является непосредственным след-
следствием из /Q.Q—^(P~^Q)j (аксиома АЛ.)
Во втором случае г~^ Р есть аксиома А.О. Обе нужные
аксиомы, по предположению, содержатся в <?¦ .
Пусть теперь K"i Z и пусть ? /— ( Р~? CSft'^
для всех L<K-1 . Так как ^?P|t-QK.~Q
для Q имеются три возможности: а) ф€? ; б) ф - Р
в) Q следует по HP из Qi и Qj^-
L
42

Случаи а), б) разбираются точно так же, как случай К-1 .
В случае в) последовательность формул, составляющая вывод
из ? , имеет такой вид (справа краткое пояснеше)
A) вывод P-^Q^ ) (индуктивное предположение)
B) .вывод р—^(Qc""^^) (индуктивнее предположение)
E) P -? Q (kP K (I) И D))*
В дальнейшей такие рассуждения будут проводиться более
кратко, с указанием лишь завершающих шагов вывода (здесь C),
D), E)).
Для формулировки следующей лешш введем одно обозначение.
Пусть ^ '¦ 7—^ {0,1} - любая интерпретация языка
Lo • Для каждой формулы Ре"? определим новую фор-
хулу р , положив %г
. г Р ,еслм ^СР)-1
Р - I IP , если *(Р)= О
(Здеоь Р и = суть значки сокращенней записи иетаязыковнх
выражений).
6.6. Основная лемма. Пусть р^. , р^ - конечное
множество атомарных Формул, содеркааее все атомарные Формулы.
входящие в р . Для любой интерпретации ^? имеем

Доказательство отложим до п. 6.8. Интуитивно лемму можно
рассматривать как оформление следующей идеи. Естественно пыта-
пытаться доказывать теорему 4.2. индукцией по длине тавтологии Р ,
представляя ее в виде 1 Q иди Q( —т> QL и т.н. Но
включать тавтологичность в индуктивное предположение невозмож-
невозможно, ибо части @ fi Qn тавтологий ~7 Q Q -}Q?
вовсе не обязаны быть тавтологиями. Если г -~ ' «X , то
Q "содержательно ложно"! Операция Р насильственно
делает любую формулу истинной в интерпретации *? , и лемма
6.6. составляет тогда важнейший шаг, поддающийся индуктивному
доказательству по длине Р .
6.7. Доказательство теоремы 6.2 с помощью основной леммы.
Нужно доказать, что если г ~ г для всех *? ,
то [fin} f Р .
Согласно основной лемме {fi"X.t p^ -< ¦ f>\ j h~ I
для некоторых атомарных формул Д' . Проведем индукцию
вниз по X .
Индуктивное предположение: ^ \йх-, ib^ ; ,,,. pj J (—
1 S S "$ t . Начало индукции: S ; ? ; конец - S -О
Переход от S к $ "L .По лемме о дедукции, из
0^ } Ь Р
следует выводимость
f А X, ^4 .. - рД j b{fta -? f ) ' По предположению
4.5. существует интерпретация *f' , совпадающая о f
на С Pi*" Ps-lj • отличающаяся на Pj-
Следовательно, из ^/4х; р^.. ft^ j
выводится как р^—^ р , так и 7ps —^ Р . Согласно
аксиоме С.4. из /Ixi выводима также формула
44

Дважды применяя МР к ней, находим
6.8. Джазательотво леммы 6.6. Проведем индукцию по длине
формулы Р (см. п. 4.5). Для формул длины I, то есть элемен-
элементов множеотва Я V [О fi.} лемма проверяется непосред
ственнс.
Предположим, что для более коротких, чем г . формул
лемма доказана. Как в п. 4.6 представим г в одном из четы-
четырех видов:
Р -  0. илир^ЦЛЧг , где&-—> или V или Д
а) Сдтчай Р~ 1 & ¦ Если <?( Q ^z 0 .то
- "I Q - Р ~ Р^ • buj^s™0011" Q z P
из yj^x Р\~ рх~ \ следует из индуктивного предполо-
жения, потому что длина Ц меньше длины
Если же1(_Ь^,^-'1. ,toQ -Q ,
Здесь Ц выводится из ^ f\j: b^ - , рг| пс
индуктивному предположению, затем 7 Q ' Р выводится
из Q и аксиомы С.I. Q—)"I7Q посредством МР.
б) Случай Р - Q( ^ Qz. . Сначала сведем в таблицу
при разных сочетаниях % я ^?(Q,) i (o)t ) формулы,
вывод которых существует по индуктивному предположению и формулы,
которые нужно вывести.
В столбцах для Д и V мы намерены вывести такие
формулы, из которых Ш AQ?) и (Qi^Q?) соответст-
зенно выводятся с помощью B.I, В.2 соответственно применением МР.
Шводимость ниже означает "выводимость из лХ и пары
юрмул 1-го столбца".
45

I Данв j Цужно вывеоти
Щ1Щ
А | V
о о
о i I 7Q1 <2L ! 2
I 0 ! W1 ; Щг ! 3
I I S Q. . Q, ! 4 Q
д Фошул I - 12. Простейшее соображение состоит в
следующем: если Р шводиыа, то для любой К формула
^—*? Р также выводима (аксиома А.I : Р—=> (?-^Р) ,
и МР). Это сразу же доставляет выводимость 2, 4. 10 и 12. Свив
в столбце Л двойные отрицания с помощью C.I, получим выво-
выводимость 5 и 7.
I выводится из 1 GL~"^ I Qi и С. 5 посредством МР.
3 выводится из С.З : Q j-^ G (?г)
(и данных) двукратным применением МР.
6 выводится из С.2 : 1 Q,"^^^
(и данных) применением МР и затем C.I и UP.
8 выводится из С.З: ^-^ (il0^ )
(и данных) применением МР, C.I к 11 Q., и снова МР.
9 выводится из С.З: 1 ^ -
двукратным МР.
И выводится из С.2: "П Ql -^ (l Q±
заменой 17 Q на Ц по C.I и МР.
46

6.10. Замечание об t/Ьс .Формула г навивается не за-
зависящей от множества 6. формул языка, есл» г и Ч г ив
выводимы из С •
Множество Я'*- определенно содержит формулы, зависящие от
остальных: из аксиом A.I, А.2, А.З, B.I, В.2 можно вывести вое
остальные (Мендельсон, стр. 39-43). Опустив эти малоинтересные
выводы, автор надеялся более выпукло показать содержание теорема
6.2.
С другой стороны, существуют частные случаи аксиом A.I,
скажем, невыводимые из А.2, А.З, B.I, В.2 и ив. (см. Мендель-
Мендельсон, стр. 46);" Среди спссбов доказательства независимости име-
имеются интересные образцы синтаксических рассуждений, и мы про-
проиллюстрируем их на следующем примере.
Утверждение. Формула (чР-~ЯР)-^(AР-?Р)-^ Р) , частннй
мучай А.З, не выводима из АЛ, А.2 посредством HP.
Доказательство. Пусть Q - формула. Обозначим через Q
формулу, которая получается устранением из Q всех знаков "J
и сопутствующих скобок. Укажите точное определение Ь( ин-
Иукцией по длине 6( !). Верны следующие утверждения:
а) Если Р еоть частннй случай АЛ или А.2, то Р
равтология.
б) Бели К является непосредственным следствием Г и
Q i a P и Q тавтологии, то К тавтология.
Значит, если Q выводима из АЛ, А.2, то Q - тавтоло-
Рия. Но QlP-Mp^Cnf^PHP)"]^ .где
Р -атомарное высказывание, не является тавтологией.
47

ГЛАВА П
ЯЗЫК ПРЕДИКАТОВ
В этой главе вводится и частично исследуется класс таких
языков |j , которые способны уже гораздо более реалисти-
реалистически описывать содержательные математические рассуждения, чем
языквнсказываний. Общее название этого класса языков: "языки
предикатов первого порядка". Мотивировка названия будет дана
ниже. Перед чтением этой главы читателе рекомендуется перечи-
перечитать § I главы I: "Общие сведения о языках". План второй главы
вначале близок к плану первой главы, но структура определений
и результатов, естественно, усложняется.
I. Алфавит и синтаксис.
1.1. Алфавит Li . Он состоит из следующих множеств сим-
символов.
а) Символы переменных (в обозначениях 0c; ^ Ъ
с индексами;,
символы констант (в обозначениях 0-{ Q; С
с индексами),
с О
символы операций (в обозначениях j-. Q . /Ъ
с индексами),
символы отношений (в обозначениях Р / % 1»
с индексами).
Каждому символу операции (отношения) сопоставляется натураль-
натуральное число - его ранг: интуитивно это число аргументов операции
(число мест отношения).
(Множество символов переменных обозначается Д ; оно
предполагается непустым, так ?э как множество символов отношений.
Остальные множества символов могут быть и пустыми).
48

В тексте слово "символ" будет часто опускаться. Мы пишем
"пусть "ЭС - переменная" вместо "пусть X. - символ перемен-
переменной", и т.п.
б) Логические связки —^ V. Л, ~7 - те же, что и
в языке L. о .
в) Квантор общности V , квантор существования j •
г) Скобки ( ; ) и запятые.
Это описание алфавита относится к целому классу языков.
Количество символов функций и отношений разных рангов и - позже -
вид налагаемых на них условий - аксиом - отличает языки разных
ориентации: языки арифметики, теории множеств, геометрии и т.п.
1.2. Синтаксис L ч. . Конечные последовательности знаков
языка L^ суть выражения. Одно выражение (в частнооти, символ)
может входить в другие как его часть несколькими разными спосо-
способами; указать вхождение Q в р означает указать пред-
представление выражения $ в виде г Q R , где г и js -
выражения. Заменить Q на Q (в данном вхождении Q в
? ) значит построить выражение PQ R .
Среди всех выражений языка L^ основную роль играют три
класса выражений: термы, атомарные Формулы и Формулы. Вот их
описание.
а) Термы. Символы переменных и констант суть термы. Если
j *f. , а \ - символ операции ранга /t< , то
№ " "Ьк) есть терм* Xnfofc теРМ получается применением
этих правил конечное число раз.
(запись-t^ .... х. есть сокращение для выражения, состоя-
щего из \лу термов, разделенных запятыми).
4-19Т7
49

Интуитивно теши - это названия математических объектов,
о которых говрит данная теория, а символы операции суть назва-
названия операций над ними. Константы суть названия каких-то конкрет-
конкретных объектов. Скажем, в языке арифметики ОС , ^ могут быть
названиями целых чисел, a J" названием операции "сложение"
(ранга два). Тогда у^^'зЛ - название "суммы X и Ч. ".
Удобно иметь также две специальные константы - названия 0 и I.
б) Атомарные формулы.Атомарная формула есть выражение
вида р (х i . 7 "ч^) , где р - символ отношения ранга К ,
a ^i ... 7 I*. ~ термы.
Интуитивно р С ki, -¦-, "*¦*.) отвечает фраза вида
"верно, что упорядоченный набор объектов ti . ., ^ч, обладает
свойством р ".
(Таким образом, р ("tij - ¦¦ ,^*.) можно рассматривать
как высказывание о t ^ „. 4ц. ; отсюда происходит другое
название для р - предикатный* символ. Мы им не пользуемся,
сохранив слово "предикат" лишь в общепринятом родовом назва-
названии языков L ^ . С теоретико-множественней точки зрения ука-
указание "свойства" К^ объектов равносильно указанию всех
К,- ОК объектов, обладающих этим свойством, то есть К -
местного отношения. Этим объясняется наша терминология).
в) Формулы. Атомарные формулы суть формулы. Если 6J, ,
Q, . Q - формулы, ОС - переменная, то выраяения
суть формулы, Любая формула получается применением этих правил
конечное число раз. \/эс(B") читается " для всех ОС верно
50

Q «. Z3^^Qj читается "существует такое DC • что
верно Q ".
(В сокращенной записи скобки будут опускаться в ооответ-
ствии с прежними соглашениями и здравым смыслом).
1.3. Замечания, а) Атомарные формулы и формулы языков
L 0 и L -1 соответственно описывают один и *от же класс ут-
утверждений. Однако описание с помощью L ^ гораздо богаче и
деаализированней, потому что, во-первых, в языке \-\ есть
средства для описания субъектов высказываний и конструкций над
ними и, во-вторых, в языке L^ есть символ для слов "для всех"
и "существует".
б) В языках выше первого порядка могут допускаться отюже-
н'л и функции, аргументами которых являются другие отношения
.: функции. Могут допускаться также кванторы по отношениям
и/или функциям. В третьей главе будет введен язык второго поряд-
порядка, ориентированный на теорию вещественных чисел и континуум-
проблему.
Конец этого параграфа посвящен описанию некоторых простых,
но важных синтаксических свойств языка i-± , которые постоянно
попользуются в дальнейшем.
Следующая лемма параллельна лемме 4.6 главы I и является
основой индуктивных рассуждений по длине термов и формул.
1.4. Лемма, а) Если тещ "Ь не является ни переменной.
ни константой, то *?_ однозначно представляется в виде
... -itC) • JJ2 *f" - Функция ранга К ,а
,!iK -SSEH-
51

б) Если формула Р не является атомарной, то она одно-
однозначно представляется в одном из видов (I).
Вот первое индуктивное рассуждение, описывающее противопо-
противопоставление свободных и связанных вхождений переменной %- в
формулу Р
1.5. Определение, а) Всякое вхождение переменной в атомар-
атомарную формулу свободно.
б) Всякое вхождение переменной в * Q или
/Q.") 1(ЦУ\ ( ? - любая связка) свободно (или связано) в
точности тогда, когда свободно (или связано) соответствующее
вхождение ее в Q (или (?>^ , или Q ).
\ V
в) Всякое вхождение переменной Ш х \
связано. Вхождения остальных переменных в Vx (Q) и Зх (О.)
таковы же.как в Q .
В пункте в) Q называется областью действия кванторов
V соответственно 3 . По лемме 1.4. область действия
каждого квантора в формуле определена однозначно.
1.6. Определение. Переменная X не ограничивает теш
"t в формуле Р , если ни одно из свободных вхождений DC
в Р не лежит в области действия квантора
где Ц - переменная, входящая в ^ .
Эквивалентная формулировка: Эс не ограничивает Т
в Р , если после подстановки х в / вместо каждого
из свобод" "Рождении X в г все вхождения переменных
под знаком х остаются свободными.
Объем класса формул, которые допускаются определением
1.2 в), несколько велик: он содержит, например, выражение
52

~1 •?. V X PC^N t которое на интуитивном уровне отвечает
неудачному высказыванию "существует такое X , что для всех
ЗС 2 обладает свойством Р ". Хотя это в общем не меша-
мешает развиио формальной теории, можно ограничиться рассмотрением
масса хороших формул.
1.7. Определение, а) Атомарные формулы хорошие.
б) Формуле *7 Q ,(Qi) *(Qi) тогда ¦ только
тогда хорошие. когда QfQxlQL *>Р°«« «. кроме того, общие
переменные дата фи Q^ входят только свободно.
в) Формуле VX(Q) я 3 X (U) тогда и только тогда
хороша, когда Q хороша, а ОС входит в б< > притом
только овободно.
Из определения нетрудно усмотреть, что. для каждой перемен-
переменней все ее вхождения в хорошую формулу Г либо одновременно
свободные, либо одновременно связанные.
2.1. Одна интерпретация f языка L^ в множестве М
состоит из наборов отображений, которые сопоставляют разным
выражениям языка элементы И или структуры над И (в смысле
Бурбаки). Эти отображения делятся на первичные. которые, собст-
собственно, и определяют интерпретацию,и вторичные, которые естест-
естественно и однозначно восстанавливаются по первичным. Сами же ото-
отображения, а также иногда их значения мы будем для краткости так-
также называть интерпретациями.
Перейдем к систематическому описанию интерпретации ^?. .
4Х-1877
53

2.2. Первичные отображеддч.
Интерпретация констант есть отображение *? множества
символов констант в М .
Интерпретация операций есть отображение, которое каждому
символу операции ± ранга К- сопоставляет операцию ^t(f)
то есть функцию на Н * Н- --. * № со значениями в М
Интерпретация отношений есть отображение, которое каждому
символу отношений р ранга К- сопоставляет подмножество
^ifb^C Нх'М*. .Х.М • то есть ^ -местное отношение над pi
2.3. Вторичные отображения.
А. Интерпретация термов. Интуитивно, мы хотим интерпретиро-
интерпретировать переменные как названия "общего элемента" множества Щ ,
которым при желании можно приписывать конкретные значения из М .
Терм 4^-г ) ^-и} мы хотим интерпретировать как функцию
от U- аргументов ^?(^1) - • "?С-*к) ,
которые могут пробегать Н , и т.п.
Чтобы дать точное определение, введем обозначение
^-j = множество всех отображений в П множества
переменных д языка [_ * .
Один элемент ^ € П , отало быть, сопоставляет каждой
переменной it из Л ее образ в И , который мы будем
обозначать ^(х)^) (а не ^Сх") !). Элементы Н
мы будем иногда называть точками.
Таким образом, мы рассматриваем переменные как функции
на Н со значениями в И , и так же будут интерпретиро-
интерпретироваться все термы.
54

Итак, интерпретация термов есть сопоставление каауюму
тещу -к функции *?(^ на Н* со значениями в Н ,
которое определяется индуктивно следующими соглашениями:
а) если С -конотапта, то ^?СС) есть постоянная
функция со значением S?(c} (которое задано первичным ото-
отображением);
б) если X -переменная, то ^.Qx) есть
как функция от ^ ;
в) если "Ь -' ^Gtl, --, t J) , то для всех
где liti Kl) € H предполагаются уже определенными,
a 4?fi.^ есть функция на n^ntf-- . X п , заданная пер-
первичным отображением.
Б. Интерпретягтия атомарных Фот^у^г Всякой формуле
языка при интерпретации *? прнпионвается ее
ности ^fCP) . В отличие от языка ?.о , Ч (Р)
не есть просто 0 или I, но функция на |Ч , пру"У"«г»аая лишь
значения 0 и I.
Если Р^ JaC-tj. ... Ю атомарная формула, эта функция
определяется так:
Интуитивно зто означает следующее. Утверждение "объекты
1 \ обладают свойством Г) "не обязано быть
верным или ложным при всех значениях объектов
55

оно иногда истинно, а иногда ложно. Переменная точка
отмечает приписывание ковкретша значений переменнш термам;
*?(Р)С1^ есть явтевЯе истинности утверждения р
для этих конкретных интерпретаций термов.
В. Интещретя""" Формул» Как и семи формулы! она опреде-
определяется индукцией по числу связок и кванторов. Интерпретация
атомарных формул уже дана.
Если Р- ~l(G0 «и (Qi)*(Qj .где # -одна
¦з связок, то функция истинности Т(Р) определяется по
S?(GO. ТОД Ч-Шг) по тем же Оюшулам. что и в
языке Lo : см. A) - D) из п. 2.4. главы I.
Чтобы определить х ( Pj в случаях Р вида vX Q
или 3 А (х удобно ввести следующее словсупотреоление.
Точка | € Н называется изменением точки ^^Н
по переменной X (соответственно, по множеству переменных Хо ),
^^ для всех переменных
отличных от X (соответственно, для всех ^ ^ Ло )•
Теперь положи*
по

3.
3.1. Ошюанные ваше свойства интерпретаций относятся ко
всем ятим класса и*. • Конкретный язык может быть ориен-
ориентирован на ту или иную математическую теорию, и на его интер-
интерпретации тогда естественно наложить те иди иные дополнительные
ограничения.
Приведем несколько примеров яаисов и интерпретаций.
3.2. Яаык арифметики L^ n% . В алфавите этого языка
есть одна константа Q . ; три символа операций (штрих)
(ранга I) -f- и • (оба ранга 2); один символ отношения
ранга 2: ~ .
г^яндрр^гияя интетдреташя *?¦ яаыка L±Ai во
множестве целы* 1гяплл & состоит из следующих отображений.
Первичные отображения
С* 0 .нуль в Z-
есть операция "прибавление единицы",
или "непосредственно следующее число"
*- v "И есть сложение •
1. С') есть умножение |
есть равенство в ^
О вторичных отображениях трудно сказать что-либо новое.
Зкажем, атомарная формула Р вида -(х,^) имеет
гледупцую функцию истинности:
I. если
О иначе
57

3.3. Язык теории множеств (_. Jut • В самом экономном
алфавите этого языка есть символ константы ф , символ отно-
отношения ранга 2 ? и совсем нет символов операций.
Стандартная интетяретя'тд^ х языка L. &2Л. подра-
подразумевает, что в качестве Н взят некоторый "универсум" -
большое множество множеств, замкнутое относительно некоторых отан-
дартннх операций над множествами, которые описаны ниже. В этой
интерпретации
*f (fl( ) есть пустое множество;
^?(?") еоть отношение "быть элементом".
3.4. Нестандартные интерпретации. Язык, даже предназначен-
предназначенный для описания некоторой конкретной области математики, -
арифметики, теории множеств иди геометрии, - может иметь также
в высшей степени нестандартные интерпретации. Обычно на интер-
интерпретации отношений и операций в ориентированных языках накладывают'
ся дополнительные условия: скажем, отношение X С - ^ (°м- п« 3"'
описание L. Д1 ) даже в нестандартной интеопретащш должно
удовлетворять естественным аксиомам равенства. Тем не менее, одас-
значнооть интерпретации эти требования не могут обеспечить: см.
ниже теорему Левенгейма-Осолема, а также - в следующей главе -
описание нестандартной интерпретации языка вещественных чиоел в
множеотве случайных чисел.
Здесь мы приведем простейший пример интерпретации произволь-
произвольного языка L-L . подчишташийся только условиям из § I.
3.5. Мирималыюя интердретпттяч М_
Это интерпретация в одноточечном множестве |Ч - /
58

Легко убедиться, что константа и функции интерпретируются одно-
однозначно. Небольшая свобода шбора есть ливь в интерпретации от-
отношений: так как И К - - - X М - одноточечное множество,
мы можем положить для каждого отношения Р :
vo гр\ - %Ф (пустое подмножество)
или
В зависимости от этого меняется значение истинности атомарных
формул ( N одноточечное множеотво, так что i(P) при-
принимает просто значения 0 или I):
f I. если <? (Р) j
VU если
для любых термов "?-^ ,-... ък и отношений ' ранга /ъ .
Интерпретация формул дальше подчиняется правилам языка
/_0 , потому что кванторы, как легко видеть, не оказывают ника-
кого влияния: <? ( V*<0 "
4. Нбкотошб вычисления
4.1. Пусть Sf - некоторая интерпретация языка *-1 .
Формула г называется истинной в интегаговтЯ1т" 1_ , если
^CPXDl для всех |€^
Пусть 3 - некоторое множество формул. Интерпретация, X
называется моделью для J , если все формулы из
истинны в ^?
59

Ниже мы фиксируем язык L и интерпретации Х_ и
приведем несколько примеров вычислений Ч!. (Р) • важных для
дальнейшего.
4.2. Лемма. Пусть г - Формула. "? f € п
Предполозаим. что для всех переменных X , имеющих свобод
вхождения в
Р ,
Доказательство. а) Пусть Т. - некоторый терм в пусть
дня люоой переменной t? , входящей в \, , имеем
С1 X^Xf) • Тогда. пользуясь 2.3.А, индукцией
по длине "t легко находим, что ^("t)^) г ^("^)(§ ) .
6) Дркажем лемлу для атомарной формулы ( вида
* С°гласн0 2.3.Б,
U иначе,
) Н ^ |
и аналогично для i(.P)(^ ) .Но если ^ и | совпа-
совпадают на всех переменных, входящих в Р , то тем более они
совпадают для всех переменных, входящих в Z.^ , и по пункту
•а) имеем ^ П \ '-
в) Проведем теперь индукцию по общему числу связок и
кванторов в [> .Воли Р  l(Q ) ¦"(&)#(&
то вывод леммы для Р из леммы для Q и ^ ^L очевиден.
ывод леммы для Р из леммы для Q и ^ ^L очевид
Пусть теперь Р~ У^(C) . и пусть лемма верна
для Q (проверка случая aX^Q) аналогична).
60

Имеем по определешш
Г I, если Ч fQK^J - 1 для всех h
изменений | no x
О иначе
1, если ^(Q)B)~l для всех ? ' ,
изменений f по X
0 иначе.
Разрешим в правых частях этих норму л изменять *? и ^ .
также по всем переменным, не входящим своооцно в Q . Утверж-
Утверждения после слова "если" останутся справедливыми или ложами в
этой более широкой области значении, если они были справедливы
или локны раньше, в силу леммы А.г. Но тогда Ь и ? будут
пробегать одинаковые области значении, потому что ^ и ^
отличаются как раз по перерешили, не входявдш свободно б d .
и по - ЭС
4.J. Следствие. ?сж дюйдула Р не содержит свиоодных
вхождений переменной, то *?(Р)= 0 или I (независимо от
^ И" )•
Следующие примеры истинных ^«р;лул будут служить шше акси-
ом--'и- а них будет «сновано определение понятия выводимости
(синтаксической истинности) в языке i-1
4.4. Формулы л'Хе, Они получаются из аксиом А.и -
С.5. (п. 4.3. главы I) языка Lo подстановкой вместо Гл ^
любых ^ормул языка L ^ . Проверка их истинности в люоой ин-
интерпретации языка L± ничем не отличается от проверки в
языке Lo
61

Более общо, если в любо": тавтолгии языка t-e на место
атомарных цормул подставить „ормулы языка U <f , получится
формула, истинная в любой интерпретации Ь1 .
4.5. Фотхлула ^.1.
, есливсе
вхоадения X в Р связаны.
Проверка истинности & .1. Предполо-, vi, что 4l (. R) \.Ц) - О
где R, - формула 95 Л, |? МХ , и придем к проти-
противоречию.
Мы должны иметь тогда Ч! ( г" -—* V3c U )[ f ) — С/
и V?(Vx(p-»G0)(f)-t
Из первого равенства следует, что i (P)C?) ~ ^~
и ^?(VjCQ)(f'] г 0 , Последнее означает, что для некоторого
^ .изменения f по х .имеем *? (Q)^?) - О
Но тогда *f(P)(V) - ^? (р )(-?) - 1 . в силу
леммы 4.2., что по предположению >^ не входит в I свободно.
Значит, Ч. (,Р"^ ^)vSo) " ^ ; но это противоречит
&-*> ту=i-
4.6. Формулы Ф .2.
(напомним, что r*^Q означает \г~~} Q)A { Q~~? г)
Проверка иотипности ф> .2 легка и оставляется читателю.
4.7. Формула 5k .3. Прежде, чем выписывать ее, шедем
следующее соглашение. Пусть ЭС^, - . ¦ j X^ - разные перемен-
переменные. ^1,-- ) ^п. - термы, и пусть Р - некоторая
формула.
62

Мы будем иногда писать Р в виде P(Xi j , ЭС^) ,
для того, чтобы указать точный смпсл очеьь неоднозначной сокра-
сокращенной записи P(ri(.---; x.^.) ;
P("tit--- /^n.) означает результат постановки в PC^Ci,--- ,Х
терма L^ вместо каждого из свободных вхож-
вхождений переменной ЭС^) "* •
терма и^, вместо каждого иэ свободных вхож-
вхождений переменной Х^, (допускается, что
части таких вхождений нет).
с
(Не путать запись Ь"(^ , - - ,--?«,) р
в случае, когда р - символ -местного отношения. Послед-
Последняя запись является лишь частным суч&т первой).
Напомним, кроме того, что переменная ЭС не ограничивает
терм Ъ в формуле г (х) г если в г ("t) все вхоядения
переменных под знаками Ь остаются свободными.
Теперь выпишем формулу 2) .3:
2>,3. VxP(V) - > Р(с) , если DC не ограничивает
ЬР. х
Проверка истинности «»Q .3» Пусть ?, ? П i К
формула S) ,з. Предположим, что ilR)Cs) — О . Тогда
Из первого равенства следует, что i(.P^')Cs )~J-
для всех ^ изменений ? по ,Х •
Возьмем в качестве > такое специальное изменение, гдя кото-
которого Ч(Х)^')~ ^(^)(?J • Если мы докажем, что
63

то получим желаемое протиюречие.
Сформулируем нужный нам результат в виде леммы:
4.8. Лемма. Пусть DC не ограничивает t в I • Если
? ? Г1 • В ? есть изменение ^ по X. , для ко-
торого Ч[У)$)^Ш%) , то
.Доказательство. Проведем индукцию по общему числу связок
и кванторов в Р .
а) Пусть г - атомарная формула
Последовательно находим:
i (результат подстановки Т
б) Пусть Р есть I ( Q) или (^) * ( QiJ. Так как -
X не ограничивает "? в г , то же верно для Q , ^J). ,
Q , и индукционный шаг проводится автоматически.
в) Наконец, пусть г еоть 3^-С\ или v*cG{ .
Разберем первый случай; второй разбирается аналогично.
64

Случай I. М~ X . Тогда эС связана в Р ; поэтому
р(*ычп-р и ^рх^-^срк*1;
в силу леммы 4.2.
Случай 2. М ф X. Индуктивное предположение;
если J?1 - такое изменение
Г) по СС , что
Нужно доказать совпадение (для :? Ц* , как в условии
леммы) двух значений истинности
I. «Ш 4(GHX1K^)-1 да
0 иначе.
I, если ^(QC-t) )(•?)= 1 для
некоторого Ь , изменения "?
/
L 0 иначе.
При этом известно, что "?' - такое изменение ^ по
Предположим сначала, что второе значение истинности равно
I , что тС (, U,V.t i ) v*7 )~ T_ #
В соответствии с индуктивной гипотезой, изменив 7 по ^ так»
чтобы ^CxU^M^S^l-t)^4) .получим
5-1977
65

Покажем, что ft есть изменение ?' по Ч ; отсюда будет
следовать, что и первое значение истинности равно I. 'В самом
деле, Ь' получилось изменением Ь по Зс , <? - изме-
изменением ^ по ^ , а ^ - изменением $ по
Значит И есть изменение ^ по Эс и Ч ; нужно про-
проверить, что изменение по ОС на самом деле не произошло:
Действительно, левая часть еоть хСх)С*7 ) по определению
h ; правая часть есть i(.^)v^) по определению ^ ,
но И получилось изменением ^ по Ч , а Ч не входит
^ -fc , ибо ос не ограничивает "С в Р~ 34 0.
Осталооь проверить, что если второе значение истинности
равно 0, то и первое равно 0. Рассуждения почти такие же. Если
второе значение истинности равно 0, то ^? (Q(-t)lC1^) - О
для всех У) , изменений ^ по ^ . По каждому такому П
поотроим Ь , как в первой части доказательства. Как выше,
проверяется, что И1 является изменением ~?' по Ч и,
более того, пробегает все такие изменения, когда Ь пробегает
все изменения ^ по "U. . Значит и первое значение истинности
равно 0.
5. Аксиомы и выводимость в U .
Перед чтением этого параграфа рекомендуется прочеоть
§ 5 главы I.
5.1. Правила вывода в L-i . их два:
66

a) MP: Q является непосредственным следатвиеы Р и
; б)<я*-И. ( C^Y>JUicJUti^VLOVi, .обобщение):
является непосредственным следствием Р , где ЭС -
любая переменная, а г - любая формула.
(Интуитивно «ьй-К* отвечает обычной практике формулировки
свойств "общих" объектов: утвервдение типа " 0**^H*'^) =
; Х1"^ " следует читать " для всех DC и для всех Ч верно,
5.2. Логические аксиомы языков t-i . Для каждого
языка L^ обозначим через Дх^ множество формул, котоше
получаются из следующих схем аксиом подстановкой в них любых
формул языка:
а) тавтологии языка Lo .
б) Формулы
Д.1. VxtP-}Qy-^(P-*?3cQ) , если все вхождения ОС
в Р связаны.
д.2. VxP<->13ocP
д.3. V^rPC^ -»P(-t) , есж X не ограничивает
t в Р .
Здесь г / У - формулы, X. - переменные, t - терм,
5.3. Специальные аксиомы L± . Это аксиомы, которые
накладываются на символы отношений и операций в ориентирован-
ориентированных языках. Ниже будут приведены некоторые специальные аксиомы
теории множеств L^. e^t и арифметики L± fit
Здесь мы укажем лишь важный пример, общий многим ориентирован-
ориентированным языкам: аксиоме равенства.
67

5.4. Аксиомы равенства. Равенство - это символ — отно-
отношения ранга 2, подчиненный следующим аксиомам: (ш пишем ЭС~Ч
вместо tr-^jV^4) ):
E.I. #*.(*--*0
Е.2. Х-^-^
где г 0*/^) получается из Р(Х( X) заменой любой
части свободных вхождений эс на свободные вхождения U. .
Интерпретация *? языка с равенством — называется
нормальной, если - интерпретируется как обычное равенство,
то есть f L~} С. Н*М есть диагональ.
5.5. Выводимость. Пусть ^ - некоторое множество формул
языка L\ , Р - формула. Как в главе I, мы пишем ? HP ,
если существует вывод формулы Г из множества <f с помощью
правил МР и Qjlvb . Мы говорим тогда, что Р выводима из
? и т.п.
5.6. Определение. Множество формулу! называется противо-
речивым или несовместным, если существует такая формула / ,
что одновременно gh-P и / I—~1 Р ,
Важный частный случай. Если s противоречива и содержит,
Я эС-t (или даже только тавтологии из Я^о ), то любая формула
R выводима из i . Вот вывод ^ :
швод Р ; вывод 7Р ; аксиома С.2: 1 Р
двойное применение иЛР к этой аксиоме.
5.7. Теорема. Пусть интерпретация *? является моделью
для множества ^ . Если ?h Р .то ^?( Р)~ d.
Иными словами, вывод сохраняет истинность.
68

Доказательство. Нужно проверить, что непосредственное
следствие S? -истинных формул является у -истинной, для
МР это рее было сделано, для Чб-И^ предоставляется читателю.
5.8. Следствие. Если для множества формул ^ существует
модель, то ? непротиворечиво.
Доказательство. Предположим, что о - модель для Q
Бели ft" Р , то ? (Р)= 1 , если ? HI P , то
- 0 • поэтому вывод Р и 7 г шесте невозможен.
5.9. Замечание. Непротиворечивость есть чисто синтаксичес-
синтаксическое свойство множества ? ; между тем, критерий 5.8 требует
привлечения содержательных соображений для доказательства не-
непротиворечивости. Согласно одной теореме Геделя, этого нельзя
избежать: уже непротиворечивость системы аксиом L^ fit.
(см. ниже) не может быть установлена чисто финитными синтаксичес-
кими рассмотрениями.
Следующий параграф будет посвящен формулировке и обсуждению
результата, обратного к 5.8. Он ведет уже не к тривиальным пред-
представлениям о природе математической истины.
6. Теоремы о моделях Геделя и Левенгейма-Сколема.
Обсуждение.
6.1. Теорема. Пусть g ~2> J\"X^ - непротиворечивое
множество формул языка i-^ . Тогда & имеет модель - интер-
интерпретацию в множестве М , мощность которого не превосходит
мощности алфавита La (или счетна. если алфавит конечен).
Существование модели было доказано для языка L^ ft-^
Геделем (финитными средствами) в 1930 г. Утверждение о мощности
принадлежит Левенгейму и Сколему A915, 1919 г.).
69

6.2. Следствие. (Совпадение содержательной и синтаксичес-
синтаксической истинности в языке L^. ). Если 6 О fiX-i то Фор-
Формула Р выводима из g тогда и только тогда, когда она
истинна во всех моделях g .
Доказательство. Если г выводима из § > то она
истинна во всех моделях ? согласно теореме.5.7.
Предположим теперь, что Р замкнута и невыводима из ? •
Мы проверим, что множество {? ,~'fj в этом случае непроти-
непротиворечиво. Из теоремы 6.1. будет следовать существование модели
/ ? "'''/ • то есть м°Дели С , в которой Р ложно.
(Случай незамкнутой г сводится к этому случаю, потому что
^? -истинность Р равносильна *? -истинности замыкания
р , а выводимость г из f равносильна выводимости
замыкания Г из с в силу Ощгх. и аксиомы Д.З. при
?=ЭС ).
Дэпустим, что У ?  Р/ несовместно и придем к
противоречию. Для любой формулы К имеем тогда ^ t. 7'j *"" /\
и {f^PJhTR . Аксиома-тавтология R-i(
и двойное применение МР дадут У f ~JPj \r P
Ниже будет доказано, что лемма о дедукции для языка Со
(п. 6.5 главы I) оставется справедливой в языке /-^ , если Р
замкнута. Применяя ее, найдем % I— ~] Р —1 Р .Из аксиома
(~Т Р -^ Р") "^> Р посредством «IP выводим наконец ? |—р ,
вопреки предполокению. ¦
6.3. Обсуждение, а) Основное отличие результата 6.2 от
соответствующей теоремы в языке 1~о состоит в отсутствии спо-
способа эффективности проверки обоих свойств формулы ( -
быть выводимой из Q и быть содержательно истинной. (Понятие
70

эффективности впоследствии также будет формализовано, и соответ-
соответствующая теорема о невозможности эффективной проверки может быть
доказана).
Доказательство эквивалентности этих свойств также будет
неэффективным.
б) В содержательных применениях множество q обычно
получается добавлением к /l ^С з. специальных аксиом ориенти-
ориентированного языка (ср. п. 5.3). Существование модели у любой
(синтаксически) непротиворечивой системы аксиом выглядит вполне
естественным. Дальнейший анализ теоремы 6.1 в применении к конкрет-
конкретным языкам, однако, шявляет такие черты аксиоматического метода,
которые были неожиданными для математиков. Мы обсудим здесь два
характерных примера: "парадоксы" Сколема и Геделя.
Первый из них относится к языку L ^ &"? и состоит в
следующем, для реалистической формализации текстов по теории мно-
множеств средствами языка L± <?t достаточно считать, что
алфавит L^&'t счетен. Тогда, по теореме Сколеиа-Девенгейма,
аксиомы Lji ^ХГ имеют счетную модель. Между тем, одна из
акском обеспечивает существование бесконечного множества в
модели, а другая говорит о множестве всех его подмножеств, кото-
которое несчетно (согласно диагональному рассуждению Кантора, которое
может быть формализовано в Ц ?еТ ).
Второй "парадокс" относится даже к L±Ai . Дня его
описания следует привлечь еще одну глубокую теорему Геделя о
существовании такой "неразрешимой" формулы Г , что ни / ,
ни I P не выводима из аксиомы L^nt , но в то же время
Г истинна в стандартной интеопретации L^nV во множестве
целых чисел (эта теорема будет доказана во второй части записок).
71

Построив тогда модель множества | аксиомы L^/li-. 7
мы получим " нестандартную арифметику", в которой все аксиомы
справедливы, однако некоторое "интуитивно истинное" утвержде-
утверждение о целых числах ложно.
При этом положение дел нельзя спасти расширением системы
аксиом: согласно Геделю, добавление какого угодно набора эффек-
эффективно распознаваемых новых аксиом не может избавить от сущест-
существования "неразрешимых" утверкдений Р
Вопрос о том, как относиться к этому открытию, принадлежит
психологии по крайней мере на столько же, насколько к математике.
Поэтому небезынтересно сравнить две крайние точки зрения, между
которыми располагается целый спектр оттенков.
"Реализм" (или "неоплатонизм"). Целые числа существуют и
однозначно определены независимо от наших конструкций, и осмыс-
осмысленные вопросы об их свойствах имеют ответы, независимо от
того, умеем мы получить эти ответы, исходя из принятых за
"интуитивно ясные" утверждении, или нет. По мере развития мате-
математики развивается и наша интуиция, Геделевские "неразрешимые"
суждения должны по очереди становиться либо "интуитивно разре-
разрешимыми" (как явные примеры Геделя), либо выводиться из тех
суждений, которые будут появляться в классе "интуитивно разре-
разрешимых" с ростом опыта и интуиции.
(Не слишком ясно, что значит "существование" в первой
фгазе. Согласно Геделю "допущение таких объектов столь же
законно, как и допущение физических тел, и имеются столь же
веские основания верить в их существование". Тем самым, сущест-
существование становится примитивным понятием и объектом веры.
72

Автор зиписок склонен разделять дух позиции Геделя, если
щ ее букву).
"Ультраинтуиционизм".Основатель этой концепции Есенин-
фльпин кратко характеризует ее в следующих словах (см. Френкель
Бар-Хиллел. Основания теории множеств. МИР, 1966, стр. 316).
"Последовательное развитие браузровского скептицизма при-
приводит к ультраинтуиционистской критике, характеризуемой неве-
неверием в единственность натурального ряда, существование хотя бы
одного натурального ряда, в котором примитивно-рекурсивные
сгункции (и даже сложение) определены всюду, а также в принцип
математической индукции и в математику, основанную на этих
спорных допцщениях.
... В основе ультраинтуиционистской программы лежит широкая
теория модальностей ... и связанная с ней теория грамматических
воемен (ибо еще не наступившие члены становящейся последователь-
последовательности следует рассматривать как возможные в будущем). Истина при
этом рассматривается как результат возможного доказательства,
т.е. процедуры, благодаря которой предложение становится беб-
сгорным".
7. Дзказательство теорем о моделях.
В этом параграфе мы считаем фиксированным язык L^ ,
с бесконечным множеством переменных. Основной целью оудет дока-
доказательство следующего результата, объединяющего теоремы Геделя
и Левенгейма-Сколема:
73

7.1. Теорема. Пусть ? - непротиворечивое множестве
Формул языка L1 . содержащее у| Xt • Тогда существует
интерпретация у языка i, ^ в некотором множестве М %
являющаяся моделью ? и текая. что
мощность /Y ? мощность алфавита и
Мы изложим сначала план доказательства этой теоремы,
которое получится в результате соединения нескольких лемм.
Чтобы сформулировать их, введем два удобных определения.
7.2. Определения. Множество Формул ?. называется
полным, если для любой замкнутой Формулы Р либо Р 6 F. ,
либо ~7 р в С •
Важнейший пример полного множества с. в ориентиро-
ориентированном- языке: "все утверждения,истинные в (интуитивной) стан-
стандартной интерпретации". Это множество должно быть полно, если
мы верим, что всякое математическое утверждение либо истинно,
либо ложно, даже когда мы не в состоянии выбрать между этими
двумя возможностями.
7.3. Определение. Алфавит языка Ь называется достаточ-
достаточным для множества С . если для любой формулы р ( ТС) ? ? ,
содержащей равно одну свободную переменную [j() , существует
такая константа С- (зависящая от Р ), что Формула
Rp :
 У* PjX) —»  Р t(p) содержится в ? .
Интуитивный смысл Rp : "если не все 5с обладают
свойством Р , то можно указать конкретный объект Cfi ,
не обладающий этим свойством". Терминология "достаточность
алфавита"- овязана с тем, что в случае нехватки формул Rb
в ? мы можем просто увеличить С , добавив все R •
Р '
74

но воли не хватит констант С л , нам придется их
добавить к алфавиту языка (см. нихе).
Свойства 7.2. и 7.3. выделяют класс таких обширных
^№еств формул ? , что для них доказательстве теоремы
^ш. можно проиесги, непосредственно построив медаль И :
7.4. Основная лемма. Если ? совместно, полно.
|"алфавит й1 достаточен для ? , тс оуществует модель ?
¦рщности С мощности алфавита (j-
Следуювде две леммы позволят вложить любое множество ?
9 полное или в такое, для которого алфавит L достаточен:
7.5. Лемма. Если ? Z> Д х совместно, то
улное совиаотяое множество Формул ? Э ? (мощность
жрторогс. конечно, ограиичена мороятьюалфавита tl f ).
7.6. Дамма. Если ? О Ax.f оовмветно. тосущастдют:
а) язык и1 , алфавит которого подучается добавлением
f алфавиту It t множества новых констап мощностк
Чоциоств алфавита I/f ;
б) множестве формул ? в языке b * совместное,
содержащее ? и AXf (яопческие аксиомы li. );
и такое, что алфавит // достаточен для мегс.
Однако этн конструкции над ? мешают друг другу:
пополняя множестве € , для которого алфавит был достато-
достаточен, мы можем получить множество с недостаточным алфавитом,
а добавляя новые константы, мы увелячмвавм обвдй запас формул
в языке н тем наруваем полноту старых множеств. Поэтому кон-
конструкции 7.5. н 7.6. нужно по очереди провести счвтшов число
pas, чтобы в конце концов доказать последнюю лемму:
75

7.7. Лемма» Если ? "Э А*1 непротиворечиво, то
существует:
/ 1вФ)
а) язык W, , алфавит которого получается добавле-
добавлением к алфавиту l/-f множества новых констант мощности
алфавита С* %
б) мночество формул с в языке
полное, совместное, содержащее с и А1< и такое,
что алфавит uf достаточен для него.
После того, как лемма 7.7. будет доказана, теорема 7.1.
получттся из основной лешы, если применить ее к С' «
а затеи ограничить получившуюся модель на Ь^ и ? .
Приступим теперь к доказательству лемм. Основная лемма
будет доказана в п. 7.8, лемиы 7.4, 7.5 и 7.6 - пп. 7.9 -
7.IO, 7.II, 7.12 соответственно.
7.8. Доказательство основной леммы. Начнем с явного
построения интерпретации jfi языка Ц* , которая окажется
моделью для ?
а) Назовем постоянным термом такой терм в i/f »
который не содержит символов переменных. Полежим далее N =
"второй экземпляр" множества постоянных термов языка
= { t I f- - постоянные термы } ,
и определим первичные отображения интерпретации У .условиями:
r- С для любой константы С ;
/yiH любого символа операции /
ранга К и люоых постоянных
термов f,,..., +п
У(р) » воли и только если
Р(*1,-~, U) (гг.
для любого отношения Р ранга 1
и постоянных термов t^ ... t».
76

Докажем теперь следующее
б) Утверждение. Пусть Р - замкнутая формула. Имеем
р = I в том и только том случае, когда р (¦ ? .
(Отсюда уже будет следовать, что j - модель С .
В самом дрлр, еслиР ? С незамкнута, то ее замыкание
VXf. ~yV»KP выводимо из ? с помощью ?вл , и в силу пол-
полноты и непротиворечивости Z должно содержаться в ?
В силу утвеождения, *f{ V%^t...f Vx^f J?) = I,
откуда У { р) =1).
Доказательство .утверждения б). Проведем индукцию по
оо'щему числу кванторов и сеязок в формуле р .
6j) р - атомарная формула /?/ff, •••, t*i)
Утверждение следует из определения у /р) в списке
первичных отображений, потому что из замкнутости р
вытекает, что териы Tt* - псстояннь.
б2) p-Li Ш
Если У(р)~ i , то У(&)-0 и fl 4t по
индуктивному предположению для Q ; в силу полноты
 62 & € . т0 есть Р €¦ €
Если же У(Р)= О , то У>{ Q ) т 1 и О
откуда 1 Q. $ ? в силу непротиворечивости ?
Сьачала покажем, что если У(О) ^=О , но Р ? ?
j. „Tj 1тально, в этом случае ^(S^)^: 4 , VlQ^) "rr. q
. индукции fft fr f ffr ^Г ; ь силу лонпочы, 7 QL& ?
отология E^ -¦ ( -7 <S?2^~» -7 (Q _ ^)] и два ifl>
77

дают € h— ~Т( Q^ —~"вг) • Б СИЛ.У полноты, выео-
димые из € замкнутые формулы содержатся в С % значит,
-r( С, -»QX) г тР е- ? •так чт0 р $ ^ •
Теперь покажем, что если р <? ? , то У[ Р) — & •
Действительно, тогда в силу полноты 7Р'- 7 { ^t "~* Й*У С с .
Тавтологии  / fit —• йг) -¦ Sf и 7 Г б* -• йг) ~* 7бг
и МР дают Е hR^ ? /-7 6*2 ' откуда i силу
полноты Q* 6 ? ~7 Q, ? ? п° индуктивной^ пред-
предложению, ^ Q^j s i * У( &t) ^ ^ ' откуда
\) P'Qfl/Вг или Q^hQr. С помощью аксиом
B.It Б.2. этот случай сесдится к предыдущим, и мы опускаем
его разбор.
Если X не входит в Q СЕобсдно; то У(Р) — /
равносильно У(Я} "= ^ , то есть, по индуктивному
предположению, Ь? € С . Это включение, в свою очередь,
равносильно включению Ух (у € ? : в одну сторо-
сторону пс ?g/t , в другую - по аксиоме Д.З. с ir= 1С и МР.
Дальше 1Ш предполагаем поэтому, что X. входит в Q .
свободно.
Сначала предположим, что У[Р) ~ d , но Р ф ?.
и придем к противоречию.
Если Р f ? t то Т Р й ?. ,то есть
 VX Q.IX) G ? • Так как алфавит Ь достаточен
для ? ,2 ? содержитсн формула 7 V% 61 (х) —•
Применяя МР, получим ? h~lQ (Са) , откуда, в
78

силу непротиворечивости С , Q( Cfi) ф Z «По
индуктивному предположению, У ( Q ( Cq)) ~ о
( Q (Cq) замкнута!). Это означает, что ?(Р)A)
если y>CV(f) =• С~Л . в противоречие с
предложением ^ р) — jf •
Теперь предположим, что У(Р) ~ О , но Р €¦ €f
придем к противоречию.
Так как }/(Р)~ О , для некоторого ^ инеем
У (&¦)!$) ~ ^ • Найдем постоянный тери тб из
условия У(ХI$) ~-t~ ?(t) .Очевидно, X
не ограничивает Г в Й i ^ак что по лекме 4.8
откуда Q("t) у С. по индуктивному предположению,
и *7 Q(t) €~ ? в силу полноты.
С другой стороны, если Р 6 € , то есть
tfxQLx) е € , то по аксиоме Д.3.: VxQ(*)—
получаем € Ь— Q. ( X/ . дно противоречит совместности
? и результату предыдущего абзаца.
б' г — з л Ы. т этот случай сводится к предыдущему
с помощью аксиомы Д.2., и мы опускаем его разбор.
7.9. Доказательство леммы 7.5. Чтобы сложить множество?
с I
в полнее совместное множество с, , мы должны будем вос-
воспользоваться леммой Цорна (которая здесь будемт применяться
буз доказательства) и леммой о дедукции для языка 4f ,
которая будет доказана в следующем пункте.
Лемма Цсрна будет применятьоя к множеству
79

('множество множеств формул с , 1
СЕ -\ с I
с И непротиворечивыху >
которое упорядочено включением.
Проверка условий леммы Цориа. Пусть
такой подмножестЕО в С ?> » что для любых ei. В либо
? . С С а , либо С- С €j . Тогда объе-
динение ^ ь— принадлежит It . Действительно, иначе
С/ C^l было бы противоречиво. Существовал бы вывод противо-
противоречия из конечного числа формул. Пусть они содержатся в
? ? ?^'
есть множество, содержащее остальные К- i ; оно было бы
противоречиво, вопреки предположению.
Вывод из леммы Цориаг в множестве С ? сущест?ует
максимальный элемент, то есц> такое непротиворечивее мно-
множество i JZ? С , что если Q. а € , то
/ € г (&У противоречиво.
Я утверждаю, что с полно. Дейстгительно, предпо-
предположим, что Р замкнута, Р $ ? 7г 6 t и
' С
придем к противоречию. Из максимальности ?¦ следует, что
{€iP)h-R/{€,iP} н- R ,гДе R -
любая формула. По лемме с дедукции (см. п. 7.10), ?h~Р~+
f /~ 7 Р "-*Я • По аксиоме С5,: LP—*R) -* [(тр
Ц \ —» ^ ) . находим ? /- Л - это противоречит
совместности С .
7.10. Лемма о дедукции. Если ? Э /j X _ и формулу Р
замкнута, то из { ? Р] h~ & следует, что
80

Доказательство. Пусть К^ . • •/ "л — ос - вывод Q
из -(€. Р} • Проведем индукцию по Л . При Л* I
доказательство ничем не отличается от соответствующего дока-
доказательства в языке 1/о (см. п. 6.5 глаьы I).
Пусть Л:>2 и для выводов длины &. К-1 лемма
доказана. По определению вывода, (St/% либо принадлежит
? С / Pj , либо выводится из МР из Bt* SLj •
С ^ / ? Л-У . либо, наконец, имеет вид Кх 62У
для J А К— 1 ¦ Все случаи, кроме последнего, разби-
разбираются как в Ь9 , . Пусть &л ~ т% «у . Вывод
-¦ Ух (Stj ) из с тогда получается так:
Вывод Р-* Qj из с (индуктивное предположение);
\/ (Р*;) (*)
V* ( Р— Q./) -*(Р~* V*Qj) (акоиома Д.З,
применимая в
силу замкнутости Р );
р —» У* <?/ (МР к двум последним формулам).
7.II. Доказательство леммы 7.6. Чтобы построить язык Z»^
с достаточный алфавитом для непротиворечивого множества
формул Г , содержащего € и А *у , поступим самым
естественным образом.
а) Добавим к алфавиту языка Iff множество новых
констант той же мощности, что и алфавит hi . Получится
язык t/f .
б) Рассмотрим множество формул С U А X у в
языке 1/1 , где A ff - вселогические аксиомы языка
Оно непротиворечиво. Действительно, если бы оуществовал вывод
Противоречия из € (//\х} ? ^ , то следующая
8-1977 81

процедура превратили бы его в вывод противоречия из &
в Li^ : возьмем конечное шюхеотво всех новых констант,
входящих в формулы этого вывода, и заменим эти константы
старыми переменными (из 1/1 ), не входящими в формулы этого
вывода. Легко проверить, что вывод противоречия останется
выводом противоречия и будет проходить целиком в и1 «.
в) В € U А"Х 1 возьмем множество формул Р(х) ,
содержащих ровно одну свободную переменную. Для каждой такой
формулы Р выберем свою новую константу С~ , определим
формулу
ftp; nVx Pt*)-+~IHCP>
и положим окончательно
?"'•= € V А*1 L
Очевидно, осталось проверить только, что С непротиво-
непротиворечиво. Если бы из € выводилось противоречие, то оно
выводилось бы с участием конечного числа формул Rp ,
Поэтому достаточно проверить, что добавление одной формулы
Кр не может привести к противоречию, если Rp добавляется
к совместному множеству. Очевидным образом, меняя обозначения,
можно считать, что это совместное множество и есть С У A %i •
Предположим обратное: {CU A"*' Rp} противоречиво.
Тогда, в частности, { t*V A *f, Rp) h iRp м,
по лемме о дедукции, { С U А 7*} h Rp ""* ~!Rp . Тавто-
Тавтология [К -»  Rp) -~7 Rp иМР дают
{ei/A^i h-?Rp= I A Vx P(X)-* lP{Cp))
Тавтология 7 ( Р'-+ Q.) •*• Р иМР теперь дают
82

С другой стороны, Р(х) б € , значит, по
if /- V% PI*) . Сопоставляя это с последней фор-
формулой предыдущего абзаца, получаем противоречие.
7,12. Доказательство леммы 7.7. Пусть lli - язык,
С - множество формул в нем. Вложим ? в полное непро-
непротиворечивое множество ? , затем к [ ?tf ? ) приме-
примени лемму 7. Получившиеся язык и множество формул обозначим
¦врез U 1 Z . Положим, далее, по индукции
I, наконец,
Множество с непротиворечиво, жбо иначе вывод про-
¦иворечия получалсы бы "на конечном уровне", а все С
совместны. Оно полно, ибо каждая замкнутая формула Ct
I ft) .
¦вписывается в алфавите и. , для какого-то I ,
f li'+D с (С) , Гй
с содержит пополнение с в l/f
|аконец, алфавит L1 достаточен дли ? по тем же
Соображениям. Я
Этим заканчивается доказательство теоремы 7.1. Щ
Некоторый недостаток теоремы 7.1. оостоит в том, что
¦нтерпретация с строятся в искусственном множестве М %
¦остоящем из слов в специально сконструированном алфавите,
между тем для содержательного обсуждения, скажем, парадокса
фколеиа, интересно иметь модель, элеиентн которой являются
рбыкновениышмножествами, интерпретация ? - обыкновенным
ксношением включения и т.п.
83

Такую модель можно получить, если подходящая "естествен-
"естественная" модель большей мощности задана, "урезая" ее надлежащим
образом, как показывает следующая
7.13. Теорема. Пусть J? - некоторая интерпретация
языка Wf , во множестве М • Тогда существует подмножество
/V С Д/ , мощность которого не превосходит мощности
алфавита (j^ , и интерпретация У' языка l/t во
множестве /Ч , со следующими свойствами:
а) ограничение У на П совпадает с У ;
б) мнояество У - истинных формул языка ?/ сов-
падает с множеством Т - истинных формул.
Доказательство. Для каждой формулы "Р языка Lji и
каждого значения истинности *t — O У , которое У(jo)
принимает в точках /Ч , выберем по точке Т & М
Р
так, чтооы
Положим
Mo = множество, состоящее из У ( С) для
всех констант ? -, и У [%¦) ("f^ J
для всех переменных X , формул Р
___ и значении С
Далее, п,,гть П ^ ri - некоторое подмножество. Положим
П ~ М U (множество значений ?lf) C^ij- ••/ ^ji ),
когда j пробегает симеолы операций ранга Ц
Л <fi, '••/%.) - Л- ка
элементов из /V , Л любое).

¦конец, положим /VI
Мощность f4 , очевидно, не превосходит мощности (бесконечного)
алфавита /,j . Нетрудно убедиться, что существует интерпрета-
интерпретация if' языка /,/ , в /W' , являющаяся ограничением j
Действительно, не совсем очевидна разве лишь возможность интер-
интерпретировать термы, не выходя за пределы Д| , но это без труда
следует из того, что значения всех ^(fy на Ы\ х.,хЦ'
по конструкции принадлежат у\ .
Наконец, для каждой формулы Р множества значений
io ( П1 f 2 \ ? ^ I\J' V*)
истинности, применяемых j\v)K.\) при | = 1И
или при ^ tE W , одинаковы, ибо по конструкции f €i N
для всех Р Ь . Поэтому и множества $ -истинных и
If' -истинных формул совпадают.
8. Метаматематические свойства языков **1 .
" С/ know vfmt ^оч'хе ikn^-tA^ c&ovt"
" but it tin't JO,
Ю, ii тлГои^оС fee: but CU vt t
it can't. TW4 to^c"
jC Солгоб TktcuQh. the. ?ооЬ.п$
8.1. Как неоднократно указывалось, языки, в том числе
класса Д< , призваны формализованно описывать те или иные
части интуитивной математики. Этот параграф будет посвящен
обсуждению того, в какой мере зто описание можно считать
в -1977
85

адекватным, и выяснению принципиальных границ формализации на
материале парадокса Сколеиа.
8.2. Достаточность логических принципов, заложенных в
языки класса AW . Логические принципы - это логические
аксиомы Л$< , и правила вывода UP, (rtiv . Аргументом в
пользу их достаточности может служить теорема 6.1. о совпадении
содержательной истинности и выводимости (коль скоро мы убедимся,
что языки Li настолько богаты выразительными средствами,
что способны описывать значительные фрагменты математики).
Все же принятая нами система логики открыта для критики
со многих точек зрения.
Конструктивистская критика считает зту логику слишком
•щедрой: аксиома 71Р —* Р является для нее безусловно
неприемлемой, ео всяком случае, при интерпретации в (потенци-
(потенциально) бесконечных областях. Ряд других принятых нами споообов
рассуждений также лишены для нее смысла.
Возможны также точки зрения, связанные с отказом от
ограничения двузначностью истинноотнах функций. Среди многих
обсуждавшихся альтернатив автору представляются особенно
интересными две.
Одна будет описана ниже в связи с континуум-проблемой:
при вей значениями истинности служат элементы специальных
булевых алгебр, например, измеримые подмножества вероятностных
пространств (по модулю меры нуль).
Другая альтернатива подсказывается, например, языком
фрагмента квантовой механики в варианте Фейнмана (интеграла по
траекториям). Этот язык можно рассматривать как состоящий из
86

двух слоев. Высказываниям типа "электрон, испущенный в
ючке Л , прошел через щели I и 2 и попал в точку Ь "
сопоставляется "комплексное значение истинности" - амплитуда.
Правила перемножения и сложения амплитуд аналогичны правилам
вычисления функций истинности для конъюнкций или дизъюнкций
высказываний.
Здесь нет возможности обсуждать эту тему подробнее.
Автор склонен думать, однако, что для адэкватной трактовки
квантовой механики окажется необходимой перестройка логических
принципов, а не только совершенствование чисто вычислительных
средств традиционной математики.
8.3. Достаточность выразительных средств языкое Ki .
Анализ конкретных текстов, посвященных данной математичес-
математической дисциплине, обычно позволяет сконструировать язык класса
/^ , дающий возможность формально записывать основные аксиомы,
рассуждения и теоремы этой дисциплины. Как правило, зто не
является тривиальной задачей, и для проведения такого анализа
в каждом случае требуются значительные навыки. Общим принципом
анализа посвящена книга JZoisez У %>
Особенно детально исследованы языки теории множеств,
на базе которой имеется принципиальное построение всей интуи-
интуитивной математики. Мы остановимся подробно на одном из стан-
стандартных языков теории множеств ниже.
8.4. Непротиворечивость. Одним из основных мотивов для
создания теории языков было желание выделить такие типы рас-
рассуждений о множествах, которые заведомо не приьодят к противо-
87

речию. После этого сложилась парадоксальная ситуация, ибо
было установлено, что непротиворечивость, скажем, системы
аксиом теории множеств (и даже только арифметики), может быть
доказана только средствами интуитивной математики, оправдания
которых и хотели первоначально достичь.
По этому поводу можно заметить следующее.
Вопрос о непротиворечивости гообще не может ьсерьез
ставиться для интуитивной математики; противоречие в конкретной
рассуждении не способно распространиться на ьсе здание матема-
математики и ведет лишь к признанию ложности нескольких ближайших
посылок. Только в жестоко формализованной системе вывод Р
и ~] Р немедленно приводит к выводу любой формулы и тем
самым к разрушению этой системы; в интуитивной математике
этот механизм просто отсутствует.
С другой стороны, анализ противоречий, обнаруженных во
многих предложенных формальных системах, которым посвящались
целые книги, также обычно не приводят к полному крушению прин-
принципов i заложенных в эти системы. Как правило, оказываются
необходимыми лишь те или иные локальные изменения. Плодотьор-
ная идея полезна, даже если при ее разработке нарушались пра-
правила гигиены.
Можно думать, что вопрос о непротиворечивости средств
описания тесно связан с вопросом о полноте описания. Вероятно,
безнадежно пытаться предусмотреть заранее все те способы кон-
конструкции множеств, которые, с одной стороны, но ьедут к проти-
противоречию, а с другой - могут оказаться полезными в интуитивной
математике.
88

Ниже мы на конкретном разборе языка /Ci o?* и
аксиом Цермело-Френкеля для теории множеств попытаемся про-
прояснить соотношение между интуитивным и формальным описанием
и дать аргументы в пользу принципиальной неполноты последнего.
8.5. Язык Li ив* . Мы введем настолько богатый алфа-
алфавит, что несколько традиционных аксиом существования сразу
будут выглядеть как определения, каковыми они по существу и
являются в интуитивной математике.
Алфавит. Константа 0 (содержательно, "пустое множество").
Переменные %,у,2, U, V^ ... (счетное множество).
Отношения; € (ранга 2) , = (равенство,ранга 2).
Операции: { J ("образование пары" ранга 2), С/ (объединение
элементов, ранга I), Ни,- (множество подмножеств, ранга I).
Мы будем также считать заданной с самого начала некоторую
интерпретацию у> языка /С/ S&t в множестве N ,
Мы будем предполагать, что элементами N являются множества
и что У(ё) ~ включение,
У(=) - тождество.
Остальные свойства интерпретации будут вытекать из требования,
чтобы специальные аксиомы языка /.¦/ $&t были истинными. Ак-
Аксиомы будут вводиться по очереди и обсуждаться по следующему
плану:
A. Словесная интуитивная формулировка.
Б. Формула языка л. / Sot , отвечающая А.
B. Условие на М , накладываемое требованием, чтобы
формула Б. была истинной в интерпретации У .
8хх-1977
89

После бтого мы сравним А. и В., особенно в случае, когда
|У| - счетная модель (см. п. 7.18), чтобы разоораться в
парадоксе Сколема.
8.6. Аксиома объемности 6л. .
А. Множество однозначно определяется своими элементами.
В. У (&Х-) —L , если и только если всякое множество
из М однозначно определяется своим пересечением с М
Утверждение В. настолько важно, что мы подробно прогедем
его доказательство, хотя оно и очень простое.
Для любого Х^ М будем писать Xim = Л '' ^
Пусть сначала з (&Z) =1 и пусть Хы — 1Ы .
Покажем, что тогда X ~1 .
Выберем две разных переменных X , у и такую "точку" f
(см. п. 2.3), что У(Х)Ц)=Х , My)(V~Y .По
правилам вычисления функций истинности находим
потому что
при воех ^'
изменениях | по ]L , что в сбою очередь равносильно
условию Хм = 114 . Теперь, комбинируя это с условием
{ «получаем: уЦ
то есть У(*)(\) = У(рЦ) .или X =Y.
Наоборот, если из Хм -1н всегда следует, что Х- I ,
то, просматривая эти рассуждения в обратном порядке, получаем,
что
90

Ооиуждение. Различие между А. и В. разительно; если в IM
есть несчетное иыожестЕО л (см. ниже), а сама модель счетнс,
то Хм "гораздо меньше" X и, тем не менее, должно полностью
определять X •
Заиетим, что положение дел нельзя спасти, "заменив" все X
на соответствующие Хм .В самом деле, изменение даже одного
X ? М иеняет все множество М- и, таким образом, затраги-
затрагивает все остальные множества Ум .
Таким образом, "не уловимые" средствами языка элементы
из Х*~Хы тем не менее оказывают сильнейшее влияние на
математику модели, обеспечивая выполнение ее аксиом.
Несколько следующих аксиом являются по существу определе-
определениями константы и операций, и иы ограничимся самыми краткими
поясненияии.
8.7. Аксиома пустого множества п .
A. Пустое иножество не имеет элементов.
б. V? (Uyz°))
B. ^(N) -i , если и только если УЧЯ)П Ы пусто.
Иными словами, \f@) - " IM —пустое" множество, элементы
не из М в f @) вполне могут быть! Пусть У@) — 0 ;
Это множество определено однозначно в силу аксиомы &Z. .
8.8^ Аксиома пары У .
А. Для любых двух множеств 3t,^ существует множество
{ % i Н} • элементами которого являются р точности
б. ^ (*{
91

В. Бели X JS М , то в Ы есть множество [л, I j,
пересечение которого с М состоит только из Л и У ;
оно (как функция от X,Y) является интерпретацией
(Дальне мы будем писать ( XJ вмеото { 3?, %J ).
8.9. Аксиома объединения И .
А. Для любого множества X существует множество u W -
объединение sex элементов X , которые являются множествами.
б.
В. Упражняйтесь*
8.10. Акоиома степени (иди множества подмножеств) cw .
A. Для любого множеотва X существует множество Vur(X),
элементами которого являются вое подмножеотва X .
б. VxVj (^ePvrfx)^V5^63^2e^
B. Для любого множеотва X е W существует такое мно-
множество Р1ЛХ) в N t что PJ (Х)м состоит
из тех элементов Y € М , для которых Yn С JfM J p^
есть интерпретация Рцг .
Расхождение между А. и В., пожалуй, еще более сильно,
чем для аксиомы объеннооти!
11II. Аксиома бесконечности I.
А*. Существует бесконечное множество.
Здесь мы впервые сталкивается со случаем, когда перевод
интуитивной фориулировки на формальный язык существенно
неоднозначен. Принятое уточнение словесной формулировки
примерно таково:
92

A. Существует множество, которое содержит Р, tPj »
Iф]и({Ф}\ » и т.д. (индуктивно: вместе со вояким
элементом у оно содержит МAч, (и}}) ~у U{у}')
ь.1х (оех Л V^ (ye х — U Йу,^}3)е х))
B. Упражняйтесь.
8.12. Мы опускаем формулировку еще трех или четырех
акоиом, ибо характер "неформализуемости" виден уже сейчас.
Мораль.
Интуитивный смыол слова "все" не может быть полностью
передан языковыми средствами. Если заменить его словами "все
(объекты), которые можно описать средствами данного языка",
то синтаксически истинные (ложные) утверждения останутся син-
синтаксически истинными (ложными).
Ряд логиков делают отсюда вывод, что интуитивное понимание
слова "все" (скажем, в контексте "все подмножества натурального
ряда") вообще лишено смысла.
Для других мыслителей это означает только, что язык как
средство общения обладает принципиальными ограничениями.
Постольку математикам все же удается добиться взаимопо-
взаимопонимания (и даже объяснить друг другу смысл фраз типа "моя
интуиция в этом пункте отлична от Вашей"!), зто поднимает
интересный вопрос о внеязыковых каналах общения.
Если не верить в парапсихологию, оледует считать, что
общность "интуиции" объясняется общностью структуры головного
мозга у разных людей. Опытные вычислители знают, что при
работе сложных программ на ЭВМ (шахматная игра, распознавание
образов ...) создается ощущение, что у программы есть своя
93

неформализуемая "интуиция", понимание которой требует подчас
значительных усилий и которая может не совпадать с "интуицией"
автора программы.
Точно так же расхождение интуитивных представлений у
людей может обуславливаться индивидуальными физиологическими
особенностями. С большой остротой эту точку зрения выразил
Адамар: "Кто энаег, мое различие мнений с Лебегом об идеализме
и реализме - не обуславливается ли оно некоторой разностью осмо-
осмотического давления Рк, в тон или иной категории клеток моего
мозга и мозга Лебега?"
Таким образом, приятие или неприятие, скадем, принципа
исключенного третьего Брауэром или Гильбертом, доставляет
идеальную психологическую модель решения, которое не имеет
никаких внешних мотивировок, но сопровокдается чувством глу-
глубокой внутренней правоты. Возможно, этот эадект более распро-
распространен, чем принято думать, и играет значительную роль в тех
случаях, когда возможность подобрать внешние причины создает
иллюзию понимания источника разногласий.
§ 9. Структура формальной математики.
В этом параграфе собраны некоторые замечания о том,
как еыглядит математика, записанная, скажем, на языке JiS'et .
9.1. Перевод. Очень многие современные матемаалческие
тексты написаны но языке наивной теории мно осте; ослальные
легко поддаются мео j«j л& такой язык. Последующий перевод
на нормальный я^ык требует подгото_ительной работы, которую
мы здесь не проделали: формализация произведени i \ * Y ,

отображений как подмножеств в Xх I , теории кардиналов и
ординалов. Этот материал монно найти в стандартных курсах.
Еще один этап подготовительной работы - формализация
"определений" и обсуждение удобных средств расширения языка
(скажем, введения новых констант для обозначения объектов
типа % , для обозначения объектов, существование и
единственность которых мы доказали). Смотри по этому погоду
книги Мендельсона и Россера.
9.2. Потенциальная математика. Научившись вышеупомя-
вышеупомянутым приемам перевода, мы можем представлять себе, скажем,
формальную теорию топологический пространств следующим образом.
Присоединим к системе аксиом языка /., ?&1 (включая аксиому
выбора!), некоторое множество формул 'Гор [_Xi) ,
каждая со свободной переменной &? » Б содержательной интер-
интерпретации означающих " 3U - топологическое пространство".
Обозначим получившееся мнокество формул через Ь . Все
выводимые из 6 формулы отвечают теоремам формальной теории,
а выводы - доказательствам теорем. Наложение на топологию до-
дополнительных условий - хаусдорфовость, метризуемость, - равно-
равносильно присоединению новых формул к %
9.3. Реальная математика. Лишь небольшая часть теорем
формальной теории отвечает теоремам реальной математики, и
не только в том смысле, что число теорем последней в любой
данный момент конечно, тогда как число первых бесконечно. Мы
чувствуем, что подавляющее большинство формально выводимых
формул абсолютно неинтересно, и лишь ничтожная доля их пред-
представляет настоящие математические открытия.
95

Было бы любопытно попытаться найти какие-то характерис-
характеристика интересных формул. Одной не них могла бы быть малость
отношения "дина формулы": "длина ее кратчайшего вывода".
Действительно, многие замечательные факты имей короткую
формулировку и очень длинное доказательство. (Рекорд, воз-
возможно, принадлежит двум проблемам Бернсайда в теории конечных
групп). Другую характеристику подсказывает наблюдение, что
после установления некоторых важных результатов из них легко
получается целый спектр следствий, которые не были известны
раньше или получались лань с большим трудом. Это означает, что
после добавления такой формулы к % длины кратчайших выводов
других формул резко сокращаются.
Важно не забывать, однако, что отбор интересных фактов
происходит и на другом конце (то есть в начале) теории: в
выборе формул-определений, которые мы присоединяем к аксиомам,
чтобы начать делать выводы. Можно с уверенностью сказать, что
кристаллизация определений комплексного чнсла, группы, топо-
топологического пространства сыграла в математике большую роль,
чем тысячи теорем, даже тонких и трудных, но относящихся к
не столь существенным объектам.
Возможно ли найти какие-то формальные признаки "хороших
определений", или здесь отвлечение от семантики делает
задачу безнадежной?
96

ГЛАВА Ш
ПРОБЛЕМА КОНТИНУУМА
§ I. Постановка задачи. Нефорналышв объяснения.
1.1. Кантору принадлежат фундаментальные открытия в
теории бесконечных множеств: существование шкалы юс мощнос-
тей и неограниченность этой шкалы.
Напомним, что два множества называются равномонными,
если между ними существует взаимно однозначное соответствие.
Напомним, далее, что если даны два множества М л /v ,
то обязательно одно из них равномощно подмножеству другого,
а если зто так в обе стороны, то М и п равномощны.
Мощность /А// есть класс равномощных множеств, к
которому принадлежит М . Согласно сказанному, бесконечные
мощности упорядочены: для любых двух мз них IМ/ , /Ml
верно одно из неравенотв (Н/ ^ INI или //I// ? /Ml •
а если верны оба, то /А// —/А7 .
1.2. Теорема. (Кантор) - Мощности вполне упорядочены;
в частности» для каждой мощности сушеотвувт "непосредственно
следующая за ней большая" (то еоть такая, что строго промежу-
промежуточных мощностей не существует)» Щ
Принятые обозначения: J~\ о - первая бесконечная мощ-
мощность (счетных множеотв); jy. jy^ _ , - следующие за
вей, определяются также мощности с трансфинитными индексами,
на которых мы здесь не можем останавливаться. Это - "шкала
алефов".
97

1.3. Теорема. (Кантор) - Пуоть Р (М) - множеотво
всех подмножеств М . Тогда \Р(М)\ отрого больше I М(
Доказательство. Предположим, что это не так. Тогда
1Р(М)\ - iMl (ибс М вкладывается в Р{МУ- каж-
каждому элементу М сопоставляется подмножество, оостоящее
иг этого элемента). Значит, должно существовать отображение
f^i на все г ( М) . Пусть при атом отображение элементу
X С М ставится в соответотвие подмножеотво Их С Л/ •
Построим явно подмножество N , не входящее в ¦[ М
вопреки предположению. Положим:
M
Если предположить, что /V ^ {Ах для некоторого X
то противоречие получится при рассмотрении положения X
относительно //
* Л: ^ Л/зс =*• У е fr/ J противоречие. ¦
По аналогии с конечными мощностям!, принято писать
}P(M)I ~ 2fMI. Мощность 2 е = мощность множества
подмножеотв ГЖ = мощность множества вещественных чисел
называется континуумом.
Проблема континуума - это следующий вопрос:
!•*• Каково место коюинт»ма на икала адвфов?
Кантор высказал следующее предположение:
1.5. Гинотеза континуума (СН). 2.1"* = J^i
Все попытки доказать или опровергнуть его оказались
98

Везуспеинымм. Гедель и Коэя выяснили причину безуспешности,
ютановив ел едущие результаты:
1.6. Теорема, а) Отрицание СН не выводимо из остальных
аксиом теории множеств, если они непротиворечивы (Гадал ь).
б) СН не выводима из остальных аксиом теории множеств,
¦ели они непротиворечивы (Кози). Ш
Мы обсудим зти результаты в конце главы, а сейчас
Объясним идею доказательства теоремы Козна, ослабленная
иодель которого будет подробнее наложено в следующих пара-
параграфах. Это доказательство отличается ох первоначального и
принадлежит Д.Скотту и Р. Соловью.-
1.7. Можно сформулировать СН как следующее утверждение:
•Любое бесконечное подмножество вещественных чисел либо
вчетно, либо имеет мощность континуума". Соответственно, ма
Вудем излагать теорему Козна на языке вещественных чисел
[и функций, функционалов ...), а не теории множеств: дока-
доказательство становитоя тогда несколько нагляднее.
Идея Скотта и Соловья состоит в тон, чтобы построить
модель вещеотвенннх чисел: случайные
¦а очень больном вероятностном пространстве.
Точнее, пусть
I ¦ множество мощности строго больм! 2 * *
J2. = €О,ПТ о
мерой 1ебега;
ft. а множество олучайннх величин на i2 ,
то есть множеотво вещестмжжо-анач
измеримых фунжвнй на
99

Соловей и Скотт доказывают следующий результат (форму-
(формулировка которого будет значительно уточнена в следующих
параграфах).
1.8. Теорема, a) J9 $ существует
мощности, промежуточной между f^j и /^?/ ( то есть
СН в модем «i не "истинна".
б) Дня /R "истинны" все аксиомы теорир рэдествавных
и все следствия из них»
Следствие. СИ ке выводима из аксиом теорм вбмеотвеян"т
чисел.
1.9. Первоначальные обьяснения. а) Конечно, подмножество
в Я промежуточной мощнооти построить нетрудно. Пусть
^ с / - несчетное подмножество мощности, строго меиьжай.
чем /Г/ .
Для любого С € J определим случайную величину
X, : S2 -*•/?: Х-(Ш)- С -н координата си в С О, 1]Т.
Тогда множеотво \~Xjj.g~CZSl имеет промежутсчвую
мощность I'JI
мощность
б) При проверке аксиом IR для R , однако, щи
встречаемся с существенной трудностью: при "естественном
понимании" аховом больмяство m них перестает быть верным
или теряют смысл.
Рассмотрим следующий пример: в Я нет делителей нуля,
то есть если Ху ~ о , то либо Х^О % либо U — О
Это не так в JR. : вполне возможно, что невулевнв
X и у €Н имеют множества нулей, в объедине-
объединении дающие J2 , тогда X р ~ ° .
100

Верно, однако, следующее утверждение: "если Ху - Q ,
go при каждом испытании со е S2. с вероятностью I
¦бо Х(СО)-О .либо Ц{и?)-0 ".
Таким образом, возникает идея: по-новому определить
Лотиннооть утверждения об /Я (хо есть формулы соответ-
соответствующего формального языка) - как "истинность при каждом
юпыхании с вероятностью единица".
Замечательно, что эту идею удаетоя провести во воех
йеталя. Эта конструкция и составляет предмет последующего
¦вложения. Конечно, при таком новом иотолковании "истинности"
смысл большинства "истинных" утверждений меняется; в тон
числе меняется смысл СН, и наше наивное рассуждение о том,
¦очеиу СН ложна в этой модели, перестает быть применимый,
[ем не менее, его основной замысел сохраняется.
§ 2. Язык Lх H&UU- и его стандартная интерпретация.
2.1. Этот лараграф посвящен описанию конкретного языка
цорого порядка, ориентированного на теорию вещественных
рисел. На этом языке мы будем записывать гипотезу континуума
Щ и аксиом.
Нужно сразу же предупредить, что язык L~z RjwJl зна-
Птельно беднее языка теории множеств; поэтому невозможность
¦шести СН средствами этого яэыка, которую мы докажем, еще
цалека от интуитивного представления о '-недоказуемости СН".
Однако основные принципы нестандартной интерпретации и механизм
Нарушения СН при использовании этого языка становится очень
IOI

внвуклыш. Распространение этих конструкций на случай более
богатых явыков ( Ь аи &&О^ - явык "бесконечного" уров-
уровня, или лучие L; i&t ) уже не требует введения сущест-
существенно новых идей.
Серед чтением этого параграфа рекомендуется перечитать
§ I гжавы П.
2.2. Алфавит Lx RjKlM. . он состоит ив следуюцях
множеств символов:
а) Символы переменных ( Xt yt 2, .. ) j
символы (переменных) функций {f,J,A, У)
символы констант О) j, t
б) Символы операций i~, ' (ранга 2)
в) Символы отноиений = } ^ (ранга 2)
г) Связка, кванторы, скобка, запятые - те же, что в
языке /L± .
2.3. Синтаксис Li RjUxA .
а) Термы. Символы переменных У~, у, Z f . . ¦
констант Ot 1 суть термы.
Далее, если tt tf) tz - термы, / - функция,
то fit) , *ftZ/ t7 +tx -термы.
Все термы получаются так.
б) Атомарные Формулы. Атомарные формулы - это выражения
вида t1 — tx м tj^=.tx , где ~tb t± - любые термы.
в) Формулы. Атомарные формулы суть формулы. Если Q_ *Ф
Qt i Q.z ~ ФоР^лы. * - одна нз связок, то -1@.) (Qf)*-(C2)
формулы.
102

Если Q. - формула, X - переменная, / - функция,
то Vx(a)>Vf(Q),^X(Q)/ 3$(Q) -формулы. Все
формулы получаются так.
2.4. Читателю рекомендуется сомоотоятельно перенести
на случай языка L>z flea, с понятия овободного и связан-
связанного вхождения переменных (обратить внимание на переиенные
функции!).Аналогично переносятся: понятие "переменная ( X
или р- ) не ограничивает герм t в формуле г " (ем.
п. 1.6. главы П) и операция подстановки термов tf , tK
вместо свободных вхождений переменных %if Хл
в Р (см. п. 4.7 главы П).
Существует, однако, еще одна полезная операция подста-
подстановки; если Р - формула, / и О - оимволы функций,
то, эеписывая Р в виде P{f) • мы можем обозначить
черев г (О) ревультат подстановки О вместо воех
свободных вхождений р в Р . (Заметии, что оимволь
функций ие являются термами!). Если все эти вхождения Q
остаютоя овободными, то / не ограничивает О в г •
2.5. Стандартная интерпретация. Это интерпретация явнка
L ^ flaai в0 множестве К вещеотвенных чисел. Опишем ее
по тому же плану, который был принят в § 2 главы П.
А) Первичные отображения. Константы 0/ j_ интерпрети-
интерпретируются как вещественные О и I; + } - как сложение и
умножение, = , ^ - как равенотво и (нестрогое) неравенотво
соответственно.
5) Вторичные отображения. Здесь определение несжолько
усложняется, потому что нужно, кроие термов, интерпретировать
символы функций.
103

Пусть IH. - множество всех функций на К
с вещественными значениями. Роль множеохва П из § 2
главы П здесь будет играть множество
отображения множества символов переменных
. R
х
(отображения множества символов функций ?
в Яа) . ]
Таким образом, задание одной точки ?* G уСС опре-
определяет для каждой переменной X вещественное число Л ? ? R
я для каждой функции / вещественную функцию / ? 6 ft
(мы пишем здесь X вместо У("х) [^) , ибо интерпре-
интерпретация фиксированна, и незачем вводить ее символ).
Теперь мы можем продолжить описание отандартной интер-
интерпретации:
а) Термы. Пусть  - терм, ~f G ^// ; тогда
t * есть вещественное число, определяемое очевидной
индукцией (ср. § 2 главы П).
б) Атомарные Формулы. Если Р есть iif ^ t^ ,
то ее функция истинности jPI определяется как отображение
М - {0,1}
iPllf) -
( О иначе
Аналогичное определение для t~f — t^ .
в) Формулы. Действие отрицаний, свявок и кванторов
определяетоя точно так же, как в языках /Со JL1 .
104
I, если tf* ij в Я

Приведем типичный случаи:
IVfPHi)-
Г I, если 1РЦ1')-1
для всех f' , изменений
под / ;
О иначе
§ 3. Котаинззи-гилотева и аксиома выбора»
3.1. В этом параграфе мы вапиием на явыкв L/% R.CU ?
некоторые важные утверждения, которые встречаются в формули-
формулировке и исоледованми проблеш континуума. Вторая цель пара-
параграфа - повнакомиться с выравитедьныии возможностями языка
на не оовсен тривиальных примерах. Как в § 8 главы П, мы
начинаем со словесных формулировок.
3.2. А. " U - целое число"..
Переход к ваписи в Lz ReCi С не очевиден. Он
может быть оовериен в два нага:
А . пи можно получить, вычитая (иди прибавляя) I из (к)
О конечное число раз".
А . "Любая функция (j) с периодом I, обращающаяся в О
в нуле, равна О в У ".
б. V f (((f(°) = о Л Vx (f (х) = Н*+и)— Яу) =о)
Формулу Б. мы обозначим 7L ( U) .
3.3. А. Континуум-гипотеза: "любое подмножество в JR.
ибо равномощно IR. , либо счетно, либо конечно".
105

A . "Для множества нулей любой функции (п.) либо
существует функция ( О) , отображающая его на Я ,
либо существует функция (f) , отображающая целые числа
иа него".
б. VA (В/ Vy
A
Формулу Б. мы будем обозначать СН. Обратите внимание,
что формула ~2_ (X) входах в СН как единое целое.
3.4. А. Аксиома выбора: "Пусть Р (Х,у) такое
утверждение о названиях вещественных числах X, У , что
для воякого значения X оуществует значение J/ , делающее
это утверждение верным. Тогда оущеотвует такая функция / ,
"so r[X./ f(X)) тождественно верно".
Б. AC: VXfy Pfajf) -~3fVxP(*,
где Р - любая формула в L% R.e.di , / - функция,
U не ограничивает / в Р , и все переменные, кроне Л,
U связаны в Р .
§ 4. Нестандартная булева интерпретация t-'
основные понятия
4.1. Алгебра истиностнну значений. В этом параграфе
будут введены понятия, необходимые для точной формулировки
теоремы о невыводимости 18 § I, и укавана зта формулировка.
Пусть I - некоторое множество (индекоов); -Q."=/~??iJ
основное вероятноотное пространство с мерой Лебега.
106

Подопн
J3 а алгебра измеримых подмножеств в SL
¦о модули множеств меры О
(краткая аапйоь - mod О ).
Операцы в J9 мы будем обозначать U, >' и
ош индуцированы обычным объединением, пересечением и доиол-
неняем до -Q (измеримых) множеств.
Положим, далее
Ю а класс пустого подмножества 6 $3
f = класс SI e В
пусть а, в € Я i *" будвн тою* ая &t
если пП в ~(Х 1 кроме того, мы будем говорить иногда,
«о Я i в не пересекамоя, eon G. П О~ О
Пуот» {CL+ ) - некоторое семейство элементов 5.
мы будем говори», что элемент CL 6 $Ь является
вейте! гранью для {(Х^) % если О.л <~ OL
для воех Ы. н, кроме того, дня воякого О. с
таким же свойством (X Я. (X . Аналогично определяется
нижняя грань ( (Хы.) • По аналоги со случаен конечных
семейств мы будем писать
Верхняя грань ( (X*. J = U Л^
Нижняя грань ( B^) ~ Q &и
Мы сведем сейчао воедино основные свойства алгебры 3 ,
которые будут использоваться в дальнейнен:
4,2» Предложение. а) Алгебра jj является йодной, т.е»
веп*чяи н нижняя гг^нн счиествдют в ней для дюб"Т семейств
107

элементов. Кроне того, на бесконечные семейства расдространя-
ютоя слезши" е обычные свойства операций?
(П ал)и4 = П (аи i/S)
(ПсиI = иа'<
б) Алгебра JJ удовлетворяет условию счатности. то есть
любое множество попарно непересекающихся и отличных от О
элементов $ не более чем счетно»
Заметим, что именно факторизация по множествам меры О
обеспечивает выполнение этих свойств. В алгебре воех измеримых
подмножеств -Q. верхняя грань семейства может не существовать
или не совпадать с объединением членов семейства (пример:
семейство точек неизмеримого множества).
Условие счетности легко следует из существования положи-
положительной меры на Я : принимающей значение ^ I. "Сумма
нечетного множества" ненулевых вещественных чисел (мер элемен-
элементов С ) не может быть конечной.
Теперь мы можем точно оформулировать основной результат
этой главы:
4.3. Теорема. Для любого множества индексов У оущест-
вувт отображение
{ вашшутые формулы L± R.eui } -*¦ Я - Я G): Р —'
("булева функция истинности") которое обладает следующими
свойствами:
106

а) Есля Р - аксиома Lz Reat , то /iPH - Л
б) Если Р непосредственно следует И8 (Q<) по прави-
правилам вывода в Lidea? и если UQ.cU- Л
для всех С , то ЦР11 =й
в) //?////.= Ю при условии, что множество J
достаточно велико, а именно /У/ > 2 . Ш
Следствие. СН невыводима из аксиом в JU2 R.BCI С
4.4. Замечания, а) Высказывание // Pll - Д является
точной формулировкой понятия об "истиннооти" Р в § I.
б) Теорема 4.3. будет доказана в последующих параграфах.
Порядок изложения следующий: в § 5 мы явно определим 1РЦ
для любой (замкнутой) формулы Р \ в § 6 проверим, что
ЦСНП - Ю для больших.^ ; в § 7 опишем аксиомы языка
/, Head и проверим их "истинность" в нетривиальных случаях.
§ 5. Конструкция булевой интерпретации JL?. i^-QQ С
5.1. мы сохраняем вое обозначения § 4. Следующее изложение
параллельно п. 2.5 этой главы; рекомендуется все время срав-
сравнивать булеву интерпретацию со стандартной.
Is 2 /Zea ? будет интерпретироваться во множестве
fR_ = случайные величины на -Q ж измеримые
вецеотвенноэначные функции на _Q .
А) Первичные отображения. Константы 0,1 интерпретируются
как поотоянные функции на Л со значениями 0,1J + a •
(как^оточечное) сложение и умножений функций; = и ^
(как поточечное) сравнение функций на равенство или неравенство.
109

юсу
Б) Вторичные отображения. Прежде всего, введем аналог 1/\
множеотва функций /R. . __
5.2. Определение. Отображение /j_ ^ ~~ ^ принад-
принадлежит множеству "случайных функций" /Rll) . если и только
если для любых К, у € IR. имеем
{ множество Ш е Л I *ш -Уш } mod О с
с {множесгво CO€Jll /(*)„, ~ ftyuu }
Это определение наотолько важно, что мы прокомментируем
его немедленно.
Пусть X - функция на Si ; тогда для U) ? Si.
значение Х'^ в точке CV - зто "значение олучайной ведШ*
чины X при испытании СО ".
Если в определении / из IR исключить уоловия
file*с/О , то новое требование будет обозначать просто, что
значение случайной величины J- ( F) при каждом испытании
должно однозначно определяться значением аргумента Х~ при
этом испытании. Добавление mod О равносильно требованию,
чтобы предыдущее условие выполнялось "с уоловной вероятность»
единица" (при условии ^~У ).
Это - очень естественное ограничение на / , если мы
хотим сохранить интуитивные свойства вещественных чисел в
напей нестандартной интерпретации. 6 оамом деле, обыкновен-
обыкновенные вещественные функции определяются своими значениями в
точках, а наши "функции" обладают аналогичный свойством при
НО

5.3. Теперь мы введен аналог множества JX ю 2.3.Б):
JJ[ — | отображения множества символов переменных в Я }*
л /отображения множества символов функций в ЯlV }
Иными словами, задание одной точки J € yU опреде-
ляет для каждой переменной X ад:,ча,-йуь зддичь'» л €-^
и для каждой функции f случайную сЬункшио / ^ в ^
Продолжая описание интерпретации, рассмотрим, наконец,
термы и формулы.
а) Теомн. Пусть t - терм, /1 JX ; тогда t*6jQ
есть случайная величина, определяемая индуктивным
процессом.
б) Атомарные Формулы. Если Р есть tf ^ tz , so
истинностное значение Р в точке -f 6 >/Л определяетоя
как следующий элемент алгебры J3 на § 4:
//tf ±
Аналогично для tt —~tx (Обратите внимание, что если
фиксированы f €¦ М-, VO 6 S1 и терм t , то t ^
обыкновенное вещественное число, "значение терма t в
точке f при мспытавп Ш ".В дальнейшем мы будем
либерально пользоваться обозначением // // в таких, напри-
например, контекстах:
в) Формулы. Если истнвостнне значения формул Pf Q. во
всех точках f 6 М. ?жв определены, мы полагаем (опуская
всюду аргумент f для краткости):
III

|ПР// = IIP'/I
tlp л аи
llP-QH
^QH~-(llPHПHUli)U(HPIi'n
Наконец,
ll\/x P(x)llli) = nt IIPlKf)
(no всем J1 изменениям f no X )
иИР//(/) (потеиже f )
(Аналогичное определение применяется к квантораи по функциям),
5.4. На этом завернается построение булевой функции ио-
тиыыости. Ниже будет проверено, что она обладает всеми свой-
свойствами, описанными в теореме 4.3. Кы рекомендуем, однако,
читателю еще раз продумать все этапы конструкции /IP//
и убедитьоя в том, что
а) Есля Р замкнута, то ПРИ не зависят от f й М.
(повторить рассуждения пп. 4.1 - 4.3 главы П с новой функцяей
истинноотн).
б) Свойство //г/1 — Л адзквагао передает представление
о том, что п Р с вероятностью I истинна при каждой испы-
испытании s обычном смысле слога" (ор. комментарии к определению
112

В заключение этого параграфа обсудии правила вывода.
Они по существу te же, что в языках /,у
5.5. Правила вывода сохраняют "истинность".
a) «IP: пусть // РЦ - Иf IIР •— Q Ц ~ i . Согласно
первому условию, IIРII - О , в силу второго
HPU'UIQII = 4 , откуда HQH= i
6)v?/l (по переменный): пусть KP// — JJ . Это
вначит, что НРЦ($)-? для всех I* ?
но тогда
( у пробегает изменения J по К ).
в) Gd/i (по функцияи): vj Р следует ив Р -
проверяетоя точно так же. Ш
§ 6. Континуум-гипотеза "ложна".
В атом параграфе мы докахеи утверждение в) теоремы 4.3:
6.1. Предложение. Если ///?¦ Т*° , то ЦСН11 = О
Доказательство. Напомним сначала вид СН (см. пп. 3.2 и 3.3).
СИ. tfAlty Vy 3
Определим Pj и Рг как первую и вторую альтернативы в
этой формуле СН есть V к ( R1 V PA) .мы хотим
доказать, что для любой данной точки f Q jj^ имеем
ИЗ

// Vl i P?VPi) II i f) = (D .По конструкции в § 5
= П I
где 5" пробегает все изиенеяия "f по Л « Чтобы прове-
проверить, что это значение равно Ф , достаточно найти одну
такую точку /' , в которой ИР^Ц') = ЦРг /I (f) - Q.
Поскольку в Р1 и Рг все переиенные, кроне А. , овязаны,
отыскание J' равносильно выбору / & /Ц
Укажем нскоиое значение д = / явно
6.2. Определение, а) фнксируеи подмножество У С I
мощности, строго промежуточной между мощностямиуМ. и /"У/
(например, 2^о ). Обозначим через JTt 6 /К
функцию "'t -я координата" как в § I.
б) Для каждой случайной величины X 6 Щ выберем
такое подмножество SI ( х) » 4t0
U ЦХ~ = У/ И =_Q [x)/ruxt О
(Здесь существенно используется предложение 4.2 а).
в) Для каждой К t/R. л Со 6-Г2 положим окончательно:
Т(?) |°» еса ш е-О. (^)J
00 I I иначе
6.3. Утверждение о корректности, а) Л (X) как
функция от СО (при фиксированном К ) измерима, так что
Л отображает (И в IR .
II*

б) Для каждого X ? /К имеем:
III (Ю-oil-U //?=*/*
в) / 6 /^ '** _ , так что существу» f '
для которой ^ ~ л ^
Доказательство, а) Л (х ) принимает на -Q-
воего два значения 0.1 и множества уровня этих авачешй жзмв-
ршш по определению и свойству полноты J] .
б) Очевидно из определения* _
в) мы должны проверить для / овойство, фигурирующее
в определении 5.2. Пусть X U e IH * Покажем, что
множеотво точек о» 6iJ. • для которых одновременно
xL-y*, и / b
имеет иеру нуль. __ _^
Достаточно разобрать случай л G)^ — 0, А(ц)ш~1
иными словами, установить, что
Их =///0llllx)=ollПИМу)=Щ- О
Запишем второй оомножитель в виде U //Х-х/" (см. в) )
и применим к нему и первому сомножителю правило дистрибутив-
дистрибутивности. Учтеи еще, что Цх~~=ЦЦО JlJT—X. // с IIU~X~yll
Тогда получим
откуда и следует требуемое.
115 .

6.3. Пояснения. Выбор ? -существенное место докааатель-
отва.и мы хотим его мотивировать.
Напомним, что А - зто название той функции, мощность
множества яулей. который в /R _мн хотим вычислить (в стан-
стандартной интерпретации) . Выбор А для "опровержения" СН _
осуществляется так, чтобы в множество "почти всюду нулей" А
входило "множество промежуточной мощности" в наивном смысле:
все у- j' е J (ср. §1). Однако, а не
иожет быть какой угодно функцией - на нее наложено сильное
араничеиие л 6 Щ , поэтоиу виесте со всеми X/
7 *
во множество п.в. нулей А иожет оказаться неизбежным вклю-
включить и еще какие-то у t /R , а также "частич-
"частично включить" какие-то 2 6 /R 1 (Последнее выражение
есть попытка передать возможность того, что /I/B)—Oll
есть не Ю и не ? , так что 2 является яулем /
с "нвнулегой вероятностью"). _
Таким образои "множество нулей" / может оказаться
больше, чей мы ожидали, так что естественно ожидать затруд-
затруднений г доказательстве того, что его нельзя отобразить на
все /^ (альтернатива Р1 ). Казалось бы, зто обстоятель-
обстоятельство облегчит опровержение альтернативы Рг ( 2 нельзя
отобразить на множество нудей), но и это неверно! Дальне мы
обнаружим, что // 2f^)l/~ 'Л для многих 7 , ие
являющихся постоянными функциями с целыми значениями, а также'
ll2(x)(/:f0 еще для каких-то X , так что "множество
целых чисел" в наией интерпретации также резко возросло.
116

Последнее замечание: в нашей обсуждении по существу
возникло понятие "случайного множества", которое и является
основнш в аналогичной нестандартной интерпретации языка
|_j. S*? i позволяющей доказать невыводимость СН в
оамом сильном смысле. "Множестве нудей *о " является слу-
случайный в sou смысле, что отношение " Z fc нули V> "
получает булево значение истинности \\ v> C"%") = О \\
6Л. Доказатедьотво. toPL\\C|')-€
Согласно правилам вычисления . \\Р \\ находки
( h определена в п. 6.2, О пробегает все элементы
R(!> ж,й ' все элементы /R ). Мы предположим,
H
410 HPilKE'^ О и придем к противоречию.
Если У<И$.)*О , *о (ХЩ)*-®
цля какой-то конкретной случайной функции 5 <=, Ш<г?
Выберем ее и положим
Кдесь U появилось, как замена llh(x)-O/l
силу 6.3 в). Далее, IIK-xjnnila=a.(K)ll^llU ^(^
¦ользуясь этим и дистрибутивностью, находим
асп и п^д-а+п
i /V
117

В частности, для каждого *ь вместо
4*}
Если, как мы предположили, QttD » *° Для каждого I
найдется /СО6 X такой, что
Поскольку I несчетно и И| </J| * есть такое
значение J.o?^ t4*0 }a 'i(-c) для всех /
из несчетного подмножества Ioa I • Это, однако,
противоречит предложению 4.2 б, потому что члены семейства
jf Ml fiGXo) попарно не пересека-
ются. В саиом деле,
еолн ^^ 1г
Обратите внимание, в какой мере это рассуждение парал-
параллельно "наивному" из § I. Функция Я* , предположительно,
отображает нули h на IR. "с ненулевой вероятностью".
Но точный смысл вычислений гораздо тоньше.
Вычисление \\Z(u))\ . Формула Z(u) написана
в п. 3.2 Б. Так как она входит в Рг , вычисление nZ(u)ll
необходимо для вычисления ||рг/|
6.5. Лемма. Пусть реМ, U2=y?/R . Тогда
j - классJ
118

(В чаояюстм, Вг(^.)|Ц^ = 4 , если U только "кусочно
целая").
Доказательство. Ны должны установить, что
J X
Проверш по очереди включение в обе стороны.
Включение с. . Достаточно найти конкретную функцию J ,
для которой соответствующий член слева содержался бн в нравом
члене.
Определим J , положив
(вместо sin гТ. можно было бы веять любую измеримую
функцию /R -»й? с периодом I и равную 0 только в целых
точках). Легко видеть, что J(jc)?fR и Je/Rca>
Тогда II>Co.uo||'=© и
Поэтому нужно лниь проверить, что
что очевидно*
Включение э • Достаточно проверить, что для любых
фиксированных значений л CZ, I ё JR. ^ д E.IR
имеем
119

Но включение О & 8 U С равносильно О Л с с
далее в наней ситуации
'п?* пили J ' '
ибо ii?;"iUH:k<p^J-Or)|| ( Л нод знаком >
постоянная функция на Я. со значенном ft )•
Поэтоиу достаточно убедиться, что
\\i-<.h)^o\\'±\\Ho)--o\\'u(u 1\к*)--ш-щ и')
х
или, переходя к дополнениям, что
о||0( Л ^
Ун линь увеличим правую часть, если оставим в ней только
члены, отвечающие х = о, I, 2, ... -I* Но пересечете
атих членов, очевидно, равно
6.6. Доказательство [| Рг)| ( \') - <О
Соглаоно правилам вычислении 11 Р^|| с учетом леммы 6.5
находим:
И
Как вине, f|x=nll c||f(jc)-j-fn))l так что
120

Далее, достаточно доказать, что член, отвечающий любому
конкретному значению J равен ф . Допустим, что зто не
так, и придем к противоречию. Пусть Q ¦* $ член,
отвечающий j- .По оказанному,
В частнооти, для каждого j.
(с х вмеото G ):
G
мы должны иметь
(учесть, что IlhCx" ) = с|| =Ф
о
хвния 6.3 б). Значит, для каждого
число п(р такое, что
И/Г ~~
в силу предло-
должно найтись целое
Так как
ЖвОТВО
несчетно, существует Ло и несчетное подмно-
^ОС Ч. ТаКИХ I , ЧТО Лб) =А2„
для всех LG %о • Тогда
образуют несчетное множество ненулевых попарно не пересекаю-
пересекающихся элементов fy , как а конце п. 6.4, что нарушает
условие счетности для j^>
8-1977
121

§ 7. Аксиомы L,
7.1. Логические аксиомы. Они разбиваются на две группы:
а) Аксиомы А Ко : результаты подстановок в тавтологии
любых формул L2 Reat
б) Аксиома A»i. ; результаты подстановок в ф-рмулы
Д.1 - Д.З иэ п. 5.2 главы П любых формул языка [,_. />Va? .
Кроме того, сюда оледует включить следующий вариант формулы Д.З
"второго порядка".
где j-,0. - символы функций.
7.2. Специальные аксиомы теории мвожес!
в) Аксиомы равенства:
г) А-гиомы выбора АС
^4-Су))
где Р - любая формула, ие имеющая свободных переменных,
кроме X и (/ , и U не ограничивает J- в Р .
7.3. Специальные аксиомы теории додай (для краткости
мы опускаем кванторы общности),
д) Аксиомы сложения:
122

e) Аксиомы умножения:
X-L-X
ж) Связь сложения с умножением:
в) Аксиомы порядка
t^ Л
yz ^
е) Аксиомы полноты СО :
А. Любое,ограниченное свврзу множество в Ik вначвия
функции } имеет верхнюю грань (z)
Б.
123

7.4. Замечания о стандартной интерпретации аксиом.
Смысл воех аксиом в стандартной интепретапни ясен; может
быть стоит сделать лишь следующие замечания.
В интуитивном понимании для аксиом группы д) подмоделью
может служить множество целых чисел <- (или только О,
или любая аддитивная подгруппа >* / ). Введение группы е)
заотавляет дополнить зту подгруппу до подполн R , содержа-
содержащего 0 и I поэтому вое рациональные числа Q . Аксиомы х)
и а) выполняются в этой модели ароматически.
Аксиомы полноты е) в инт.уити ном понимании заотавляют
добавить к подмодели все предельные точм и поэтому включить
в нее все (? (ибо любое вещественное чи >ло есть верхняя
грань некоторого множества рациональных 4исел).
Однако, со ласно теореме 7.13 главы П, L^Peaf
всегда есть счетная подмодель (если алфавит счетен), ибо
по существу множество мех ограниченных подмножеств в R
и их верхних граней, которые можно описать формулами языка,
счетно, и смысл слова "see" меняется - уже знакомый нам
эффакт.
7.5. Проверка аксиом в булевой модели. Проверить аксиому Р
в булевой иодели - значит показать, что IIРII - И
Аксиомы Ахо проверяются стандартными вычислеяяшш.
Аксиомы А л ,? проверяются по тому же плану, по которому
вычислялись их обычные функции истинности в § 4 главы П.
Первая аксиома равенства трквиажыо; вторан проверяется
сначала для атомарных формул Р и затем проводитси индукции
124

по числу связок и кванторов в R . Расоуждения довольно
кропотливые, но простые. Аксиомы полей д) - з) проверяются
без воякого труда.
Ограничимся одним прииером:
Чтобы проверить, что его значение равно % достаточно про-
проверить, что при любом фиксированном X6R найдетоя
такое
Подходящее значение 4 легно построить явно: положим
( X~J) » если ^uj^0
I О , если Ktj-o
Аксиомы выбора АС и полноты СО требуют отдельного
обсуждения, ибо их проверка не тривиальна.
§ 8. Аксиома выбора "истинна".
В этом параграфе мы докажем
8.1. Предложение НАСЦ=-:й
Доказательство. Начнем с того, что, воспользовавшись
"наивной" акоиомой выбора, вполне упорядочим IR отношением
JT<i7 (не путать о UU ; зти отношения никак не
8*-1877 J25

Как обычно, такой
Фиксируем точку ?
связаны). Напомним, что полная упорядоченность влечет сущест-
существование наименьшего элемента в каждом подмножестве). Идея до-
доказательства - построить / так, чтобы ±(х) был наимень-
наименьшим 18 элементов у , удовлетворяющих P^jJ)
придетон "склеивать и8 кусочков".
и будем проверять равенство
начнем с исследования первой части ком-
позиции
, а (при фиксиро-»-
по и .
следующим образом?
пробегает изменения ? по Л
g ) 6 пробегает изменения h
где
ваннон
При фиксированной
и
упорядочим 6
Положим, далее:
4 4 К<Л *oJ
12)
Следующая лемма доказывается бее труда индукцно!:
8.2. Лемма. a). U a^ U ё6
(Здеоь
б) ^Л^4 = Ф .если
фиксировано, а А пробегает изменения
по
Заметим теперь, что прм фиксированном Р точка
виолно определяется значениями х -X и и -
и. ).
126

Будвы писать &\м вместо &д
8.3* Дшма. Фиксируем К (то есть g ) ¦ заставим
пробегать всевозможные значвшя и е Я? . Mono! найти
такой момент x'&R , гависяинй от х «что
Д1Я ВСвХ 0, , ^- -С /JX'=<J И
Доказательство. Согласно лемме 8.2
Из условии счетности (предложение 4.2 б) следует, что можно
найти подмножества В^ - <=¦ Q • из которых только,
счетные множества 6y*ji непустыми, со свойствами
Теперь определим i ' условиями:
xir*yur дня всех с*ге
Проверка того, что x'gW. и что &, _ - flx'= 5 JJ
тривмальна>
Интуитивно, х' на 5?п еоть наимевьо! П ,
удовлетворявший Р .
8.4. Лемма. Отображение J: IR~*IR » определенное
формулой ?'
127

где Х/ определяется CD к , как в лемме 8.3, принадлежи*
Доказательство опущено. В вен используется "истинность"
второй аксиомы равенства.
8.5. Теперь вернемоя к нашей основной цели. Мы хотим до-
доказать, что ПАСИ (?) - й. ,ю есть что
Левая часть равна, по вышесказанному, Ох «и >
а правая часть равна »
г у
где 1 ' пробегает изменения V по jr , а §?
изменения f ' по X . Для проверки включкния Л 0 ^ L/ Л
* ? Т'5"
достаточно проверить, что член слева, отвечающий данному зна-
значению х , содержится в члене справа, отвечающем точке '§" ,
для которой f^-j- ( F H8 леммы 8.4), дс^'=У ,
то есть что С _ &Xq&UP(x,J-(.iv)HC$») , если
i5^j x •=? .Это следует из того, чю
потому чтс
по аксиоме равенства.
128

§ 9. Аксиома полноты "иотинна".
9.I-. Предложение.
Доказательство. Мы должны установить» что для каждой
и п
<7 х " 2 и 7 ¦¦ ' " \ч
где мы положили Q *-* ?>=z(an&)U(Q Л В') . Достаточно
раосмотреть член слева с фиксированным о.
Для каждого рационального числа qeQ положим
Очевидно, и & R . Положим, далее
9.2. Лемма, a) U 6Q = /) /f J"OrJ iU ||
б) Л 6 =(D в) L^ П &i_
Доказательство, а) Включение С. очевидно. Включение 2
проверяется с поиощью
которое s свою очередь можно проверять "поточечно", ибо Q счетно.
129

б) следует «з того, >«о 1^ е II ± (б) & ^ <jji ? И 4 <°J
м "поточечного" соотношения П||^оLо || -<D
Наконец, в) проверяется аналогично.
9.3. Лемма. Можно выбрать 5О С
ж
так, чтобы
Доказательство. Сначала выберем любые В
классах
.
, затеи полоши
при
наконец, положим
?
9.4. Лемма. Определим Z '
так:
Тогда ZG/% ш 6t?1t
9.5. Мы хотим теперь вернуться к доказательству llo^"|l= -С.
Согласно (I) достаточно проверить, что
130

где ? определяется по п как в лемме 9.4. По лемме
9.2 а) 9Ю равносильно включению (для всех О )
u в*^иг <u и)
Чтобы окончить доказательство, нужно еще воспользо-
воспользоваться нетрудным рвенством
Дальнейшие детали мы опускаем.
§ 10. Обсуждение.
В связи с теоремаш Геделя и Козна о континуум-проблеме
два круга вопросов заслуживают обсукдеяия: смысл результатов
ж смысл методов.
10.1. Результаты. Существует точка зрения, согласно кото-
роя несчетные (и дахе счетно-бесконечные) множества являются
фм«цчцшт Став на такую точку зрения, мы, конечно, не иожем
рассматривать и проблему континуума.
С точка зрения последовательного формализма невыводимое»
СН и 1 СЯ означает возможность добавления любой из этих
формул (или утверждения о точном месте континуума на шале
алефов) к системе акоиом и исследования получившееся разветв-
разветвлений теории множеств на равных основаниях с другими вариантами.
131

Наконец, многие практически работающие математики чувст-
чувствуют, что континуум-проблема имеет смысл и однозначное реив-
нив. Тогда, очевидно, Гедель и Козн показали глубокую недоста-
недостаточность наших представлений о континууме: либо ин противо-
противоречивы, либо неполны в столь важном пункта.
Как развить интуицию до такой степени, чтобы положение два
с континуум-проблемой прояснилось?
Возможно, некоторые указания на это содержатои в методах
Геделя и Коэыа.
10.2. Методы. В среде специалистов по математической логике
наблюдалась сильная тенденция испольаовать для доказательства
непротиворечивости и независимости "как можно более синтакси-
синтаксические" методы. В частности, метод булевых моделей возник в
результате реинтерпретации "вынуждения" Коана, в котором роль
модели гораздо скромнее и мнее связана с другими областями
математики.
Конструкция модели по Скотту-Соловью очень красива и аппе-
лирует к привычному кругу понятий, но в какой мере она является
существенной?
Технически - ни в какой. Алгебра ЛЬ не обязана возникать
из вероятностного пространства; в конструкции не обязаны участ-
участвовать "настоящие" несчетные множества - все можно делать в
счетной подмодели, согласно Левенгейму-Скодему.
Автору представляется, однако, что введение вероятностных
идей в самые основания математики является очень существенным.
Вот немногие аргументы в пользу зтой точки зрения.
132

10.3. Фантазии. Обычная критика теории множеств исходит
из утверждения, что положения (и трудности) теории множеств
возникают при перенасевии на бесконечное опыта обращения с
конечным.
Мне кажется более важным то обстоятельство, что теория
множеств абстрагирует опыт обращения с макрообъектами, кото-
которые существуют отделенно друг от друга, различимы и т.п., а
также с макропроцессами, которые - в идеале классической
физики - детерминированы и финитно описываемы.
Теория вещественного континуума, однако, мокет оказаться
глубоко связанной с теорией микромира, где нет ни безграничной
делимости, ни возможности жестко фиксировать положение, ни
детерминированности.
Аксиомы теории множеств, абстрагированные от представле-
представлений о "множестве фотонов в ящике" или "множестве электронов
в атоме", могут оказаться совершенно не похожими на привычные
аксиомы Цермело-Френкеля. Обсуждение аксиомы выбора или поня-
понятия взаимно-однозначного соответствия с подобной точки зрения
могло бы пролить новый свет на эти тякелые проблемы и обнаружить
любопытный "физический смысл" методов Геделя, Скотта и Соловья.

llui ->01273 I 77302 t,> 60x90 16.
Фи ii E,0. \ i i j 4.
> 1977. ! 'Г'* 500. Uphi 16
Ixi ( я II ат \ I '