<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>


(E) Для некоторого множества X, рассмотрим множество всех его подмно-
жеств 2X , упорядочим его отношением включения, а именно x < y если
x ? y и x = y. Такой порядок в общем случае не является линейным.

(F) Над множеством A? слов над алфавитом A, где алфавит частично упоря-
дочен отношением <A , определим лексикографический порядок следующим
образом: x < y если либо длина (число символов) слова x меньше длины
слова y, либо, если их длины одинаковы и x <A y , где x и y – первые
различающиеся буквы. Например, если A – латинский алфавит, <A – по-
рядок следования букв в алфавите, то лексикографический порядок будет
полным, причем для множества слов A? верно, например, что z <A? f ish
и home <A? last. Но если A – вещественные числа, то лексикографический
порядок будет линейным, но не будет полным.
9.2 Отношение порядка 67


Справедливо следующее утверждение:

Теорема 9.1 В любой модели системы аксиом Цермело-Френкеля следующие
три свойства частичных порядков (A, <) эквивалентны:

(i) Порядок (A, <) является фундированным.

(ii) Не существует бесконечной строго убывающей последовательности x0 >
x1 > x2 > . . . > xk > . . . элементов множества A.

(iii) Для множества X верен принцип математической индукции в следующей
форме: если (при каждом x ? X) из истинности для всех y < x следует
истинность P(x), то свойство P верно при всех x.

Доказательство: Теорему будем доказывать по частям. Перейдем к доказа-
тельству эквивалентности первых двух свойств. Рассмотрим бесконечную убы-
вающую последовательность x0 > x1 > x2 > . . .. Очевидно, что множество ее
значений не имеет минимального элемента (следующий элемент найдется для
любого элемента, так как последовательность бесконечная, и он еще меньше, так
как она убывающая). Поэтому (i) влечет (ii). И обратно, если X непустое мно-
жество, не имеющее минимального элемента, то бесконечную убывающую после-
довательность можно строить следующим образом. Зафиксируем некий элемент
x ? X, он не минимальный по предположению, тогда берем меньший элемент
x1 < x, x1 ? X, таким образом получаем бесконечную убывающую последова-
тельность {xi }? .
i=1

Теперь выведем принцип математической индукции из существования минималь-
ного элемента в любом подмножестве. Пусть P(x) – свойство элементов множе-
ства X, верное не для всех элементов x ? X. Рассмотрим множество тех элемен-
тов, для которых свойство P неверно. Множество B непусто по предположению.
Пусть x0 - минимальный элемент множества B. Тогда для всех x < x0 свойство
P(x) выполнено, так как элементов меньших x0 в множестве B нет. Но тогда по
предположению должно быть выполнено и P(x0 ), таким образом мы пришли к
противоречию.
И последнее: из принципа математической индукции следует существование ми-
нимального элемента в любом непустом множестве. Пусть B - множество, в кото-
ром нет минимальных элементов. Докажем что B пусто: в качестве P(x) возьмем
свойство x ? B. Тогда, если P(x) верно для всех x < x0 , то никакой элемент,
меньший x0 , не лежит в B. Значит, если бы x0 лежал в B, то он был бы там
минимальным, таким образом, мы пришли к противоречию.
68 Формальная теория множеств


9.3 Аксиома регулярности

Теперь мы можем сформулировать еще одну, весьма важную аксиому системы
аксиом Цермело-Френкеля, называемую аксиомой регулярности, или фундиро-
вания (the foundation axiom). Эта аксиома записывается следующим образом:

?x ¬x = ? > ?y y ? x ? y ? x = ? , (ZF7 )

где y ? x = ? – сокращенное написание формулы

z ? y = ? := ?r r = z ? y ? r = ? .

