ИПОВС - 6 семестр / Пособие / G2

(a ) (a ), значит, (a) (a ). Так как – вложение, то a a , но это невозможно. Таким образом, .

Следствие. Вполне упорядоченное множество A не может быть изоморфно своему начальному отрезку, отличному от A.

Доказательство. Пусть A – вполне упорядоченное множество и : A A – вложение, сохраняющее порядок, причём (A) – начальный отрезок множества A. Тождественное отображение : A A, a a, тоже является изоморфизмом A на начальный отрезок A, откуда по лемме получаем: . Следовательно, (A) A.

2.2.2. Лемма Цорна и теорема Цермело

Цепью называется линейно упорядоченное множество.

Пусть A – частично упорядоченное множество и – его подмножество, являющееся цепью. Мажорантой (или верхней границей) цепи называется любой элемент a A такой, что x a для всех x .

Обозначим через B( ) множество всех мажорант цепи . Введём ещё одно обозна-

чение. Пусть – цепь и a . Положим a {x | x a}.

Наша дальнейшая цель – сформулировать два новых утверждения – лемму Цорна и теорему Цермело – и доказать их эквивалентность аксиоме выбора.

Аксиома выбора (формулировку см. в начале раздела).

Лемма Цорна. Пусть A – частично упорядоченное множество, в котором каждая цепь имеет мажоранту. Тогда A имеет хотя бы один максимальный элемент.

Теорема Цермело. На всяком множестве можно ввести отношение порядка, превращающее его во вполне упорядоченное множество.

Докажем эквивалентность этих утверждений по схеме (1) (2) (3) (1).

(1) (2). С помощью аксиомы выбора нам надо доказать лемму Цорна. Пусть A – частично упорядоченное множество, в котором каждая цепь имеет мажоранту. Обозначим

через f функцию выбора f : 2A \{ } A. Предположим, что множество	A не имеет
максимального элемента, и приведём это предположение к противоречию.	Так как в A
нет максимального элемента, то B( ) \ для любой цепи A.

Назовём подмножество множества A отмеченным, если выполняются условия: (а) вполне упорядочено отношением порядка, перенесённым на из A;

(б) для любого a имеет место равенство a f (B( a ) \ a ).
Отмеченные подмножества существуют.				Например, . Примером непустого отме-
ченного подмножества может служить {a0},							– два отмечен-
				где a0 f (A). Пусть и
ных подмножества, a min ,	a							поэто-
			min . Тогда a a ,			B( a ) B( a ) A,
	минимальные			элементы всех	отмеченных		подмножеств
му a f (A \ ) a . Итак,
совпадают друг с другом (и совпадают с a0 f (A)).
Докажем, что для любых отмеченных подмножеств и
						либо , либо		.

По предыдущей теореме одно из этих множеств изоморфно начальному отрезку другого.

Пусть, например,		изоморфно начальному отрезку множества
						и : – изомор-
физм на ( ).			то (a0 ) a0. Докажем, что (x) x для
		Так как a0 min min ,
всех x .	Пусть это не так и c – минимальный элемент такой,					что (c) c. Ввиду (б)
c f (B( c ) \ c ). Ввиду минимальности элемента c отображение						тождественно на c.
Значит, c
	. Докажем, что между элементами из и элементом ( ) в цепи
элементов			x (c),	x y	для всех y c .Так		как
	нет. Действительно, пусть x ,
		36

x (c), то		x ( ). Значит,		x (u) при некотором u .		Так как	x (c), то u c ,
откуда (u) u. Значит,			x u c , что противоречит выбору элемента				x. Итак, между c
и (c) в		элементов	нет.	Это означает,		Так как		отмеченное, то
					что c (c).
(c) f (B( c ) \ c ). Это влечёт, что (c) c
					– противоречие. Следовательно, .

Пусть – объединение всех отмеченных подмножеств. Ранее было показано, что для любых двух отмеченных подмножеств одно из них содержится в другом в качестве начального отрезка. Отсюда следует, что тоже является отмеченным подмножеством. Очевидно, – наибольшее отмеченное подмножество. По условию B( ) \ . Следо-

