<< Пред. стр.

стр. 9
(общее количество: 9)

ОГЛАВЛЕНИЕ

провести по следующей схеме.
Доказательство теоремы 9.3:
Обозначим через ?? точную верхнюю грань множества тех ординалов ?, которые
имеют строго меньший порядковый тип, чем Y , т.е.

?? := sup {? : ? Y }.

Из определения ?? следует ?? +1 Y , где формула ? ? означает, что либо ?
?, либо ? ? ?, поскольку иначе выполнялось бы ?? + 1 Y , что противоречило
бы определению ?? . Но выражение

Y ?? + 1

означает, что Y изоморфен некоторому начальному отрезку ?? + 1 (который, по
свойству (iii), является ординалом), или самому ?? +1. Единственность ординала
? следует из свойства (iv).



Упражнение 9.5 Докажите, что любое вполне упорядоченное множество изоморф-
но единственному начальному отрезку [0, ?) в классе всех ординалов (образованному
всеми ординалами, меньшими ?).


Упражнение 9.6 Докажите, что в предположении непротиворечивости системы
аксиом Цермело-Френкеля ZF не существует множества всех ординалов. Данное
утверждение известно под названием парадокса Бурали-Форти.


Теперь введем следующее определение.

Определение 9.8 Ординал ? будем называть непосредственно следующим за
ординалом ? и писать ? = ? + 1, если ? = ? ? {?}. Предельным ординалом бу-
дем называть ординал, который не следует непосредственно ни за каким орди-
налом.

Формула
Limord(x) := Ord(y) ? ¬?y(Ord(x) ? x = y + 1),
где x = y + 1 := x = y ? {y}, “говорит” о том, что x – предельный ординал. Оче-
видно, что 0 является предельным ординалом, а каждый конечный ординал k,
где k ? N, отличный от 0, непосредственно следует за ординалом k ? 1.
9.5 Ординалы и стандартная модель арифметики 77


Определение 9.9 Минимальным бесконечным ординалом (или первым счет-
ным ординалом) называется предельный ординал ?0 , которому не предшеству-
ет никакой предельный ординал, кроме ?.

Таким образом, формула

x = ?0 := ¬x = 0 ? (Limord(x) ? ?y(y ? x > ¬Limord(x)))

“говорит” о том, что ?0 является первым счетным ординалом.
С учетом введенных обозначений можно записать свойство конечности ординала
следующей формулой:

F in(x) := ?y(y = ?0 ? x ? y).

Данная формула истинна, если и только если множество, соответствующее в мо-
дели аксиом Цермело-Френкеля символу x, является конечным ординалом (это
можно принять за формулировку определения конечного ординала). Ординалы,
не являющиеся конечными, называются бесконечными.
Использую аксиоматику Цермело-Френкеля ZF, мы можем показать существо-
вание стандартной модели арифметики Пеано. Практически все для этого уже
подготовлено. А именно, в качестве универсума рассмотрим N := ?0 определим

sN (?) = ? + 1, 0N := ?.

Таким образом, натуральные числа оказываются просто конечными ординала-
ми. Осталось определить операции суммирования +N и умножения ?N и про-
верить выполнение аксиом Пеано. Читателю предоставляется возможность по-
упражняться в этом или прочитать об этом в любом стандартном курсе теории
множеств ([4], [6]). Таким образом доказывается следующий фундаментальный
результат:

Теорема 9.4 В предположении непротиворечивости аксиоматики
Цермело-Френкеля ZF существует стандартная модель арифметики Пеано.

Кстати, интересно отметить, что ординал ?0 + 1 представляет собой не что иное,
как порядок (X, <X ) из примера 9.3 (B). В качестве упражнения рекомендуем чи-
тателю представить себе как выглядит ординал ?0 + k. Продолжим рассмотрение
структуры класса всех ординалов. Множество ?0 является предельным ордина-
лом и образовано объединением всех конечных ординалов, которые естественным
78 Формальная теория множеств


образом отождествляются с натуральными числами, однако ряд ординалов не ис-
черпывается таким образом. Так, за ординалом ?0 следует ?0 + 1, за последним
?0 + 2, и так далее. Так, что существуют ординалы

?0 + 1, ?0 + 2, . . . , ?0 + k, . . . k ? N.

Вслед за приведенными выше ординалами, очевидно, найдется следующий пре-
дельный ординал ?1 , являющийся первым предельным ординалом несчетной
мощности (поупражняйтесь в доказательстве этого утверждения), также ?1 на-
зывают первым несчетным ординалом. За ним следуют ординалы ?1 + 1, ?1 + 2,
и далее в ряду ординалов найдется следующий предельный ординал ?2 , и так
далее. Таким образом, ряд ординалов выглядит так:

