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