И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 7

Показать, что (а*)'=а для любого порядкового типа а„ 19. Показать, что л' = л, су' = су, Л' = Л, в* ,-4 в. 20. Доказать, что: (а) для любых порядковых типов а и )5 супсествуют и однозначно определены порядковые типы а+8 и а ф; (б) для любого линейно упорядоченного множества 2 и любого семейства порядковых типов (а,). существует н однозначно определен порядковый тип ~~с а,. иву 21. Привести пример порядковых типов а и )5 таких, что а+сбм)8+а. 22.

Доказать, что: (а) а+ ф+у) = (а +уз) +у; (б) а + О = О + а = а; (в) 2 + 3 = 5; (г) 1 + в = в, нов + 1 в в; (д) в + в = л; (е) су + су = су; (ж)Л+ 1+Л =Л; (з)Л+ЛФЛ; (и) 1+Л+ 1 естьпорядковыйтипсегмента (а, Ь)при а<Ь. 23. Привести пример порядковых типов а и)5 таких, что а р' в уу ° а.

24. Доказать, что: (а) а ф у)=(а )5) у; (б) а О = О а = О; (в)а.1 = 1 а = а; (г) 2 2 = 4; г (д) су =% (е) в.су и в (су+1). 25. Построить множества порядковых типов в, в, в, ... 2 3 4 26. (а) Доказать, что для любых порядковых типов а, )5 и у а ф+у) = а )5+а у. (б) Привести пример порядковых типов а, р и у таких, что (а+)5) у и а у+)3 у. ЧЛ. ТЕОРИЯ МНОЖЕСТВ 27. Пусть У и 1 — линейно упорядоченные множества, (В,) . ! (Е1 семейство попарно непересекающихся подмножеств множества Х такое, что () В. = Х. Доказать, что если Х = '>' В., то для любого се- 1 !Е1 (Е1 .«-- Р«.-., ь.) ...-.~..-~ (~.,). 1 ?Е1 I 1Е1 (Е1 1ЕВ, 28.

Доказать, что а ф = ~~> а, где аЬ = а для всех ЬЕВ и В = ф. ЬЕВ 29. Доказать, что: (а) (а + (9) = р + а; (б) (а.ф)' = а' ф'; (х.) -х.;-"-- -" ------' (Е1~ а) есть множество1с двойственным порядком. 30. Доказать, что: (а) всякое конечное линейно упорядоченное множество вполне упорядочено; (б) множество Ф', где Ос!<2<..., вполне упорядочено; (в) множество «К, где 0<2<4с...<1с3<5<..., вполне упорядочено; (г) множество Ф', где ...<3<2с1сО, не является вполне упорядоченным. 31.

Являются ли вполне упорядоченными следующие множества: (а) множество Я' целых чисел с их естественным порядком; (б) множество У рациональных чисел с обычным порядком «; (в) множество У действительных чисел с обычным порядком «; 1 (г) множество чисел вида 1 — —, где л — положительное целое л' число, с обычным порядком «? 32. Доказать, что: (а) всякое непустое вполне упорядоченное множество имеет наименьший элемент; (б) каждое подмножество вполне упорядоченного множества вполне упорядочено. 33. Доказать, что если А — В и А вполне упорядочено, то В можно вполне упорядочить так, чтобы было А В. 34. Показать, что если А — вполне упорядоченное множество, то у каждого элемента множества А, кроме наибольшего, имеется непосредственно следующий за ним элемент (см. задачу 11).

1 5. ОРдинлльные числА 41 35. Можно ли во вполне упорядоченном множестве выделить бесконечную убывающую цепь элементов х >х >х >...? Эб. Доказать, что линейно упорядоченное множество вполне упорядочено тогда и только тогда, когда оно не содержит подмножества типам . 37. Пусть А — вполне упорядоченное множество. Доказать, что не сугдествует такого монотонного взаимно однозначного соответствия у: А- А, чтобы для некоторого элемента аЕА былоу(а)<а. 38. Доказать, что вполне упорядоченное множество не может быть подобным своему отрезку или часги своего отрезка. 39.

Доказать, что два различных отрезка вполне упорядоченного множества не могут быть подобными. 40. Доказать, что существует не более одного изоморфизма двух вполне упорядоченных множеств. 41'. Доказать, что из двух вполне упорядоченных множеств одно подобно другому нли его отрезку. 42. Доказать, что линейно упорядоченное множество конечно тогда и только тогда, когда оно вполне упорядочено относительно заданного н относительно двойственного порядков.

43. Пусть А — вполне упорядоченное множество, В~А и для любого элемента хЕА множество В удовлетворяет условию: если А СВ, то х хЕВ. Доказать, что В=А (принцип трансфинитной индукции). 44. Пусть а, )5 — произвольные порядковые числа. Доказать, что: (а) акр'или)5<аилиа =)5; (б) из указанных выше условий выполняется для а и)5 лишь одно.

45. Пусть Ь' = ()5 ~ )5(а), где а и р — порядковые числа. Показать, что)г =а. а 46. Доказать, что всякое множество порядковых чисел вполне упорядочено. 47. Доказать, что для любого множества порядковых чисел 5: (а) существует порядковое число, большее всех чисел нз 5; (б) среди порядковых чисел, не принадлежащих множеству Я, существует наименьшее. 48. Доказать, что не существует множества, содержащего все порядковые числа. 49. Доказать, что а+1 есть порядковое число, непосредственно следующее за а (см. задачу 11). 50.

Доказать, что для любого порядкового числа а имеет место одно и только одно из утверждений: 1) а=О; 42 ЧЛ. ТЕОРИЯ МНОЖЕСТВ 2) множество ф ! ф — порядковое число иф<а) имеет максимальный элемент; 3) а — предельное порядковое число. 51 . Доказать, что любое порядковое число представимо в виде а+и, где а есть предельное порядковое число или О, л — натуральное число. 52. Доказать, что: (а) сумма двух порядковых чисел есть порядковое число; (б) произведение двух порядковых чисел есть порядковое число; (в) упорядоченная сумма порядковых чисел, где множество индексов вполне упорядочено, есть порядковое число.