0, 1, 2, ..., ?0 , ?0 + 1, ?0 + 2, ..., ?1 , ?1 + 1, ?1 + 2, ..., ?2 , ...

Мы, естественно, привели здесь лишь начальный отрезок этого ряда.
Понятие ординала, позволяющее легко сравнивать порядки, может быть адап-
тировано и для сравнения множеств по мощности. Введем для этого следующее
определение.


Определение 9.10 Кардиналом называется ординал, не равномощный ни од-
ному из меньших (предыдущих) ординалов.


Иначе говоря, формула

Card(x) := Ord(x) ? ?y(y ? x > ¬(y ? x))

означает, что x является кардиналом. Формула y ? x означает, что множества y
и x равномощны (выпишите “полную версию” этой формулы самостоятельно).
Так, 0, 1, 2 и все конечные ординалы являются кардиналами. Также являются
кардиналами ?0 и ?1 , однако, например, ?0 + 1, ?0 + 2, и вообще ?0 + k, где
k ? N, не являются кардиналами, так как все они имеют счетную мощность, и
равномощны меньшему ординалу ?0 . Кардиналы являются естественной мерой
мощности множеств в той же мере, в той же мере, в какой ординалы являются
мерой “величины” порядков. Для обозначения кардиналов часто используются
буквы древнееврейского алфавита. Так, ?0 и ?1 , рассматриваемые как кардина-
лы, обычно обозначают ?0 и ?1 , соответственно, и при этом о них говорят, что
это, соответственно счетный и первый несчетный кардиналы (мощности).
9.6 Аксиома выбора 79


9.6 Аксиома выбора

Сформулируем, наконец, последнюю, наиболее нетривиальную из аксиом Церме-
ло-Френкеля – аксиому выбора. Данная аксиома утверждает, что существует
функция (называемая функцией выбора), которая каждому множеству из набо-
ра ставит в соответствие ровно один элемент этого множества. Это утверждение
кажется весьма тривиальным, однако оно может быть выведено из других ак-
сиом Цермело-Френкеля лишь для конечных наборов множеств. Предположение
же его справедливости для произвольного набора множеств (впрочем, не вполне
произвольного: эти наборы должны быть множествами) ведет к целому ряду
нетривиальных следствий, иногда, казалось бы, противоречащих здравому смыс-
лу. Поскольку в теории, которую мы строим, все объекты являются множествами
(в том числе функции и “наборы” множеств, с которыми мы можем работать),
то формальная запись данной аксиомы несколько менее интуитивна, чем ее сло-
весное описание.
Для упрощения записи введем формулу

Disjoint(x) := ?u?v (u ? x ? v ? x ? ¬u = v > u ? v = ?),

которая “говорит” о том, что x состоит из попарно непересекающихся множеств.
С помощью этого сокращения аксиому выбора можно записать в следующем,
сравнительно компактном виде:

?x (¬? ? x ? Disjoint(x) > ?y (?w (w ? x - ?! z(z ? w ? y)))) (AC)

Здесь утверждается существование множества y, имеющего ровно по одному об-
щему множеству с каждым из элементов исходного множества x, при условии,
что x непусто и его элементы – попарно непересекающиеся множества.
В наши цели не входит подробное обсуждение аксиомы выбора. Интересующий-
ся читатель может обратится, например, к [6] или [5]. Здесь отметим только, что
аксиома выбора является одним из краеугольных камней современной математи-
ки в том смысле, что многие фундаментальные утверждения последней (скажем,
целый ряд важных результатов математического анализа) справедливы исклю-
чительно в предположении истинности аксиомы выбора. В то же время, интерес-
ным следствием данной аксиомы является парадокс Банаха-Тарского, который
утверждает, что любое тело (например, шар) может быть разрезано на конечное
число непересекающихся частей, из которых можно потом составить два тела,
равных исходному. Это утверждение кажется противоречащим здравому смыс-
лу, так как если бы подобное разбиение было бы осуществимо, то легко можно
80 Формальная теория множеств


было бы осуществить известное евангельское чудо, а именно “накормление верую-
щих двумя рыбами и пятью ячменными хлебами” (Евангелие от Иоанна 6:13-14).
Однако в доказательстве данного утверждения существенным образом исполь-
зуется аксиома выбора. Последняя является весьма неконструктивной, так как в
ней утверждается существование “функции выбора”, но не приводится алгоритма
построения этой функции. А значит, любые доказательства, которые существен-
ным образом используют аксиому выбора, в том числе и доказательство парадок-
са Банаха-Тарского, неконструктивны. Поэтому, например, невозможно привести
никакого алгоритма деления тела на составные части, утверждаемого в форму-
лировке парадокса, хотя и можно утверждать существование соответствующего
разбиения.
Следует отметить, что аксиома выбора является еще одной аксиомой создания
множеств, наряду с аксиомами выделения (ZF3 ), пары (ZF2 ), суммы (ZF5 ), мно-
жества подмножеств (ZF1 ) и замены (ZF6 ). Аксиоматику Цермело-Френкеля с
аксиомой выбора обозначают ZFC. Отметим, что (AC) не зависит от остальных
аксиом ZF.