Эта аксиома является несколько искусственной и никогда явным образном не
используется в привычной нам математике. Она утверждает, что каждое непу-
стое множество X содержит элементы, минимальные по отношению к отношению
принадлежности ? (а не включения ?). С интуитивной точки зрения мы бы хо-
тели, чтобы все наши множества строились из пустого множества ?. Поэтому мы
хотим избавиться от бесконечных последовательностей множеств, убывающих по
отношению к порядку, определенному отношением принадлежности ?. Аксиома
регулярности (ZF7 ) утверждает таким образом, что никакое множество, в этом
смысле, не может иметь бесконечной “глубины”. В привычной нам математике мы
имеем дело с натуральными, рациональными, действительными числами, функ-
циями и т.п. В дальнейшем мы покажем, что все эти объекты явным образом
строятся из пустого множества ?.
Условие, налагаемое аксиомой регулярности на отношение принадлежности ?,
очень похоже на понятие фундированного порядка. Правда, стоит иметь в виду,
что отношение принадлежности не упорядочивает все множество, например, хотя
бы потому, что из x = y не следует, что x ? y либо y ? x.
/ /
Требование справедливости данной аксиомы является весьма сильным, и, в част-
ности, исключает из возможных моделей аксиоматики Цермело-Френкеля все-
возможные экзотические объекты, такие как множество всех множеств или мно-
жество всех множеств не содержащих себя в качестве элемента. Действительно,
если бы существовало множество A всех множеств, не содержащих самого се-
бя, то есть x ? A, если и только если x ? x, то оно содержало бы бесконечную
/
(“бездонную”) последовательность множеств, включающихся друг в друга. Вот
строгая формулировка и доказательство этого утверждения.
9.4 Аксиома бесконечности 69


Предложение 9.1. ZF ?x(¬x ? x)

Доказательство: Докажем теперь, что никакое множество не принадлежит
самому себе. Воспользуемся аксиомой регулярности и уже доказанным фактом
существования одноэлементного множества {x}, а также тем, что
ZF ?x(x ? {x}), где

x ? {x} := ?y(x ? y ? y = {x})

(докажите этот факт самостоятельно). Дерево доказательства формулы ?x(¬x ?
x) выглядит следующим образом.
[y ? {x} ? ?z(z ? {x} > ¬z ? x)]1 (?e)
?z(z ? {x} > ¬z ? x)(?e)
z ? {x} > ¬z ? x z=x
x ? {x} x ? {x} > ¬x ? x(>e) ?v(?y(y ? v) > ?y(y ? v ? ?z(z ? v > ¬z ? y)))?e,v={x}
¬x ? x?i ?y(y ? {x}) ?y(y ? {x}) > ?y(y ? {x} ? ?z(z ? {x} > ¬z ? y))(>e)
?x(¬x ? x) (?y)(y ? {x} ? ?z(z ? {x} > ¬z ? y))1,(?e)
?x(¬x ? x)




Упражнение 9.4 Докажите, что в модели аксиоматики Цермело-Френкеля
не существует множества всех множеств. Иначе говоря,

ZF ¬?x?y(y ? x).

Указание: Если бы такое множество существовало, то оно содержало бы
себя, что противоречит предложению 9.1.


9.4 Аксиома бесконечности

Рассмотренные до сих пор аксиомы системы аксиом Цермело-Френкеля позво-
ляли конструировать различные математические объекты, например, конечные
вектора, отношения, отображения как некоторые специальные множества. Од-
нако, легко заметить, что все множества, которые мы таким образом констру-
ировали, были конечными. Так, например, мы доказали существование пустого
множества в любой модели системы аксиом Цермело-Френкеля. Следовательно,
хотя бы в силу аксиомы множества подмножеств (ZF4 ), существует и одоэле-
ментное множество 2? , а также трех (четырех, пяти) элементные множества, и
70 Формальная теория множеств