53. Пусть | и (А.). линейно упорядочены. Доказать, что если 1 1НУ А. -е и, У А.есть порядковое число, то 2 и все А.вполне упорядочены. 1 И! 54. Доказать, что: (а) если А и В вполне упорядочены и АСВ, то А«В; (б) а < а+ у, а<у+а; (в) а <)5» у+ а < у+ф; (г)а<ф» а+у<ай+у; (д) у + а» у + р» а =,В; (е) а+ у <ф+ у» а <)5.

55. Привести пример порядковых чисел а, ф и у таких, что амит и а+у»ф+у. 56. Доказать, что; (а)а«ф» а.у(ф у; (б) а<ф» у а<у ф, если ум0; (в) у а<у ф» а<ф; (г) у.а=у.ф» а=р', если у~0; (д) а у<ф у» а<ф. 57. Пусть р «а. Порядковое число у называется разностью а и ф и обозначается через а-ф, если а=ф+у. Доказать, что: (а) а — ф существует и единственно; (б)у«ф<а» р — у<а — у; (в)у<ф<а» а — ф<а — у; (г))5<а» у (а — ф)=у а — уф. 5(). Доказать, что: (а) еслиа1+ф = а +ф иф <ф1, тоа <а; (б)«если у<а)5, то существуют и единственны такие д и е, что 5<а, е<ф и у=а е+д; (в) еслибы>0, то для любого а существуют и единственны такие у и д, что д<ф и а = ф у + д (теорема о делении с остатком). 1 з. ОРдинАльные числА 43 59. Доказать, что для любых порядковых чисел ао и ан если а мО и а, ы О, то существуют натуральное число и и порядковые числа а, ..., а, Ц,рг, ...,р такие, чтоа >а »...а >О и ае=а, Р)+аг а)=аг Рг+аа'"'*а -г=а — 'Р— +а а — =а 'Ф (алгоритм Евклида) .

60. Пусть свойство Р таково, что для любого ординального числа а из того, что все ординальные числа )5<а обладают свойством Р, следует, что а обладает свойством Р. Доказать, что все ординальные числа обладают свойством Р (принцип трансфинитной индукции для ординальных чисел). 61. Доказать, что для любых порядковых чисел а и)5 существует и единственно а ~. 62. Построить множество порядкового типа и! . 63'.

