<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

формальной системы), что противоречит теореме 8.1.
57


Требование корректности является необходимым для осмысленности формаль-
ной системы: формальная система строится для того, чтобы получать логиче-
ские, то есть семантические, истины, поэтому некорректная формальная система,
которая позволяет выводить в том числе формулы, не являющиеся истинными,
не имеет никакой практической ценности. Только что доказанная теорема утвер-
ждает, таким образом, что осмысленная (т.е. корректная) формальная система
для языка логики второго порядка не может быть полной. Иначе говоря, при
помощи такой формальной системы мы не можем вывести все семантические
истины. В то же время другого инструмента, пригодного для поиска на прак-
тике семантических следствий для заданного множества формул, кроме вывода
при помощи некоторой формальной системы, нет. Поэтому утверждение теоре-
мы 8.3 фактически является препятствием к широкому использованию языков
логики второго порядка. Языки логики второго порядка являются, таким обра-
зом, “чересчур” выразительными, настолько, что их чрезмерная выразительная
сила ограничивает возможность их применения. В этом смысле языки логики
первого порядка являются вполне подходящими, так как инструмент для их ис-
пользования (достаточно удобные формальные системы) существует, и в то же
время, как показывает опыт, при помощи языка логики первого порядка можно
записывать практически все важные естественнонаучные теории, хотя и нельзя
охарактеризовать какую-нибудь серьезную модель однозначно.



9 Формальная теория множеств

В качестве еще одного примера языка логики первого порядка, находящего самые
широкие применения в современной математике, рассмотрим язык теории мно-
жеств. Определим язык теории множеств как язык L? логики первого порядка с
равенством, с сигнатурой, содержащей лишь один символ, отличный от равенства
– символ предиката принадлежности ?. Иначе говоря, ?(L? ) := {=, ?}. Принято
писать x = y и x ? y вместо = (x, y) и ? (x, y) соответственно. Например, мы
будем считать формулы x = y, ?x ? y ? z ? q правильными формулами язы-
ка L? . Как и принято в математике, мы будем интерпретировать эти формулы
соответственно как “множества x и y совпадают” и “существует множество x, при-
надлежащее множеству y, и множество z принадлежит множеству q”. Несколько
необычным с точки зрения наивной теории множеств является утверждение о
том, что одно множество принадлежит другому. Привычнее говорить о том, что
элемент принадлежит множеству. Однако заметим, что во введенном языке име-
ются символы предметных переменных только одного cорта, а именно – только
для обозначения множеств (нет специального сорта переменных для обозначения
58 Формальная теория множеств


элементов множеств). Поэтому, имея дело с семантикой языка L? , мы будем ин-
терпретировать все предметные переменные как “множества”. Таким образом мы
будем иметь дело с миром, состоящим только из одного типа объектов – “мно-
жеств”. При этом нас не будет интересовать, насколько понятие “множества” как
элемента интерпретирующего универсума соответствует интуитивному понятию
множества как совокупности разных объектов. К этому вопросу мы еще вернемся
в дальнейшем.
Несмотря на то, что введенный в рассмотрение язык L? кажется весьма бедным,
на нем можно выразить все привычные факты о множествах (а также, и всю
математику – но об этом речь пойдет чуть позже). Например, “x подмножество
y” можно записать в виде правильной формулы языка L? , которую будем обо-
значать x ? y, следующим образом:

x ? y := ?z(z ? x > z ? y).

Здесь и далее подчеркивание указывает на то, что мы имеем дело с сокращенным
обозначением правильной формулы. Чуть позже мы еще займемся “кодировани-
ем” основных математических понятий в виде формул L? . А теперь покажем, что
к перенесению основных интуитивных понятий о множествах на формальный
язык L? нужно подходить с большой осторожностью. Рассмотрим следующий
пример.
Парадокс Рассела-Фреге. Мы привыкли формировать множества путем груп-
пирования элементов, обладающих заданным свойством (принято обозначать
{x : P (x)} множество элементов, обладающих свойством P ). Попробуем форма-
лизовать такой способ формирования множеств на языке L? . А именно, логично
предположить, что множество z := {x : P(x)} существует для любого “свойства”
(т. е. формулы L? с одной свободной переменной). Это легко записать в виде
формулы
?z?x(x ? z - P(x)),
где #free(P) = 1 (здесь и далее запись A - B понимается как сокращенная
запись формулы (A > B) ? (B > A). Каким бы заманчивым с интуитивной
точки зрения ни было это утверждение, оно ведет к абсурду. Действительно,
выберем в качестве P свойство множества не принадлежать самому себе, то есть
P(x) := ¬x ? x. Тогда для множества z := {x : ¬x ? x}, очевидно, выполняется
либо z ? z, либо z ? z, причем в силу определения множества z в первом случае
z ? z, а во втором z ? z. С более формальной точки зрения это означает, что
предложение
Q := ?z?x(x ? z - ¬x ? x)
противоречиво.
9.1 Аксиоматика Цермело-Френкеля. Основные аксиомы 59