вообще множества с любым конечным числом элементов. Действительно, среди
аксиом, которые позволяли формировать новые множества, лишь аксиома пары
(ZF2 ), аксиома множества подмножеств (ZF4 ) и аксиома суммы (ZF5 ) позво-
ляли формировать множества, имеющие больше элементов, чем было в исход-
ных множествах, остальные же (например, аксиома выделения (ZF3 )) позволяли
лишь уменьшать число элементов в формируемых множествах. Таким образом,
пользуясь сформулированными до сих пор аксиомами, мы не сможем вырваться
из мира конечных множеств, а, значит, мы не можем утверждать, опираясь на
эти аксиомы, существование многих привычных математических объектов, таких
как, например, множество натуральных (вещественных, комплексных) чисел и,
вообще, любые другие бесконечные множества. Вообще говоря, это не является
принципиальным ограничением для построения математики, а именно, можно
построить “конечную” математику, то есть оперирующую исключительно с ко-
нечными объектами. Однако надо сказать, что такая конечная математика будет
существенно беднее общепринятой, так что отказ от последней ради исключения
из нее бесконечных множеств создает весьма значительные сложности. Иначе го-
воря, хотя без бесконечных множеств “прожить” и можно, но это существенно ме-
нее удобно: представьте себе, например, как определить вещественную функцию,
не используя понятия бесконечных множеств. Впрочем, в этих рассуждениях мы
оставили в стороне философский вопрос о том, существуют ли на самом деле бес-
конечные множества: в окружающей нас природе мы, очевидно не можем указать
ни на какой конкретный пример бесконечного множества, а лишь на сколь угодно
большие, но все же конечные множества. Иначе говоря, в житейских ситуациях
мы вряд ли когда либо можем встретиться с действительной (актуальной) беско-
нечностью (то есть с действительно бесконечным множеством). И в то же время
встречаемся со сколь угодно большими множествами, то есть с потенциальной
бесконечностью.
Для того, чтобы ввести в формируемую нами теорию бесконечные множества,
предназначена специальная аксиома системы аксиом Цермело-Френкеля, назы-
ваемая аксиомой бесконечности и записываемая следующим образом:

?x(? ? x ? ?v(v ? x > {v} ? v ? x)) (ZF8 )

Данная аксиома утверждает существование множества, содержащего по крайней
мере все элементы вида 0 := ?, 1 := {?} . . . 2 := {?} ? {{?}} то есть все элементы
вида
k = k ? 1 ? {k ? 1}, k ? N.
Такое множество, очевидно, является бесконечным (по крайней мере счетным).
Стоит отметить, что мы не можем сказать ничего более определенного о мощно-
сти данного множества. В частности, мы не можем утверждать, что это множе-
9.5 Ординалы и стандартная модель арифметики 71


ство счетно, так как аксиома бесконечности не гарантирует, что в нем содержатся
только элементы вида k.
С использованием аксиомы бесконечности мы получаем множество новых объек-
тов, и жизнь сразу делается более “приятной”. В частности можно сравнительно
легко доказать существование самых разных привычных объектов современной
математики. Для примера мы построим в следующем параграфе множество на-
туральных чисел и, вместе с ним, фактически стандартную модель арифметики.
Натуральные числа мы будем отождествлять с только что введенными элемен-
тами вида k, где k ? N, а “множество натуральных чисел” со множеством, со-
держащим все “натуральные числа”, то есть множества k, k ? N, и только их.
Такое множество очевидно содержится в бесконечном множестве, существование
которого гарантируется аксиомой бесконечности (ZF8 ). Таким образом, множе-
ство “натуральных чисел” можно получить, применяя к последнему множеству
аксиому выделения (ZF3 ).
Этой конструкции посвящен следующий параграф, в котором попутно вводятся
более общие весьма важные объекты, обобщающие как понятие чисел, так и мно-
жества натуральных чисел, называемые порядковыми числами или ординалами.


9.5 Ординалы и стандартная модель арифметики

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

Определение 9.4 Порядки (X, <X ) и (Y, <Y ) изоморфны, если существует би-
екция f : X > Y , сохраняющая порядок, то есть такая что из x1 <X x2
следует f (x1 ) <Y f (x2 ).

