1611141236-738b6049e710338c8c4dd43e7bd2b717 (824981), страница 10
Текст из файла (страница 10)
Показать, что множества из двух, трех и четырех элементов имеют соответственно 2, 5 и 15 рззлкчных фактормножеств. 4. Пусть — отношение эквивалентностк на множестве Х и /: Х -+ У— отображение, для которого *-*' =о /(я) = /(я'). Показать, что это условие соемесщомоств / с (более слабое, чем рассмотренное в п. 2) позволяет правильно определить индупированное отображение /: е «+ /(я) из Х/ в г', приводящее к факториэапии / = /. р, но / уже не обязательно должно быть инъективным.
В чем заключается условие инъективности /? 5. Изобразить диаграммамк частично упорядоченные множества: 1) 'У((а,ь,с,б)); 2) множество всех делителей пелого числа 24 (отношения порядка указаны в тексте). Гл. 1. Устои« алгебры 8 Т. Принцип математической индукции Считается, что нам известно множество 1Ч = (1, 2, 3,... ) всех натпуральных (или целых по южшпельнмх) чисел. На самом деле отправной точкой для изучения 1Ч служит аксиоматика Пеано (Дж. Пеево, 1858-1932). Из аксиом Пеано (мы их не приводим) вытекают свойства сложения, умножения и линейного упорядочения (см.
п. 4 у 6) натуральных чисел, точнее, системы (Ч 0 (О). В частности, доказывается внтуитивно ясное утверждение: в каждом не«устном множестве Я С 1Ч «меетсл наименьший элемент, т.е. натуральное число з е Я, меньшее всех остальных чисел в Я. С учетом этого утверждения из аксиом Пеано извлекается следующий Принцип индукции. Предположим, что для каждого и е )Ч мы имеем некоторое утверждение М(п). Предположим также, что мы располагаем правилом, поэволлтоитим устпановитпь истинностпь М(1) длл данного 1 при условии, что М(й) верно длл всех й < 1 (в частпности, подраэумевастсл, чтпо мы можем проверить истинность М(1)). Тогда М(п) верно длл всех п Е (Ч.
В самом деле, допустим, что подмножество Я = (з ~ з Е 1Ч, М(з) неверно) С 1Ч непусто. Согласно сказанному вьппе Я содержит наименьший элемент зс. Тогда утверждение М(зс) ложно, а М(з) истинно для каждого з < зо. Это, однако, противоречит нашему предполагаемому умению доказывать истинность М(зе). Здесь не место для всестороннего обсуждения принципа математической индукции. Мы ограничимся замечанием, что он отражает, так сказать, суть натурального ряда, а познание последнего не сводится к чему-либо существенно более простому. Стоит еще обратить внимание на одно обстоятельство. Именно, непременным моментом "доказательства методом полной индукции" является установление базиса индукции, т.е. проверка того, что свойство или утверждение выполнено для небольших и.
Вез такой проверки можно приходить к произвольным умозаключениям типа "все студенты одинакового роста". Вот и рассуждение. Пустое множество студентов и множество из одного студента обладают этим свойством. Делаем предположение индукции, что им обладает любое множество из < и студентов. Во множестве из и+ 1 студентов первые и и последние и студентов одинакового роста по предположению индукции. Эти множества пересекаются по подмножеству вз п — 1 студентов тоже одинакового роста. Значит, все «+ 1 студентов одинакового роста. На самом деле первое содержательное утверждение относилось бы ко множеству из л ю б ы х двух студентов, а здесь-то оно как раз и неверно.
Насколько же длинным должно быть основание индукции? Обычно это ясно у 7. Прннпнп машемашкческоб нкдукинн из доказательства. В нашем элементарном примере важным является условие непустоты пересечения двух множеств, т.е. выполнение неравенства п — 1 ) 1, откуда и ) 2. В более сложных ситуациях, в особенности когда приходится определять или строить объект по индукции при помощи рекуррентных соотношений, необходимо проявлять особую заботу о базисе индукции. Например, делимость на 5 числа Фибоначчи уб (см. пример 2 9 3) при любом целом пэ ) 1 вытекает из равенства Ь = 5 и из соОтНОШЕНИя Ь(„,+1) = 5уа т1+ ЗЬш, КОтОрОЕ Ещв НужНО ПОЛуЧИтЬ. С другой стороны, нельзя впадать в иную крайность: убедившись в истинности М(й) для всех й из достаточно длинного отрезка 1 < й < 1 натурального ряда, делать необоснованный вывод (это будет так называемая неполная нндрэсцил) об истинности М(п) для всех п Е 5(.
Вот — два обескураживающих примера. Пример 1. П. Фермб полагал, что все числа вада Р„ш 2Э + 1, и = 0,1,... (чнсла Ферма), простые. Первые нять чисел Ферма простые, ио длл Ре Эйлер нашел раэложенке Ре = 4294967297 = 641 6700417. Настойчивые усилия получить при помощи новекших ЭВМ хотя бы одно новое простое число Ферма пока не увенчались успехом.
Одним вэ последних "достшкенкй" в этом направлении является проверка того, что рэвеэ делится ка б 2ЭВег + 1. Пример 2. Исследование при и = 1,2,...,40 чисел вида пэ — и+41 (много- член, предложенный Эйлером) способно склонить к мысли о простоте этих чисел прк любом и (о простых числах см. 1 9). Однако 41э — 41 + 41 = 41э. Примеров такого рода можно приводить сколь угодно много. В рассуждениях по индукции иногда самое важное — придать надлежащую форму доказываемому утверждению. Предположим, что нужно найти сумму рл(п) =1 +2 +3 +...+(п — 1) +пв, 5=1,2,3. Задача значительно облегчится, когда вам скажут, что предполагаемый ответ содержится в выражениях п(п+ 1) п(п+ 1)(2п+ 1) ) п(п+ 1) р1( ) гл Рз(п) = Рз(п) = Степенные суммы ра(п) самого общего вида будут еще обсуждаться в связи с корнями многочленов (см.
гл. 6), а сейчас заметим, что встретившаяся нам в п. 5 2 3 сумма Г(п) имеет вид Г(п) = п(п — 1) +... + )с()с — 1) +... + 1 (1 — 1) = в о йэ — ~ й = рз(п) — р1(п) а=1 а=1 (в дальнейшем знак суммирования ) будет систематически использоваться). Опираясь на приведенные вьппе выражения для рэ(п) и р1(п), получаем, что Г(п) = (пэ — п)/3. Разумеется, к тому же ре- 48 Гм 1. Иеепоки а«зебры зультату нетрудно прийти, рассуждая по индукции непосредственно в Г(п). Если до вида р1(п) додуматься нетрудно, то вид рй(п) и ре(п) уже не так тривиален, а соотношение рь+ре = 2 вообще нужно было бы искать по какому-то определенному плану. В данном случае такой план указать можно, но не в этом дело.
Для обоснования всех указанных вьппе соотношений нужно провести прямыми вычислениями шаг индукции от и к п + 1. Оставим это читателю в качестве полезного упражнения. Кстати, в этом упражнении пригодится так называемая биномиальнал рормр,еа (а» Ь)п ап» ( 1 оп-»Ь~-,» ( 1 оп-«Ь«»», Ьп (1) Здесь под а и Ь подразумеваются произвольные числа, а биномиаль- ныЬ коэффивиенеп ( й) при одночлене ап «Ьй имеет вид () п1 п! п(п — 1)... (и — »е+1) йl й!(п — й)! Ь(й — 1)...2 1 (2) где и! = п(п — 1)... 2 1 (эн-факториал).
Это — быстро растущая величина, например, б! = 720, 10! = 3828800, а 100! > 10що. Полезно дополнить выражение (2) соглашениями О! = 1 и ( й ) = 0 при Ь < О. Отметим еще, что (свойство симметричности биномиальвых коэффнциентов). Формулу (1), очевидно, верную при п = 1, 2, мы докажем индукцией по п. Считая ее справедливой для всех показателей < п, умножим обе части соотношения (1) на а + Ь.
Получим (а .»- Ь)п+ = (а -»" Ь)п(а»- Ь) = ап(а + Ь) +... + ( 1 ап « Ьй(а + Ь) +... + Ь" (а + Ь) = 1Й/ п+1 + пЬ+ + и+3-«Ь«-1 + и+1-«Ь« + ~й — 1/ '», й — 1/ + ( ! вьй-«Ь«+/ '! и-йЬй+1+ Ь Ьп+Ьп+« 1к/ ~й/ Приведение подобных членов показывает, что коэффнциентом при Ь' 7. Приниин маеаемаенинеекаа индукции 49 одночлене а"+1 «Ь«будет с о! и! Ь вЂ” 1,) + ~й/ (Ь вЂ” Ц!( -й+ Ц(+ Ь)( — Ь)! + (Ь вЂ” Ц)(п — й)! п — й + 1 Ь о! о+1 (в+ц! (о+11 (Ь-Ц)( -Ь)! Ь( — Ь+Ц Ь)( +1 — Ь)! ~ Ь ) ' т.е. как раз биномиальный коэффициент вида (2) с верхним индексом, увеличенным на единицу.
Тем самым справедливость формулы (ц доказана для всех п Е !«!. Если записать (а+Ь)" = (и+Ь)(а+ Ь)... (а+Ь), присвоив каждому множителю справа номер от 1 до ц, и посмотреть на те подмножества номеров 1<««<1««...1«<п, которые отвечают при умножении одночлену а" «Ь», то мы придем к выводу, что (Ь) есть не что иное, как число всех подмножеств мощности й множества из ц элементов. Несколько "старомодный" термин — число с« = ("„) сочетаний из и по Ь вЂ” выражает по существу то же самое.
В частности, мощность множества Щзы..., з„)) (см. упр. 4 3 5) равна Но, полагая а = Ь = 1 в формуле (Ц, получим 2"=( )г( )г( )г...г( )г( ). Таким образом, Саго'У([зывз,...,вн1) = 2". Виномиальные коэффициенты — почти непременный атрибут элементарных комбинаторных рассуждений.
Вот — наглядный геометрический пример. Гя. 1. Иск!они алгебры 50 Пример (Ап1ег. МасЬ. Моп!Ыу. — 1977, — чу. 54, Х' 5). Известна задача об определеыии числа В„областей, образуемых в кРуге (2 ) хордами, которые соединяют к фиксиро- 4 3 ванных точек на окружности, при предположении, 4' 1 3' что никакие три хорды не пересекаются внутри круга (рис. 12). Результат прн и = 1, 2, 3, 4, 5 наводит на мысль, что В, ы 2" г; но на самом деле правильной 5 5~ 2' будет фоРмУла Ве = 1+ (2) + (4). Попробукте зто доказать.
1Р Доказательство теоремы или построение объек- 1 та иногда удобно проводить, опираясь на более сложные формы индукции. Например, прынцып двоякое Рис. 12 индукции заключается в сведующем. Пусть любым натуральным числам гп и н отвечает некоторое утверждение У(тп,п), причем: !) У(ю, 1) н У(1, и) ыстинны длл всех гп и и; Н) если У(й — 1,1 ) и У(5,1 — 1) истинны, то У(й,1) также истинно.
Это зквкваяентно: Н ) если У(В', Р) истинно при всех Н < Ь, 1' < 1, Ь + 1' < 5+1, то У(Ь, 1) также истинно). Тогда утвержденке У(пз,п) истинно для всех натуральных пз к и. УПРАЖНЕНИЯ 1. Положим з(п) = в!и и+в!и гр+... + в!и ию, с(и) = сое и + сов гр+... + сов и!з. Индукцией по н доказать формулы з(н) = в!п(пр/2) в!п((п + 1)!з/2) в!п(ез/2) 2. Имеют место формулы: Йн п(2п — 1) а) 1 с!5 (г +1/ З ) ~("Н". '") =' Убедиться в их справедливости хотя бы при и < 5.
в!п(ны/2) сов((п + 1) р/2) в!п(р/2) 5 8. Перестановки 1. Стандартная запись перестановки. Разовьем немного тему, начатую в 2 5, применительно к биектнвным преобразованиям конечных множеств. На этой базе естественным образом возникают важные алгебраические понятия. Пусть й — конечное множество из ц элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