Приведенный парадокс, который, несмотря на его название, был впервые об-
наружен Г. Кантором, показывает что далеко не все интуитивно осмысленные
предложения введенного формального языка теории множеств имеют право на
существование. Поэтому для построения содержательной и осмысленной фор-
мальной теории множеств явно недостаточно интуиции, основанной на наивных
представлениях о множествах. Традиционный способ выхода из такой ситуации –
ограничить формальную теорию множеств утверждениями, выводимыми из до-
статочно простого, понятного и непротиворечивого набора аксиом. В то же время
математика развивалась в течение по крайней мере последних двух с половиной
тысяч лет и накопила за это время огромный набор фактов, давно ставших досто-
янием как собственно математики, так и всех использующих ее наук. Теория же
множеств как основание математики появилась сравнительно недавно, начиная с
работ Г. Кантора в 70-х годах 19 века. Поэтому система аксиом для формальной
теории множеств кроме непротиворечивости должна обладать еще и следующим
важным с прикладной точки зрения свойством: она не должна существенным
образом обеднять создаваемую на ее основе формальную теорию множеств и ма-
тематику в целом. В связи с особой важностью теории множеств для построения
современной математики на протяжении 20 века было предпринято много по-
пыток предоставить такой набор аксиом. Ни одна из предложенных аксиоматик
не была абсолютно удачной, так что проблема формального обоснования совре-
менной математики до сих пор остается открытой. В то же время хотелось бы
предостеречь от немедленных попыток взяться за решение этой проблемы. Де-
ло в том, что, во-первых, существует несколько вполне удовлетворительных для
практических целей аксиоматик (наиболее популярные среди них – аксиоматики
Цермело-Френкеля и Геделя-Бернайса), а во-вторых, полное решение проблемы
формального обоснования вряд ли что-либо изменит в развитии современной ма-
тематики. Вскоре мы подробнее рассмотрим эти вопросы. А сейчас выпишем с
небольшими комментариями аксиомы наиболее простой и часто используемой ак-
сиоматики формальной теории множеств, предложенной Цермело и Френкелем.



9.1 Аксиоматика Цермело-Френкеля. Основные аксиомы

• Аксиома объемности.

?x?y(?z(z ? x - z ? y) - x = y) (ZF1 )

Эта аксиома говорит о том, что множество однозначно определяется своими
элементами. Очень часто она используется в доказательстве единственности
различных специальных множеств (например, пустого множества).
60 Формальная теория множеств


• Аксиома пары.

?x?y?z?v(v ? z - v = x ? v = y). (ZF2 )

Целесообразно записать ее в сокращенном виде, введя для множества z –
пары элементов x и y обозначение

z = {x, y} := ?v(v = x ? v = y - v ? z).

Таким образом, (ZF2 ) можно записать в виде

?x?y?z(z = {x, y}),

то есть утверждается, что из любых двух элементов можно построить мно-
жество-пару.

• Аксиома выделения.

?x?y (?z (z ? y - (z ? x) ? P (z))) , x, y ? free (P) , #free (P) = 1.
(ZF3 )
Эта аксиома представляет собой исправленный вариант обсуждавшегося
выше принципа, по которому можно формировать множества путем груп-
пирования элементов, обладающих заданным свойством. В исходном вари-
анте, как было показано, этот принцип ведет к противоречию. Способ слегка
подправить его с целью получить в действительности часто используемый
в математике факт, очень прост – достаточно заметить, что на практике
множества всегда формируются путем выделения элементов, обладающих
заданным свойством, из заданного множества, а не просто путем группиро-
вания “всех вообще” элементов с заданным свойством. Так например, мно-
жество {n : n2 ? 1 = 0} на самом деле получено выделением элементов из
N (то есть правильнее было бы писать {n ? N : n2 ? 1 = 0}). Такой способ
исправления основного принципа формирования множества по заданному
свойству его элементов был предложен Фреге и реализован в (ZF3 ).

• Аксиома множества подмножеств. Для сокращения записи введем об-
щепринятое обозначение для множества y всех подмножеств заданного мно-
жества x: y = 2x := ?z(z ? x - z ? y). Заметим, что в данном определении
использовано ранее введенное сокращение – формула z ? x. Рассматривае-
мая аксиома позволяет формировать новое множество как множество всех
подмножеств заданного множества и может быть с использованием введен-
ных обозначений записана в виде

