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

Докззать, что область значений этой функции конечна нлн счетна. 1 4. кАРдинАльные числА зз (б) Доказать, что непустое множество А является счетным или конечным тогда и только тогда, когда оно есть множество значений некоторой функции из,Х в А. 11. Доказать, что если из счетного мнолсества удалить конечное подмножество, то оставшееся мновсество будет счетным. 12. Доказать, что: (а) еслиА и Всчетны, тоАОВ счетно; (б) если все А. конечны, непусты и попарно не пересекаются, то ! О А.

счетно; (е т (в) если все А.счетны, то О А, счетно. ! (емт 13. Доказать, что: (а) если А бесконечно и  — конечное или счетное мнохсество, то АО — А; (б) если А бесконечно и несчетно, В конечно или счетно, то А~ — А. 14. Доказать, что если А,, ...., А (1~и) счетны, то счетно мнои жествоА,х...хА . У1' 15.

Доказать, что: (а) множество целых чисел счетно; (б) множество рациональных чисел счетно; (в) множество рациональных чисел сегмента [а, Ы счетно при а<Ь; (г) множество пар (х, у), где х и у — рациональные числа, счетно. 16. Доказать, что множество всех конечных последовательностей, составленных из элементов некоторого счетного мноасества, есть счетное множество. 17. Доказать, что множество всех конечных подмножеств счетного множества счетно.

18. Доказать, что множество многочленов от одной переменной с целыми коэффициентами счетно. 19. Доказать счетность множества алгебраических чисел, т. е. чисел, являющихся корнями многочленов от одной переменной с целыми коэффициентами.

20. Доказать, что любое множество попарно непересекающихся открытых интервалов на действительной прямой не более чем счетно. 21 . Доказать, что мощность любого множества попарно непересекающихся букв Т на плоскости не более чем счетна. 2 И.А. Лавров, Л.Л.

Максимова чл. твогия множвств 22. Доказать, что если АС У и существует д >О такое, что для всех различных элементов х, у из А справедливо 1х — у) ~д, то А конечно или счетно. 23. Доказать, что множество точек разрыва монотонной функции на действительной оси не более чем счетно. 24. Доказать, что: (а) (0,1) — [О, 1 1 - [О, 1 [ — [О, 1); (б) [а, Ь1 — [с, а1, где а<Ь, с<Н; (в) [а, Ь[ — У.

25. Доказать, что множества точек квадрата и отрезка эквивалентны. 26. Доказать, что множества точек двух окружностей эквивалентны. 27. Доказать, что У" — У~ (1 <л, л!). 28. Установить взаимно однозначное соответствие между точками квадрата и плоскости. 29*. Доказать, что множествоточек сегмента [О, 11несчетно. 30. Какова мощность множества иррациональных чисел? 31, Доказать существование трансцендентных (неалгебраическнх) чисел.

32. Доказать, что обьединение конечного или счетного числа множеств мощности с.имеет мощность с. 33 . Доказать, что множество всех счетных последовательностей натуральных чисел имеет мощность с. 34. Доказать, что: (а) множество всех счетных последовательностей, составленных из О и 1, имеет мощность с; (б) Р( )Тг) )с.

35. Доказать, что: (*) т.= ! (а!,* л Г зэ"-д ! 1 "' в (б) если А.= сдля всех !!=.(и1= с, тоП А.= с. ! 1е! 36. Какова мощность множества: (а) всех счетных последовательностей действительных чисел; (б) всех непрерывных функций на действительной прямой; (в) всех монотонных функций на действительной прямой? 5 5. ОРДИНАЛЬНЫЕ ЧИСЛА 35 37. Пусть А — счетное множество точек на действительной прямой.

Можно ли выбрать а так, чтобы (х + а [ хЕА[()А = и? 38 . Доказать, что множество действительных функций, заданных на сегменте [О, 1 [, имеет мощность, большую с. 39. Доказать, что мощность множества всех функций, определенных на сегменте [а, Ь[ при а < Ь и разрывных хотя бы в одной точке, больше с. 40 . Доказать, что множество всех подмножеств Р[А) множества А имеет мощность, большую А. 41. Пусть А — семейство множеств такое, что для каждого множества А из А существует множество В из А, не эквивалентное никакому подмножеству множества А. Доказать, что объединение всех множеств из А не эквивалентно никакому подмножеству множества из А.

42. Доказать, что не существует множества, содержащего все множества. 43. Будем говорить, что последовательность натуральных чисел Ьг, Ь, ... растет быстрее, чем последовательность а, а, ..., если ан 1пп — = О. Доказать, что: и-~ 00 гг (а) для каждой последовательности натуральных чисел существует последовательность, растущая быстрее ее; (б) если множество последовательностей А обладает свойством, что для каждой последовательности а,, а, ... существует последовательность из А, растущая быстрее, чем а,, а, ... то множество А несчетно. $5. ОРДИНАЛЬНЫЕ ЧИСЛА Пусть А и  — линейно упорядоченные множества.

Множество А называется подобным В (символически А В), если А и В изоморфны как частично упорядоченные мно:кества. Порядковьгм шипом линейно упорядоченного множества А называется класс всех линейно упорядоченных множеств, подобных А, и Обозначается через 7г. Мощностью порядкового типа 7г называется А. Будем считать О порядковым типом (5. Обозначим через п порядковый тип множества 4' = (О, 1, ..., и — Ц, ЧЛ. ТЕОРИЯ МНОЖЕСТВ Зб гдеО<1« ... п — 1 ила Ф'. Обозначим через!э,л, !), (порядковые типы множеств натуральных чисел, целых чисел, рациональных чисел н действительных чисел соответственно с нх естественным порядком. Если а есть порядковый тип множества А, то через а' обозначим порядковый тип множества А с двойственным порядком. Назовем начальным отрезком, отсекаемым элементом аЕА от линейно упорядоченного множества А, множество А = (х~ хЕА,х<а).

и Пусть а н р — порядковые типы линейно упорядоченных непересекающихся множеств А и В с порядками «и «соответственно. Суммой порядковых типов а и ф называется порядковый тип множества А(.)В с порядком «, определенным следующим образом: х«У «» (хЕА,У(=В)нли(х,УЕАихи У) нлн(х.УЕВихплУ). Сумма порядковых типов а и )У обозначается через а+р. Пусть дано семейство попарно непересекающихся линейно упорядоченных множеств А.

с порядковыми типами а. н порядкамн « . соот! ! ветственно, где !ЕЕ, а 1 линейно упорядочено отношением « . Суммой порядковых типов а называется порядковый тип множества () А. с !н! ! порядком «, определенным следующим образом: х«у «» (х, у!:-А, их «удля некоторогоЫ1) илн ( хЕА., у(=А. для некоторых !, «! ! ! э Сумма порядковых типов а. обозначается через ~ аг ! !и! Пусть а ир — порядковые типы линейно упорядоченных множеств А н В с порядками «и «соответственно. 1!роизведением порядковых типов а и !д называется порядковый тип множества А хВ с порядком «, определенным следующим образом: (х! У!)ж(хз Ут) «» (У! «лУз) или(У! Утих! « ~хз)' Произведение порядковых типов а и ф обозначается через а р.

Обозначим через а" выражение (... (а а) ° ... а) (и раз). Порядковые типы вполне упорядоченных множеств называются ординальными или порядковыми числами. Если а и р — порядковые числа, то говорят, что а<ф, если любое множество А порядкового типа а изоморфно некоторому начальному отрезку множества В порядкового типа)»'; а«ф означает, что а<ф нли а=)э. 1 5. ОРДИНАЛЬНЬЩ ЧИСЛА Порядковое число а называется предельным, если а мО и а=зпрф~ р — порядковоечислоиф<а).

Возведение в степень для порядковых чисел определяется следую- щим образом; а =1, а~ =а~ а, а~ = зпр(а~ ~ $<р) для предельного порядкового числа ф. 1. Доказать, что если линейно упорядоченные множества подобны, то они и эквивалентны. 2. Доказать, что любое множество А, эквивалентное линейно упорядоченному множеству В, можно линейно упорядочить так, что А станет.

подобным В. 3. Пусть А, В, С вЂ” линейно упорядоченные множества. Доказать, что: (а) А = А (рефлексивность); (б) если А = В, то В = А (симметричность); (в) если А = В и В = С, то А С (транзитивность) . 4. Пусть А и  — линейно упорядоченные множества. Доказать, что если А =В, то А=В, но обратное неверно. 5. Доказать, что множество из и элементов можно линейно упорядочить п! способами. б.

Доказать, что все конечные линейно упорядоченные множества одинаковой мощности подобны между собой. 7. Доказать, что для бесконечных множеств утверждение предыдущей задачи неверно. 8. Доказать, что линейно упорядоченные множества подобны тогда и только тогда, когда между ними существует взаимно однозначное соответствие, являющееся монотонным отображением. 9. Доказать, что для любого линейно упорядоченного множества А и любых а, ЬЕА: (а) оЮА; '(б) если а — наименьшийэлементА, тоА = и; а (в) А — линейно упорядоченное множество„ (г) если а<В, то (А ) = А . 10.

Доказать, что множество всех отрезков линейно упорядоченного множества А, упорядоченное отношением включения, подобно А. ЧЛ. ТЕОРИЯ МНОЖЕСТВ зз 11. Доказать, что бесконечное линейно упорядоченное мнохсество А имеет порядковый тип се тогда и только тогда, когда оно удовлетворяет следующим условиям: (а) в А имеется наименьший элемент а,; (6) для любого аЕА существует точная нижняя грань а' в множестве (х ~ а < х, хЕА) (а' называется непосредственно следующим за а); (в) для любого подмножества Х множества А из того, что а ЕХ и о Х содержит вместе с каждым своим элементом непосредственно следующий за ним элемент, следует, что Х=А.

12. Доказать, что бесконечное линейно упорядоченное множество имеет порядковый тип с» тогда и только тогда, когда все его начальные отрезки конечны. 13 . Доказать, что любое счетное линейно упорядоченное множество А имеет порядковый тип с) тогда н только тогда, когда А удовлетворяет следующим условиям: (а) в А нет наименьшего и наибольшего элементов; (б) для любых х, уЕА таких, что х<у, существует зЕА такой, что х<з<у (такой порядок называется плотным).

14*. Доказать, что всякое счетное линейно упорядоченное множество подобно некоторому подмножеству множества У рациональных чисел. 15 . ПустьА — линейно упорядоченное множество, содержащее не менее двух элементов, В = А(.)А ()...(.)А"(.)... Положим для любых х,...,х,у,...,у ЕА (1жп,т) (Х,,...,Х)ж(у,...,у ) «ь (ПятИХ =у,...,Х =у)НЛН (х, =у,, ..., х, =у, х <у для некоторого пип и с<т) . Д (а) ж есть линейный порядок на В; (б) любое счетное линейно упорядоченное множество подобно некоторому подмножеству множества В. 16. Доказать, что порядковый тип любого интервала (не сегмента) действительных чисел есть (.

17 . Подмножество В линейно упорядоченного множества А с порядком Е называетСя плотным еА, если для любых а а Е А сущест- Н 2 вует ЬЕВ такое, что а,лбова или а ед «а,. Доказать, что если А содержит счетное плотное в А подмножество, то А подобно некоторому З 5. ОРДИНАЛЬНЫЕ ЧИСЛА 39 подмножеству множества действительных чисел У с естественным по- рядком. 18.