9.7 Теория множеств и основания математики

Материала предыдущего параграфа должно быть вполне достаточно, чтобы убе-
диться в том, что рассматриваемого нами “примитивного” языка теории мно-
жеств (мы называем его “примитивным”, поскольку это язык логики первого
порядка, в котором сигнатура состоит всего из двух предикатных символов –
равенства = и принадлежности ?) и системы аксиом Цермело-Френкеля вполне
достаточно, чтобы описать и построить практически всю современную математи-
ку. Так, этих инструментов было достаточно для построения натуральных чисел
и основных действий над ними. Отталкиваясь от этих понятий, можно построить
целые числа (целое число можно определить, например, как пару натуральных
чисел), рациональные числа (как пары целых чисел) и, наконец, действитель-
ные числа, вектора, комплексные числа, геометрические фигуры (как множе-
ства векторов), функциональные пространства и так далее. Соответствующие
построения проводятся “по нарастающей” (целые числа строятся на основе нату-
ральных, рациональные на основе целых, вещественные на основе рациональных
и т.д.). Несколько неожиданным и, возможно, даже не вполне соответствующим
интуитивному представлению о математических объектах оказывается то, что
в любой модели построенной таким образом математики все объекты (числа,
вектора, функции, геометрические фигуры, и т.д.) оказываются множествами,
и даже, более того, все без исключения построены на основе одного объекта –
9.7 Теория множеств и основания математики 81


пустого множества ?. То, что построенные таким образом математические объ-
екты оказываются, на первый взгляд, не имеющими отношения к реальной жизни
(например, натуральные числа, построенные как конечные ординалы, не имеют
отношения к практическому подсчету предметов) можно считать платой за стро-
гость обоснования факта существования всех математических объектов. Кому-то
такая плата, приводящая к формализации математики и её кажущемуся “отры-
ву от реальной жизни”, может показаться чрезмерной. В то же время, на наш
взгляд, требование формализованности и строгости рассуждений никогда не мо-
жет чрезмерным, а опасность работы с плохо определенными “интуитивными”
понятиями проявляется в многочисленных парадоксах, некоторые примеры ко-
торых были приведены в данной главе.
Поскольку, как мы уже убедились, математика может быть построена на теорети-
ко-множественных основаниях, возникает естественный вопрос о том, насколько
прочными могут быть такого рода основания. А именно, является ли аксиоматика
теории множеств (например, аксиоматика Цермело-Френкеля ZFC) непротиво-
речивой? Из непротиворечивости последней следовала бы непротиворечивость и
всей математики. К сожалению, однако, до настоящего времени непротиворечи-
вость аксиоматики Цермело-Френкеля не была ни доказана, ни опровергнута. Не
лучшим образом обстоит дело и с другими популярными аксиоматическими тео-
риями множеств, которые также предлагались для построения оснований мате-
матики. Поэтому вопрос “строгого обоснования” математики, как ни странно, на
сегодняшний день в известной мере является вопросом веры или доверия к мно-
готысячелетнему опыту математиков и “пользователей” математического аппа-
рата (за все известное в истории время использования математического аппарата
противоречия получить не удалось, поэтому есть шанс, что математика являет-
ся непротиворечивой). К сожалению, дело обстоит в известной мере еще хуже,
ибо даже в предположении непротиворечивости математики ни системы аксиом
Цермело-Френкеля, ни какой-либо другой системы аксиом, достаточно богатой,
чтобы построить современную математику, и, в то же время, достаточно “обозри-
мой” (такой, которую можно описать конструктивным образом, как например,
мы описали ZFC) не хватит, чтобы доказать непротиворечивость этой систе-
мы аксиом. Иначе говоря, в предположении непротиворечивости ZFC, пользу-
ясь только аксиомами ZFC, нельзя доказать непротиворечивость ZFC. Данный
результат является следствием второй теоремы Геделя о неполноте формальных
теорий (кстати, выводимой из системы аксиом ZFC, как и вся та математическая
логика, которую мы строим).
Другим важным вопросом является вопрос о том, достаточно ли системы аксиом
Цермело-Френкеля для описания всей современной математики. Иначе говоря,
все ли интересные математические объекты и теории могут быть описаны в рам-
82 Формальная теория множеств