?x?y(y = 2x ). (ZF4 )
9.1 Аксиоматика Цермело-Френкеля. Основные аксиомы 61


• Аксиома суммы говорит о существовании объединения произвольного
множества множеств. Для удобства записи введем обозначение для объ-
единения (иногда называемого также суммой) всех элементов множества x
(напомним, что все объекты, с которыми мы работаем – множества):

y = ?x := ?z(z ? y - ?v(v ? x ? z ? v)).

С учетом введенного обозначения аксиома суммы записывается в виде

?x?y(y = ?x). (ZF5 )


Прежде чем рассмотреть оставшиеся четыре аксиомы Цермело-Френкеля, по-
тренируемся в “кодировании” основных фактов о множествах на языке L? и в
их доказательстве с использованием уже введенных аксиом. Будем обозначать
систему аксиом Цермело-Френкеля (кроме аксиомы выбора) ZF .


Пример 9.1 Докажем существование и единственность пустого множества,
то есть множества, не содержащего ни одного элемента. Для этого введем
общепринятое обозначение:

x = ? := ?y(¬y ? x).

Требуется доказать ZF ?!x(x = ?). Напомним, что ?!x P(x) – общепринятое
сокращение формулы

?x P(x) ? ?y?x(P(y) ? P(x) > x = y).


Доказательство:
Существование. Аксиома (ZF3 ) записывается в виде

?x?y?z(z ? y - z ? x ? (¬z = z)).

Применяя правило (?e), получаем (ZF3 ) ?y R, где

R := ?z(z ? y - z ? x ? (¬z = z)).

Теперь докажем R ?z(¬z ? y). Это доказательство удобно представить в виде
62 Формальная теория множеств


дерева
?z(z ? y - z ? x ? (¬z = z)) (?e)
z ? y - z ? x ? (¬z = z) (?e)
z ? y > z ? x ? (¬z = z) [z ? y]1 (m.p.)
z ? x ? (¬z = z)
¬z = z
? 1, (¬i)
¬z ? y (?i)
?z(¬z ? y)
Осталось объединить две “ветви” для завершения доказательства:

(ZF3 ) [R]2
?y R ?z(¬z ? y)
2
?y?z(¬z ? y)

(здесь применено одновременно несколько правил; мы предоставляем читателям
возможность самим убедиться в корректности соответствующего перехода).
Единственность. Надо доказать

ZF ?x?y(?z(¬z ? y) ? ?z(¬z ? x) > (x = y)).

Представим доказательство в виде дерева

[?z(¬z ? x) ? ?z(¬z ? y)]1 [?z(¬z ? x) ? ?z(¬z ? y)]1
?z(¬z ? x) ?z(¬z ? y)
¬z ? x ¬z ? y
¬z ? x ? ¬z ? y
(ZF1 ) z?x-z?y
?z (z ? x - z ? y) > (x = y) ?z (z ? x - z ? y)
x=y 1
?z(¬z ? x) ? ?z(¬z ? y) > x = y
?x?y (?z(¬z ? x) ? ?z(¬z ? y) > x = y)

Предоставляем читателю определить, какие правила применены на каждом шаге
доказательства, а также заполнить недостающие фрагменты. После этого оста-
нется объединить доказательство существования с доказательством единствен-
ности при помощи правила (?i). .

Упражнение 9.1 Доказать
9.1 Аксиоматика Цермело-Френкеля. Основные аксиомы 63


(A) ZF ?x?y?!z(z = x ? y), где

z = x ? y := ?v(v ? z - v ? x ? v ? y)

(существование и единственность объединения множеств).

(B) ZF ?x?!y(y = {x}), где

y = {x} := y = {x, x}

(существование и единственность одноэлементного множества, содер-
жащего заданный элемент).


Указание:

(A) Для доказательства существования использовать аксиому суммы, приме-
ненную к множеству-паре {x, y}. Существование последнего гарантируется
аксиомой пары. Для доказательства единственности использовать аксиому
объемности.

(B) Использовать аксиому пары и аксиому объемности.


Упражнение 9.2 Введем упорядоченную пару как пару с выделенным первым
элементом:
x = (y, z) := x = {{y}, {y, z}}.
Доказать
ZF ?y?z?x(x = (y, z)).


Указание: Для доказательства существования упорядоченной пары (y, z) ис-
пользовать уже доказанные факты существования одноэлементного множества
{y} и пары {y, z}, затем еще раз сослаться на существования пары, элементами
которой будут только что построенные множества. Для доказательства един-
ственности использовать аксиому объемности.
64 Формальная теория множеств


Упражнение 9.3


