Бурбаки - Книга 1. Теория множеств (947355), страница 48
Текст из файла (страница 48)
2) Пусть Ь вЂ” целое число, К1п1 — такое соотношение, что соотношение К ] А ] и (~бе) ( (и — целое число )~ А и К ] е ] ) ='Ь К ] и .+ 1 ] ) истинно. Тогда соотношение (чп) ((и — целое число)~к)='ЬК]п]) истинно ('индукция начиная с Ь"). В самом деле, пусть 8]п] есть соотношение „(п)~А)=]ьК1п]"; тогда. испольауя метод разделения случаев, видим, что соотношение 810] истинно; с другой стороны, легко провернется, что соотношение (и — целое число и 81п1)=]ь8]а+ 11 истинно. Из критерия С61 заключаем, что соотношение (п — целое число)=]ь8(п) истинно, откуда и следует наше утверждение, 3) Пусть а и Ь вЂ” два целых числа, такие, что ас„д, и пусть К]п1 — такое соотношение.
что выполняется К1а1 и (1гп)((п — целое число и а < и (Ь и К)п1)рК]и+11). Тогда соотношение (вп) ((и — целое число и а (и ~Ь)=]ьК)п1) в % с нлтгглльныи целыв числа. конвчнып множиствл 201 истинно. Делается, как в предыдущем случае, если взять за 81е1 соотношение „(а ( п ( Ь) =]ЬК 1п]" (,икдукция, ограниченная интервалом"). 4) Пусть а и Ь вЂ” два целых числа, такие, что а (Ь, и пусть К]п] — такое соотношение, что выполняется К]Ь] и (чп)((п — целое число и а с и( Ь и К)п-»-11)=]ьК]п]). Тогда соотношение (Уп) ((п — целое число и а(п (Ь)=]ьК]п]) истинно.
Имеем, в самом деле, соотношение (п — целое число и а (и ( Ь и (не К)п 1)) =]ь (не К] и-» Если бы для некоторого и, такого. что а (и (Ь, было (не К] и]), то из 3) следовало бы (не К ] Ь1), что противоречит предположению; критерий докааан („ипдукция спуска" ). 4. гТопечпые часта упорядоченных множеств Пгвдложинив 3. Пусть Š— фильтруюгцввся вправо (соответственно сетчатое, совершенно упорядоченное) упорядоченное множество. Всякая непустая конечная часть множества Е ограничена сверху (соответственно обладает верхней гранью и нижней гранью, обладает наибольшим элементом и наименьшим элементом). Докажем предложение инлукцией по числу и элементов рассматриваемой части.
Для и=1 результат тривиален. Пусть Х вЂ” часть из и+ 1 элементов множества Е (с п)~1), и положим Х=У() ]х], где У состоит из и элементов и, следовательно, не пусто. Из предположения индукции следует, что существует мажоранта (соответственно верхняя грань, наибольший элемент) у множества У.
Так как Š— фильтрующееся вправо (соответственно сетчатое. совершенно упорядоченное), ]х, у] обладает мажорантой (соответственно верхней гранью, наибольшим элементом) г, которая, очевидно, является и мажорантой (соответственно верхней гранью. наибольшим элементом) множества Х. Слидствив 1. Всякое непустое конечное совершенно упорядоченное множество вполне упорядоченно и обладает наибольшим элементом. Слвдствив 2. Всякое непустов конечное упорядоченное множество обладает максимальным элементом.
В самом деле, такое множество индуктивно в силу следствия 1 (см. $ 2, теорему 2). Упр. Ь 4 НАТУРАЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА. КОНЕЧНЫЕ МНОЖЕСТВА Я6 262 гл. Не упорядоченные множествл Упр. Ю. Свойства конечного характера Определение 2. Пусть Š— множество. Говорят, что множество Ф частей множества Е есть мяожестао конечного характера, или имеет конечный характер, если сооткошекие Х ~Ей экаивалектпо соотношению „всякая копечкая часть множества Х принадлежит чр".
Говорят, что свойство Р~Х) части Х множества Е есть свойство конечного характера, если множество частей Х множества Е. для которых истинно Р) Х), есть множество конечного характера. Примеры. 1) Множество совершенно упорядоченных частей упорядоченного множества Е есть множество конечного карактера: в самом деле, для того чтобы часть Х множества Е была совершенно упорядоченной, необкодимо и достаточно. чтобы всякая часть из двух элементов множества Х была такой.
2) 'Множество свободнык частей векторного пространства есть множество конечного карактера (.Алгебра' гл. П, 6 1). То же верно для множества алгебраически свободных частей произвольного расширения поля (,Алгебра* гл. У, 5 5). 3) Множество подмодулей модуля А не есть множество конечного характера, ибо, вообще говоря, конечная часть подмодуля модуля А не является подмодулем модуля А., ТеОРемА 1. Всякое множество Ф частей множества Е. имеющее конечный характер, обладает максималькым элементом (при упорядочении включением).
В силу теоремы 2 й 2 достаточно доказать, что чр нндуктивно: для этого покажем, что для всякой части (В множества Ж, совершенно упорядоченного включением, объединение Х множеств из (т) принадлежит к чр ($ 2, следствие 2 теоремы 2). Так как Ф вЂ” множество конечного характера, достаточно установить, что всякая конечная часть У множества Х принадлежит к Ж. Но для всякого уеду существует множество Е ЕЮ, такое. что у~оТ; поскольку множество множеств Х (у~У) конечно н совершенно упорядоченно включением, оио обладает наибольшим элементом Б (следствие 1 предложения 3); иначе говоря, существует такое множества В ~чю.
что Уг=Б. Но так как Б~(ю, У вЂ” конечная часть множества 5, а йо — множество конечного характера, имеем У цчр. что заканчивает доказательство. Упражнения 1) а) Пусть Š— множество, 3(Е) — множество конечных частей множества Е. Показать, что Гэ(Е) является наименьшим элементом среди частей Ю мнозгества 1(з(Е), удовлетворяющих следующим условиям: 1' И 5®; 2' соотношения Х б Е и х б Е влекут ХО(х) б Е.
б) Вывести из а), что объединение двук конечнык частей А и В множества Е конечно (рассмотреть множество таких частей Х множества Е, что ХЦА конечно). в) Вывести из а) и б), что для всякого конечного множества Е (эт(Е) — конечное множество (рассмотреть множество таких частей Х множества Е, что йб(Х) конечно). 2) Показать, что для того, чтобы множество Е было конечным, необходимо и достаточно, чтобы всякая непустая часть множества 1(5(Е) обладала максимальным элементом для соотношения включения (чтобы увидеть, что условие достаточно, применить его к множеству $ (Е) конечнык частей множества Е). 3) Показать, что если вполне упорядоченное множество Е таково, что упорядоченйое множество, полученное нзделением множества Е противоположным порядком, также вполне упорядочено, то Е конечно (рассмотреть наибольший элемент х множествз Е, такой, что отрезок Вл конечен).
4) Пусть Š— конечное множество из и > 2 элементов, С вЂ” часть множества Е )( Е, такая, что для любой пары (х, у) различных элементов из Е один из двух элементов (х, у), (у, х) принадлежит к С. Показать, что существует отображение у' интервала (1, и) на Е, такое, что (у(1), у(1+1))6 С для 1 (1< и (рассуждать нндукцией по и), 11 5) Пусть Š— упорядоченное множество, для которого существует такое целое число д, что д есть накбольшее число среди чисел элементов свободных частей Х множества Е (6 1, упр. 5).
Показать, что существует разбиение множества Е на Д множеств, совершенно упорадоченных индуцнрованным порядком. Проделать это в два этапа: а) Если Е конечно и имеет и элементов, доказывать индукцией по и: пусть и — минимальный элемент множества Е, и пусть Е' Š— (а). Если существует разбиение множества Е' на й множеств С~ (1с:1(д), совершенно упорядоченнык индуцированным порядком, рассмотреть для каждого индекса 1 множество ()г элементов х б Сь мзжорирующих а; показать, что существует по крайней мере один индекс 5 такой, что в Е' — ()1 имеется свободная часть, содержащая не больше А — 1 элементов. Для этого надо рассуждать от противного, рассмотрев в каждом Е' — (1г свободную часть Б~ из А элементов и взяв затем объединение 5 множеств Зг и для каждого индекса уп А наименьший элемент зг множества 8ПСХ показать, что д+! элементов а, зь ..., за образуют свободную часть множества Е.
б) Если Š— произвольное множество, доказывать индукцией по Д следующим образом. Говорят, что часть С множества Е сильно сэялпкнап в Е, если для всякой конечной части Р множества Е существует такое разбиение множества Р на не более чем Д совершенно упорядоченных множеств, что СДР содержится в одном из них Показать, что существует максимальная сильно связанная часть Сп и что в Š— Сп всякая свободная часть имеет не больше А — 1 элементов. (Рассуждать от противного, предположив, что существует свободная часть (аь ..., па) из д элементов; рассмотреть каждое из множеств Сп0(аг) (1 ~1<й) и выразить, что оно не сильно связанное, что даст для каждого индекса 1 конечную часть Рг множества Е. Рассмотреть, наконец, объединение Р множеств Рг н использовать для получения противоречия тот факт, что С, †силь связанное.) 7 6) а) Пусть А — множество, Е и Ю вЂ д конечные части множества чт (А), имеющие соответственно т и и элементов.
Пусть 5 — наименьшее целое число, такое, что для всякого целого числа г объединение некоторого семейства г+5 частей множества А, принадлежащих к Я, пересекается по меньшей мере с г множествами, принадлежащими к ЯВ. Показать, что в А существует такое конечное множество В из самое большее и+А элементов, что каждое множество из Эу и каждое множесто из Е пересекаются с В. (Пусть Упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