Мы будем писать (X, <X ) ? (Y, <Y ), если порядки (X, <X ) и (Y, <Y ) изоморфны.
В этом же случае мы будем писать просто X ? Y , позволяя себе некоторую воль-
ность отождествления порядка с соответствующим упорядоченным множеством,
если ясно, какое отношение порядка имеется в виду. Рассмотрим некоторые при-
меры.
72 Формальная теория множеств


Пример 9.3


(A) Рассмотрим множество натуральных чисел N со стандартным порядком
и множество четных чисел Even с тем же самым порядком. Очевидно,
что соответствующие порядки изоморфны: изоморфизм осуществляется
биекцией f : N > Even, определяемой формулой f (x) = 2x.

(B) Рассмотрим множества натуральных чисел N со стандартным порядком
и множество X := N ? {?} = {0, 1, 2, 3, 4 . . . , ?}. В последнем множестве
порядок определяется следующим образом: x <X y, если либо {x, y} ? N и
x <N y в смысле стандартного порядка на множестве N, либо x ? N, y =
?. Соответствующие порядки не являются изоморфными, несмотря на
то что сами множества X и N равномощны. Иначе говоря, между X и
N существует биекция, но никакая биекция не может сохранять порядок.
Докажем это от противного. Пусть f : X > N – биекция, сохраняющая
порядок. Тогда f (x) < f (?) для любого x ? N, что противоречит сюрьек-
тивности f .


Если (Y, <) – частичный порядок, то под начальным отрезком y этого порядка,
?
соответствующим элементу y ? Y , будем понимать множество y = {x ? Y, x < y}
?
с тем же самым отношением порядка <. Стоит отметить несколько простейших
свойств начальных отрезков (поупражняйтесь в их доказательстве):

(i) начальный отрезок полного порядка является полным порядком;

(ii) если Y – частичный порядок, а y – его начальный отрезок, то y также можно
? ?
рассматривать как порядок (отношение порядка унаследовано от Y ). Тогда
любой начальный отрезок порядка y является начальным отрезком порядка
?
Y;

(iii) объединение любого числа начальных отрезков одного и того же линейного
порядка является начальным отрезком того же порядка;

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

Теперь введем следующее определение.
9.5 Ординалы и стандартная модель арифметики 73


Определение 9.5 Будем говорить, что

(i) порядки (X, <X ) и (Y, <Y ) имеют одинаковый порядковый тип, если X ?
Y;

(ii) порядок (X, <X ) имеет строго больший порядковый тип, чем (Y, <Y ), если
существует y ? Y , такой что y = Y и X ? y . В этом случае будем писать
? ?
X Y;

(iii) порядок (X, <X ) имеет строго меньший порядковый тип, чем (Y, <Y ), если
порядок (Y, <Y ) имеет строго больший порядковый тип, чем (X, <X ), то
есть существует x ? X, такой что x = X и Y ? x. В этом случае будем
? ?
писать X Y .

В последнем примере в пункте (A) оба порядка имеют одинаковый порядковый
тип, а в пункте (B) порядковый тип N меньше порядкового типа X. Справедливо
следующее утверждение.

Теорема 9.2 (Бернштейна) В предположении непротиворечивости системы
аксиом Цермело-Френкеля ZF для любых двух полных порядков верно ровно одно
из следующих утверждений:

(i) X и Y имеют одинаковый порядковый тип;

(ii) X имеет строго больший порядковый тип, чем Y;

(iii) Y имеет строго больший порядковый тип, чем X.

