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