вательно, существует элемент z f (B( ) \ ). Цепь {z} тоже является отмечен-

ным подмножеством, поэтому . Но это противоречит тому, что z . Утверждение доказано.

(2) (3). Предположим, что справедлива лемма Цорна. Докажем теорему Цермело.

Пусть A – множество и Х – множество пар (B, ),

где B – подмножество множества A, а

– отношение порядка на B такое, что B вполне упорядочено этим отношением. Введём

на множестве

X отношение порядка, положив (B, ) (B , ), если B B , |B

(т.е.

на множестве

B порядки

B является начальным отрезком в

и совпадают) и

B .

Пусть {(B , ) | }

– цепь в X (здесь – какое-либо множество индексов). Оче-

видно,

– мажоранта цепи . Итак,

каждая цепь в X имеет мажоранту. От-

B ,

сюда следует по лемме Цорна, что X имеет максимальный элемент. Пусть это будет

(C, ). Докажем,

что C A. Пусть C A. Тогда существует элемент a A \ C. Положим

C C {a} и продолжим

на множество C ,

положив a a и c a для всех c C

(здесь

– продолжение порядка ). Получим: (C

, ) (C, ), что противоречит макси-

мальности элемента (C, ). Итак, C A, значит, A вполне упорядочено отношением .

(3) (1). Предположим, что справедлива теорема Цермело, и требуется доказать аксиому выбора. Пусть A – произвольное множество. По теореме Цермело существует порядок на A, превращающий его во вполне упорядоченное множество. Для каждого непустого подмножества B A положим f (B) min B. Тогда f будет являться функцией выбора f : 2A \{ } A.

Итак, нами доказана эквивалентность аксиомы выбора, леммы Цорна и теоремы Цермело. Значит, каждая из них с одинаковым успехом может быть принята в качестве аксиомы, тогда две другие будут являться теоремами. Обычно за аксиому принимают первое утверждение – аксиому выбора ввиду её простоты и достаточной очевидности.

Замечание. Аксиома выбора так же, как лемма Цорна и теорема Цермело, носят неконструктивный характер. Аксиома выбора утверждает, что существует функция выбора, но не говорит о том, как её построить. Теорема Цермело утверждает, что всякое множество можно сделать вполне упорядоченным, но как это сделать, из теоремы извлечь невозможно. Никому ещё не удалось вполне упорядочить несчётное множество (скажем, множество действительных чисел). Некоторые математики – конструктивисты – не признают «голых теорем существования», т.е. теорем, не дающих способа построения объекта, а лишь доказывающих существование этого объекта. Вместе с тем большинство математиков признаёт аксиому выбора и вытекающие из неё утверждения и считает её частью математического знания, источником получения других результатов.

Далее мы увидим, что с помощью аксиомы выбора, леммы Цорна и теоремы Цермело можно доказать некоторые утверждения, доказательство которых другими методами не-

37

известно. В частности, сейчас мы докажем, что любые два множества сравнимы по мощности.

Теорема 2. Для любых двух множеств A и B справедливо хотя бы одно из следующих соотношений: | A | | B |, | B | | A |.

Доказательство. Ввиду теоремы Цермело мы можем считать, что A и B вполне упорядочены. По теореме 1 одно из множеств А, В изоморфно начальному отрезку другого. Если A изоморфно начальному отрезку множества B, то | A | | B |, если наоборот, то

| B | | A |.

Теорема 3. Пусть A – бесконечное множество мощности m. Тогда: (а) A можно разбить на два непересекающихся подмножества, мощность каждого из которых равна m; (б) A можно разбить на m непересекающихся двухэлементных подмножеств.

Доказательство. Ввиду теоремы Цермело мы можем считать, что множество A вполне упорядочено. Пусть a0 min A. Назовём элемент a A предельным, если у него нет предыдущего элемента (т.е. такого элемента a a, что между a и a нет других элементов множества A), и непредельным, если предыдущий элемент есть. Будем обозначать предыдущий элемент через a 1, а последующий – через a 1. Если множество A имеет максимальный элемент u, то рассмотрим элементы u 1,u 2, Так как в A нет бесконечных убывающих цепей, то при некотором натуральном n элемент u n b будет яв-