Доказательство: Упражняйтесь, либо загляните в [4].
В “наивной”, то есть неаксиоматизированной теории множеств обычно вводят по-
нятие ординала как порядкового типа всех изоморфных между собой порядков.
Говоря более строгим языком, это означает, что таким образом определяемый
ординал является классом эквивалентности всех изоморфных между собой по-
рядков. Например, ординал 1 должен быть классом всех порядков, изоморфных
порядку {?}, ординал 2 должен быть классом всех порядков, изоморфных поряд-
ку {?, 1}, где 1 > ?. Однако, в строгой теории множеств, которую мы пытаемся
строить, подобное “определение” понятия ординала не может быть реализовано.
А именно, для того чтобы доказать существование хоть какого-нибудь ордина-
ла как класса всех изоморфных порядков, необходимо выделить этот ординал с
использованием аксиомы выделения (ZF3 ) из некоторого достаточно большого
74 Формальная теория множеств


множества, которому принадлежат все порядки. Достаточно легко заключить,
что само существование подобного чересчур “большого” множества весьма про-
блематично. Для того, чтобы обойти это затруднение, Дж. фон Нейман предло-
жил определить понятие ординала слегка по-другому, так что ординал, введен-
ный согласно новому определению, автоматически оказывался бы множеством.
Для описания этой конструкции введем следующие определения.


Определение 9.6 Множество x называется транзитивным, если для всех y,
таких что y ? x, и z, таких что z ? y, выполнено z ? x.


Иначе говоря, на языке теории множеств формула

T rans(x) := ?y?z(z ? y ? y ? x > z ? x)

“говорит” о том, что x – транзитивное множество.

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

Стоит отметить, что на произвольном множестве отношение принадлежности ?,
вообще говоря, не задает даже частичного порядка. Однако на транзитивном
множестве это отношение является отношением частичного порядка.
На рассматриваемом нами языке теории множеств формула

Linord(x, ?) := ?y?z(y ? x ? z ? x > z ? y ? y ? z ? y = z)

“говорит” о том, что множество x упорядочено отношением принадлежности ?,
а формула

F ound(x, ?) := (v ? x > ?w(w ? v ? ?q(q ? v > (w ? q ? w = q)))),

“говорит” о том, что отношение принадлежности ? превращает x в фундирован-
ное множество.
Тогда формула

Ord(x) := T rans(x) ? Linord(x, ?) ? F ound(x, ?)

“говорит” о том, что x – ординал.
9.5 Ординалы и стандартная модель арифметики 75


Пример 9.4 Следующие множества является ординалами:

0 := ?, 1 := {0}, 2 := 1 ? {1}, . . . , k := k ? 1 ? {k ? 1}, . . . k ? N.

Все такие ординалы называются конечными ординалами.

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

Теорема 9.3 Если система аксиом Цермело-Френкеля ZF не является проти-
воречивой, то любой полный порядок изоморфен единственному ординалу ?.

(Y, <) ? (?, ?)

В цели данной книги не входит подробное изложение теории множеств, будь
то наивной или аксиоматической, а лишь иллюстрация применения математи-
ческой логики для описания различных математических теорий, в том числе
теории множеств. Поэтому мы приведем здесь лишь немногие основные свойства
ординалов без доказательства, предлагая читателям самим поупражняться в их
доказательстве. В случае трудностей, а также при желании более углубленно
изучить теорию множеств, мы рекомендуем обращаться к [4], [6].
В связи с этим для начала мы предлагаем читателю в качестве упражнения до-
казать теорему 9.3. Помочь в этом могут следующие свойства ординалов:

(i) любое ограниченное семейство ординалов имеет точную верхнюю грань;

(ii) класс всех ординалов вполне упорядочен отношением принадлежности ?
между своими элементами;

(iii) начальный отрезок ординала также является ординалом;

(iv) изоморфные ординалы совпадают.

Обратите внимание, что мы говорим о классе, а не о множестве всех ординалов.
Действительно, не трудно показать (см. ниже), что множества всех ординалов
не существует. Однако понятие частичной (линейной, полной) упорядоченности
очевидно можно применять не только к множествам, но и к произвольным сово-
купностям объектов (классам).
76 Формальная теория множеств


С использованием вышеприведенных свойств доказательство теоремы 9.3 можно

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>