Доказать, что: (а) еслна<)у ну>1, тоуа<у)); (б) а в+У=а Р аг; (в) (ар)у=ар г 64'. Доказать, что: (а) если щг = а + )5 и )5 ««О, то)5 = в!г; (б) если а>1 и)5>1, то а!'>а )5; (в) если а >1 и)5> 1, то существуют и однозначно определены с, у и д такие, что )у=а» у+д и у<а, д<а»; (г) если у>1 и 1<а<у, то существуют натуральное число и и такие последовательности порядковых чисел р(, рг, ..., р и д, д,... ь ..., д, что н а = у ! )5, + у ! )52 + " + у 'дн 3 3 3 д>д >д »...д и 0<)5.<у для ! = 1,2, ...

! 2 65'. Множество Я называется транзитивным, если отношение Х< У «ь (Х= У илн ХЕ У) вполне упорядочивает Я, !аЕЯ и если из ХЕУ, УЕЯ следует ХЕЯ. Доказать, что для любого порядкового числа а>0 существует и единственно транзитивное множество, упорядоченное по типу а. Ч.!. ТЕОРИЯ МНОЖЕСТВ 44 66 . Следующее утверждение называется аксиомой выбора. (1) Аксиома выбора.

Пусть Х вЂ” непустое множество для любого а а~А. Тогда существует функция выбора у', А- Г) Х такая, что асл У(а)ЕХ для любого аЕА. Доказать, что каждое из следующих утверждений эквивалентно аксиоме выбора. (2) Лемма Цорна. Частично упорядоченное множество, каждое из линейно упорядоченных подмножеств которого имеет верхнюю грань, содержит максимальный элемент. (3) Принцип максимальности Куратовского — Хаусдорфа.

Каждая цепь частично упорядоченного множества содержится в некоторой максимальной цепи. (4) Аксиома Цермело. Для любого семейства Я непустых попарно непересекающихся множеств существует такое множество С, что АПС для каждого АЕЯ состоит ровно из одной точки. (5) Теорема Цермело.

Каждое множество можно вполне упорядочить. (6) Лемма Тейхмюллера — Тычки. Каждое семейство множеств, имеющее конечный характер, обладает максимальным элементом. !Семейство Я множеств имеет конечный характер, если оно удовлетворяет условию: ХЕЯ «» каждое конечное подмножество множества Х принадлежит Я.) 67. Пусть А — частично упорядоченное множество, в котором каждая цепь имеет верхнюю грань, и аЕА. Доказать, что существует максимальный элемент тЕА такой, что тра. 68.

Пусть А — множество подмножеств множества В такое, что для каждой цепи С (порядок по включению) объединение множеств из С принадлежит А. Доказать, что тогда А имеет максимальный элемент. 69'. Доказать, что для всякого частичного порядка А на множестве А существует линейный порядок 2, на множестве А такой, что )сС2.. $ б. ДЕЙСТВИЯ НАД КАРДИНАЛЬНЪ|МИ ЧИСЛАМИ Кардинальное число щ называется суммой кардинальных чисел и, и п и обозначается через и, + и, если каждое множество мощности щ эквивалентно объединению двух непересекающихся множеств мощностей и, и и . Аналогично, кардинальное число щ называется суммой кардинальных чисел и.