(C) Введем следующее обозначение для векторов, обобщающее понятие упоря-
доченной пары:
x = (x1 , ..., xn ) := x = (x1 , (x2 , ..., xn )).
Докажите ZF ?x1 ?x2 ?!y(y = x1 ? x2 ), где
y = x1 ? . . . ? xn := ?u(u ? y - ?z1 ...?zn (z1 ? x1 ? . . . ? zn ? xn ? u = (z1 , . . . , zn )))
(существование и единственность декартова произведения множеств).
(D) Доказать ZF ?x(¬x = ?)?!y(y = ?x), где
y = ?x := ?z(z ? y - ?v(v ? x > z ? v))
(существование и единственность пересечения произвольного числа мно-
жеств).
(E) Доказать ZF ?x?y?!z(z = x ? y), где
z = x ? y := ?v(v ? z - (v ? x ? v ? y)).

Указание:


(F) Рассмотрим случай только элементов в произведении, поскольку техни-
ка доказательства в других случаях аналогична. Единственность следует
из аксиомы объемности, а существование из аксиомы выделения, приме-
x ?x
ненной к множеству x := 22 1 2 , и свойству P := ?z1 ?z2 (z1 ? x1 ? z2 ?
x2 ? z = (z1 , z2 )).
(G) Для доказательства существования применить аксиому выделения к
множеству ?x и свойству P := ?v(v ? x > z ? v) Единственность
следует из аксиомы объемности.
(H) Применить (E) к паре (x, y).

• Аксиома замены. Можно создавать новое множество как множество зна-
чений некоторой функции.
?x(?y?z?w((y ? x ? P (y, z) ? P (y, w)) > z = w) >
?r?s(s ? r - ?t(t ? x ? P (t, s)))). (ZF6 )
9.2 Отношение порядка 65


9.2 Отношение порядка

Перед обсуждением остальных аксиом Цермело-Френкеля рассмотрим понятие
порядка. Введем следующее определение:

Определение 9.1 Частичным порядком называется пара (A, <), где A – мно-
жество, а < – двуместное отношение на A (напомним, что n-местное от-
ношение на A это просто подмножество An , то есть < это подмножество
A ? A), обладающее следующими свойствами:

(i) y < y для всех y ? A,

(ii) Из x < y и y < z следует x < z для всех x, y, z ? A.

В этом случае говорят также, что отношение < частично упорядочивает
множество A либо что A частично упорядоченно отношением <.

Следуя традиции, мы используем значок < (а не букву) как знак отношения
частичного порядка и называем это отношение “меньше”.

Определение 9.2 Частичный порядок (A, <) называется линейным, если все
элементы множества A сравнимы отношением <, иначе говоря, если для всех
a ? A , b ? A выполнено либо a < b, либо b < a, либо a = b. В этом случае
говорят также, что отношение < является отношением линейного порядка
на A, или что A является множеством, линейно упорядоченным отношением
<.

Пусть (A, <) – частичный порядок. Очевидно, что любое B ? A также частично
упорядоченно отношением <. Элемент x ? B называется минимальным элемен-
том множества B, если не существует никакого меньшего его элемента этого
множества. Элемент x ? B называется наименьшим элементом множества B,
если он меньше всех элементов этого множества. Заметим, что наименьший эле-
мент множества автоматически является и его минимальным элементом, однако
обратное, вообще говоря, неверно. Например, во множестве коробок определим
отношение порядка таким образом, что коробка A меньше коробки B, если ее
можно поместить внутрь коробки B. Ясно, что при таком определении необя-
зательно все коробки являются соизмеримыми, то есть полученный порядок не
обязательно является линейным, (например, если в рассматриваемом множестве
коробок найдутся такие две, что ни одна из них не помещается внутрь другой).
66 Формальная теория множеств


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

Определение 9.3 Порядок (A, <) называется фундированным, если любое под-
множество B ? A содержит минимальный элемент. В этом случае говорят
также, что частично упорядоченное множество A является фундированным.
Фундированный линейный порядок называется полным. В этом случае говорят
также, что множество A вполне упорядочено отношением <.

Вот некоторые примеры частичных порядков:

Пример 9.2


(A) Множество натуральных чисел N со стандартным отношением < – пол-
ный порядок.

(B) Множество Z (целых чисел), также со стандартным отношением < –
не является полным порядком, хотя и является линейным порядком.

(C) Множество комплексных чисел C со следующим отношением порядка
(z1 < z2 - Re(z1 ) < Re(z2 )) является частичным, но не является даже
линейным порядком.

(D) Множество целых положительных чисел Z+ с отношением <, введен-
ным следующим образом: x < y если x делит y. Такой порядок является
частичным, но не является линейным порядком.

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>