ляться предельным. Переупорядочим элементы множества				A, «отправив»			элементы
b,b 1, ,b n в начало этого множества, т.е. будем считать,				что b b 1 b n a0.
Очевидно, множество A останется вполне упорядоченным.				Но теперь у него нет наи-
большего элемента. Отсюда следует,	что	A является объединением непересекающихся
счётных подмножеств Ac {c, c 1, c 2, , c n, },			где c – предельный элемент. Итак,
A {Ac | c – предельный}.	Положим		Ac {c, c 2, c 4, , c 2n, },
			предельный},				| c – пре-
Ac {c 1, c 3, c 5, , c 2n 1, },	A {Ac | c –				A	{Ac
дельный}. Мы имеем разбиение множества A на два подмножества							мощности
					A	и A ,

которых равны m (нетрудно установить взаимно однозначное соответствие между множествами A и A , A и A ). Тем самым доказано утверждение (а). Доказательство утверждения (б) осуществляется аналогично – двухэлементными подмножествами здесь будут {c, c 1},{c 2, c 3}, , где c – предельный элемент.

Следствие 1. Если m – бесконечная мощность, то m m m, 2 m m (объедине-

ние двух непересекающихся множеств мощности m имеет мощность				m),	m 2 m
(объединение m непересекающихся двухэлементных множеств имеет мощность m).
Следствие 2. Если m и n – бесконечные мощности, то
m n max (m,n).
Доказательство.	Пусть, например, m n.	Ввиду	следствия	1	получим:
n m n n n n, откуда m n n.
Следствие 3. Пусть A и B – бесконечные множества (возможно, пересекающиеся).
Тогда | A B | max (| A |, | B |).
Доказательство.	Пусть, например, | A | | B |. Тогда | B | | A B | | A | | B | | B |, от-
куда следует, что | A B | | B |.
Следствие 4. Если A – бесконечное множество,		B – множество такое, что | B | | A |,
то | A \ B | | A | .
Доказательство. Можно считать, что B A. Утверждение очевидно, если множество
B конечно. Пусть B бесконечно. Если предположить, что |			A \ B | | A |, то мы получим:
| A | | A \ B | | B | max (| A \ B |, | B |) | A | – противоречие.
	38

2.2.3.Примеры решения задач

1.Доказать, что всякое линейное пространство имеет базис.

Доказательство. Напомним, что базисом линейного пространства L над полем F называется такое множество B (необязательно конечное), что всякий вектор x L является линейной комбинацией x 1b1 nbn , где i F,bi B. Рассмотрим множество

X всех линейно независимых (необязательно конечных) подмножеств S пространства L.

Это множество		является частично упорядоченным обычным включением					. Пусть
{S | }		– цепь в X. Положим S {S | }. Проверим, что S X ,					т.е. S ли-
нейно независимо. Действительно, пусть 1s1 nsn 0, где s1, , sn S и не все								i
равны 0. Так как S S ,			то si S i при некоторых i. Так как – цепь, то среди					S i
есть наибольшее по включению. Скажем, S S i						при i 1, , n. Тогда s1, , sn S и
1s1 nsn	0. Так как		S	линейно независимо, то 1 n 0 – противоречие.
Мы доказали,	что S S .			Очевидно, S является мажорантой цепи . Таким обра-
зом, множество		X удовлетворяет условиям леммы Цорна, а потому Х содержит макси-
мальный элемент B. Итак,			B – максимальное (по включению) линейно независимое под-
множество. Докажем, что			B – базис.		Пусть x L.	Если x B, то x выражается через
элемент из B :		x 1 x. Если x B, то			B {x} B,	значит, B {x} – линейно зависимая

система. Так как B линейно независимо, то x линейно выражается через элементы из B. 2. Доказать, что всякое ненулевое кольцо с единицей имеет максимальный идеал, не

совпадающий со всем кольцом.

Доказательство. Пусть R – кольцо с единицей. Рассмотрим идеалы I кольца R такие, что I R. Такие идеалы существуют, например, I 0. Эти идеалы образуют по

включению частично упорядоченное множество

X. Пусть {I | } – цепь в

X.

Так как – цепь, то I I – идеал кольца R.

Если I R,

то

1 I, а значит, 1 I при

некотором . Но тогда

I R,

а это противоречит условию

I X . Таким образом,

I R,

следовательно, I

– мажоранта цепи .

Множество

X

удовлетворяет условиям

леммы Цорна, поэтому в

X есть максимальный элемент I0.

Ясно, что I0 и есть макси-

мальный идеал, отличный от R.

3.

Доказать, что в любом частично упорядоченном множестве частичный порядок

может быть продолжен до линейного.

Доказательство. Пусть A

– множество, на котором задан частичный порядок

.

Пусть X – множество всех частичных порядков на A таких,

что . Множество X

частично упорядочено отношением включения . Пусть { | } – цепь в

X.

Пусть – объединение цепи элементов . Проверим,

что если каждое

– от-

ношение порядка, то – тоже. Пусть

a A. Так как рефлексивно, то (a,a) ,

по-

этому

(a, a) , т.е.

рефлексивно.

Докажем

его транзитивность. Пусть (a,b) и

(b,c) . Тогда (a,b)

, (b,c)

при некоторых , . Так как – цепь, то

или

.

Пусть, например,

. Тогда

(a,b), (b,c)

. Ввиду транзитивности

отношения

получим:

(a,c) .

Но ,

поэтому (a,c) . Таким образом, отно-

шение транзитивно. Антисимметричность отношения доказывается аналогичным образом. Следовательно, – отношение порядка.

39

Итак, в множестве X каждая цепь {

| } имеет мажоранту

. Поэтому

по лемме Цорна X имеет максимальный элемент .

Докажем, что максимальный порядок

обязательно является линейным. Действительно, пусть

a,b A – не сравнимые относи-

опре-

тельно элементы, т.е. (a,b) и (b, a) . Продолжим порядок до порядка ,

транзитив-

делённого следующим образом: {(x, y) | x a, y b}. Рефлексивность,

Значит,

ность и антисимметричность отношения

проверяются непосредственно.

действительно является отношением порядка.

Так

а

это

как (a,b) \ ,

то ,

противоречит максимальности порядка . Значит, – линейный порядок.

Кроме того,

,

т.е. является продолжением порядка .

2.2.4. Задачи для самостоятельного решения

1.

(а) Доказать, что если G – группа и a G, то существует в группе G максималь-

ная (по включению) подгруппа, не содержащая элемента a.

(б) Верно ли, что в любой группе G есть максимальная подгруппа H G ?

Ответ: (б) Нет. Например, группа

p

–

объединение

цепочки

групп

p p2 p3 ... – такова, что все её подгруппы, отличные от неё самой, конечны и ни

одна из них не максимальна.

Назовём антицепью множество элементов частично упорядоченного множества, которые попарно не сравнимы друг с другом. Доказать утверждения:

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

(по включению) цепь (теорема Куратовского – Хаусдорфа);

(б) всякое частично упорядоченное множество содержит максимальную антицепь.

2.Доказать, что всякий связный граф (не обязательно конечный) содержит максимальное дерево.

3.Подмножество B линейно упорядоченного множества A назовём конфинальным, если a A b B b a. Доказать, что всякое линейно упорядоченное множе-

ство содержит конфинальное вполне упорядоченное подмножество.

4. Будем говорить, что частично упорядоченное множество удовлетворяет условию минимальности, если в нём нет бесконечных убывающих цепей x1 x2 x3 ... элементов. Доказать, что множество удовлетворяет условию

минимальности в том и только в том случае, если все его цепи вполне упорядочены.

5.Пусть A – частично упорядоченное множество, в котором каждая цепь имеет мажоранту. Доказать, что для любого a A в множестве A есть максимальный элемент p такой, что p a.

6.Пусть A – множество и a,b – какие-либо его различные элементы. Доказать, что

существует максимальное (по включению) отношение эквивалентности на A такое, что (a,b) . Сколько классов эквивалентности имеет отношение ?

Ответ: два.

2.3. Кардинальные и ординальные числа

2.3.1. Ординальная арифметика

Порядковым типом вполне упорядоченного множества A называется совокупность всех вполне упорядоченных множеств, изоморфных множеству A.

40

Порядковый тип вполне упорядоченного множества называется также ординальным (или порядковым) числом или просто ординалом. Ординальные числа, соответствующие конечным вполне упорядоченным множествам, обозначаются 0,1,2, (их можно отождествить с натуральными числами). Например, 3 – это порядковый тип, соответствующий трёхэлементной цепи a b c (очевидно, все трёхэлементные цепи изоморфны между собой). Наименьшее бесконечное ординальное число – это порядковый тип множества натуральных чисел. Оно обозначается символом .

Введём отношение порядка среди ординалов. Пусть , – ординалы, а A, B – соответствующие им вполне упорядоченные множества. В предыдущем разделе было доказано, что либо множество A изоморфно начальному отрезку множества B, либо наоборот. Если множество A изоморфно начальному отрезку множества B, то считаем .

Докажем следующие свойства ординалов:

(1) ; (2) , ; (3) , .

Доказательство. Свойство (1) очевидно. Пусть теперь и			. Тогда сущест-
вуют изотонные (т.е. сохраняющие порядок) вложения : A B и			: B C такие, что
(A)	– начальный отрезок в B, а (B)	– начальный отрезок	в C. Произведение
:	A C является изотонным вложением	A в C, а ( )(A) ( (A)) – начальным от-

резком множества C. Значит, , т.е. выполнено (2). Осталось доказать свойство (3). Пусть : A B и : B A – изотонные вложения, причём (A) – начальный отрезок в B, а (B) – начальный отрезок в A. Произведение : A A является изотонным вложением. По следствию из леммы предыдущего раздела получаем, что – тождественное отображение. Аналогично доказывается, что – тождественное отображение. Значит, (A) B и – изоморфизм, поэтому .

Как обычно, мы считаем, что , если и . Например, 3 5, 2 3, 6 . Понятно, что из , следует .

Введём теперь операцию сложения двух ординалов.

Пусть и – ординалы, а A и B – соответствующие им вполне упорядоченные множества. Будем считать, что A B . Введём на множестве A B порядок, положив, что на A и B порядок прежний и, кроме того, a b при a A, b B. Ясно, что A B вполне упорядочено. Его порядковый тип называется суммой .

Легко видеть, что 2 3 5, 1 , 1 (множество 1 имеет максимальный элемент, а не имеет. Таким образом, в общем случае.

Закон ассоциативности ( ) ( ) имеет место для любых ординалов. Для доказательства рассмотрим вполне упорядоченные множества A, B,C, соответствующие ординалам , , . Будем считать, что они попарно не пересекаются. Тогда множество

A B C (где a b c при a A, b B,	c C) соответствует как числу ( ) , так и
числу ( ). Значит, ( ) ( ).
Пусть , – ординалы, соответствующие вполне упорядоченным множествам				A, B.
Произведением называется порядковый тип лексикографического произведения				A B
(напомним, что (a,b) (a ,b ), если либо a	a , либо a a		&b b ).
Нетрудно видеть, что 2 ,	2 . Следовательно, в общем
случае. Однако ассоциативность ( ) ( )		имеет место для любых ординалов –

это следует из легко проверяемого изоморфизма (A B) C A (B C). Важное свойство ординалов даёт следующая теорема.

Теорема 1. В любом множестве ординалов есть наименьший элемент.

41

Доказательство. Пусть X { | I} – множество ординалов. Обозначим через A

вполне упорядоченное множество, соответствующее ординалу . Возьмём какое-либо

A 0	и удалим из рассмотрения все A , которые не изоморфны начальным отрезкам мно-
жества A 0		. Будем отождествлять множество A с его изоморфным образом, т.е. считать,
что	A –	начальный отрезок A 0 . Для каждого такого,	что	A	A 0 , положим
a min(A 0 \ A ). Затем выберем наименьший элемент из этих			a :	a	min{a | I}.

Легко видеть, что – наименьший ординал в множестве X.

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

Например, 1, 2, 1, 2 3 – непредельные ординалы, а , , 3 – предельные. Каково бы ни было ординальное число , существует число, непосредственно следующее за ним – это число 1. Нетрудно проверить, что ординал является предельным в том и только в том случае, если он не имеет непосредственно предшествующего, т.е. не представим в виде 1, где – некоторый другой ординал.

Теорема 2. Всякий ординал представим в виде k, где – предельный ординал или 0, а k – натуральное число или 0.

Доказательство. Если , то утверждение теоремы очевидно. Пусть . Рассмотрим вполне упорядоченное множество A, соответствующее ординалу . Если A не имеет максимального элемента, то – предельный ординал, и он представим в виде0. Если A имеет максимальный элемент a1, то рассмотрим множество A \{a1}. В

этом множестве обозначим максимальный элемент (если он есть) через a2. Затем рас-

смотрим множество A \{a1, a2} и т.д. Так как a1 a2 a3 ... и A вполне упорядочено, то эта цепь конечна. Значит, при каком-то k множество A \{a1, , ak } не содержит макси-

мального элемента. В этом случае k, где – предельный ординал.

Теорема 3. Каково бы ни было множество ординалов { | I}, существует ординал

такой, что при всех I.

Доказательство. Рассмотрим вполне упорядоченные множества A , соответствую-

щие ординалам . Пусть A A и B 2A. Тогда | B | | A | при всех . Следователь-

но, порядковый тип множества B (вполне упорядоченное каким-нибудь отношением порядка) больше всех .

Замечание. Если в теореме 3 мы возьмём «множество всех ординалов», то получим странное утверждение: ординал больше любого ординала вообще, а значит, больше самого себя: , что невозможно. Борьба с этим противоречием осуществляется следующим образом: все ординалы не образуют множества. Итак, мы запрещаем такие «множества», как «множество всех множеств», «множество всех ординалов», «множество всех линейных пространств» и т.д.

Теорема 4. Если X { | I} – множество ординалов, то существует sup X.

Доказательство. По теореме 3 существует ординал такой, что при всех .

Мы можем теперь рассмотреть вполне упорядоченное множество B, соответствующее

ординалу , и считать множества			A ,	соответствующие ординалам , начальными от-
			A	– также начальный отрезок множества B. Пусть
резками множества B. Тогда A
						sup X .
		– порядковый тип множества A . Ясно, что
				42

2.3.2. Трансфинитная индукция

Оказывается, что принцип математической индукции, в которой аргумент пробегал множество натуральных чисел, может быть существенно обобщен с натуральных чисел на ординальные. Этот обобщённый принцип называется трансфинитной индукцией. Дадим точные формулировки.

Принцип трансфинитной индукции. Пусть – некоторое свойство ординальных чисел. Предположим, что наименьший ординал 0 обладает свойством и для каждого ординала , если все обладают свойством , то обладает свойством . Тогда свойством обладают все ординальные числа.

Доказательство. Пусть верно не для всех ординалов . Тогда существует наименьший ординал 0 , для которого неверно. Так как 0 – наименьший, то все 0

обладают свойством . Но тогда и 0 обладает свойством , что противоречит выбору

0.

2.3.3. Кардинальные числа (мощности)

Кардинальным числом (или кардиналом) называется наименьший ординал заданной мощности.

Заметим, что по теореме 1 в любой совокупности ординалов есть наименьший, поэтому наше определение корректно.

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

.

Некоторые из ординальных чисел являются мощностями, некоторые – нет. Например, все натуральные числа 0, 1, 2, ... – мощности, – мощность. Однако 1, 2, не являются мощностями. Нетрудно видеть, что всякая бесконечная мощность является пре-

дельным ординалом. Действительно, пусть – бесконечный непредельный ординал. Тогда 1 для некоторого . Так как бесконечен, то ~ . Значит, не может быть мощностью.

Пусть и – ординальные числа. Определим с помощью трансфинитной индукции

число . А именно, положим 0 1, 1 ,	sup{ | ]				для предельного
ординала . Таким образом мы можем построить ординалы 2			, ,			и т.д.

Теорема 5. В любой совокупности каких-либо множеств есть множество, наименьшее

по мощности.
Доказательство. Пусть {A | }			– совокупность множеств A и { | } – их
мощности. Тогда по теореме 1 среди			есть наименьшее. Соответствующее множество
A будет иметь наименьшую мощность.
Ранее мы видели, что ,			c c c. Оказывается, что аналогичное равенство

справедливо для любой бесконечной мощности.

Теорема 6. Если m – бесконечная мощность, то m2 m.

Доказательство. Нам надо фактически доказать, что | A A | | A | для любого бесконечного множества A. Предположим, что это не так. Тогда по теореме 5 существует множество A наименьшей мощности такое, что | A A | | A |. Ввиду теоремы Цермело мы можем считать, что множество A вполне упорядочено. Рассмотрим начальные отрезки B

43

множества A,

удовлетворяющие условию | B B | | B |. Такие отрезки существуют,

на-

пример, отрезок, изоморфный натуральному ряду .

Для каждого такого начального от-

резка B

есть взаимно однозначное отображение : B B

B . Рассмотрим множест-

во пар U {(B , ) | }

и введём на нём отношение порядка, положив (B, ) (B , ),

если B B и |B .

Проверим, что множество U удовлетворяет условиям леммы Цор-

на. Действительно, пусть

{(B , ) | } – цепь в

U.

Положим

B {B | },

f : X Y Z мы рассматриваем здесь как подмножество

{ | } (отображение

множества X Y Z). Тогда

B

B

B

:

взаимно однозначно и (B

, ) – мажоранта

цепи U. Итак,

множество U удовлетворяет условиям леммы Цорна. Следовательно, в

множестве U существует максимальный элемент

(B, ).

Здесь : B B B – взаимно

однозначное отображение.

Так как | B B | | B |, то | B | |

A |,

поэтому | A \ B | | A | (см. следствие 4 из теоремы 3

раздела 2.2). Очевидно, A \ B – вполне упорядоченное множество, большее по мощности,

чем B,

поэтому

A \ B

имеет

начальный

отрезок

Пусть

Тогда

C B B .

Ввиду наличия взаимно однозначного ото-

C C (B B) (B B ) (B

B) (B

B ).

бражения все четыре скобки равномощны множеству

B. Следовательно, существует

что

взаимно однозначное отображение : (B B ) (B

B) (B

B ) B . Это означает,

:C C C – взаимно однозначное отображение, продолжающее

. Но

(B, ) –

максимальный элемент, а (C, ) (B, ).

Мы получили противоречие. Тем самым ус-

тановлено, что | A A | | A |.

Определим теперь для каждого порядкового числа мощность .

Воспользуемся

трансфинитной

индукцией.

Положим

(это

известно

из

предыдущего),

min{m | m }, а если – предельный ординал, то sup{ | }.

Вопрос о том, верно ли равенство c, является достаточно тонким. Предположе-

ние о том, что c, называется гипотезой континуума (continuum hypothesis). Часто эту гипотезу формулируют немного иначе:

(СН) Континуум-гипотеза: не существует мощности m, удовлетворяющей условию

m c.

Следующее утверждение является усилением континуум-гипотезы.

(GCH) Обобщённая континуум-гипотеза: каково бы ни было ординальное число ,

не существует мощности m, удовлетворяющей неравенству m .

Гипотеза континуума была сформулирована ещё в XIX веке Г.Кантором. Многие математики XIX-XX веков пытались её решить, но попытки оказывались неудачными. Лишь в 1964 году американскому математику Дж.Коэну удалось решить эту проблему. Ответ оказался неожиданным: гипотезу континуума невозможно ни доказать, ни опровергнуть.

Точнее говоря, из аксиом теории множеств (аксиом Цермело – Френкеля) не следует ни утверждение СН, ни его отрицание СН. Таким образом, не боясь получить противоречие, можно развивать любую из «двух теорий множеств»: ту, в которой принимается СН, или ту, в которой принимается СН. Ситуация здесь в точности такая, как в геометрии: геометрия Евклида постулирует единственность параллельной прямой, а геометрия Лобачевского требует наличия по крайней мере двух прямых, проходящих через данную точку и параллельных данной прямой. Обе геометрии непротиворечивы. Аналогичное утверждение справедливо и для обобщённой гипотезы континуума.

44

2.3.4. Примеры решения задач

1. Доказать, что для любых ординалов , , справедливо равенство

( ) .

Доказательство. Будем отождествлять ординал со вполне упорядоченным множест-

вом, соответствующим	этому ординалу. Построим отображение : ( )
следующим образом. Если u ( p, x), где		p ,	x , то
(a, x), если	p a ,
(u)	p b .
(b, x), если

Очевидно, – взаимно однозначное отображение. Проверим, что сохраняет поря-

док. Пусть u v. Положим, что u ( p, x),		v (q, y). Тогда (u) ( p, x) ,
(v) (q, y) . Мы имеем: либо p q,		либо p q & x y. Если p q и p,q ,
то (u), (v) , и (u) (v) по определению лексикографического порядка. Анало-
гично рассматривается случай, когда p q и		p,q .		Если же p q	и p , q , то
(u) , (v) , поэтому (u) (v). Пусть теперь				p q & x y. Тогда (u) ( p, x),
(v) ( p, y), откуда легко следует, что (u) (v).
2. Привести пример ординалов , , ,	для которых ( ) .
Решение. 2 ( 1) – это объединение	двух множеств 1, следующих друг за дру-
гом. Поэтому 2 ( 1) ( 1) ( 1)	(1 ) 1 1,				в то время как
2 2 1 2. Очевидно, 1 2			(так как 1 – начальный отрезок
множества 2).
3. Доказать изоморфизм абелевых групп и

Доказательство. Группу можно рассматривать как линейное пространство над полем . Выясним, какую размерность имеет это пространство, т.е. какова мощность его

базиса. Пусть	B – базис пространства	над полем	и | B | m.	Так как | | и
m m, то	мощность множества	всех линейных	комбинаций	b ... b , где
				1 1	k k
i , bi B,	равна m. Итак, | | m. Ясно, что пространство имеет такую же
мощность базиса, что и . Взаимно однозначное соответствие между базисами продол-
жается до изоморфизма линейных пространств. Значит,			как линейные про-

странства, а следовательно, и как абелевы группы. Заметим, что как кольца и не изоморфны (это ясно хотя бы потому, что – поле, а – нет).

4. Какому начальному отрезку множества 3						изоморфно множество 2 ?
Решение. 3	{(a,b,c) | a,b,c {0}}, 2				{(a,b) | a,b {0}}. Так как сравнение
строчек A , (a,b)				2	(a,b,c)			3
		и (a ,b )		в , а также			и (a ,b ,c )	в осуществляется
слева направо, то естественно рассмотреть в 3						подмножество {(0,b,c) | b,c {0}},
Оно и будет начальным отрезком, изоморфным 2.
5. Какой порядковый тип имеет множество 2 ?
Решение. 2 sup{2n | n } .
6. Доказать,	что	для		ординальных		чисел	имеют	место	импликации
,			.			Привести пример таких			, , , что
, но .

Решение. Так как , то можно	множество считать начальным отрезком множе-
ства , отличным от . Отсюда ясно,	что – начальный отрезок множества , не
совпадающий с . Таким образом,	. Для доказательства второй имплика-
ции будем вкладывать множество		в , т.е. рассматривать изоморфизмы
		45