ках теории множеств, построенной на базе аксиом ZFC? Ответ на этот вопрос
также отрицательный, хотя ситуация здесь не настолько трагична, в том смыс-
ле, что для построения весьма значительной части современной математики до-
статочно системы аксиом Цермело-Френкеля с аксиомой выбора. Есть однако,
весьма интересные и важные, в том числе в приложениях, утверждения, кото-
рые не выводятся из ZFC. К числу таких утверждений относится, например,
континуум-гипотеза, заключающаяся в том, что множество вещественных чи-
сел R равномощно ?1 , то есть
#R = ?1 (CH)
Заметим, что из аксиоматики ZFC можно вывести, что #R ? ?1 , однако в от-
ношении континуум-гипотезы (CH) справедливо следующее утверждение, дока-
занное К. Геделем и П. Коэном.

Теорема 9.5 Если ZFC непротиворечива, то
ZFC CH и
ZFC ¬CH.
Иначе говоря, в этом случае континуум-гипотеза является независимым от-
носительно аксиоматики Цермело-Френкеля утверждением.

В cвязи с возможностью построения математики на теоретико-множественных
основаниях возникает естественный вопрос о том, как устроены модели матема-
тики, содержащие все мыслимые математические объекты. Очевидно, что, мо-
дель математики, построенной на системе аксиом Цермело-Френкеля, существу-
ет, если и только если ZF непротиворечива (нетривиальная часть этого утвер-
ждения следует из теоремы о модели 6.5). Однако, в этом случае все модели
математики будут бесконечными (так как они должны содержать хотя бы все
ординалы, число которых бесконечно), поэтому, в силу теоремы Левенгейма-
Скулема о повышении мощности модели 7.4, в этом случае математика будет
иметь сколь угодно много неизоморфных между собой моделей (с универсума-
ми сколь угодно большой мощности). Но наиболее интересные и нетривиальные
результаты дает теорема Левенгейма-Скулема о понижении мощности модели
7.2: в предположении непротиворечивости аксиоматики ZFС построенная с её
помощью математика будет иметь модель A со счетным универсумом. Данное
утверждение кажется абсурдным: каким образом в счетном универсуме может
уместиться принципиально несчетное число объектов, например, хотя бы несчет-
ное множество вещественных чисел? Тем не менее данный парадокс, называемый
парадоксом Скулема, является кажущимся. На самом деле счетность или несчет-
ность множества определяется наличием биекции между данным множеством и
9.7 Теория множеств и основания математики 83


?0 (напомним, последнее можно считать просто множеством натуральных чи-
сел). Множество вещественных чисел в любой модели математики, в том числе и
в модели со счетным универсумом, является несчетным (данный факт, доказан-
ный еще Кантором, сравнительно легко выводится из аксиоматики ZFC). Иначе
говоря, это означает, что в данной модели нет объекта, соответствующего биек-
ции между RA и ?0 A . В то же время, поскольку универсум A счетен, то можно
рассматривать его в качестве подмножества некоторой большей модели матема-
тики B, универсум которой несчетен. В этой большей модели RA и ?0 A являются
равномощными (поскольку оба они являются счетными множествами), то есть в
ней имеется объект (множество), соответствующий биекции между RA и ?0 A , од-
нако этот объект отсутствует в меньшей модели A. То есть понятия конечности,
счетности, несчетности на самом деле зависят от модели.

Данная ситуация проиллюстрирована на
рисунке, где модель A изображена в ви-
B де “плоского мира”, а B в виде “объем-
ного мира”. Биекция между RA и ?0 A
изображена в виде мостика между RA и
?0 A , который существует только в “объ-
емном мире” (из “плоского мира” он недо-
A
R
A ступен).
A
Литература

[1] Дж. Шенфилд, Математическая логика, “Наука”,Москва, 1975.

[2] Математическая теория логического вывода, под редакцией А. В. Иделсона
и Г .Е. Минца, “Наука”,Москва, 1967.

[3] И. А. Лавров, Л. Л. Максимова, Задачи по математической логике и теории
алгоритмов, “Наука”,Москва, 1984.

[4] Н. К. Верещагин и А. Шень, Начала теории множеств, МЦНМО, Москва,
1999.

[5] K. Hrbacek and T. Jech, Introduction to Set Theory, Marcel Dekker, Inc., New
York, 1999.

[6] Пол Дж. Коэн, Теория множеств и континуум-гипотеза, “Мир”, Москва,
1969.
Максим Алексеевич Коротков
Евгений Олегович Степанов
Основы формальных логических языков
Учебное пособие

В авторской редакции
Компьютерная верстка К. А. Ворошилов
М. А. Коротков
Дизайн обложки Я. А. Иванов
Редакционно-издательский отдел СПб ГИТМО (ТУ)
Зав. РИО Н. Ф. Гусарова

Лицензия ИД №00408 от 05.11.99
Подписано к печати 15.01.03
Тиражирование на ризографе.
Тираж 100 экз.

<< Пред. стр.

стр. 9
(общее количество: 9)

ОГЛАВЛЕНИЕ