Элементы теоретической арифметики, алгебры и анализа

Маневич Виктор Борисович «Элементы теоретической арифметики, алгебры и анализа» Предисловие Мысль о написании книги «Элементы теоретической арифметики, алгебры и анализа», предлагаемой сейчас вниманию читателя, возникла у автора в конце 60-х годов прошлого века, когда издательством «Мир» были напечатаны переведѐнные на русский язык книги У.Рудина «Основы математического анализа», М.Спивака «Математический анализ на многообразиях» и А.П. и В.Дж. Робертсонов «Топологические векторные пространства». Изложение основ математического анализа в первых двух из этих книг резко отличалось по стилю и содержанию от изложения основ анализа в традиционных руководствах, известных автору к тому времени. Так, изложение дифференциального исчисления функций нескольких переменных в упомянутых книгах начинается с ведения общего понятия дифференцируемого отображения (одного конечномерного евклидова пространства в другое) и его производной. Затем, после доказательства терем об обратной функции (доказываемой в книге У.Рудина без использования понятия определителя) и неявной функции, вводится понятие кратного интеграла Римана и доказывается теорема о замене переменных в кратных интегралах. Далее излагается исчисление дифференциальных форм и доказывается абстрактная теорема Стокса (об интегрировании (k-l)-формы по границе kцепи). Следует заметить, что студент, добросовестно изучивший доказательства классических теорем Грина, Стокса и Гаусса-Остроградского в их традиционном изложении, был не в состоянии понять (как справедливо отмечал Д.А.Райков), что эти теоремы являются частными случаями вышеупомянутой абстрактной теоремы Стокса. С тех пор прошло сорок лет. За это время отечественная математическая литература пополнилась руководствами, излагающими теорию дифференциальных форм, вышеупомянутую абстрактную теорему Стокса и еѐ связь с классическими интегральными теоремами анализа. Таковы, например, книга В.А.Ильина и Э.Г.Поздняка «Основы математического анализа. Ч. 2» (М.: Наука, Гл. ред. физ.-мат. лит-ры, 1982) и университетский учебник «Математический анализ. Ч. 2» авторов В.А.Ильина, В.А.Садовничего, Бл.Х.Сендова (Изд-во Проспект и изд-во МГУ, 2006). Однако, в указанном университетском учебнике теория дифференциальных форм в евклидовом пространстве излагается (достаточно сжато) лишь в дополнение к основному тексту. Кроме того, по мнению автора, изложение теории дифференциальных форм в духе книги У.Рудина более доступно для студента, впервые приступающего к изучению анализа. Книги У.Рудина и М.Спивака в некотором смысле являются взаимно дополняющими друг друга. Так, например, книга У.Рудина содержит элементы теории метрических пространств, теорию интеграла Римана-Стильтьеса, элементы теории рядов Фурье, элементы теории интеграла Лебега. Всѐ это отсутствует в книге М.Спивака. С другой стороны, книга М.Спивака содержит достаточно подробную теорию кратного интеграла Римана (включающую теорему Фубини), тогда как в книге У.Рудина понятие кратного интеграла определяется лишь для непрерывных функций, заданных на параллелепипедах. Кроме того, в книге М.Спивака определяются многообразия и многообразия с краем, вложенные в n-мерное евклидово пространство. Для этих многообразий доказывается общая теорема Стокса, из которой выводятся классические теоремы анализа в их современной формулировке. Для обеих рассматриваемых книг характерна предельная точность обозначений. Следует также заметить, что обе они написаны очень сжато и не содержат некоторые важные разделы анализа (такие, например, как теория несобственных интегралов, и интегралов, зависящих от параметра). 1

Приступая к написанию «Элементов», автор ставил себе целью соединить в одной книге достоинства упомянутых работ У.Рудина и М.Спивака с достоинствами известного курса Г.М.Фихтенгольца, содержащего «недостающие» разделы анализа и богатого примерами и упражнениями, облегчающими усвоение студентами теоретического материала. Кроме того, автор ставил себе целью написать книгу, которая могла бы служить введением в теорию локально выпуклых топологических векторных пространств. «Элементы теоретической арифметики, алгебры и анализа» содержат достаточно много упражнений, которые нельзя пропустить без ущерба для понимания основного текста (в котором, однако, приводятся ссылки на эти упражнения). Большинство упражнений снабжено подробными указаниями, фактически являющимися решениями (читателю рекомендуется попытаться решить се упражнения самостоятельно). Следует заметить, что в упражнениях приведена значительная часть теоретического материала. Так, в упражнениях к первой главе приведена элементарная теория конечных групп, в упражнениях ко второй главе – элементарная теория векторных пространств и т.д. Книга «Элементы теоретической арифметики, алгебры и анализа» задумана как учебное пособие для студентов математических и физических факультетов педагогических вузов и некоторых втузов с углублѐнным изучением математики. Ульяновск 2008

2

Глава 1. Элементы теории множеств. Множества, отношения, функции. Понятие множества или совокупности объектов той или иной природы является одним из основных, первичных понятий математики. Не определяя понятия множества, приведем примеры, иллюстрирующие это понятие. Можно говорить, например, о множестве всех жильцов данного дома или множестве всех книг в данном книгохранилище. В первом случае мы предполагаем, что в рассматриваемый момент никто в доме не рождается и не умирает; а во втором – что в рассматриваемый момент книгохранилище не пополняется новыми книгами и не «прощается» с некоторыми из старых. Примеров подобного рода можно привести сколько угодно. Все это – так называемые конечные множества. Простейшим примером бесконечного множества является множество N всех натуральных чисел: 1, 2, 3, …, n, … (Далее мы приведем определения понятий конечного и бесконечного множества). В следующем разделе мы подробно изучим множество N всех натуральных чисел, действия сложения и умножения, и отношения порядка в нем. Здесь же (в примерах 1.15, 1.31) предполагается, что читатель знаком с арифметикой натуральных и целых чисел. 1.1. Обозначение. Если х – один из объектов, составляющих множество А (эти объекты называются элементами множества), то этот факт записывается так: х А (х принадлежит А). Если х не является элементом множества А, то пишут х А или х А. Из соображений удобства вводят в рассмотрение так называемое пустое множество, т. е. «множество», не содержащее ни одного элемента. Пустое множество обозначается символом  . Запись вида Х= a, b, c,..., l будет означать, что Х – множество, состоящее из элементов а, b, с, …, l. Заметим, что порядок записи элементов внутри фигурных скобок не играет никакой роли. 1.2. Определение. Если каждый элемент множества А является элементом множества В, то говорят, что А есть подмножество множества В и пишут А  В или В  А. Если А  В и в В имеется элемент, не принадлежащий А, то А называется собственным подмножеством множества В. Заметим, что, если А  В (т. е. А не является подмножеством В), то в А существует элемент х В. Если взять пустое множество  , то в нем нет элемента, не принадлежащего произвольно взятому множеству В. По это причине пустое множество  считается подмножеством любого множества. Множество, содержащее хотя бы один элемент, называется непустым множеством. 1.3. Замечание. Для установления факта совпадения двух по-разному определенных множеств А и В достаточно установить, что А  В и В  А. В этом случае будем писать А=В. Вообще, знак равенства «=» будет употребляться нами только для обозначения совпадения объектов, записанных слева и справа от этого знака. Знак «  » будет обозначать несовпадение объектов, записанных слева и справа от него.

3

1.4. Обозначения. Пусть Х – некоторое заданное множество и Р - некоторое условие, которому могут удовлетворять или не удовлетворять элементы множества Х. Тогда запись {x X: х удовлетворяет Р} будет означать подмножество (может быть и пустое) множества Х, состоящее из всех тех элементов х Х, которые удовлетворяют условию Р. Имеет смысл также рассматривать всевозможные подмножества множества Х. Если множество, состоящее из множеств, назвать классом, то класс всех подмножеств множества Х будем обозначать B (Х). 1.5. Определение. Пусть а и b – два различных объекта. Упорядоченной парой объектов а и b, взятых в указанном порядке, будем называть класс, состоящий из двух множеств {a} и {a, b}. Этот класс принято обозначать (а, b): (а, b) = {{a}, {a, b}} Ясно, что (а, b)  (b, а) = {{b}, {a, b}} Элементы а и b будем называть соответственно первой компонентой и второй компонентой упорядоченной пары (a, b). Мы будем рассматривать также пары вида (а, а)={{a}}, обе компоненты которых представляют собой один и тот же элемент. 1.6. Определение. Прямым (декартовым) произведением непустых множеств А и В, взятых в указанном порядке, называется множество { (а, b): а А, b В. Это множество обозначается АxВ (А2 при В=А). ОТНОШЕНИЯ. ФУНКЦИИ В повседневной жизни мы встречаемся с различными типами отношений: отношения между родителями и их детьми; отношения начальника и его подчиненных; отношения шефства одного коллектива над другим и т. д. Если R – отношение, то запись aRb , будет означать, что а находится в отношении R с b. Например, если R – отношение между родителями и их детьми, то запись aRb означает, что а является одним из родителей b. Мы коротко коснемся лишь так называемых бинарных отношений. Бинарное отношение – это отношение, в котором может находится элемент одного множества А с элементом второго множества В (не исключается случай В=А). Мы определим бинарные отношения на основе понятий «множество», «подмножество», «декартово произведение двух множеств». В дальнейшем слово «бинарное» будем опускать. 1.7. Определение. Пусть А и В – два непустых множества. Всякое непустое подмножество R декартова произведения АхВ определяет некоторое отношение между теми или иными элементами множества А и теми или иными элементами множества В. При этом запись aRb (a А, b В) будет означать то же самое, что и запись (а,b) R. Областью определения DR отношения R будем называть множество всех первых компонент входящих в R пар (DR  А), а областью значений ЕR отношения R будем называть множество всех вторых компонент, входящих в R пар (ЕR  В): 4

DR= {х А: для некоторого у В (х, у) R} ER= {y В: для некоторого x А (х, у) R}. Если х DR, то R-образом элемента х назовем множество R[x] всех элементов у ER, для которых (х, у) R: R[x]= {y ER: (х, у) R} 1.8. Пример Пусть А – множество жильцов данного дома, В=А, R - отношение между детьми и их родителями. Тогда запись R[a]={b,c} означает, что b и с являются родителями а. 1.9. Определение Пусть А – непустое множество. Отношение R  АхА называется отношением эквивалентности в А, если DR=А и выполняются следующие свойства: Рефлексивность: (х,х) R для любого х A Симметричность: если (х,у) R, то (у,х) R Транзитивность: если (х,у) R и (у,z) R, то (x,z) R 1.10. Пример Пусть А – множество учащихся одной данной школы. Учеников школы будем обозначать малыми буквами латинского алфавита: a, b, c, x, y, z…Будем писать aRb или (a,b) R тогда и только тогда, когда b учится в одном классе с а. Ясно, что условия рефлексивности, симметричности, транзитивности выполняются, так что R – отношение эквивалентности. 1.11. Теорема. Пусть R – отношение эквивалентности в множестве А и a,b – различные элементы множества А. Тогда R-образы R[a] и R[b] элементов a и b либо совпадают, либо не имеют общих элементов. Доказательство: Допустим, что R[a] и R[b] имеют общий элемент х и установим, что в таком случае R[a]=R[b]. Так как (а,х) R и (b,х) R, то (х,b) R (симметричность) и (а,b) R (использовано свойство транзитивности отношения R). Пусть теперь с – любой элемент множества R[a]. Тогда (а,с) R и верна следующая цепочка принадлежностей: (с,а) R, (с,b) R, (b,с) R. Значит, с R[b]. Этим доказано, что R[a]  R[b]. Аналогично доказывается и обратное включение. 1.12. Обозначение Если R – отношение эквивалентности в множестве А, то вместо aRb или (а,b) R принято писать a  b, если другие (кроме R) отношения эквивалентности в множестве А не рассматриваются. При этом говорят, используя симметричность отношения R, что элементы a и b эквивалентны между собой. Условия рефлексивности, симметричности и транзитивности отношения R запишутся теперь следующим образом: a : а для любого а А; если a : b, то b : a; если a : b и b : с, то a : с. 1.13. Замечание Пусть R – отношение эквивалентности в множестве А. Образуем R-образы R[a] для всех элементов а А и рассмотрим класс K различных получившихся таким образом множеств. Согласно теореме 1.11, эквивалентные между собой элементы «порождают» один и тот же R-образ, которому эти элементы принадлежат; если же a  b, то R-образы R[a] и R[b] не только различны, но и не имеют общих элементов. Таким образом, отношение эквивалентности R в множестве А порождает разбиение этого множе5

ства на ряд подмножеств (R-образов элементов А), называемых классами эквивалентности и обладающих следующими свойствами: 1) каждый элемент а А принадлежит одному и только одному классу эквивалентности; 2) каждый класс эквивалентности состоит из эквивалентных между собой элементов; 3) если элементы a и b принадлежит различным классам эквивалентности, то эти элементы не эквивалентны между собой. Все сказанное хорошо иллюстрирует пример 1.10, в котором отношение эквивалентности R распределяет всех учащихся школы по различным классам этой школы (которые и будут классами эквивалентности). 1.14. Определения Пусть А – непустое множество. Отношение R  AхА, не содержащее пар вида (а,а), называется частичным упорядочением множества А, если R антисимметрично и транзитивно, т. е. 1) если (a,b) R, то (b,a) R; 2) если (a,b) R и (b,с) R, то (a,с) R. Множество А, рассматриваемое вместе с заданным в нем частичным упорядочением, называется частично упорядоченным множеством. Если R – частичное упорядочение, то вместо aRb или (a,b) R будем писать a  b или b  а ( а предшествует b или b следует за а). При такой записи условия 1) и 2) принимают вид: 1) если a  b, то b  а; 2) если a  b и b  с, то a  с. Заметим также, что из a  b следует, что a  b. Частичное упорядочение R множества А называется направлением, если для любых двух элементов а А и b А найдется элемент с А, следующий и за а и за b, т. е. a  с и b  с. Множество А, рассматриваемое вместе с заданным в нем направлением, называется направленным множеством. Частичное упорядочение R множества А будем называть совершенным упорядочением, если для любых двух различных элементов а,b А выполняется либо a  b либо b  а. Множество А, рассматриваемое вместе с заданным в нем совершенным упорядочением, называется совершенно упорядоченным множеством. 1.15. Примеры (а) Пусть А={x, y, z, u, v, t}, R={(x,y), (y,z), (x,u), (x,z), (y,v), (x,v)}. Тогда R - частичное упорядочение множества А. (в) Множество N всех натуральных чисел, рассматриваемое вместе с отношением порядка «<», является направленным и совершенно упорядоченным множеством. (с) Пусть k – любое натуральное число. Назовем k-членным отрезком натурального ряда множество Nk ={n N: n  k} Множество Nk (при k  2), рассматриваемое вместе с отношением порядка «<» (меньше), является совершенно упорядоченным, но не направленным множеством. 6

(d) Назовем множество M  N ограниченным, если M  Nk при некотором k N (в частности, все отрезки Nk натурального ряда суть ограниченные множества). Пусть K - класс всех ограниченных подмножеств множества N. Будем писать М  M  (М, M   K ), если М  M  и М  M  (т. е. М – собственное подмножество M  ). Ясно, что класс K , рассматриваемый вместе с частичным упорядочением «  », является направленным множеством. В то же время K не является совершенно упорядоченным множеством, ибо в нем содержатся «несравнимые» множества. Например, М={2,11,23} несравнимо с M  ={7,15,23,48}, т.е. ни одно из них не является собственным подмножеством другого. 1.16. Определение Пусть А и В - непустые множества. Отношение f  АхВ называется функцией из А в В (или отображением множества А в В), если Df = A и f-образ f[x] каждого элемента х А состоит ровно из одного элемента, который обозначается f(x) и называется значением функции в точке х. Говорят также, что на множестве А определена функция f со значениями в В и пишут f:A  B (f отображает А в множество В). 1.17. Замечание Мы определили функцию как частный случай отношения, стремясь к тому, чтобы понятие функции опиралось только на одно неопределяемое, первичное понятие, а именно на понятие множества. Часто встречается также другое определение понятия функции, которое, ввиду важности этого понятия, мы и приводим в пункте 1.18. 1.18. Определение Пусть А и В – непустые множества. Говорят, что на множестве А задана функция f со значениями в В, если каждому элементу х множества А некоторым способом поставлен в соответствие один и только один элемент множества В, который обозначается через f(x) и называется значением функции в точке х. При этом пишут f:A  B (f отображает А в В), дополняя эту запись в каждом конкретном случае задания функции указанием на то, как именно по элементу х А находится соответствующий ему элемент f(х) В. Множество А называется областью определения функции f, а множество всех значений функции f называется ее областью значений. 1.19. Замечания Необходимо четко различать функцию f и ее значение f(x) в той или иной точке х. Заметим также, что исходя из определения 1.18 (как наиболее часто встречающегося), мы можем определить понятие «график функции». 1.20. Определение Графиком Gf функции f:A  B называется следующее подмножество декартова произведения АхВ: Gf ={(x,y)  АхВ: y= f(x)} Как видим, график функции (если исходить из определения 1.18) есть фактически то, что мы назвали функцией в определении 1.16. 1.21. Определения Пусть f – функция из А в В. Для любого множества U  А образом множества U при отображении f называется множество всех элементов f(x), х U. Это множество обозначается (при этом допускается некоторая непоследовательность) символом f(U). Ясно, что f(А)это область значений функции f. 7

Отображение f:A  B называется сюръективным (или отображением А на В), если f(A)=B. Прообразом любого множества V  B при отображении f называется множество всех таких х А, что f(x)  V. Это множество обозначается f -1(V). Таким образом, всякое отображение f:A  B порождает отображение -1 f : B (В)  B (А). Если при любом у  В множество f -1({y}) состоит не более, чем из одного элемента (т.е. при любом у  f(А) множество f -1({y}) состоит ровно из одного элемента), то отображение f называется инъективным (или взаимно однозначным). Ясно, что f:A  B инъективно тогда и только тогда, когда любым двум различным элементам х, x из А соответствуют различные же элементы f(x), f( x ) из В. Отображение f:A  B, являющееся и сюръективным и инъективным, будем называть биективным отображением (биекцией). 1.22. Определение Пусть f – биективное отображение множества А на В. Каждому элементу у  В поставим в соответствие тот единственный элемент х А, для которого f(x)=y. Так определенное отображение множества В на А (очевидно, биективное) называется обратным по отношению к f и обозначается символом f -1. 1.23. Замечания (а) Таким образом, обратное отображение определено только для биективного отображения f:A  B. Если f инъективно, но не сюръективно, то, строго говоря, f не имеет обратного отображения. Однако, допуская некоторую вольность в обозначении, можем сказать, что отображение f:A  B 1 =f(A) биективно и потому обратимо (т.е. имеет обратное отображение) (в) Как видим, в случае биективного отображения f символ f -1 используется в двух различных смыслах, что, однако, не приводит к недоразумениям, т.к. в каждом конкретном случае ясно, в каждом смысле употребляется этот символ. (с) Из определения обратного отображения для биективного отображения f:A  B с очевидностью следует, что имеют место равенства: f -1(f(x))=x для любого х А, f (f -1(у))=у для любого у В. 1.24. Определение Пусть заданы функции f:A  B и g:B  C. Суперпозицией g  f функций f и g называется функция, отображающая множество А в С и определяемая равенством: (g  f )(х)=g(f(x)) для любого х А. 1.25. Теорема Если отображения f:A  B и g:B  C биективны, то и суперпозиция g  f биективна, причем (g  f ) -1 = f -1  g -1 . Доказательство Установим сперва инъективность отображения g  f . Пусть х, x  А и х  x . Т. к. f инъективно, то f(x)  f( x ), а т. к. и g инъективно, то g(f(x))  g(f( x )), что и доказывает инъективность отображения g  f . Докажем теперь его сюръективность. Пусть z – любой элемент множества С. Т. к. g сюръективно, то найдется элемент у В такой, что g(y)=z. А т. к. f сюръективно, то найдется элемент х А такой, что f(x)=у. Таким образом, 8

g ( f ( x)) =z и сюръективность отображения g  f доказана. Итак, g  f инъективно и сюръективно, т.е биективно и потому обратное отображение (g  f ) -1 существует и отображает С на А. Далее, g -1 отображает С на В, а f -1 отображает В на А. Следовательно, суперпозиция f -1  g -1 имеет смысл и отображает С на А. Остается доказать, что для любого z  C (g  f) -1 (z)= f -1 (g -1 (z)). Обозначим у= g -1 (z), х= f -1 (у) (у  В, х  А). Тогда f(x)=у, g(y)=z, откуда (g  f)(х)=z и (g  f ) -1 (z)=x. Т. к. и (f -1  g -1 )(z)= f -1 (g -1 (z))=x, то действительно (g  f ) -1 = f -1  g -1 , ч. т. д. 1.26. Замечания (а) Если отображение f:A  B биективно, то указанные в 1.23(с) равенства с использованием понятия суперпозиции отображений могут быть записаны так: f -1  f=I A, f  f -1 =I В , где I A – тождественное отображение А на А, а I В тождественное отображение В на В. Это значит, что I A (х)=х, I В (у)=у для любых х А, у  В. (в) Рассмотрим множество всех биективных отображений какого-либо непустого множества А на себя. Обозначив это множество через FA, замечаем, что для любых f, g FA имеют смысл суперпозиции g  f и f  g и обе они сами принадлежат FA. Это означает, что операция взятия суперпозиции двух отображений из FA является алгебраической операцией, т. е. любым двум элементам из FA , взятым в определенном порядке, эта операция сопоставляет элемент этого же множества FA. Легко проверить, что эта алгебраическая операция подчиняется ассоциативному закону: для любых  , f, g из FA (   f)  g=   (f  g). Кроме того, в FA имеется элемент I A (тождественное отображение А на А), «нейтральный относительно рассматриваемой алгебраической операции, т. е. для любого f FA f  I A = I A  f=f. Наконец, для любого f FA имеется элемент f -1  FA, который, как мы знаем из 1.26 (а), вместе с f удовлетворяет равенствам: f  f -1 = I A , f -1  f = I A . Все сказанное позволяет заключить, что множество FA всех биективных отображений множества А на себя, рассматриваемое вместе с операцией «  », представляет собой так называемую группу преобразований множества А. Приведем определение важного алгебраического понятия «группа». 1.27. Определение Пусть в множестве G (непустом) задана алгебраическая операция (т. е. отображение GхG в G), сопоставляющаяся любым двум элементам a,b из G, взятым в определенном порядке, третий элемент с  G.Записывая это сопоставление просто как умножение, будем иметь: a  b=c (или a+b=c, если указанное сопоставление записывается как сложение). Множество G, рассматриваемое вместе с алгебраической операцией «  » (т.е. пара (G,  )), называется группой, если выполняются условия: 1) имеет место ассоциативный закон (a  b)  c=a  (b  c) для любых a,b,с из G 2) существует элемент l  G, для которого a  l= l  a=a при любом a  G 3) для любого a  G существует элемент b a  G такой, что a  ba = b a  a=l 9

1.28. Теорема Существует только один элемент l группы, для которого выполняются равенства a  l= l  a=a при любом a  G Доказательство: Предположим, что существует l   l, l   G, для которого a  l  = l   a=a при любом a  G. Тогда, с одной стороны, l  l  = l   l= l  ,а с другой - l  l  = l   l=l, т.е. l= l  . Полученное противоречие доказывает теорему. 1.29. Теорема Для любого a  G существует только один элемент b  G такой, что a  b= b  a=l. Доказательство: Допустим, что существует элемент с  b, c  G такой, что a  с= с  a=l. Тогда b  (a  с)=b  l, (b  a)  с=b, l  c=b, т.е. с=b. Полученное противоречие доказывает теорему. 1.30. Замечание Если алгебраическая операция в множестве G записывается символом «+», то обычно предполагается, что она подчиняе тся также коммутативному закону: a+b=b+a для любых элементов а,b  G. В этом случае условия 1), 2), 3) определения 1.27. примут вид: 1) (a+b)+с=а+(b+с) для любых а,b,с  G 2) существует элемент   G такой, что а+  =  +а=а для любого aG 3) для любого элемента a  Gсуществует элемент, называемый противоположным к а и обозначаемый -а, такой, что а+(-а)=(-а)+а=  . Единственность элемента  со свойством 2) (он называется нулевым элементом группы) и единственность противоположного элемента -а доказана в 1.28 и 1.29 (ибо доказательства не зависели от обозначения групповой операции) Если групповая операция записывается как умножение, то элемент l со свойством 2) называется единичным элементом группы, а элемент b a со свойством 3) называется обратным к элементу а и обозначается а -1 1.31. Примеры (а) Множество Z всех целых чисел, рассматриваемое вместе с обычной операцией сложения целых чисел, является, очевидно, коммутативной (или, как еще говорят, абелевой) группой (т.е. групповая операция подчиняется коммутативному закону). Подмножество множества Z, состоящее из всех четных целых чисел, рассматриваемое вместе с операцией «+», также является группой. (в) Множества {1} и {-1,1}, рассматриваемые вместе с обычной операцией умножения целых чисел, являются коммутативными группами. (с) Рассмотрим какой-либо отрезок натурального ряда N k ={1,2,3,…,k}, k  1. Согласно доказанному в 1.26 (в) множество всех биективных отображений множества N k на себя, рассматриваемое вместе с операцией «  », представляет собой группу. Биективное отображение множества N k на себя принято называть подстановкой k цифр 1,2,3,…k. Таким образом, мы имеем дело с группой всех подстановок k цифр, которую будем обозначать символом  k. Подстановки принято 10

1 2  k  записывать в виде f=   , где i1 =f(1), i 2 =f(2),…, i k =f(k). Цифры  i1 i2  ik  в верхней строке подстановки можно расположить и в другом п орядке, переставив при этом соответствующим образом и цифры в нижней строке. Группа  k при k  3 не коммутативна. Например, при k=3 подстанов1 2 3  1 2 3 ки f=  и = не перестановочны:    2 1 3 3 2 1    1 2 3  1 2 3  f  =   =   f. На основе этого примера легко ука 2 3 1 3 1 2 зать неперестановочные подстановки при любом k>3.

НАТУРАЛЬНЫЕ ЧИСЛА Мы принимаем, что существует множество (которое будем обозн ачать символом N), элементы которого называются натуральными числами и которое удовлетворяет следующим аксиомам (модифицированная система аксиом Пеано): 1) множество N не пусто: оно содержит элемент (натуральное число), называемый единицей и обозначаемый 1; 2) для каждого числа n  N определено единственное число n  N, называемое следующим за n, причем функция  : N  N, определяемая равенством  (n)= n (которую будем называть функцией следования) – инъективна и содержит в своей области значений все натуральные чи сла, кроме 1; 3) если M  N и известно, что М содержит число 1 и вместе с любым своим числом n содержит также число n , то M=N (аксиома индукции). 1.32. Замечание Рассмотрим множество М всех тех натуральных чисел, которые имеют своим «родоначальником» число 1: 1 =2, (1) = 2 =3, ((1)) = 3 =4 и т.д. Легко видеть, что 2=  (1)  1 , т.к. 1 не содержится в области значений функции  . По той же причине 3  1. Кроме того, 3  2, т.к. 3= 2 , 2= 1 и 2  1 (здесь мы используем инъективность функции  ). Аналогично доказывается, что 4  1, 4  2, 4  3. Подобные рассуждения можно продолжить сколь угодно далеко. Возникает вопрос: всякое ли натуральное число имеет своим «родоначальником» число 1? Аксиома индукции дала бы положительный ответ на этот вопрос, если бы понятие «число n имеет своим родоначальником число 1» было четко определено (и тем самым было бы четко определено множество М). Но указанное понятие нельзя считать четко определенным, а потому положительный ответ на поставленный выше вопрос не имеет доказа-

11

тельной силы. Но мы в этом замечании и не собирались что-либо доказывать, а только аппелируем к интуиции читателя. 1.33. Теорема Всякое натуральное число b  1 является следующим за одним и только одним натуральным числом k, которое назовем предыдущим для b. Доказательство: Существование числа k, следует из того, что b   ( N ) (аксиома 2)), а его единственность следует из инъективности функции  . 1.34. Определение Зафиксируем любое натуральное число а и назовем суммой числа а с любым натуральным числом b (которую запишем как a+b) натуральное число, определяемое следующими равенствами: 1) а+1= a ; 2) если b  1 и b= k  , то a+b= (a  k ) (то есть a+ k  = (a  k ) ). 1.35. Теорема При любом фиксированном а  N значение суммы a+b действительно можно определить для любого натурального числа b при помощи равенств 1) и 2) определения 1.34. Доказательство: Обозначим через М множество всех тех натуральных чисел b, для которых значение суммы a+b можно определить с помощью равенств 1) и 2) определения 1.34. Тогда 1  М, т. к. значение суммы а+1 можно определить с помощью равенства 1). Число 2 также принадлежит М (это рассуждение можно и опустить), т. к. а+2=а+ 1 = (a  1) = (a) , т.е. значение суммы а+2 можно определить с помощью равенств 1) и 2). Пусть b – любое натуральное число из М, т. е. значение суммы a+b можно определить с помощью равенств 1) и 2) определения 1.34. Тогда и b  M , т.к. а+ b = (a  b) , т.е. и значение суммы а+ b можно определить с помощью равенств 1) и 2) определения 1.34. На основании аксиомы индукции заключаем, что М=N, т.е. значение суммы a+b действительно можно определить с помощью равенств 1) и 2) для любого натурального числа b. 1.36. Замечание (а) Изменяя число а  N , можем получить значение суммы a+b для любой пары (a,b)  NxN. (в) Определение 1.34. представляет собой так называемое индуктивное определение, которое требует применения аксиомы индукции для доказательства того, что некоторое понятие (в формулировке которого фигурирует произвольное натуральное число n) действительно определено теми или иными равенствами для всех n  N. В дальнейшем мы будем неоднократно использовать индуктивные определения, опуская д оказательства их законности, ибо все они проводятся по схеме, обозн аченной при доказательстве теоремы 1.35. (с) На аксиоме индукции базируется и так называемый принцип математической индукции, состоящий в следующем. Если некоторое утверждение, справедливость которого требуется установить для прои з12

вольного натурального числа n, доказано для n=1 и если справедливость этого утверждения для какого-либо (любого) числа n влечет за собой справедливость утверждения и для числа n+1= n , то доказываемое утверждение верно для всех натуральных чисел. Для обоснования такого заключения достаточно обозначить через М множество всех тех натуральных чисел, для которых рассматриваемое утверждение верно, и применить аксиому индукции. 1.37. Теорема Сложение натуральных чисел подчинено ассоциативному закону, т.е. для любых натуральных чисел a, b, c имеет место равенство (a+b)+c=a+(b+c) Доказательство: Зафиксируем по произволу натуральные числа a и b и докажем теорему индукцией по числу с. При с=1 утверждение теоремы верно: (a+b)+1= (a  b) =a+ b =a+(b+1). (Мы дважды воспользовались равенством 1) и один раз – равенством 2) определения 1.34. Предположим теперь, что утверждение теоремы верно для некоторого натурального числа с и докажем, что оно справедливо и для числа c . Итак, пусть (a+b)+c=a+(b+c) и требуется доказать, что (a+b)+ c =a+(b+ c ). Имеем: (a+b)+ c =[(a+b)+c) ] =[a+ (b  c)] =a+ (b  c) =a+(b+ c ). Здесь мы трижды воспользовались равенством 2) определения 1.34. Кроме того, мы использовали предположение индукции о том, что (a+b)+c=a+(b+c). Теорема доказана (методом математической индукции, т.е. с использованием принципа математической индукции) 1.38. Лемма Для любого натурального числа а 1+а= a Доказательство: При а =1 утверждение леммы верно, т.к. 1+1=1 (равенство 1) определения 1.34.) Предположим, что равенство 1+а= a верно для некоторого натурального числа а и установим справедливость утверждения леммы для числа a , т.е. докажем, что 1+ a = (a) . Имеем: 1+ a = (1  a) = (a) . Здесь мы воспользовались равенством 2) определения 1.34. и предположением индукции. Лемма доказана. 1.39. Теорема Сложение натуральных чисел подчиняется коммутативному закону, т.е. для любых натуральных чисел a,b a+b=b+a. Доказательство: Зафиксируем по произволу натуральное число а и докажем теорему индукцией по числу b. При b=1 утверждение теоремы верно: а+1= a (равенство1) определения 1.34.) и 1+а= a (согласно лемме 1.38), так что а+1=1+а. Предположим, что для некоторого натурального числа b a+b=b+a и установим справедливость утверждения теоремы для числа b , т.е. докажем, что a  b  b  a . В самом деле a  b  (a  b)  (b  a) и b +а=(b+1)+a=b+(1+a)=b+ a = (b  a) , так что действительно a  b  b  a . Теорема доказана. 1.40. Теорема Каковы бы ни были натуральные числа a и b a+b  а 13

Доказательство: Зафиксируем число b и докажем теорему индукцией по числу а. При а=1 утверждение теоремы верно, т.к. 1+b=b+1= b =  (b)  1. Пусть при некотором а N утверждение теоремы верно, т.е. a+b  a. Установим справедливость утверждения теоремы и для числа a , т.е. докажем, что a +b  a . Имеем:  (a+b)   (a) , откуда (a  b)  a , (b  a)  a , b+ a  a и a  b  a , ч.т.д. Мы воспользовались инъективностью функции  , коммутативностью сложения и равенством 2) определения 1.34. Теорема доказана. 1.41. Определение Пусть a и b натуральные числа. Будем говорить, что а меньше b и писать аа и читать «b больше а». 14

1.46. Теорема Пусть a и b натуральные числа и a< b. Тогда натуральное число k, для которого выполняется равенство b=a+k и которое существует в силу определения 1.41. – единственно. Доказательство: Допуская противное, найдем натуральное число m  k и такое, что b=a+m. По теореме 1.44. одно из чисел m,k меньше другого (и только одно, ввиду антисимметричности отношения «<»). Пусть, например, m ао и потому ао+1 М. Отсюда следует, что в множестве М найдется такое число n, что n+1 М (в противном случае по аксиоме индукции М содержало бы все натуральные числа). Т.к. n М, то n
(в) Множество А  N будем называть ограниченным, если А  Nk при некотором k N. 1.54. Теорема Любое непустое и ограниченное множество А  N содержит наибольшее число. Доказательство: Обозначим через В множество всех тех натуральных числе k, для которых А  Nk . Ввиду ограниченности множества А, можем заключить, что В   . По теореме 1.50. множество В содержит наименьшее число, которое обозначим ko. Если ko=1, то А  N1={1}, а т.к. А   , то А={1}, так что число 1 является и наименьшим и наибольшим числом множества А. Пусть ko>1. Тогда А  Nko, но А  Nko-1. Следовательно, а  ko для любого а А и найдется число a  А такое, что a > ko-1, откуда ko  a (теорема 1.49). Итак, a  ko и ko  a , что возможно только при ko= a . Поэтому а  a  A для любого а А, а это и означает, что a – наибольшее число множества А. Теорема доказана. 1.55. Теорема Если a, b, c – натуральные числа и a
Доказательство: Зафиксируем по произволу числа a и b и докажем теорему индукцией по числу с. При с=1 утверждение теоремы верно, т.к. а  (b+c)= а  (b+1)= а  b+а= а  b+а  1= а  b+а  с. Мы воспользовались равенством 2), а затем равенством 1) определения 1.57. Пусть утверждение теоремы верно для некоторого c N: а  (b+c)=a  b+a  c. Установим его справедливость и для числа с+1, т.е. докажем, что a  [b+(c+1)]= a  b+a  (c+1). Имеем: a  [b+(c+1)]= a  [(b+c)+1]=a  (b+c)+a=(a  b+a  c)+a= a  b+(a  c+a)= a  b+a  (c+1), ч.т.д. Мы воспользовались ассоциативностью сложения, равенством 2) определения 1.57, предположением индукции, еще раз – ассоциативностью сложения и еще раз – равенством 2) определения 1.57. Теорема доказана. 1.61. Теорема Для любых натуральных чисел a и b (a+1)  b=a  b+b Доказательство Зафиксируем число a и докажем теорему индукцией по числу b. При b=1 утверждение верно, т.к. (a+1)  1=a+1= a  1+1. Здесь мы дважды воспользовались равенством 1) определения 1.57. Пусть утверждение теоремы верно для некоторого числа b N , т.е. (a+1)  b=a  b+b. Установим его справедливость и для числа b+1, т.е докажем, что (a+1)  (b+1)= =а  (b+1)+ (b+1). Имеем: (a+1)  (b+1)=(a+1)  b+(a+1)=(a  b+ b)+(a+1)=(a  b+ +а)+(b+1)= a  (b+1)+(b+1), ч.т.д. Мы воспользовались равенством 2) определения 1.57, предположением индукции, ассоциативностью и коммутативностью сложения (ассоциативность – несколько раз) и еще раз – равенством 2) определения 1.57. Теорема доказана. 1.62. Теорема Умножение натуральных чисел подчинено коммутативному закону, т.е. для любых a, b N a  b=b  a Доказательство Зафиксируем по произволу число b и докажем теорему индукцией по числу а. При а=1 утверждение теоремы верно, т.к. 1  b=b (теорема 1.59) и b  1=b (равенство 1) определения 1.57). Пусть утверждение теоремы верно для некоторого числа a N. Установим его справедливость и для числа a+1, т.е. докажем, что (a+1)  b=b  (a+1). Имеем: (a+1)  b=a  b+b= = b  а+b= b  (a+1), ч.т.д. Мы воспользовались теоремой 1.61, предположением индукции и равенством 2) определения 1.57. Теорема доказана методом математической индукции. Следствие из теорем 1.62. и 1.60. Для любых a, b, c N (а+b)  c=a  с+b  c Доказательство (а+b)  c= c  (а+b)= c  a+c  b= a  с+b  c 1.63. Теорема Умножение натуральных чисел подчинено ассоциативному закону, т.е. для любых a, b, c N (а  b)  c=а  (b  c) Доказательство Зафиксируем по произволу числа a и b и докажем теорему индукцией по числу с. При с=1 утверждение теоремы верно, т.к. (а  b)  1= а  b= а  (b  1). Пусть утверждение теоремы верно для некоторого c N, т.е. (а  b)  c=а  (b  c). Установим его справедливость и для числа с+1, т.е. 17

докажем, что (а  b)  (c+1)=а  [b  (c+1)]. Имеем: (а  b)  (c+1)= (а  b)  c+а  b= =а  (b  c)+а  b= а  [(b  c)+b]= а  [b  (c+1)], ч.т.д. Мы воспользовались равенством 2) определения 1.57, предположением индукции, теоремой 1.60 и еще раз – равенством 2) определения 1.57. 1.64. Теорема Если a, b, c N и сb Доказательство Достаточно взять любое число n, большее, чем b (например, n=b+1). Тогда, если а=1, то n  a= n>b. Если же a>1, то n  a>n  1, т.е. n  a>n. А т.к. n>b, то n  a>b, ч.т.д. 1.67. Замечание Внимательный читатель, конечно, заметил, что теорема 1.66 представляет собой аналог геометрического предложения, известного под названием «аксиома Архимеда». 1.68. Определение Число a N называется делителем числа b N, если существует q N такое, что b=a  q. Говорят также, что b делится на а. 1.69. Теорема Если a N является делителем числа b N, то число q N , удовлетворяющее равенству b=a  q и существующее в силу определения 1.68 – единственно. Доказательство Допуская противное, найдем два различных числа q и m (q,m  N) таких, что b=a  q и b=a  m. В силу теоремы 1.44, одно из чисел q, m меньше другого. Пусть, для определенности, q<m. Тогда a  q
Особую роль в теоретической арифметике играют натуральные числа, не имеющие других делителей, кроме самих себя и 1. 1.72. Определение (а) Натуральное число p  1, не имеющее других делителей, кроме р и 1, называется простым числом. (в) Натуральное число n  1, имеющее другие делители, кроме n и 1, - называется составным числом. (с) Число 1 не считается ни простым, ни составным числом. 1.73. Теорема Если a, b N , причем ab. Множество А – непустое (теорема 1.66). По теореме 1.50 множество А содержит наименьшее число, которое обозначим no. Тогда nоa>b, а т.к. a1. Обозначим nо-1=q. Т.к. no - наименьшее число в А, то q A, т.е. qa  b. Но а не является делителем числа b. Следовательно, qaa, то r=a+k, k N и b=aq+(a+k)=(aq+a)+k=a(q+1)+k=anо+k. Отсюда b>nо a, а т.к. nо a>b, то получаем b>b, что противоречит антисимметричности отношения «<». Итак, rr. Тогда из равенства aq+r= аq1+r1 следует, что aq-aq1= =r1-r или a(q-q1)= r1-r, где q-q1 N (предварительно доказывается, что q1
(в) Если В равномощно А, то существует биективное отображение f:A  B. Тогда обратное отображение f -1:В  А (см. 1.22) осуществляет биективное отображение множества В на А, откуда следует, что А равномощно В. (с) Пусть А равномощно В, а В равномощно С. Это значит, что существуют биективные отображения f:В  А и g:C  B. Тогда суперпозиция g  f осуществляет биективное отображение множества С на А (теор. 1.25). Но это и означает, что А равномощно С. 1.76. Замечание Мы видим, что отношение равномощности множеств обладает теми же свойствами рефлексивности, симметричности и транзитивности, что и ранее изученное отношение эквивалентности в том или ином множестве. По этой причине равномощные множества называются также эквивалентными. При этом вместо «А равномощно В» пишут просто А  В. 1.77. Определение (а) Множество А называется конечным, если оно либо пустое, либо эквивалентно некоторому отрезку Nk натурального ряда. (в) Множество А называется бесконечным, если оно не является конечным, т.е. А – не пусто и неэквивалентно никакому отрезку натурального ряда. (с) Множество А называется счетным, если А  N. (d) Множество А называется несчетным, если А не конечно и не счетно. (e) Множество А называется не более, чем счетным, если А либо конечно, либо счетно. 1.78. Замечание Определение 1.77 (а) не предполагает, что непустое конечное множество эквивалентно только одному отрезку натурального ряда. Доказательству этого факта мы предпошлем лемму и следующую за нею теорему. 1.79. Лемма Пусть В – непустое собственное подмножество множества А и А  В. Пусть также а - произвольный элемент множества А. Утверждается: (а) Если а В, то существует такое биективное отображение g:A  B, что g(a)=a. (в) Если а В, то найдутся непустое собственное подмножество В1 множества А и биективное отображение g:A  B1 (так что А  B1) такие, что а B1 и g(a)=a. Доказательство (а) Рассмотрим какое-либо биективное отображение f:A  B (такое отображение существует, т.к. А  В). Если f(a)=a, то полагаем g=f. Если же b=f(a)  a (a,b B), то найдем элемент с А, для которого f(c)=a. Отображение f переводит элементы с и а множества А соответственно в элементы а и b множества В (см. рис.) c a

  a b Определим отображение g:A  B, отличающееся от f только своими значениями на элементах с и а: g(c)=b, g(a)=a, g(x)=f(x) при х  с и х  а (х А) 20

c а ][ a b Ясно, что g:A  B биективно и т.к. g(a)=a, то g – именно то отображение, существование которого требовалось доказать. (в) Пусть f – какое-либо биективное отображение множества А на В и b=f(a) (b B). Рассмотрим следующее подмножество В1 множества А: В1= ={х А: x=a или х B, х  b} (В1 содержит элемент а и все элементы множества В, кроме элемента b). Ясно, что В1 – непустое собственное подмножество множества А, ибо а B, b B1. Определим отображение g:A  B1, полагая:  f ( x), если х  а, х  А g(x)=  а, если х  а Очевидно, что g:A  B1 – биективно и g(a)=a, поэтому множество B1 и отображение g суть именно те объекты, существование которых требовалось доказать. 1.80. Теорема Конечное множество не может быть эквивалентным своему собственному подмножеству. Доказательство Теорема верна для пустого конечного множества, т.к. оно не имеет собственных подмножеств. Непустое конечное множество эквивалентно по крайней мере одному отрезку натурального ряда. Докажем индукцией по числу k, что любое конечное множество, эквивалентное отрезку Nk натурального ряда, не эквивалентно никакому своему собственному подмножеству. При k=1 это утверждение верно, т.к. множество, эквивалентное отрезку N1 натурального ряда, имеет вид {a} и у него нет собственных подмножеств, кроме пустого множества. Пусть наше утверждение верно для любого конечного множества, эквивалентного отрезку Nk натурального ряда. Докажем, что оно справедливо и для любого конечного множества, эквивалентного отрезку Nk+1 натурального ряда. Допустим противное. Тогда найдется множество А, эквивалентное отрезку Nk+1 натурального ряда, а также эквивалентное некоторому своему собственному подмножеству В (очевидно, непустому). Пусть  - биективное отображение множества Nk+1 на А и а=  (k+1) (а А). Не ограничивая общности рассуждений, можно считать (см. лемму 1.79), что а B и существует биективное отображение g:A  B, для которого g(a)=a. Заметим, что множество А содержит элемент, не принадлежащий В (ведь В – собственное подмножество А), а потому – отличный от а (а B). Этот элемент и элемент а переводятся отображением g в различные элементы множества В. Так как g(a)=a, то заключаем, что множество В содержит элемент, отличный от а. Рассмотрим множества A ={x А: x  a},  ={x В: x  a}. Образно выражаясь, можем сказать, что множества А и В  B «получаются из множеств А и В соответственно удалением из них элемента  не пусты, В   А и А соа». Согласно вышесказанному, множества А и В 21

 (это элемент множества А, не принаддержит элемент, не принадлежащий В  - непустое собственное подмножество лежащий множеству В). Значит, В  , т.е. А  В  . Так как  (Nk)= множества А . При этом очевидно, что g( А )= В А , то А  Nk. Но это противоречит предположению индукции. Значит, сделанное выше допущение неверно, т.е. любое конечное множество, эквивалентное отрезку Nk+1 натурального ряда, не эквивалентно никакому своему собственному подмножеству. Методом математической индукции теорема доказана. Следствие Любое непустое конечное множество эквивалентно только одному отрезку натурального ряда. Доказательство Допуская противное, найдем непустое конечное множество А, эквивалентное различным отрезкам Nk и Nр натурального ряда: А  Nk , А  Nр , k  p. Используя симметричность и транзитивность отношения равномощности, можем заключить, что Nk  Nр. По теореме 1.44. одно из чисел k, p меньше другого. Пусть для определенности k
бражения f: Nk+1  А, для которого f(k+1)=a. Пусть  - какое-нибудь биективное отображение множества Nk+1 на А (таковое существует, ибо А является k+1 – элементным множеством). Если  (k+1)=a, то полагаем f=  . Если же  (k+1)= a  а, то найдем число n (n Nk)такое, что  (n)=а. Рассмотрим отображение f: Nk+1  А, которое отличается от  только значениями в «точках» n и k+1: f(n)= a , f(k+1)=a, f(x)=  (x) при х  n, k+1. Ясно, что f – биективно вместе с  и f(k+1)=a. Теорема доказана. 1.84. Теорема Число элементов любого непустого конечного множества больше числа элементов любого его непустого собственного подмножества. Доказательство Пусть А – произвольное непустое конечное множество и В – любое непустое собственное подмножество множества А. По теореме 1.83. множество В конечно. Обозначим через n и m числа элементов множеств А и В соответственно. Требуется доказать, что n>m. Рассмотрим какое-либо биективное отображение f множества А на отрезок Nn натурального ряда. Так как В – собственное подмножество множества А, то при отображении f В биективно отображается на собственное подмножество отрезка Nn, т.е. В  f(B)  Nn и f(B)  Nn. С другой стороны, В  Nm, а потому и Nm  f(B) (симметричность и транзитивность отношения равномощности). Если допустить, что m  n, то окажется, что Nm  f(B)  Nn  Nm и f(B)  Nm, т.е. окажется, что Nm эквивалентно своему собственному подмножеству. Но это противоречит утверждению теоремы 1.80. Следовательно, mm an=am  an-m, an m n откуда следует, что а является делителем числа а и что =an-m m a (а,m,n N, n>m ) Индуктивно определяется также произведение первых n натуральных чисел, обозначаемое n! (произносится «эн-факториал»): 1!=1, (n+1)!=n!  (n+1) где n  1. Имеем: 2!=1!  2=1  2; 3!=2!  3=1  2  3; 4!=3!  4=(1  2  3)  4 и т.д.

23

(с) Пусть Х – конечное n-элементное множество. Выясним, сколько элементов содержит класс B ( X ) всех подмножеств множества Х , т.е. найдем число всех подмножеств множества Х, включая пустое подмножество. При n=1, когда Х имеет вид X={a}, имеется всего два подмножества множества Х: само Х и  . При n=2, когда Х имеет вид X={a, b}, имеется всего четыре подмножества множества Х:  , {a}, {b}, Х. В обоих рассмотренных случаях число всех подмножеств множества Х можно записать в виде 2n. Докажем индукцией по числу n, что число всех подмножеств n-элементного множества действительно равно 2n. Это утверждение верно, как мы видели выше, при n=1. Предположим, что оно верно для некоторого n и докажем, что оно остается справедливым и для числа n+1, т.е. убедимся, что число всех подмножеств n+1-элементного множества равно 2n+1. Пусть А – любое n+1элементное множество и а – любой элемент этого множества. Рассмотрим сперва все те подмножества множества А, которые не содержат элемента а. Это будут все подмножества n-элементного множества {х А: х  а}. Согласно предположению индукции, таких подмножеств будет 2n. «Добавляя» к каждому из этих подмножеств элемент а, получим все подмножества множества А, содержащие элемент а. Таких подмножеств также будет 2n. Число всех подмножеств множества А будет равно 2n + 2n=2n  2=2n+1, что и доказывает наше утверждение. Индукцией по числу n легко доказать неравенство 2n>n для любого n N. Следовательно, можно утверждать, что число элементов класса B (Х) больше числа элементов конечного множества Х. Впрочем, это последнее утверждение легко доказать следующим образом. Пусть Х={a,b,…,l} есть n-элементное множество. Ясно, что Х эквивалентно классу {{a}, {b}, …,{l}} всех одноэлементных подмножеств множества Х. Значит, этот класс содержит n элементов (см. 1.82). С другой стороны, этот класс является собственным подмножеством класса B (Х) и потому (1.84) число элементов класса B (Х) больше n. (d) Сочетаниями из n элементов по m (n, m N, n  m) называются различные m-элементные подмножества n-элементного множества. Число таких подмножеств, т.е. число сочетаний из n элементов по m будем обозначать символом Cnm . Очевидно, что Cn1 =n, Cnn =1. Считая n>2, найдем выражение для Cn2 . Пусть дано n-элементное множество {a,b,c,…,k,l}. Двухэлементные множества, содержащие элемент а, таковы: {a,b}, {a,с},…, {a,k}, {a,l}. Число таких множеств равно n-1. Множества, содержащие элемент b (двухэлементные), не считая уже рассмотренного множества {a,b}, таковы: {b,с},…, {b,k}, {b,l}. Число таких множеств равно n-2. Продолжая эти рассуждения, убедимся, что число двухэлементных подмножеств n-элементного множества равно n(n  1) n! (n-1)+( n-2)+…+1, т.е. Cn2 = = 2 2!(n  2)! n! Докажем индукцией по числу n, что Cnm = . Предварительно усm!(n  m)! тановим формулу Cnm1 = Cnm + Cnm1 , в которой предполагается, что 2  m  n. 24

Пусть А – любое n+1-элементное множество, а – какой-либо элемент множества А и A ={x A: x  a}. Рассмотрим всевозможные m-элементные подмножества множества А, не содержащие элемента а. Это будут всевозможные m-элементные подмножества n-элементного множества A . Следовательно, их число равно Cnm . Чтобы получить всевозможные m-элементные подмножества множества А, содержащие элемент а, следует «добавить» этот элемент ко всевозможным m-1элементным подмножествам множества A . Т.к. число этих последних равно Cnm1 , то действительно Cnm1 = Cnm + Cnm1 . Эта формула сохранит свою силу и при m=1, если принять, что для любого n N Cn0 =1. Это определение естественно, т.к. всякое множество содержит единственное пустое подмножество. Примем также, что 0!=1, после чего перейдем к доказательству формулы n! при любом n N и любом целом m, удовлетворяющем нераCnm = m!(n  m)! венствам 0  m  n. При n=1 0  m  1 (m-целое) наша формула, очевидно, верна. Пусть она верна для некоторого натурального числа n и всех целых m, удовлетворяющих неравенствам 0  m  n (другими словами, мы предполагаем, это число m!(n-m)! при указанных m является делителем числа n! и что n! частное равно Cnm . В этом предположении установим, что докаm!(n  m)! зываемая формула остается справедливой для числа n+1 и всех целых m, удовлетворяющих неравенствам 0  m  n+1. Иными словами, мы должны доказать, что число m!(n+1-m)! является делителем числа (n+1)! и что (n  1)! Cnm1 = . Справедливость этих утверждений очевидна при m=0 и m!(n  1  m)! n! n! m=n+1. Если же 1  m  n, то Cnm1 = Cnm + Cnm1 = + = m!(n  m)! (m  1)!(n  1  m)! n!(n  1  m) n!m (n  1)! = + = , ч.т.д. m!(n  1  m)! m!(n  1  m)! m!(n  1  m)! При этом мы воспользовались предположением индукции (выписывая выражения для Cnm и Cnm1 ), а также следующими легко доказуемыми предложениями: 1) Пусть a, b, c – натуральные числа. Тогда ac является делителем bc в том и только в том случае, если а является делителем b. При этом bc b = . ac a 2) Если а является делителем b и с (a, b, c N), то а является делителем b c bc b+c и + = . a a a

25

Доказанной формуле при m>1 можно придать следующий вид: n(n  1)...(n  (m  1)) . Отсюда следует, что произведение любых m поCnm = m! следовательных натуральных чисел делится на m! (ведь Cnm есть натуральное число). (е) Нетрудно доказать (это предоставляется читателю), что всякое совершенно упорядоченное конечное множество является вполне упорядоченным. Для упрощения записи пар, принадлежащих отношению порядка в таком множестве, используется следующий прием. Сначала выписывается первый элемент множества, т.е. элемент, предшествующий всем остальным элементам. Затем на каждом шагу выписывается элемент, первый из невыписанных до этого элементов. Так продолжается до тех пор, пока не придем к последнему элементу, которому предшествуют все остальные элементы. Пусть, например, дано множество {a, b, c}, в котором c  a, c  b и a  b. Вместо того, чтобы выписывать все эти «неравенства», пишут просто cab, подразумевая при этом, что элемент с предшествует элементам a и b, и что элемент а предшествует b. Вполне упорядоченное n-элементное множество называется перестановкой n элементов (этого множества). Если дано (неупорядоченное) n-элементное множество, то возникает вопрос: сколькими способами можно вполне упорядочить данное множество или, другими словами, сколько перестановок можно составить из элементов данного множества? Подчеркнем, что различные перестановки n элементов данного n-элементного множества отличаются друг от друга только порядком элементов. Чтобы ответить на поставленный вопрос, рассмотрим сначала двухэлементное множество, например, {a, b}. Число перестановок, которые можно составить из элементов этого множества, равно 2 (перестановки ab и ba). Пусть теперь дано трехэлементное множество { a, b, с}. Чтобы получить все различные перестановки трех элементов a, b, с, следует к каждой из перестановок ab и ba двух элементов a и b приписать третий элемент с. Сделать это можно тремя способами, так что перестановка ab двух элементов «порождает» три перестановки трех элементов: cab, acb, abc. Точно так же перестановка ba двух элементов «порождает» три перестановки трех элементов: cba, bca, bac. Всего получаем 2  3=3! перестановок трех элементов. Теперь уже индукцией по числу n N легко доказать, на чем мы не останавливаемся, что число всех попарно различных перестановок n элементов (того или иного n-элементного множества) равно n!. (f) Возвращаясь к примеру 1.31 (с), можем заключить (на основании доказанного в 1.85 (е)), что группа  k подстановок k цифр 1, 2, 3, …, k содержит ровно k! элементов (подстановок). Чтобы в этом убедиться, сопоставим каж1 2  k  дой перестановке i1 i2 …ik k цифр 1, 2, 3, …, k подстановку  . i i  i k  1 2 Ясно, что это сопоставление является биективным отображением множества всех перестановок k цифр 1, 2, 3, …, k на множество  k всех подстановок указанных k цифр. Следовательно,  k содержит столько различных под26

становок, сколько различных перестановок можно составить из k цифр 1, 2, 3, …, k, т.е. k!. (g) Выясним, сколько существует различных отображений m-элементного множества Х в n-элементное множество Y. Если n=1, то при любом m N существует ровно одно отображение Х в Y. Пусть n  2 и  - какое-либо биективное отображение отрезка Nn натурального ряда на множество Y. Обозначив  (1)=у1,  (2)=у2, …,  (n)=уn, можем написать: Y={у1, у2, …, уn}. Будем решать поставленную задачу при различных значениях m N, начиная с m=1. При m=1, когда Х={a}, существует n различных отображений f1, f2, …,fn множества Х в Y: f1(а)= у1, f2(а)= у2,…, fn(а)= уn. Пусть m=2, т.е. Х имеет вид {a, b}. Существует n отображений Х в Y, которые обозначим f11, f12, …,f1n, каждое из которых переводит элемент а в у1: f11(b)= у1, f12(b)= у2,…, f1n(b)= уn. Точно так же, существует n отображений f21, f22, …, f2n Х в Y, каждое из которых переводит элемент а в у2: f21(b)= у1, f22(b)= у2,…, f2n(b)= уn. Продолжая эти рассуждения, убедимся, что существует ровно n2 различных отображений fik множества {a, b} в Y, где индексы i и k независимо друг от друга «пробегают» отрезок Nn натурального ряда. Все эти отображения могут быть сведены в таблицу: f 11 f 12  f 1n f 21 f 22  f 2 n     fn1 fn 2  fnn При этом каждое отображение fik определяется равенствами: fik(а)= уi, fik(b)= уk. Обратим внимание на то, что каждое из отображений fi множества {a} в Y «порождает» n отображений fi1, fi2, …, fin множества {a, b} в Y . Мы видим, что в обоих рассмотренных случаях (m=1 и m=2) число всевозможных попарно различных отображений множества X в Y можно записать в виде nm. Докажем индукцией по числу m при любом фиксированном n (m, n N), что число различных отображений m-элементного множества в nэлементное множество действительно равно nm. При m=1 это утверждение, как доказано выше, справедливо. Предположим, что подлежащее доказательству утверждение верно для некоторого m N и установим, что оно остается таковым при замене m на m+1. Итак, пусть Х - произвольное m+1-элементное множество, Y={у1, у2, …, уn} – любое n-элементное множество и требуется доказать, что число различных отображений X в Y равно nm+1. Рассмотрим какой-нибудь элемент a X и обозначим  X ={x X: x  a}. Согласно предположению индукции существует ровно р= nm различных отображений f1, f2, …,fр множества  X в Y (ведь  X - m-элементное множество). Каждое из этих отображений «порождает» n отображений множества X в Y . Например, f1 «порождает» отображения f11, f12, …,f1n , которые определяются следующим образом: при любом k Nn 27



f1k(х) = f1(x), если x  X yk, если x=a Аналогично, любое отображение fi (i Np) множества  X в Y «порождает» n отображений fi1, fi2, …, fin множества Х в Y. При этом для любого i Np и любого k Nn отображение fik : X  Y определяется равенством fik(х) = fi(x), если x  X yk, если x=a. Все «порожденные» отображения можно свести в таблицу:



f 11 f 12  f 1n f 21 f 22  f 2 n     fp1 fp 2  fpn

(*)

Число этих отображений равно p  n= nm  n= nm+1. Остается доказать, что среди отображений fik нет двух одинаковых отображений и что любое отображение f : X  Y заключено в указанной таблице. Рассмотрим любые два отображения fik и fjs из таблицы (*). Если k  s, то fik  fjs, ибо fik(а)=уk  уs= =fjs(а). Пусть k=s, но i  j (i, j Np). Если бы при этом оказалось, что fik= fjk, то отсюда следовало бы, что fik(x)= fjk(x) для любого x  X , т.е. fi= fj. Но это противоречит предположению индукции о том, что f1, f2, …, fр суть всевозможные попарно различные отображения множества  X в Y. Значит, fik  fjk при i  j , чем и доказано, что в таблице (*) нет двух одинаковых отображений. Пусть теперь f – любое отображение множества Х в Y и f(a)=yk (k Nn). Определим отображение f :  X  Y, полагая f (х)= f (х) для любого x  X (заметим, что отображение f называется сужением отображения f на множество  X ). Так как среди отображений f1, f2, …, fр содержатся все отображения  X в Y, то f =fi при некотором i Np. Следовательно, f (х) = fi(x), если x  X yk, если x=a. т.е. f= fik. Итак, функции fik таблицы (*) попарно различны и среди них содержится любое отображение f : X  Y. Т.к. число этих отображений fik равно nm+1, то наше утверждение (о количестве различных отображений m-элементного множества в n-элементное) доказано методом математической индукции. 1.86. Обозначение Для любых непустых множеств Х и Y (не обязательно конечных) через YX принято обозначать множество всех различных отображений f : X  Y. При конечных Х и Y это обозначение напоминает нам, сколько элементов содержится в указанном множестве. 1.87. Замечание Если Х – n-элементное множество, а Y – двухэлементное множество, то, согласно доказанному в 1.85 (g), множество YX всех отображений Х в Y содержит 2n элементов. Так как множество B (Х) всех подмно-



28

жеств множества Х также содержит 2n элементов (см. 1.85 (с)), то B (Х)  YX. Как показывает следующая теорема, этот результат справедлив для любого (не обязательно конечного) непустого множества Х. 1.88. Теорема Для любого непустого множества Х класс B (Х) всех подмножеств множества Х эквивалентен множеству YX всех отображений множества Х в Y, где Y – любое двухэлементное множество. Доказательство. Пусть Y={a,b}. Каждому элементу множества YX, т.е. каждому отображению f : X  Y поставим в соответствие множество f -1(a) B (Х) (если f(х)=b при всех х Х, то f -1(a)=  ). Убедимся, что указанное соответствие инъективно. В самом деле, пусть f,   YX и f   . Найдется элемент x  Х такой, что f( x )   ( x ). Будем считать, для определенности, что f( x )=а,  ( x )=b. Ясно, что x  f -1(a), но x   -1(a). Следовательно, f -1(a)   -1(a). Остается доказать сюръективность указанного выше соответствия. Рассмотрим любой элемент А B (Х) (т.е. А – любое подмножество множества Х). Мы должны доказать существование такого отображения f : X  Y , что f -1(a)=А. Но этому условию удовлетворяет отображение f, определяемое следующим образом: a, еслих  А f ( x)   b, еслих  Х , х  А Теорема доказана. 1.89. Теорема Непустое множество Х не эквивалентно классу B (Х) всех подмножеств множества Х, хотя и эквивалентно подмножеству класса B (Х), а именно – классу всех одноэлементных подмножеств множества Х. Доказательство Справедливость утверждения теоремы для непустого конечного множества установлена ранее (1.85 (с)). Пусть Х – бесконечное множество. Эквивалентность множества Х классу всех одноэлементных подмножеств множества Х – очевидна. Установим, что Х  B (Х). Т.к. B (Х)  YX, где Y-двухэлементное множество {a, b}, то достаточно доказать, что Х  YX. Допустим, что существует биективное отображение F множества Х на YX. Образ любого элемента х Х при этом отображении обозначим fx (fx YX). Рассмотрим отображение  : X  Y, для которого значение  (х) при любом х Х определяется следующим образом. Находим fx, затем значение fx на взятом элементе х, т.е. fx (х). Если при взятом х окажется, что fx (х)=а, то  (х)=b; если же fx(х)=b, то  (х)=а. Так определенное отображение  принадлежит множеству YX и при любом х Х  (х)  fx (х). C другой стороны (т.к. F – сюръективно),  должно быть образом при отображении F некоторого элемента х0 Х:  =F(х0)= fxo. Следовательно,  (х0)=fxo(х0), что противоречит определению отображения  . Полученное противоречие доказывает, что допущение об эквивалентности множеств Х и YX неверно. Теорема доказана. 1.90. Замечание Если А – бесконечное множество и А  В, то В - бесконечное множество. В самом деле, если допустить противное, то найдется биективное отображение f множества В на некоторый отрезок Nk натурального 29

ряда. Сужение отображения f на множество А (см. 1.85 (g)) есть биективное отображение множества А на множество f(А)  Nk. Но f(А), как подмножество конечного множества Nk, само конечно (1.83). Выходит, что А эквивалентно конечному множеству f(А), т.е. А – конечно, что противоречит предположенной бесконечности этого множества. Следовательно, допущение о конечности множества В неверно. 1.91. Пример несчетного множества Рассмотрим класс B (N) всех подмножеств множества N всех натуральных чисел. Множество N бесконечно (1.85 (а)) и эквивалентно классу всех одноэлементных подмножеств множества N. Следовательно, этот класс есть бесконечное множество. А т.к. B (N) содержит указанный класс в качестве собственного подмножества, то и B (N) есть бесконечное множество (1.90). При этом B (N)  N (1.89)., т.е. B (N) не конечно и не счетно. Множество a, b N, т.е. множество всех отображений множества N в двухэлементное множество, также несчетно, ибо оно эквивалентно множеству B (N) (1.88). 1.92. Определение (а) Пусть Х – произвольное множество. Всякую функцию f:N  X будем называть последовательностью элементов множества Х. Последовательность f принято обозначать символом (хn), где хn= f(n) при любом n N. Значения функции f, т.е. элементы хn X (n N), называются членами последовательности (хn) (члены последовательности с различными «номерами» не обязательно обозначают различные элементы множества Х). Вместо (хn) иногда пишут просто х1, х2, …, хn, … (b) Конечной, а именно k-членной последовательностью элементов множества Х будем называть всякую функцию f:Nk  X. Такую последовательность будем записывать в виде х1, х2, …, хk (хi=f(i), i Nk) 1.93. Замечания (а) Пусть А – счетное множество, т.е. А  N. Существует биективное отображение f: N  A. Полагая (для любого n N) f(n)= хn, мы видим, что А является множеством значений последовательности f=(хn), причем хi  хj при i  j (i, j N). Именно это имеют в виду, когда говорят (допуская некоторую вольность речи), что элементы любого счетного множества можно «расположить в последовательность». (b) Возвращаясь к примеру 1.91, заметим, что если в качестве двухэлементного множества a, b взять множество 0,1 , то полученный там результат можно сформулировать следующим образом: множество всех последовательностей, элементами которых служат цифры 0 и 1, - несчетно. 1.94. Теорема Всякое бесконечное подмножество счетного множества Х счетно. Доказательство Пусть А  Х и А бесконечно. Расположим все элементы множества Х в последовательность (хn), в которой члены с разными номерами обозначают различные элементы множества Х. Определим индуктивно последовательность (nk) натуральных чисел следующим образом. Пусть n1 – наименьшее натуральное число, для которого xn  А. Так как А бесконечно и 1

30

все элементы множества А являются членами последовательности (хn), то среди хn с n>n1 есть элементы множества А. Пусть n2 – наименьшее натуральное число, большее n1 и такое, что xn  А. Вообще, если n1,…, nk (k=2, 3, 4, …) уже выбраны, то пусть nk+1 – наименьшее натуральное число, большее nk и такое, что xn  А. Легко видеть, что n1 < n2<…< nk< nk+1<…Полагая f(k)= хnk (k=1, 2, 3, 4, …), получим биективное отображение f множества N на А (инъективность его очевидна, а строгое доказательство сюръективности предоставляется читателю). Теорема доказана. 1.95. Определение Пусть Х – множество и f – отображение какого-либо непустого множества А в класс B (Х) всех подмножеств множества Х (для любого   А f(  ) B (Х), т.е. f(  )  Х). Всякое такое отображение f: А  B (Х) будем называть семейством подмножеств множества Х или коротко - семейством множеств. При этом множество А будем называть множеством индексов, а само семейство обозначать символом ( E ), где  любой «индекс» (элемент) из А, а E = f(  ). В случае, когда А=N, будем говорить о последовательности (Еn) подмножеств множества Х (или о счетном семействе множеств). При А=Nk (k=1, 2, 3, 4, …) говорят, что задана конечная последовательность Е1, Е2,… Еk подмножеств множества Х. 1.96. Замечание Вполне может оказаться, что различным значениям индекса (т.е. различным элементам   ,    А) «отвечает» одно и то же подмножество множества Х (т.е. может оказаться, что E  = E  ) 1.97. Определение Объединением семейства множеств ( E ), обозначаемым символом  E , называется множество всех тех элементов х Х, каж2

k 1

 A

дый из которых принадлежит E хотя бы при одном   А. Если А=N, то бу

дем пользоваться символом

E

n

. В случае А=Nk объединение семейства

n 1

k

множеств будем обозначать символом

E

i

или Е1  Е2  …  Еk.

i 1

1.98. Определение Пересечением семейства множеств ( E ), обозначаемым символом  E , называется множество всех тех элементов х Х, каж A

дый из которых принадлежит E при всех   А. При А=N будем пользовать

ся символом

E

n

. При А=Nk пересечение семейства множеств будем обо-

n 1

k

значать символом

E

n

или Е1  Е2  …  Еk. Если Е1  Е2=  , то говорят, что

n 1

множества Е1 и Е2 не пересекаются; если же Е1  Е2   , то говорят, что множества Е1 и Е2 пересекаются. 1.99. Замечания Объединения и пересечения множеств подчиняются законам коммутативности, ассоциативности и дистрибутивности: А  В=В  А; А  В=В  А (коммутативность) 31

А  (В  С)=(А  В)  С; А  (В  С)=(А  В)  С (ассоциативность) А  (В  С)=( А  В)  ( А  С) (дистрибутивность) Проверка выполнения этих свойств предоставляется читателю. Заметим, что закон ассоциативности оправдывает отсутствие скобок в обозначениях Е1  Е2  …  Еk и Е1  Е2  …  Еk. Легко проверяются также следующие соотношения. Если ( E ) – семейство множеств (   А), то при любом    А E    E ,  E  E  .  A

 A

Кроме того, если Е  F, то Е  F=F, Е  F=E. 1.100. Определение Пусть А, В B (Х). Разностью множеств А и В, обозначаемой А\В, называется следующее множество: А\В={x X: x A и x B}. Можно также написать: А\В={ x A: x B}. 1.101. Пример Пусть А= a, b, c, d  , В= a, b, c, k , l , m, p . Тогда А\В= d  , В\А= k , l , m, p . 1.102. Замечание Предыдущий пример показывает, что для установления «близости» двух множеств А и В по составу элементов недостаточно отдельно рассмотреть разность А\В или разность В\А . Следует установить «близость» к пустому множеству множества (А\В)  (В\А). Разумеется, понятие «близости» двух множеств требует уточнения, но мы здесь не собираемся приводить какие-либо определения, а только апеллируем к интуиции читателя. 1.103. Определение Симметрической разностью множеств А и В называется следующее множество, обозначаемое S(A,B): S(A,B): (А\В)  (В\А). 1.104. Замечания Легко проверяются (что предоставляется читателю) следующие свойства разности и симметрической разности двух множеств (а) А\В=А\(А  В); (А\В)  С=(А  С)\(В  С) (b) S(A,B)  S(A,С)  S(С,В) (с) S(A1  A2,В1  В2 ) S(A1  A2,В1  В2 )  S(A1,B1)  S(A2,B2) S(A1-A2,В1-В2 )



Докажем для примера свойство (b). Пусть х  S(A,B)=(А\В)  (В\А). Тогда либо х (А\В), либо х (В\А). Рассмотрим случай х (А\В), т.е. х А, но х В. Если при этом х С, то х (С\В) и потому х S(С,B)=(С\В)  (В\С). Подавно х S(А,С)  S(С,B). Если же х С, то х (А\С) и потому х S(А,С)=(А\С)  (С\А). Подавно х S(А,С)  S(С,B). Рассмотрим теперь случай х (В\А), т.е. х В, но х А. Если при этом х С, то х S(А,С)=(А\С)  (С\А) и подавно х S(А,С)  S(С,B).

32

Если же х С, то х S(С,B)=(С\В)  (В\С) и подавно х S(А,С)  S(С,B). Итак, принадлежность х S(А,В) влечет за собой принадлежность х S(А,С)  S(С,B), а это и означает справедливость свойства (b). 1.105. Определение Пусть Х – множество и Е B (Х), т.е. Е  Х. Разность Х\Е будем называть дополнением множества Е до Х и обозначать Е c . 1.106. Теорема Имеют место следующие формулы Де Моргана: А) Х\(  E )=  ( X \ E )  A

 A

В) Х\(  E )=  ( X \ E ) , где ( E ) – любое семейство подмножеств мно A

 A

жества Х. Доказательство А) Пусть х Х\(  E ), т.е. х Х, но х  E . Тогда х E при любом  A

 A

  А, откуда х Х\ E при любом   А. Следовательно, х  ( X \ E ) . Этим  A

доказано, что Х\(  E ) 

( X \ E ) . Пусть теперь х  ( X \ E ) , т.е. при     любом   А х E и потому х  E . Следовательно, х Х\(  E ). Этим   доказано, что  ( X \ E )  Х\(  E ). Оба доказанных включения убеждают   A

A

A



A

A

A

A

в справедливости формулы А). В) Пусть х Х\(  E ), т.е. х Х, но х  E . Найдется «индекс»    А  A

 A

такой, что х E , откуда х Х\ E и подавно х  ( X \ E ) . Этим доказано,  A

что Х\(  E ) 

 ( X \ E ) . Пусть теперь х  ( X \ E ) . Найдется    А, для которого х Х\ E , т.е.  х Х, но х E . Следовательно, х  E , откуда х Х\(  E ). Этим доказа  но, что  ( X \ E )  Х\(  E ). Оба доказанных включения убеждают в спра   A

 A



A



A

A

A

A

ведливости формулы В). 1.107. Замечание Формулы Де Моргана коротко читаются так: дополнение к объединению равно пересечению дополнений «слагаемых»; дополнение к пересечению равно объединению дополнений «множителей». 1.108. Теорема Объединение счетного семейства счетных множеств – счетно. Доказательство Пусть (Еn), n=1,2,3,… -последовательность счетных 

множеств и Е=  En . Установим счетность множества Е. С этой целью расn 1

положим каждое множество Еn в последовательность (xnk), k=1,2,3,…, и рас33

x11 x12 x13 x14  x 21 x 22 x 23 x 24  смотрим бесконечную таблицу x 31 x 32 x 33 x 34  , в которой элементы x 41 x 42 x 43 x 44       множества Еn образуют n-ю строку. Эта таблица содержит все элементы множества Е. Все элементы хij указанной таблицы можно расположить в последовательность f: N  E так, как указывают стрелки. Обозначив эту последовательность через (ym), m=1, 2, 3,…, будем иметь: у1=х11, у2=х21, у3=х12, у4=х31, у5=х22, у6=х13, … Последовательность (ym) содержит все элементы множества Е, т.е. отображение f: N  E сюръективно. Если множества последовательности (Еn) попарно не пересекаются, то уi  уj при любых неравных i,j N, т.е. в этом случае отображение f: N  E будет и инъективным. Следовательно, для указанного случая теорема доказана. Рассмотрим теперь случай, когда некоторые (или все) множества последовательности (Еn) имеют общие элементы. Определим множество А  N следующим образом: А={k N: yk= yi , хотя бы при одном i
ясним сначала, каково необходимое и достаточное условие того, чтобы множество Е было конечным. Если Е – конечно, то все множества E оказываются подмножествами одного и того же конечного множества. И обратно, если все множества E являются подмножествами одного и того же конеч , то и Е  E  , т.е. Е – конечно (это верно при любом множеного множества E стве индексов, даже несчетном). Если же не существует такого конечного  , что E  E  при всех  А, то Е бесконечно (даже если все E множества E конечны). Покажем, что при вышеуказанных условиях (наложенных на А и 34

E ) множество Е будет счетным, если оно не является конечным. С этой целью расположим элементы множества А (индексы) в конечную (если А - конечно) или бесконечную последовательность  1, 2, ... Затем элементы каждого из множеств E , E ,…расположим в конечную или бесконечную последовательность. Эти последовательности составят некоторую таблицу, наподобие той, что рассматривалась в 1.108 (эта таблица может оказаться «неполной» по тем или иным строкам или столбцам, но это не играет никакой роли). Все элементы этой таблицы можно (как и в 1.108) расположить в бесконечную последовательность (ym) (мы считаем, что Е бесконечно). Повторяя дословно все рассуждения теоремы 1.108, мы убедимся в счетности множества Е. 1.110 Теорема Декартово произведение Е=АхВ двух счетных множеств А и В само счетно. Доказательство Расположим элементы множества А в последовательность: а1, а2,…, аn, …и для любого n N обозначим Еn={an}xB . Ясно, что Еn  В, т.е. Еn – счетное множество (n=1,2,3,…). 

Так как Е=  En , то (1.108) Е счетно , ч.т.д. n 1

1.111. Замечание Выше мы определили понятие декартова произведения двух множеств. Пусть теперь k>2 и Е1, Е2,…, Еk – конечная последовательность множеств. Имея целью определить декартово произведение Е1хЕ2х…хЕk, заметим, что Е1хЕ2 можно отождествить с множеством всех таких двучленных последовательностей х1, х2, что х1 Е1, х2 Е2 (т.е. с множеством всех таких функций f, определенных на N2, что х1=f(1) Е1, и х2=f(2) Е2). Это замечание делает естественным принятие нижеследующих определений. 1.112. Определения (а) Декартовым произведением непустых множеств конечной последовательности Е1, Е2,…, Еk (k>2) называется множество всех таких k-членных последовательностей х1, х2,… хk, что х1 Е1, х2 Е2,…, хk Еk. Это множество k

обозначается символом Е1хЕ2х…хЕk или

 E . Элементы декартова произi

i 1

ведения будем в дальнейшем записывать в виде (х1, х2,… хk) (по аналогии с записью упорядоченных пар – элементов декартова произведения двух множеств) (b) Декартовым произведением непустых множеств (бесконечной) последовательности Е1, Е2,…, Еn, … называется множество всех таких последовательностей х1, х2,…, хn, …, что хi  Еi, i=1,2,3,… Это множество обозначается 

символом



 E . Элементы декартова произведения  E i

i 1

i

будем в дальней-

i 1

шем записывать в виде (х1, х2,…, хn,…) (с) Пусть А – непустое множество индексов и ( E ),   A - семейство непустых множеств. Декартовым произведением множеств семейства ( E )

35

называется множество всех таких функций f, определенных на множестве А, что при любом   A f(  ) E . Это множество обозначается

E .   A

1.113. Замечания (а) Декартово произведение Е1хЕ2х…хЕk в случае, когда Е1=Е2=…=Еk=Е, представляет собой множество всех k-членных последовательностей элементов из Е, т.е. множество всех отображений Nk в Е. Допуская некоторую непоследовательность, это множество обозначают символом Еk (вместо ЕNk) 

(b) Декартово произведение

E

i

в случае, когда Еi=Е при всех i N,

i 1

представляет собой множество всех последовательностей элементов из Е, т.е. множество ЕN всех отображений N в Е. (с) Декартово произведение

E  

в случае, когда E =Е при всех   A ,

A

представляет собой множество ЕА всех отображений А в Е. 1.114. Теорема Для любого k  2 (k N) и любой конечной последовательk

ности Е1, Е2,…, Еk счетных множеств декартово произведение

 E – счетно. i

i 1

Доказательство При k=2 теорема верна (1.110), причем (см. 1.111) Е1хЕ2 можно отождествить с множеством всех двучленных последовательностей х1, х2 таких, что х1 Е1, х2 Е2. Пусть теорема верна для некоторого k  2, т.е. мы предполагаем, что декартово произведение любой k-членной последовательности счетных множеств – счетно. Установим, что утверждение теоремы остается справедливым и для числа k+1, т.е. докажем, что если Е1, Е2,…, Еk, Еk+1 – любые счетные множества, то Е1хЕ2х…хЕkхЕk+1 также счетно. Согласно предположению индукции декартово произведение Е1хЕ2х…хЕk счетно, т.е. счетно множество всех таких функций f, определенных на Nk, что f(1) E1, f(2) E2, …, f(k) Ek. Расположим все эти функции в последовательность f1, f2, …fn,…, в которой fi  fj, если i  j (i, j N). Расположим также в последовательность х1, х2,…, хm, …,( хp  хq при p  q) все элементы счетного множества Еk+1. Рассмотрим теперь следующие функции gij (где индексы i и j независимо друг от друга «пробегают» множество N), определенные на N k+1:  fi ( s), если s  Nk gij(s)=   xj, если s  k  1

Ясно, что все функции gij являются элементами декартова произведения Е1хЕ2х…хЕkхЕk+1. Если gij= grl, то j=l (т.к. gij(k+1)=xj , а grl(k+1)=xl и xj  xl при j  l). Кроме того, при любом s Nk gij(s)=grl(s), т.е. fi(s)=fr(s) или fi=fr, что возможно только при i=r. Убедимся еще, что любой элемент g декартова произведения Е1хЕ2х…хЕkхЕk+1 содержится среди функций gij. Т.к.

36

g(k+1) Еk+1, то при некотором j N g(k+1)= xj. Рассмотрим сужение f функции g на множество Nk: f(s)=g(s) для любого s Nk. Т.к. f Е1хЕ2х…хЕk, то при некотором i N f= fi . Выходит, что  fi ( s), если s  Nk g(s)=   xj , если s  k  1

т.е. g=gij . Итак, таблица g 11 g 12  g 1n  g 21 g 22  g 2 n       gm1 gm 2  gmn       состоит из попарно различных элементов декартова произведения Е1хЕ2х…хЕkхЕk+1 и содержит все элементы этого произведения. Но все эти элементы можно расположить в последовательность (см. 1.108), откуда и следует счетность декартова произведения Е1хЕ2х…хЕkхЕk+1. Методом математической индукции теорема доказана. Следствие 1 Если Е – счетное множество, то при любом n N множество n Е всех n-членных последовательностей (х1, х2,…, хn) элементов множества Е – счетно. Для доказательства следует применить теорему 1.114 к случаю Е1=Е2=…=Еn=Е Следствие 2 Если Е – счетное множество, то множество всех конечных последовательностей элементов множества Е – счетно. 

В самом деле, указанное множество представляет собой

E

n

n 1

1.115. Замечания (а) Однако, множество всех бесконечных последовательностей, составленных из элементов даже конечного множества Е с числом элементом n  2 – несчетно (см. 1.91 и 1.93 (b)) (b) При доказательстве многих теорем (и, в частности, при доказательстве теоремы 1.116), относящихся как к теории множеств, так и к другим разделам математики, оказывается необходимым применение так называемой аксиомы выбора или одного из эквивалентные ей предложений. Здесь мы сформулируем лишь три эквивалентных между собой аксиомы. Доказательство эквивалентности этих и ряда других предложений (которые будем называть различными формами аксиомы выбора) интересующийся этим вопросом читатель найдет в книге Дж. Л. Келли «Общая топология». Аксиома Цермело Для любого класса K непустых попарно непересекающихся множеств существует такое множество С, что для любого множества А K пересечение А  С состоит ровно из одного элемента.

37

Аксиома Цермело постулирует существование множества С, состоящего из элементов, «выбранных по одному» из каждого множества класса K . Аксиома выбора пусть ( X  ) ,   A - семейство непустых подмножеств некоторого множества Х. Тогда существует функция  : А  Х такая, что для любого   A  (  ) X  . Функция  , существование которой постулируется аксиомой выбора, называется функцией выбора. Заметим, что в аксиоме выбора множества X  при различных   A не предполагаются непересекающимися. Аксиома максимальной цепи Пусть K - какой-либо непустой класс  - любая цепь мномножеств (подмножеств некоторого множества Х) и K  , жеств из K . Это означает, что, каковы бы ни были два множества из K одно из них содержится в другом (класс множеств содержащий лишь одно множество, даже пустое, также считается цепью). Утверждается, что сущест : вует максимальная цепь М множеств из K , содержащая K   М K K Поясним, что максимальность цепи М (в K ) означает следующее: каков бы ни был класс K  , такой, что М  K   K и М  K  - этот класс K  уже не является цепью.  -максимальная цепь в Заметим также, что вполне может случиться, что K  . K и тогда М= K 1.116. Теорема Всякое бесконечное множество содержит счетное подмножество. Доказательство Пусть множество А бесконечно и требуется доказать существование счетного подмножества множества А. Т.к. А   , то класс K 1 всех одноэлементных подмножеств множества А непуст. Индукцией по числу n легко доказать (это предоставляется читателю), что при любом n N класс K n всех n-элементных подмножеств множества А непуст. Рассмотрим клас n= K n! для любого n N. Они составляют семейство ( K  n), n N несы K пустых подмножеств множества B (А). Согласно аксиоме выбора существует  n. Обозначая функция  : N  B (А) такая, что при любом n N  (n) K Мn=  (n), получаем последовательность множеств М1, М2,…, Мn,…, причем для любого n N Мn состоит из n! элементов множества А. Определим новую n 1

 n), полагая M  1= М1, M  n= Мn\ Mi (n  2). последовательность множеств ( M  i 1

 n не пусто, так как множество При любом n N множество M

n 1

M

i

содержит

i 1

не более, чем (n-1)  (n-1)! элементов, тогда как число элементов множества Мn равно n!= n  (n-1)!>(n-1)  (n-1)! Легко доказать также, что множества по n) попарно не пересекаются. Применяя еще раз аксиому следовательности ( M выбора, получим последовательность (хn) элементов множества А такую, что  n для любого n N . Так как члены последовательности (хn) оказываютхn  M 38

ся попарно различными, то множество всех этих членов и есть искомое счетное подмножество множества А. 1.117. Теорема (Шрёдер-Бернштейн) Если каждое из двух данных множеств эквивалентно собственному подмножеству другого, то данные множества эквивалентны.   В( B   В), Доказательство Пусть А и В – данные множества и А  B В  A  А( A  А). Требуется установить эквивалентность множеств А и В. С  и какоеэтой целью рассмотрим какое-либо биективное отображение f:А  B либо биективное отображение g:В  A , после чего определим последовательность (Еn) подмножеств множества А, полагая: Е1=А\ A , Еn= g(f(Еn-1)) при n  2. Согласно условию теоремы, Е1 – непустое множество. Индукцией по числу n легко доказать (это предоставляется читателю), что при любом n N множество Еn непусто. Определим, далее, последовательность непустых подмножеств (Bn) множества В, полагая Bn= f(Еn), n N . Тогда при n  2 

 при всех n N . Рассмотрим множества Е= En Еn=g(Bn-1) и Еn  A , а Bn  B  n 1

(Е  А) и



B



n

n 1

и убедимся, что множества В\  Bn и А\Е непусты. Непустота n 1





n 1

n 1

  В\ Bn и немножества В\  Bn следует из очевидного соотношения В\ B   . Для доказательства непустоты множества А\Е возьпустоты множества В\ B 

мем любой элемент у В\  Bn и найдем х=g(у) A . Ясно, что х Е1= А\ A . n 1

Если бы х принадлежал Еn при некотором n  2, то нашелся бы элемент y  



n 1

n 1

Bn-1, для которого g( y )=х. При этом y  у, ибо y   Bn , а у  Bn . Таким образом, получилось бы, что g( y )=g(у) при y  у, что противоречит инъективности отображения g. Полученное противоречие доказывает, что 

х  En =Е и, следовательно, х А\Е. Итак, множество А разбивается на два n 1



непустых подмножества: Е=  En и А\Е. Аналогично, множество В разбиваn 1



ется на два непустых подмножества:

B



n

n 1

и В\  Bn (см. нижеследующий n 1

рисунок).

Е2 Е1=А\ A

Е3

А\Е

В1

В2 В3



В\  Bn n 1

39

Перейдем теперь непосредственно к доказательству эквивалентности множеств А и В. Заметив, что А\Е  А\Е1= A =g(B), определим отображение h:A  B следующим образом:  f ( x), прих  Е h(x)=  1  g ( x), прих  А \ Е Установим сначала сюръективность отображения h:A  B. Пусть у – любой элемент множества В. Если при этом у Вn при некотором n N, то найдется элемент х Еn, такой, что f(x)=y. Для этого х (т.к. х Е) h(x)=f(x)=y, т.е. 

у h(А). Если же у В \  Bn , то, как уже доказано выше, элемент х= g(у) приn 1

надлежит множеству А\Е. Поэтому h(x)=g-1(x)=y, т.е. и в этом случае у h(А), чем и доказана сюръективность отображения h. Убедимся в его инъективности. Пусть х1 и х2 – любые различные элементы множества А. Если оба они принадлежат Е, то h(х1)= f(х1), h(х2)= f(х2), и h(х1)  h(х2), ввиду инъективности отображения f. Если х1 и х2 оба принадлежат А\Е, то h(х1)=g-1(x1), h(х2)=g-1(x2) и h(х1)  h(х2), ввиду инъективности отображения g-1. Если, наконец, х1 Е, а х2 А\Е, то х1 Еn при некотором n N и h(х1)= f(х1) f(Еn)=Вn. Допустим, что h(х1)=h(х2). Тогда g-1(x2) Вn, откуда х2 g(Вn)=Еn+1, т.е. х2 Е, что противоречит предположению о том, что х2 А\Е. Значит, и в этом случае (х1 Е, х2 А\Е) h(х1)  h(х2) и инъективность отображения h доказана. Следовательно, h биективно и А  В, ч.т.д. 1.118. Замечания и обозначения Как уже отмечалось выше (1.74), про эквивалентные (равномощные) множества говорят, что они имеют одно и то же кардинальное число (или, что то же – одну и ту же мощность). Но что такое кардинальное число множества? Если речь идет о конечных множествах, то (1.82) конечные множества эквивалентны между собой тогда и только тогда, когда они имеют одно и то же число элементов (за число элементов пустого множества принимается число 0). Поэтому естественно определить кардинальное число конечного множества как число его элементов. Пусть теперь K - четко определенный класс множеств, в который могут входить как конечные, так и бесконечные множества. Отношением равномощности «  » K разбивается на классы эквивалентности, про каждый из которых мы будем говорить, что он определяет кардинальное число любого множества этого класса эквивалентности. При этом различные классы эквивалентности определяют различные кардинальные числа. Если класс эквивалентности состоит из конечных множеств, то будем говорить, что он определяет конечное кардинальное число, равное числу элементов каждого множества этого класса эквивалентности. Если же класс эквивалентности состоит из бесконечных множеств, то будем говорить, что он определяет бесконечное кардинальное число. Некоторые бесконечные кардинальные числа (т.е. некоторые классы эквивалентных между собой бесконечных множеств), как наиболее важные и 40

часто встречающиеся, получили специальные обозначения. Так, кардинальное число счетных множеств принято обозначать символом  0 (читается «алеф-нуль»;  - есть первая буква древнееврейского алфавита). Кардинальное число несчетного множества всех последовательностей, составленных из цифр 0 и 1 (см. 1.93 (b)), а также всех эквивалентных ему множеств (в частности B (N)), - обозначается символом «с» и называется мощностью континуума (латинское слово «continuum» означает «непрерывное»). Причину этого названия мы выясним после изучения действительных чисел. Заметим еще, что, например, фраза «множество А имеет своим кардинальным числом  0» означает то же самое, что и фраза «А есть счетное множество». По мере изучения тех или иных бесконечных множеств может возникнуть одна из следующих ситуаций: 1) изучаемое множество эквивалентно тем или иным ранее изученным множествам и тогда ему приписывается то же кардинальное число, которое имеют ранее изученные эквивалентные ему множества; 2) изучаемое множество не эквивалентно ни одному из ранее изученных множеств и тогда ему приписывается в качестве кардинального числа новый символ, отличный от ранее введенных в рассмотрение. Перейдем к вопросу о сравнении кардинальных чисел. С использованием аксиомы выбора можно доказать, на чем мы не останавливаемся, что из двух множеств А и В (каковы бы ни были эти множества) по крайней мере одно из них эквивалентно подмножеству другого. Поэтому, если даны два множества А и В, то либо А  В, либо А  В, но одно (и только одно, как следует из теоремы 1.117) из этих множеств эквивалентно собственному подмножеству другого. Учитывая сказанное, примем следующее определение. 1.119. Определение Пусть  и  - различные кардинальные числа, т.е. множество А, имеющее  своим кардинальным числом, не эквивалентно множеству В, имеющему  своим кардинальным числом. Если при этом множество А эквивалентно собственному подмножеству В (тогда В не эквивалентно никакому подмножеству А), то будем считать, что кардинальное число  меньше кардинального числа  и писать:  < (или  >  ). 1.120. Замечание (а) Из вышесказанного (1.118) следует, что любые различные кардинальные числа  и  сравнимы, т.е. одно (и только одно) из них меньше другого. (b) Как следует из 1.89, для любого кардинального числа  найдется большее кардинальное число  , т.е. такое, что  < . 1.121. Примеры (а) Пусть k – любое натуральное число. Так как Nk  N и Nk  N, то k< 0 . (b) Если  - бесконечное кардинальное число, отличное от  0 , то из 1.94 следует, что    0 , а из 1.116 непосредственно следует, что  0<  . (с) Так как множество N не эквивалентно B (N), но эквивалентно подмножеству класса B (N) (1.89), то  0<с. Впрочем, это следует и из (b), если в качестве  взять с. И, вообще, из (b) следует, что  0 – наименьшее бесконечное кардинальное число. 41

1.122. Теорема Если  ,  ,  - кардинальные числа и  <  , а  < , то  < (транзитивность отношения «<» для кардинальных чисел). Доказательство Пусть А, В, С – множества, имеющие своими кардинальными числами  ,  ,  соответственно. Тогда из условия теоремы следует, что А  В, В  С и найдутся множества В1, С1 такие, что В1  В, С1  С и А  В1, В  С1. Рассмотрим какое-либо биективное отображение f:В  С1. Обозначая f(В1)=С2 (С2  С1), видим, что В1  С2. При этом, как легко видеть, В1 - собственное подмножество В, С1 - собственное подмножество С, С2 - собственное подмножество С1. Из А  В1 и В1  С2 следует, что А  С2  С и остается доказать, что А  С. Допустим противное, т.е. что А  С. Тогда С2  С и (поскольку С2  С1  С) из теоремы 1.117 следует, что С1  С. Выходит, что В  С, т.е.  = , что противоречит условию теоремы. Полученное противоречие доказывает, что А  С и, следовательно (т.к. А  С2  С),  < , ч.т.д. 1.123. Замечание Чтобы разумно определить операции сложения и умножения кардинальных чисел, заметим, что для конечных множеств А и В, состоящих соответственно из m и n элементов, - декартово произведение АхВ состоит из m  n элементов; если при этом множества А и В не пересекаются, то объединение А  В состоит из m+n элементов. Поэтому естественно принять следующие определения. 1.124. Определения Пусть ( m ),   А – семейство кардинальных чисел и ( X  ),   А – семейство множеств, такое, что при каждом   А множество X  имеет своим кардинальным числом m . (а) Произведением кардинальных чисел семейства ( m ),   А, обозначаемым  m , называется кардинальное число множества  X  - декартова  A

 A

произведения множеств семейства ( X  ),   А. (b) Суммой кардинальных чисел семейства ( m ),   А, обозначаемой  m , называется кардинальное число множества  X  при том дополни A

 A

тельном условии , что множества семейства ( X  ),   А попарно не пересекаются. 1.125. Определение Пусть m и а – кардинальные числа. Степенью ma называется произведение  m , где А – любое множество, имеющее а своим  A

кардинальным числом, а m = m при всех   А. 1.126. Замечание Взяв любое множество Х, имеющее m своим кардинальным числом, и положив X  =Х при любом   А, мы видим, что ma представляют собой кардинальное число множества ХА всех отображений множества А в Х. 1.127. Теорема Если в сумме  m все слагаемые равны одному и тому  A

же кардинальному числу m, то

m = mа, где а – кардинальное число мно  A

жества индексов А. 42

Доказательство рассмотрим семейство ( X  ),   А попарно непересекающихся множеств, каждое из которых имеет одно и то же кардинальное число m ( m =m при любом   А). Пусть Х – одно из этих множеств. Тогда X   Х при любом   А и для каждого такого  найдется (аксиома выбора) биективное отображение f  : X   Х. Определим теперь отображение f:  X   ХхА, полагая  A

f(х)=( f  (х),  ), где х – любой элемент множества

X , а   

- то единствен-

A

ное «значение» индекса, для которого имеет место принадлежность х X  . Если докажем, что f – биективно, то этим и будет установлено равенство  m = mа. Докажем сперва инъективность f. Пусть х, x   X  и х  x . Ес A

 A

ли при этом х и x принадлежат одному и тому же множеству X  , то f(х)=( f  (х),  ), f( x )=( f  ( x ),  ) и f(х)  f( x ), ибо (ввиду биективности f  ) f  (х)  f  ( x ). Если же х X  , x  X   и     , то f(х)=( f  (х),  )   ( f   ( x ),   )=f( x ), что и доказывает инъективность отображения f. Убедимся в его сюръективности. Пусть (у,  ) – любая пара из ХхА. Так как для этого  отображение f  : X   Х биективно, то в X  найдется единственный элемент х, для которого f  (х)=у. Следовательно, f(х)=( f  (х),  )=(у,  ), что и доказывает сюръективность отображения f. Итак, f – биективно,  X   ХхА и, следовательно,  m = mа, ч.т.д.  A

 A

1.128. Теорема Для любого семейства ( b ),   А кардинальных чисел и произвольного кардинального числа m имеет место формула

 b

mA

  mb .  A

Доказательство Рассмотрим множество Х, имеющее m своим кардинальным числом, и семейство ( В )   А попарно непересекающихся множеств, такое, что каждое множество В имеет своим кардинальным числом b .

m

Пусть В=  В . Тогда  А

множества ХВ, а

ХВ  



A

mb  

 b

 A

представляет собой кардинальное число



A

представляет собой кардинальное число множества

. Если установим, что ХВ 

ХВ  



A

В Х  Определим отображение Ф: Х  

, то теорема будет доказана.



В

A

следующим образом. Зафикси43

руем любое отображение f:В  Х (f ХВ) и для каждого   А найдем сужеВ

ние f  отображения f на множество В ( f   Х ), после чего положим В Х Ф(f)=F , где F(  )= f  для любого   А. Докажем инъектив-

  A

ством, что f(  )  g(  ). Тогда f  

ХВ

и f  g, т.е. найдется   В с тем свой g  , где   - единственный элемент из А,

ность отображения Ф. Пусть f, g

для которого   В  . Обозначив Ф(f)=F, Ф(g)=G, видим, что F  G, ибо F(   )= f   , а G(   )= g  . Этим доказана инъективность отображения Ф. УсВ Х тановим его сюръективность. Пусть Н – любая функция из , т.е.

  A

В

при любом   А Н(  ) Х . Определим отображение f:В  Х следующим образом. Для каждого   В найдем тот единственный элемент   А, для которого   В , и положим f(  )=Н(  )(  ). Убедимся, что для так определенного отображения f:В  Х имеет место равенство f  = Н(  ) при лю-

В ). Зафиксируем элемент из В . Тогда

бом   А, ( f  - сужение отображения f на множество

любое   А и пусть  - любой f  (  )=f(  )=Н(  )(  ), откуда и следует, что f  =Н(  ). Так как при любом   А Ф(f)(  )= f  и Н(  )= f  , то Ф(f)=Н, чем и доказана сюръективность В В Х отображения Ф. Итак, Ф – биективно и Х  , что и доказывает

  A

справедливость утверждения теоремы. 1.129. Следствие из теорем 1.127 и 1.128 Для любых кардинальных чисел m, b, a имеет место формула (mb)a= mbа. Доказательство Пусть А – любое множество, имеющее а своим кардинальным числом. Рассмотрим семейство ( b ),   А кардинальных чисел, в котором b =b для всех   А. Пользуясь определением 1.125 и теоремами 1.128 и 1.127, находим: b a

(m ) =

m   A

b

=m

 b

 A

= mbа, ч.т.д.

1.130. Примеры (а) Пусть k –любое натуральное число.

0k

есть кардинальное число мно-

жества NNk, которое счетно (1.114) Следовательно, 0 = 0 (b) Пусть ( m ),   А – семейство кардинальных чисел и а – кардинальное число множества А. k

44

Если а  0 и m  0 при всех   А, то и

m  0  

(1.109)

A



(с) 2 0 - есть кардинальное число множества 0,1 N всех последовательностей, составленных из цифр 0 и 1. Это множество несчетно (1.93 (b)), его кардинальное число обозначается символом «с» и называется мощностью контиуума (1.118). Таким образом, с=2 (d)

Так

как

с=2

0

0  0  c0 =(2 0 )0 =20 0 =20 =с, 0

то

0 0 = c

0

=с. И подавно, при любом n N сn=с. (е) Из теорем 1.88 и 1.89 следует, что для любого кардинального числа m имеет место неравенство m<2m. В частности, с<2с. 1.131. Замечание Более подробные сведения о кардинальных числах интересующийся этим вопросом читатель найдет в книге П. С. Александрова «Введение в общую теорию множеств и функций». Упражнения к Главе 1 1. Пусть (G,  ) – конечная группа, т.е. множество G – конечно (число элементов множества G называется порядком конечной группы). Степень an любого элемента а G при любом n N определяется индуктивно: а1=а, аn+1=аn  а (n  1) (а) Доказать, что для любого а G и любых m, n N имеют место равенства m n а  а =аn+m, (аm)n=аmn. (b) Рассматривая различные степени любого элемента а G, доказать, что существуют показатели n N такие, что аn=е (единица группы). Наименьший из таких показателей называется порядком элемента а. Доказать, что если а  е и k – порядок элемента а (k  2), то среди элементов е, а, …, аk-1 нет одинаковых и пара ( H  ,  ), где H  ={е, а, …, аk-1}, представляет собой группу (порядка k). (с) Если Н  G и пара (Н,  ) представляет собой группу, то эта группа называется подгруппой или делителем группы (G,  ). Для того, чтобы пара (Н,  ) была подгруппой группы (G,  ), конечно, необходимо выполнение условия: для любых a, b Н (не обязательно различных) a  b Н. Доказать, что выполнение этого условия является и достаточным для того, чтобы (Н,  ) была подгруппой группы (G,  ) (конечной). (d) Если А  G и В  G, то под А  В будем понимать следующее множество: А  В={x G: x=a  b при некотором а А и b В}. Если В={b}, то вместо А  {b} будем писать просто А  b. В случае, когда (Н,  ) – подгруппа группы (G,  ), то множества типа Н  а, а G называются смежными классами. Доказать, что если m – порядок группы (Н,  ), то при любом а G смежный класс Н  а состоит из m элементов. Доказать также, что при a, b G и a  b-1 Н (то45

гда и b  а-1 Н) смежные классы Н  а и Н  b совпадают; если же a  b-1 Н (тогда и b  а-1 Н), то смежные классы Н  а и Н  b не пересекаются. (е) Доказать, что если (Н,  ) – подгруппа группы (G,  ), то найдутся натуральное число s и конечная последовательность а1, …, аs элементов группы G, в которой а1=е, такие, что смежные классы Н  а1, …, Н  аs попарно не переs

секаются и G=

H a

i

(это равенство носит название разложения группы по

i 1

подгруппе). Вывести отсюда равенство n=m  s, s N, где n – порядок группы (G,  ), а m – порядок подгруппы (Н,  ). Из последнего равенства следует (теорема Лагранжа), что порядок подгруппы есть делитель порядка группы (в частности, порядок любого элемента группы есть делитель порядка группы). n Число s  называется индексом подгруппы (Н,  ) относительно группы m (G,  ) и часто обозначается символом (G:Н). (f) Пусть a, b – произвольные элементы группы G. Элемент b-1ab называется элементом, преобразованным из а при помощи b. Будем говорить также, что элемент b-1ab является b – сопряженным с а. Если элемент b фиксирован, то для любого элемента a G элемент b-1ab будем просто называть сопряженным с а. Если все элементы какого-либо множества А  G, А={а1, а2, …, аk} подвергнуть преобразованию при помощи элемента b, то получим преобразованное множество b-1  А  b ={b-1  а1  b, b-1  а2  b, …, b-1  аk  b, }. Доказать, что порядок элемента, b – сопряженного с а, равен порядку элемента а (предварительно индукцией по числу n N установить формулу (b-1  а  b)n= b-1  а n  b). Доказать, что если (Н,  ) – подгруппа группы (G,  ) и H =b-1  Н  b (b – любой элемент G), то ( H ,  ) также является подгруппой группы (G,  ) и имеет тот же порядок, что и подгруппа (Н,  ). Подгруппу ( H ,  ) будем называть b – сопряженной с подгруппой (Н,  ). (g) Подгруппа (Н,  ) называется нормальным делителем (или инвариантной подгруппой) группы (G,  ), если при любом b G b-1  Н  b=Н. Ясно, что всякая подгруппа абелевой (коммутативной) группы является ее нормальным делителем, так как для такой группы b-1ab=а при любых a, b G. Если (Н,  ) не является нормальным делителем группы (G,  ), то все же равенство b-1  Н  b=Н может выполняться при некоторых b G\Н (при всех b Н указанное равенство очевидным образом выполняется). Множество всех тех элементов b G, для которых b-1  Н  b=Н, называется нормализатором подгруп (очевидно, H   Н). пы (Н,  ). Будем обозначать это множество символом H  ,  ) представляет собой подгруппу группы (G,  ). Доказать, что ( H  ,  ). Если (Н,  ) Ясно, что (Н,  ) является нормальным делителем группы ( H является нормальным делителем группы (G,  ), то существует только одна сопряженная с (Н,  ) подгруппа группы (G,  ), а именно сама подгруппа (Н,  ).  =G, т.е. индекс нормализатора (G: H  )=1. Если (Н,  ) не являВ этом случае H   G, т.е. индекс нормализается нормальным делителем группы (G,  ), то H 46

 )>1. В этом случае возникает вопрос о числе различных подгрупп тора (G: H группы (G,  ), сопряженных с (Н,  ). Доказать, что это число равно индексу  ) нормализатора подгруппы (Н,  ) (предварительно установить, что при (G: H умножении множеств действует ассоциативный закон). Указание Представить G в виде объединения попарно непересекающихся   а1, H   а2,…, H   аs (а1=е, s=(G: H  )) и доказать, что подсмежных классов H группы Н, a21 Н а2, …, as1 Н аs (мы допускаем вольность в обозначениях) попарно различны и что при любом b G подгруппа b-1  Н  b совпадает с одной из указанных подгрупп, сопряженных с Н. (h) Пусть (Н,  ) – нормальный делитель группы (G,  ). Согласно 1(е), имеет s

место равенство G=

 H  a , где а1=е, s=(G:Н) и смежные классы Н  ai поi

i 1

парно не пересекаются. Заметив, что для любого b G b  H=H  b, доказать, что класс множеств {Н, На2, …, Наs} рассматриваемый вместе с операцией умножения множеств, представляет собой группу (называемую дополнительной группой к нормальному делителю (Н,  ) и обозначаемую символом (G/H,  ). Указание Воспользоваться тем, что если b Н  а (a, b – любые элементы из G, (Н,  ) – любая подгруппа группы (G,  )), то a  b-1 Н и потому (см. 1(d)) Н  а=H  b. Убедиться, что единицей группы (G/H,  ) служит Н, а обратным элементом к Н  аi служит смежный класс Н  аj, которому принадлежит элемент ai1 (этот смежный класс можно записать в виде Н  ai1 ). (i) Доказать, что если (Н1,  ) и (Н2,  ) суть подгруппы группы (G,  ) и Н=Н1  Н2, то и (Н,  ) есть подгруппа группы (G,  ). Доказать, что если (Н1,  ) и (Н2,  ) суть нормальные делители группы (G,  ), то и (Н,  ) является нормальным делителем группы (G,  ). (k) Пусть (Н,  ) – произвольная подгруппа группы (G,  ) и Н1=Н, Н2, …, Нk суть все попарно различные подгруппы, сопряженные с Н (для краткости мы k

допускаем вольность в обозначениях). Доказать, что если Н0=  Hi , то (Н0,  ) i 1

есть нормальный делитель группы (G,  ). k

Указание Установить, что для любого b G b-1  Н0  b=  b-1  Нi  b. i1

Кроме того, показать, что множества b  Н1  b, b  Н2  b,…, b-1  Нk  b попарно различны и представляют собой множества Н1, Н2, …, Нk, записанные, быть может, в другом порядке. (l) Две группы (G,  ) и (Г,*) называются изоморфными, если существует такое биективное отображение  :G  Г , что для любых а, a  G имеет место равенство  (а a )=  (а)*  ( a ) (при этом для любых b, b  Г имеет место равенство  -1(b* b )=  -1(b)*  -1( b ). -1

-1

47

Доказать, что если е – единица группы (G,  ), то  (е) – единица группы (Г,*). Доказать также, что, если элементу а G соответствует элемент b Г (т.е.  (а)=b), то  (а-1)=b-1. Изоморфные группы не считаются существенно различными (они могут отличаться только природой своих элементов). Конечные изоморфные группы имеют равные порядки; если одна из них коммутативна, то коммутативна и другая и т.д. Доказать, что каждая конечная группа (G,  ) изоморфна некоторой группе подстановок. Указание Пусть G={а1, а2, …, аn}, где а1=е. Сопоставим каждому элементу а G подстановку n цифр следующим образом. Элементы а  а1, а  а2, …, а  аn попарно различны и потому представляют собой те же элементы а1, а2, …, аn только расположенные, быть может, в другом порядке: а  а1= a 1 , а  а2= a 2 ,…, а  аn= a n , где  1 ,  2 , …,  n есть не1 2  n которая перестановка цифр 1, 2,…, n. Полагая  (a) =   , дока 1  2   n   зать, что отображение  :G   n инъективно. Далее, пусть a, b – любые эле1 2  n 1 2  n менты из G,  (a) =  , = и  ( b )   1  2  n   1  2   n     - любая цифра из {1, 2, …, n}. Подстановка  (b) переводит  в цифру  , которую обозначим через  :   = . Подстановка  (a) переводит цифру  в цифру  , которую обозначим через  :  = . Тогда подстановка  (a)   (b) переводит  в  . Учитывая, что b  a = a и что а  a = a , доказать, что подстановка  (a  b) переводит  в  , как и подстановка  (a)   (b) . Обозначив Г=  (G)   n , убедиться, что (Г,  ) – группа (подгруппа группы  n ), изоморфная группе (G,  ). (m) Группа называется простой, если она не имеет нормальных делителей, кроме самой себя и единичной группы. Нормальный делитель (Н,  ) группы (G,  ) называется максимальным, если не существует нормального де ,  ) группы (G,  ) такого, что Н  H  G и H   Н, H   G. лителя ( H Доказать, что нормальный делитель (Н,  ) конечной группы (G,  ) является максимальным тогда и только тогда, когда дополнительная группа (G/H,  ) – простая. Указание Пусть группа (G/H,  ) – простая, но (Н,  ) не является максимальным нормальным делителем группы (G,  ). Тогда существует нормальный де ,  ) такой, что Н  H  G и H   Н, H   G. Доказать, что ( H  /Н,  ) литель ( H есть нормальный делитель группы (G/H,  ), отличный от (G/H,  ) и единичной группы (в противоречие с предположением о простоте группы (G/H,  )). Обратно, пусть (Н,  ) – максимальный нормальный делитель группы (G,  ), но дополнительная группа (G/H,  ) не является простой. Выпишем элементы группы (G/H,  ): G/H={H  а1, H  а2, …, H  аk, H  аk+1,…, H  аp} (а1=e, смежные

48

p

классы H  аi попарно не пересекаются и G=  H  ai ). Не ограничивая общноi 1

сти, можно считать, что смежные классы H, H  а2, …, H  аk (1
 = H  ai , доказать, ют нормальный делитель группы (G/H,  ). Обозначив H  i 1

 ,  ) – нормальный делитель группы (G,  ), причем Н  H  G и H   Н, что ( H   G (в противоречие с предположением о максимальности нормального H делителя (Н,  )). (n) Пусть (Н1,  ) и (Н2,  ) суть взаимно-простые (т.е. Н1  Н2={е}) нормальные делители группы (G,  ). Доказать, что каждый элемент а Н1 перестановочен с каждым элементом b Н2, т.е. что ab=ba. Указание Установить, что элемент aba-1b-1, называемый коммутатором элементов a и b, принадлежит и Н1 и Н2. (о) Пусть (Н1,  ) и (Н2,  ) - взаимно-простые нормальные делители группы (G,  ) и Н= Н1  Н2. Доказать, что (Н,  ) представляет собой группу (подгруппу группы (G,  )). Установить, что равенство ab= a b (где а, a  Н1, b, b  Н2) имеет место лишь в том случае, когда а= a и b= b . Вывести отсюда, что порядок группы (Н,  ) равен произведению порядков групп (Н1,  ) и (Н2,  ). Доказать, что (Н,  ) является нормальным делителем группы (G,  ). Так как Н1  Н и Н2  Н, то группы (Н1,  ) и (Н2,  ) является нормальными делителями группы (Н,  ) и можно рассматривать дополнительные группы (Н/Н1,  ) и (Н/Н2,  ). Доказать, что (Н/Н1,  )  (Н2,  ) и (Н/Н2,  )  (Н1,  ), где символ «  » означает, что группы, записанные слева и справа от него, - изоморфны. (р) Пусть (Н1,  ) и (Н2,  ) – два максимальных нормальных делителя группы (G,  ) и D=Н1  Н2 Тогда (D,  ) является нормальным делителем группы (G,  ) (см. упражнение (i)). Доказать, что (G/H1,  )  (Н2/D,  ), (G/H2,  )  (Н1/D,  ) и что (D,  ) является максимальным нормальным делителем групп (Н1,  ) и (Н2,  ). k

Указание Написав разложение Н2 по D: Н2=  D  bi (k  2, b1=e, смежные i 1

классы D  bi попарно не пересекаются), доказать, что смежные классы H1, H1  b2, …, H1  bk попарно различны и (рассматриваемые вместе с операцией умножения множеств) составляют делитель и, притом, нормальный делитель группы (G/H1,  ). Но группа (G/H1,  ) – простая и потому G/H1={H1, H1  b2, …, H1  bk}. Так как Н2/D={D, D  b2, …, D  bk}, то изоморфность групп (G/H1,  ) и (Н2/D,  ) очевидна. Аналогично доказывается, что (G/H2,  )  (Н1/D,  ), откуда следует простота групп (Н1/D,  ) и (Н2/D,  ). Остается применить результат упражнения (m). (r) У конечной группы G (для краткости мы допускаем вольность в обозначениях) всегда существует по крайней мере один отличный от G максимальный нормальный делитель G1 (если G – простая группа, то G1=I, где I – единичная группа; сама группа G предполагается отличной от I). Если G1  I, то можно найти максимальный нормальный делитель G2  G1 группы G1. 49

Продолжая эти рассуждения, придем к так называемому композиционному ряду G, G1, G2,…, Gk-1, I, в котором каждая группа, начиная со второй, является максимальным нормальным делителем предыдущей (отличным от этой предыдущей). Композиционный ряд группы G должен оканчиваться единичной группой, так как порядки членов композиционного ряда последовательно убывают. Конечная группа может иметь либо единственный композиционный ряд, либо несколько различных композиционных рядов. Каждому композиционному ряду G, G1, G2,…, Gk-1, I группы G сопоставим ряд дополнительных групп G/G1, G1/G2, …, Gk-2/Gk-1, Gk-1/I  Gk-1. Доказать, что все композиционные ряды конечной группы G имеют один и тот же ряд дополнительных групп, если отвлечься от порядка расположения этих дополнительных групп и не считать различными изоморфные группы (другими словами, ряды дополнительных групп любых двух композиционных рядов конечной группы G могут отличаться друг от друга только порядком расположения групп, если не считать различными изоморфные группы – теорема ЖорданаГѐльдера). Указание Утверждение верно для любой конечной группы порядка 2, ибо всякая такая группа – простая и имеет единственный композиционный ряд. Пусть подлежащее доказательству утверждение верно для всех конечных групп, порядок которых m удовлетворяет неравенствам: 2  m  n. Доказать, что утверждение сохраняет свою справедливость и для любой конечной группы G порядка n+1. С этой целью рассмотреть любые два композиционных ряда группы G: G, G1, G2,…, Gk-1, I (1) и G, G1 , G2 ,…, Gs  1 , I (2) Пусть D= G1  G1 (согласно упражнению (р), D – максимальный нормальный делитель групп G1 и G1 ) и D, D1,…, D , I – какой-либо композиционный ряд, составленный для группы D. Рассмотреть еще два композиционных ряда группы G: G, G1, D, D1, …, D , I (3) и G, G1 , D, D1, …, D , I (4) Убедиться (на основании предположения индукции), что ряды дополнительных групп для композиционных рядов (1) и (3) отличаются только порядком. Далее, установить, что ряды дополнительных групп для композиционных рядов (3) и (4) отличаются только порядком (ибо, согласно результатам упражнения (р), G/G1  G1 /D, а G1/D  G/ G1 ). И, наконец, убедиться (на основании предположения индукции), что ряды дополнительных групп для композиционных рядов (4) и (2) отличаются только порядком. Вывести следствие из теоремы Жордана-Гѐльдера: ряды индексов (G:G1), (G1:G2), …, (Gk-1:I) для различных композиционных рядов одной и той же конечной группы G могут отличаться лишь порядком. (s) Группа, образованная степенями какого-нибудь элемента а  е, называется циклической группой. Ясно, что всякая циклическая группа – абелева, 50

т.е. подчиняется коммутативному закону. Доказать, что всякая циклическая группа простого порядка – циклическая. Конечная группа G  I называется разрешимой, если для ее композиционного ряда (любого) G, G1, G2,…, Gm, I ряд индексов (G:G1), (G1:G2), …, (Gm:I) состоит исключительно из простых чисел (другими словами, порядки всех дополнительных групп G/G1, G1/G2, …, Gm/I суть простые числа). Доказать, что всякая циклическая группа разрешима. Указание Если G – циклическая группа простого порядка, то ее композиционный ряд имеет вид G, I и разрешимость группы G очевидна. Пусть G имеет порядок n, где n – составное число и пусть группа G образована степенями элемента а  е: G={ e, a, а2, …, аn-1}. Если р – один из простых делителей числа n, так, что n=pq, то рассмотреть элементы e, ap, (ap)2, …, (ap)q-1. Установить, что эти элементы попарно различны и составляют циклический нормальный делитель группы G. Убедиться, что G1={e, ap, a2p, …, a(q-1)p} есть максимальный нормальный делитель группы G (ибо G/G1 – простая группа, т.к. имеет порядок (G:G1)=n:q=p). Если q – простое число, то композиционный ряд группы G имеет вид G, G1, I и индексы (G:G1), (G1:I) суть простые числа. Если же q – составное число, то в отношении циклической группы G1, можно провести те же рассуждения, что и для группы G. Замечание Доказательство разрешимости всякой абелевой группы G  I (а не только циклической) читатель может найти, например, в книге Н. Чеботарева «Основы теории Галуа». (t) Пусть (G,  ) – заданная группа. Элементы группы, представимые в виде aba-1b-1 при каких-либо а, b G, называются коммутаторами (см. упражнение 1(n)). Абелева группа имеет лишь единственный коммутатор (единица группы). Множество Н всех тех элементов из G, каждый из которых либо является коммутатором, либо является произведением двух или нескольких коммутаторов, - очевидно, замкнуто относительно групповой операции. Следовательно, (Н,  ) – подгруппа группы (G,  ), называемая коммутантом или производной группой заданной группы. Доказать, что производная группа (Н,  ) группы (G,  ) является нормальным делителем заданной группы и, вообще, любой группы (U,  ), содержащей группу (G,  ) в качестве нормального делителя. Указание Достаточно показать, что для любого с U с-1Нс  Н. Пусть h – любой элемент Н. Если h –коммутатор, т.е. h= aba-1b-1 (а, b G), то и с-1hс= =с-1 aba-1b-1 с=(с-1aс)( с-1bс)( с-1a-1 с)( с-1b-1 с)= (с-1aс)( с-1bс)(с-1aс) -1( с-1bс) -1 является коммутатором группы G, ибо с-1aс G с-1bс G (ведь G - нормальный делитель группы U). Если h есть произведение двух или нескольких коммутаторов из G, то аналогично предыдущему доказать, что с-1hс есть произведение такого же числа коммутаторов из G. (u) Доказать, что если (Н,  ) – производная группа группы (G,  ), то дополнительная группа (G/H,  ) – абелева. Указание Для любых а, b G (На)  (Нb)= (На)  (bН)=Н(aba-1b-1)  (bаН)

51

(v) Доказать, что если (Н,  ) – нормальный делитель группы (G,  ) и дополнительная группа (G/H,  ) – абелева, то Н заключает в себя все элементы производной группы. Указания Достаточно установить, что для любых а, b G aba-1b-1 Н. Так как (На)  (Нb)=(Нb)  (На)=, то Н  ab=Н  ba (Н – нормальный делитель!), откуда ab=h  ba при некотором h Н. (w) Пусть Н- производная группа группы G и Н  G (для краткости мы допускаем вольность в обозначениях). Считая известным факт разрешимости любой абелевой группы, отличной от единичной группы (см. замечание к упражнению 1(s)), доказать следующее: либо Н – максимальный нормальный делитель простого индекса группы G, либо при некотором k N существуют группы G1, G2,…, Gk такие, что в ряду G, G1, G2,…, Gk, Н каждая группа, начиная со второй, является максимальным нормальным делителем предыдущей и все индексы (G:G1), (G1:G2), …, (Gk:Н) являются простыми числами. Указание Так как группа G/H – абелева (см. упражнение 1(u)), то она разрешима. Убедиться, что если ее композиционный ряд имеет вид G/H, I* (где I*={H}), причем обязательно (G/H : I*) – простое число, то Н - максимальный нормальный делитель простого индекса группы G. В общем случае композиционный ряд группы G/H имеет вид (при некотором k N ) G/H, U1, U2,…Uk, I*, где индексы (G/H:U1), (U1:U2), …, (Uk:I*) суть простые числа. Пусть Gi есть объединение смежных классов, принадлежащих Ui (i=1, 2, … k). Тогда G  G1  G2  …  Gk  Н. Доказать, что при любом i Gi есть делитель и, притом, нормальный делитель группы G (при доказательстве нормальности делителя Gi воспользоваться тем свойством, вытекающим из коммутативности группы G/H, что для любых а, b G ab=h  ba при некотором h Н). Пусть далее,  (А) означает число элементов любого конечного множества А. Тогда  (G)=  (G/H)   (Н),  (G1)=  (U1)   (Н),  (G2)=  (U2)   (Н), …,  (Gk)= =  (Uk)   (Н), откуда (G:G1)=(G/H:U1), (G1:G2)= =(U1:U2), …, (Gk:Н)= (Uk:I*) (х) Пусть G  I – конечная группа и ряд G, Н, Н1, Н2,… - состоит из групп, каждая из которых, начиная со второй, является производной группой предыдущей. Доказать, что группа G разрешима тогда и только тогда, когда упомянутый ряд оканчивается единичной группой. Указание Если ряд последовательных производных групп имеет вид G, Н, Н1, Н2,…, Нk, I (где Н, Н1, Н2,…, Нk отличны от I), то H  G, Н1  Н, …, Нk  Нk-1. Применяя результаты упражнения 1(w) достаточное число раз, установить разрешимость группы G. Пусть теперь группа G – разрешима и требуется установить, что ряд G, Н, Н1, Н2,… оканчивается единичной группой. Доказать, что группа Н отлична от G (и потому имеет порядок, меньший, чем у G) и либо Н=I, либо группа Н разрешима. С этой целью рассмотреть какой-либо максимальный нормальный делитель G1 группы G (G1  G). В силу разрешимости группы G, индекс (G:G1) есть простое число. Следовательно, дополнительная группа G/G1 – простого порядка, а потому является циклической и абелевой. Согласно 1(v), Н  G1 и потому H  G. Используя результаты упражнения 1(w), убедиться, 52

что Н является членом композиционного ряда разрешимой группы G, а потому либо Н=I, либо H  I , но является разрешимой группой. В последнем случае, рассуждая аналогично вышеизложенному, убедиться, что группа Н1 – меньшего порядка, чем Н и либо Н1=I, либо группа Н1  I, но является разрешимой группой и т.д. (у) Доказать, что всякая разрешимая группа G либо сама абелева, либо содержит отличный от единичной группы (и от G) абелев нормальный делитель. Указание Если G не является абелевой группой, то ряд ее последовательных производных групп имеет вид Н1, Н2,…, Нk, I, где k  1 и группы Н1, Н2,…, Нk отличны от I (и от G). Так как I – коммутант группы Нk, то Нk - абелева группа. Чтобы убедиться в нормальности Нk (и, вообще, - всех производных групп) по отношению к G, достаточно несколько раз применить доказанное в упражнении 1(t).   I разрешимой группы G сама раз(z) Доказать, что всякая подгруппа G решима.  ряды последовательных производных Указание Составить для G и G групп: G, Н, Н1, Н2,…, Нk, I; , H k, H k  1 .  1, H , H  2 , …, H G  есть подгруппа Н и при любом Убедиться (последовательно) в том, что H  i есть подгруппа Нi . Вывести отсюда, что H  k  1 =I (вполне моi=1, 2, …, k H  1 =I и т.д.)  =I или H жет случиться, что уже H 2. Рассмотрим множество  k (k N) всех подстановок k цифр, т.е. множество всех биективных отображений множества Nk на себя. Это множество, рассматриваемое вместе с операцией суперпозиции отображений, является группой (см. 1.26 (b) и 1.31 (с)). Согласно 1.85 (f) порядок этой группы (которую часто называют симметрической группой подстановок k-ой степени) равен k! (а) Пусть р N и 1  р  k. Подстановка f  k называется р-членным циклом, если выполняются следующие условия: 1) среди цифр 1, 2, … k имеются р цифр i1, i2, …ip таких, что множество {i1, i2, …ip} переводится подстановкой f в самое себя, но никакое непустое собственное подмножество множества {i1, i2, …ip} не переводится подстановкой f в самое себя; 2) при р
остальные цифры на своих местах. Двучленный цикл называется также транспозицией, а k-членный цикл f  k называется еще круговой подстановкой. Доказать, что если подстановка f  k является р-членным циклом (1  р  k) и множество {i1, i2, …ip}  {1, 2, …k} удовлетворяет выше указанным условиям 1) и 2), то числа j1=i1, j2=f( j1), …, jp=f( jp-1) попарно различны и представляют собой те же числа i1, i2, …ip, только расположенные, быть может, в другом порядке. Доказать также, что f( jp)=j1. Замечание р-членный цикл f будем записывать в виде [j1 j2 …jp]. При этом предполагается, что f( j1)=j2, f( j2)=j3, …, f( jp-1)= jp, f( jp)=j1 (цикл замкнулся). Предполагается также, что цифры, не записанные внутри квадратных скобок, являются неподвижными точками отображения f (для записи циклов часто применяют круглые скобки, но мы используем круглые скобки для записи  1 2 3 4 5 перестановок). Например, в предположении, что k=5, [14]=  , 4 2 3 1 5   1 2 3 4 5  1 2 3 4 5 [235]=  , [15342]=  5 1 4 2 3. 1 3 5 4 2    (b) Доказать, что всякая подстановка f  k либо является циклом, либо может быть представлена в виде произведения двух или нескольких циклов (под произведением двух подстановок  и  1 мы понимаем суперпозицию   1 ). Эти циклы можно считать не имеющими общих цифр. Указание Будем говорить, что подстановка f перемещает цифру i Nk, если f(i)  i. Если она не перемещает ни одной цифры, то f представляет собой тождественную подстановку, т.е. одночленный цикл. Пусть  - количество цифр, перемещаемых подстановкой f, и   N (2    k ). Если А множество цифр, перемещаемых подстановкой f, то f(А)=А.. Если при этом никакое собственное подмножество множества А (непустое) не переводится подстановкой f в само себя, то f есть  -членный цикл. В противном случае найдется непустое собственное подмножество В множества А такое, что f(В)=В, то никакое непустое собственное подмножество множества В не переводится подстановкой f в само себя. Пусть р – количество цифр множества В (2    k ). Взяв любую цифру i1 B, найдем i2=f(i1), …, iр=f(iр-1). Доказать, что f=[i1 i2 …ip]   , где  имеет своими неподвижными точками i1, i2, …ip и все неподвижные точки подстановки f, а на множестве А\В  совпадает с f:  (j)=f(j) для любого j А\В. Заметить, что количество цифр, перемещаемых подстановкой  , равно  -р<  . Применяя к  рассуждения, аналогичные вышеприведенным, убедиться в том, что f представимо в виде произведения двух или нескольких циклов без общих цифр. (с) Пусть i1, i2, …ip суть р попарно различных цифр множества {1, 2, … k} и f=[i1 i2 …ip] есть р-членный цикл. Рассматривая различные степени этого цикла: [i1 i2 …ip]2=f  f, [i1 i2 …ip]3= f  (f  f) и т.д., доказать (методом математической индукции), что при любом n N подстановка [i1 i2 …ip]n переводит 54

цифру is (s=1, 2, …, p) в цифру ir, где r определяется следующим образом. Если s+n не кратно р, то r есть остаток от деления s+n на р; если же s+n кратно р, то r=р. Вывести из доказанного, что порядок р-членного цикла, как элемента группы  k, равен р. (d) Записать все подстановки группы  3 (кроме тождественной подста1 2 3  новки е=   ) в виде циклов и доказать, что группа  3 имеет одну под1 2 3   группу порядка 3 и три подгруппы порядка 2. Убедиться, что все эти подгруппы – циклические. Легко видеть, что подстановки е , [12], [34] группы  4 не меняют выражения х1  х2+х3  х4 (где под х1, х2, х3, х4 понимаются некоторые числа). Найти все подстановки группы  4, не меняющие указанное выражение, и убедиться, что они составляют подгруппу порядка 8. Показать, что группа (так называемая Vierergruppe), е, [12]  [34], [13]  [24], [14]  [23], сама являющаяся подгруппой предыдущей группы порядка 8 – абелева, но не циклическая. (е) Пусть (i1 i2 …ik) – какая-либо перестановка цифр 1, 2, …, k. Если s Nk, s>1, но is
цифрами it-2 , it-3, …, получая перестановки P 2, P 3, … . Через t-s таких операций получим перестановку P t-s=(i1 i2 …is-1  is+1 … it-1 it+1…ik). Будем теперь последовательно менять местами цифру  с цифрами is+1 , is+2 … it-1, получая перестановки P t-s+1, P t-s+2, …. Через t-s-1 таких операций получим перестановку P 2(t-s)-1=Ff( P ). Таким образом, перестановка Ff( P ) получается из перестановки P с помощью нечетного числа операций, каждая из которых меняет четность перестановки. Следовательно, перестановки P и Ff( P ) – разной четности. (f) Легко видеть, что любой цикл может быть разложен в произведение транспозиций: [  ]=[  ]  [  ]; [  ]=[  ]  [  ]  [  ] и т.д. Пользуясь результатами упражнений 2 (b) и 2 (е), доказать, что всякая подстановка может быть разложена в произведение транспозиций, причем при различных способах разложения четность числа транспозиций – «множителей» не меняется (т.е. это число либо четное при всех способах разложения подстановки, либо всегда нечетное). Убедиться, что если подстановка может быть представлена в виде произведения m циклов и порядки этих циклов равны соответственно n1, n2, …, nm , то подстановка может быть разложена в произведение n1+ n2+ …+nm – m транспозиций. Подстановка называется четной (нечетной), если она разлагается в произведение четного (нечетного) числа транспозиций. Например, подстановка (принадлежащая  9) 1 2 3 4 5 6 7 8 9  4 6 5 1 8 7 2 9 3  =[14]  [267]  [3589] может быть представлена в   виде произведения 2+3+4-3=6 транспозиций и потому является четной подстановкой. Доказать, что подстановки f и f -1 всегда либо обе четные, либо обе 1 2  k  нечетные. Доказать, что подстановка   является четной тогда и  i1 i 2  ik  только тогда, когда перестановка (i1 i2 …ik) – четная. Доказать, что подста i1 i 2  ik  новка   является четной тогда и только тогда, когда либо обе j 1 j 2  j k   перестановки (i1 i2 …ik), (j1 j2 …jk) – четные, либо обе они – нечетные. Докаk! зать, что группа  k содержит четных и столько же нечетных подстано2 вок. Ясно, что четные подстановки группы  k составляют группу, которая называется знакопеременной группой подстановок k-ой степени. Мы будем обозначать эту группу символом Uk. Доказать, что каждую четную подстановку при k  3 можно разложить в произведение трехчленных циклов. Указание Достаточно установить, что произведение двух несовпадающих транспозиций можно представить либо в виде одного трехчленного цикла, либо в виде произведения двух трехчленных циклов. Если транспозиции [  ] и [  ] не содержат общей цифры, то [  ]  [  ]= =([  ]  [  ])  ([  ]  [  ])=[  ]  [  ]. Тождественную подстановку е

56

можно представить в виде произведения двух трехчленных циклов следующим образом: е=[  ]  [  ] (g) Группа G подстановок k цифр 1, 2, …, k (т.е. группа  k или одна из ее подгрупп) называется транзитивной, если для любой пары цифр (i, j) NkxNk в рассматриваемой группе найдется подстановка, переводящая цифру i в цифру j. Если это условие не выполняется, то группа G называется интранзитивной. Так, например, Vierergruppe (см. упр. (d)) является транзитивной группой, а группа {е, [12], [34], [12]  [34]} – интранзитивна (в обоих случаях k=4). Доказать, что если группа G подстановок k цифр – интранзитивна, то отрезок натурального ряда Nk={1, 2, …k} можно разбить на попарно непересекающиеся подмножества, называемые системами интранзитивности группы G, характеризующиеся следующими свойствами: 1) группа G содержит подстановки, переводящие друг в друга любые цифры одной и той же системы интранзитивности; 2) группа G не содержит подстановок, переводящих друг в друга цифры разных систем интранзитивности. Указание Пусть R – отношение в множестве {1, 2, …k} определяемое следующим образом: iRj тогда и только тогда, когда в группе G есть хотя бы одна подстановка, переводящая i в j. Установить, что R – отношение эквивалентности и рассмотреть разбиение множества {1, 2, …k} на классы эквивалентности по отношению R. (h) Группа подстановок k цифр 1, 2, …k называется m раз транзитивной (1  m  k), если для любых двух наборов m цифр i1, i2, …im и j1, j2, … jm (каждый набор состоит из различных чисел отрезка Nk натурального ряда, но некоторые числа могут быть общими для обоих наборов) в группе G найдется подстановка, переводящая i1 в j1, i2 в j2, …, im в jm. Очевидно, что симметрическая группа  k k раз транзитивна. Доказать, что знакопеременная группа Uk (состоящая из четных подстановок k цифр 1, 2, … k) k-2 раза транзитивна, но не является k-1 раз транзитивной. Указание Пусть i1, i2, …ik-2 и j1, j2, … jk-2 два набора различных чисел, принадлежащих отрезку Nk натурального ряда. Пусть также {ik-1, ik}= =Nk\{i1, i2, …ik-2}, {jk-1, jk}=Nk\{j1, ji2, …jk-2}. Рассмотреть подстановки  i1 i 2  ik  2 ik  1 ik   i1 i 2  ik  2 ik  1 ik   j1 j 2  jk  2 jk  1 jk  и  j1 j 2  jk  2 jk  и доказать, j k  1     что одна из них – четная. Убедиться также, что ни одна подстановка из Uk не может перевести цифры 1, 2, 3, 4, …, k-1 соответственно в цифры 2, 1, 3, 4, … k-1. (i) Про транзитивную группу подстановок k цифр будем говорить, что она имеет одну систему интранзитивности {1, 2, …k}. Пусть G – группа подстановок k цифр (транзитивная или нет) и {i1, i2, …im} – одна из ее систем интранзитивности (1  m  k). Зафиксируем любую цифру is (1  s  m) рассматриваемой системы интранзитивности и пусть Нs – множество всех подстановок группы G, оставляющих цифру is на месте. Доказать, что Нs – подгруппа 57

группы G (очевидно, наибольшая из подгрупп, оставляющих цифру is на месте) и что (G:Нs)=m. Указание Для любого р Nm найти подстановку fp G, переводящую iр в is (fs Нs), и рассмотреть смежные классы Нs f1, Нs f2,…, Нs fm . Доказать, что они попарно не пересекаются (если, например, смежные классы Нs f1 и Нs f2 имеют общий элемент, то найдутся подстановки  ,    Нs такие, что   f1=    f2 , откуда f11   1 = f 21   1 . Убедиться в невозможности этого равенства. m

Установить, далее, равенство G=  Hsfp (если   G и переводит в is цифp 1

ру j, то цифра j должна принадлежать той же системе интранзитивности, что и цифра is, т.е. j=ip при некотором p Nm. Следовательно,   f p1  Нs и   Нs fр). Проиллюстрировать доказанное на примере интранзитивной группы {е, [12], [34], [12]  [34]}. Вывести из доказанного следствие, относящееся к транзитивной группе подстановок k цифр. (j) Рассмотрим подстановки двух абелевых групп (k=4), одна из которых (Vierergruppe) транзитивна, а вторая – интранзитивна: {е, [12]  [34], [13]  [24], [14]  [23]} и {е, [12], [34], [12]  [34]}. Каждая подстановка первой группы разлагается в произведение циклов (без общих цифр), порядки которых одинаковы (е=[1]  [2]  [3]  [4]). Не так обстоит дело с подстановками второй группы. Например, подробная запись разложения подстановки [12] в произведение циклов без общих цифр (и содержащая явно все цифры 1, 2, 3, 4) имеет вид [12]= [12]  [3]  [4] и это разложение содержит циклы разных порядков. Доказать, что подобная ситуация не может иметь места для транзитивных абелевых групп. А именно, доказать, что каждая подстановка, кроме круговой, транзитивной абелевой группы G разлагается в произведение циклов (без общих цифр), порядки которых равны между собой. Указание Допустив противное, найти подстановку f G, разложение которой в произведение циклов (без общих цифр) содержит циклы разных порядков. Обозначив через m наименьший из порядков циклов, входящих в разложение подстановки f, рассмотреть подстановку  =fm. Эта подстановка должна перемещать некоторые из цифр 1, 2, 3, … k, но не все. Пусть  переводит цифру i1 в цифру i2  i1 , а цифру i3 оставляет на месте. В силу транзитивности группы G в ней найдется подстановка  , переводящая i3 в цифру i1. А так как группа G – абелева, то       . Убедиться, однако, что подобное равенство не может иметь места. Замечание Транзитивная абелева группа может содержать круговые подстановки, которые не разлагаются в произведение двух или нескольких циклов без общих цифр. Таковы, например, следующие подгруппы групп  3 и  4 : {е, [123], [132]} и {е, [1234], [13]  [24], [1432]}. 58

(к) Доказать, что порядок транзитивной абелевой группы подстановок k цифр равен k. Указание Если какая-нибудь подстановка f  e транзитивной абелевой группы оставляет одну из цифр, например, is на месте, то f разлагается в произведение циклов разных порядков. Так как это противоречит доказанному в 2(j), то для транзитивной абелевой группы подгруппа Нs всех подстановок, оставляющих цифру is на месте, совпадает с единичной группой. Применить результат упражнения 2(i). (l) Пусть G – группа подстановок k цифр и f,   G. Доказать, что если f является р-членным циклом (1  р  k), т.е. f=[  1 2... p ], то и подстановка  1  f   , преобразованная из f при помощи  , является р-членным циклом:  1  f   =[  1 2... p ], где  i =  1 (  i ), i=1, 2, …, р. Указание Записать подстановку  1 в виде 1  2   p  p  1   k    1  2   p  p  1   k  и определить, в какую цифру переводится   каждая из цифр  1,  2, ...,  p,  p  1, ...,  k суперпозицией  1  f   . Сформулировать общее правило преобразования подстановки f при помощи  , заметив, что если f=f1  f2  …  fm , то  1  f   =(  1  f1   )   (  1  f2   )  …  (  1  fm   ) Убедиться, что Vierergruppe {е, [12]  [34], [13]  [24], [14]  [23]} является нормальным делителем симметрической группы  4 , а группа {е, [1324], [1423], [12]  [34], [13]  [24], [14]  [24], [12], [34] } подстановок, не меняющих выражения х1х2+х3х4, не является нормальным делителем группы  4 . Чтобы обосновать последнее утверждение, достаточно преобразовать подстановку [12] или [34] с помощью подстановки [23]  4 . Доказать, что знакопеременная группа Uk является нормальным делителем симметрической группы  k при любом k  2 (максимальным). Найти композиционный ряд симметрической группы  4 и убедиться в ее разрешимости. (m) Доказать, что при k  5 знакопеременная группа Uk проста, , т.е. не имеет нормальных делителей, отличных от Uk и единичной группы. Указание Пусть Н – нормальный делитель группы Uk, отличный от единичной группы, и требуется доказать, что Н= Uk. Достаточно установить, что Н содержит хотя бы один трехчленный цикл [i1i2i3]. Тогда, если [j1j2j3] – любой трехчленный цикл, то в группе Uk найдется подстановка  i1 i 2 i 3   f=  (ибо Uk k-2 раза транзитивна), причем f  [i1i2i3]  f -1 H.   j1 j 2 j 3   Так как f  [i1i2i3]  f -1=[j1j2j3] (убедиться в этом), то из принадлежности группе Н хотя бы одного трехчленного цикла следует принадлежность этой группе и любого трехчленного цикла. Отсюда, в свою очередь, следует принадлежность группе Н любой четной подстановки (см. 2(f)), что и доказывает равенство Н=Uk в случае, когда Н 59

содержит хотя бы один трехчленный цикл. Чтобы доказать такую принадлежность, рассмотреть подстановку   Н, отличную от тождественной и перемещающую наименьшее количество цифр (по сравнению с другими нетождественными подстановками группы Н). Убедиться, что разложение подстановки  в произведение циклов без общих цифр (одночленные циклы опускаются) должно содержать либо один цикл, либо несколько циклов равных порядков. Рассмотреть следующие возможные случаи. 1)  представляет собой цикл порядка m  4:  =[i1 i2 i3 i4…im]. Взяв подстановку f=[i1i2i3] Uk , убедиться в том, что [i1imi3]=(f   1  f -1)   Н 2)  разлагается в произведение циклов (без общих цифр) порядка m  4:  =[i1 i2 i3 i4…im]  [im+1 im+2… i2m]  … . Как и в случае 1) убедиться, что [i1imi3] Н. 3)  разлагается в произведение двух или нескольких трехчленных циклов (случай, когда  представляет собой трехчленный цикл, не нуждается в особом рассмотрении):  =[i1 i2 i3]  [i4 i5 i6]  … Взяв подстановку f=[i1 i2 i4] Uk, убедиться в том, что [i1 i3 i6 i2 i4]= (f   1  f -1)   Н. Но тогда, согласно 1), Н содержит и трехчленный цикл. 4)  разлагается в произведение двух или нескольких двучленных циклов:  =[i1 i2]  [i3i4]  … Так как k  5, то найдется цифра j Nk, отличная от i1, i2, i3, i4. Пусть s=  (j) (ясно, что s, как и j, отлично от i1, i2, i3, i4). Убедиться, что при s=j [i1 j i2]=  1  ( f -1    f) Н, где f=[i1 i2 j] Uk. При s  j в разложение  входит цикл [js]. Убедиться, что в этом случае [i1s]  [ i2j]=  1  ( f -1    f) Н. Взяв подстановку  =[i1 s i3]  Uk, установить, что [i1 i3 s]=[i1s]  [ i2j]  ( 1  [i1s]  [ i2j]   ) Н. (n) Доказать, что симметрическая группа  k при k  5 не содержит нормальных делителей, кроме знакопеременной группы (отличных от  k и I). Указание Если Н – нормальный делитель группы  k , отличный от  k , Uk и I, то Н  Uk=I (ибо Н  Uk – нормальный делитель групп  k и Uk, а группа Uk – простая и Uk  Н). Следовательно, все подстановки группы Н, кроме тождественной, - нечетные. Не ограничивая общности, можно считать Н максимальным нормальным делителем группы  k . В силу 2(l) и 2(m), один из композиционных рядов группы  k имеет вид  k , Uk, I с рядом индексов 2, k! k! . На основании 1(r) можем утверждать, что либо (G:H)=2, либо (G:H)= . 2 2 Убедиться в невозможности обоих этих случаев. При доказательстве обраk! тить внимание на следующее. Если (G:H)= , то Н должна содержать (кроме 2 тождественной подстановки) только одну (нечетную) подстановку f, которая (так как f2=e) может быть только транспозицией или произведением нечетного числа транспозиций без общих цифр. При этом для любой подстановки    k должно выполняться равенство  1  f   =f. Проверить, что это ра60

венство нарушается и при f=[i1 i2] и при f=[i1 i2]  [i3 i4]  [i5 i6]  …, если взять  =[i1 i2 i3]. 3. Индукцией по числу n  N доказать следующую формулу Ньютона для n-ой степени бинома (двучлена) х+1 (где под х пока понимается натуральное число): (x+1)n= Cn0 x n + Cn1 x n1 +…+ Cnk x nk +…+ Cnn1 x + Cnn n

Или, коротко, (x+1)n=  Cnk x nk (под х0 понимается 1). Вывести формулу для (x+а) (х, а N)

k 0

n

Указание Воспользоваться результатами 1.85(d) 4. Обозначим Sn( k ) =1k+2k+…+nk (n, k N). Написать формулу Ньютона для (x+1)k+1 и положив в ней последовательно х=1, 2, …, n, вывести, пользуясь полученными равенствами, формулу (n  1)k 1  (n  1) 1 k 1 i 1 ( k i ) (k )  Sn =  Ck 1 Sn (k  2). k 1 k  1 i 1 Эта формула позволяет вычислить Sn( k ) , зная Sn(1) , Sn(2) , …, Sn( k 1) . Учиты(n  1)n вая, что , доказать, что Sn(1) =1+2+3+…+n= 2 n(n  1)(2n  1) 12+22+…+n2= и 13+23+…+n3=(1+2+3+…+n)2. Найти выражение 6 (4) для Sn . 5. Доказать, что при n  5 2n>n2, а при n  10 2n>n3. Выяснить, при каких значениях n 2n>n4. 6. Доказать, что 2n  n!<(n+1)n при n>1. Указание Применить индукцию по числу n. Использовать неравенство (n+2)n+1>2(n+1)n+1, которое выводится из формулы Ньютона n+1 n+1 n (х+1) =x +(n+1)x +…, если положить x=n+1. 7. Доказать (индукцией по числу n), что при n  3 выполняется неравенство (n+1)n
61

10. Написаны n  2 писем n различным адресатам и заготовлены n конвертов с их адресами. Сколькими способами можно вложить письма в конверты, чтобы ни одно письмо не попало тому лицу, которому оно адресовано? (задача Бернулли-Эйлера о перепутанных письмах). Указание Пронумеровав письма и соответствующие им конверты цифрами 1, 2, 3, …, n, легко заметить, что задача сводится к нахождению числа an круговых подстановок (т.е. подстановок, перемещающих все цифры 1, 2, 3, …, n), содержащихся среди n! подстановок n цифр. Доказать, что число подстановок, оставляющих на месте ровно k цифр (1  k  n-2, n  3), равняется Cnk an  k . Вывести из этого (учитывая, что число подстановок, оставляющих на месте ровно n-1 цифр, равняется 0), что an следующим образом выражается через a2, a3, …, an-1: an=n!-[ Cn1an  1 + Cn2 an  2 +…+ Cnn2 a 2 +1]. Эта формула позволяет (с учетом очевидного равенства a2=1) последовательно находить a3, a4, …. Замечание Соотношения, выражающие n-ый член последовательности через предыдущие ее члены называются возвратными или рекуррентными соотношениями. Можно выразить an непосредственно через n, но мы на этом не останавливаемся, так как пока считаем изученными только натуральные числа. Интересующийся этим вопросом читатель может найти вывод форму(1) n 1 1 1 лы an=n! [ - + -…+ ], например, в книге С. Сташевича и Е. Бров2! 3! 4! n! кина «Польские математические олимпиады», 1978. 11. Доказать, что если натуральные числа x, y, z, n удовлетворяют уравнению xn+yn=zn, то min(x; y)  n (под min(x; y) понимается наименьшее из чисел x, y). Указание Пусть min(x; y)= х . Так как zn> yn, то z> y, откуда z  y+1 и zn  yn+nyn-1. 12. Рассмотрим всевозможные перестановки натуральных чисел 1, 2, 3, …, 99, 100. Пусть А – множество всех таких натуральных чисел а, что в любой перестановке чисел 1, 2, 3, …, 99, 100 найдется десятка последовательных чисел, сумма которых больше или равна а. Найти наибольшее число множества А. Указание Рассмотреть перестановку  =(100 99 98 97 96 1 2 3 4 5 95 94 93 92 91 6 7 8 9 10..55 54 53 52 51 46 47 48 49 50). Она получается из основной перестановки (1 2 3 4 5 … 94 95 96 97 98 99 100) следующим образом. Выписываются в убывающем порядке пять последних чисел основной перестановки, а затем – в порядке возрастания – пять первых чисел основной перестановки. С оставшейся частью основной перестановки поступаем таким же образом и т.д. до исчерпания основной перестановки. Убедиться, что максимальная сумма десяти последовательных чисел перестановки  равна 505. Следовательно, 506 А. Остается доказать, что 505 А. С этой целью в любой перестановке (  1,  2, …,  100) чисел 1, 2, 3, …100 рассмотреть следующие десятки последовательных чисел: 1)  1,  2, …,  10; 2)  11,  12, …,  20; …, 10)  91,  92, …,  100. Если допустить, что в каждой из этих десяток сумма 62

чисел <505, то сумма всех чисел 1, 2, 3, …100 должна быть <5050. Но эта 1  100 сумма равна  100=5050. 2 13. Сколькими способами множество, содержащее четное число n элементов, можно разбить на непересекающиеся множества, каждое из которых содержит по два элемента? Указание Обозначив искомое число способов через аn , доказать справедливость рекуррентного соотношения аn=(n-1) аn-2 (n  4). Вывести отсюда (учитывая, что а2 =1), что аn =1  3  …  (n-1). В правой части здесь фигурирует произведение последовательных нечетных чисел от 1 до n-1, которое обозначается (n-1)!! Символ «!!» читается «факториал дважды». Вообще, через k!! обозначается произведение всех натуральных чисел, не превосходящих k и одной четности с k. 14. Доказать, что n человек (n  5), сидящих за круглым столом, можно пересадить так, чтобы у каждого из сидящих оказались по два новых соседа. Указание Занумеровав сидящих за круглым столом цифрами 1, 2, …, n (переходя от одного сидящего к другому, скажем, по часовой стрелке), рассмотреть отдельно случай четного n и случай нечетного n. Если n нечетно и n=2k+1 (k  2), то сидевших первоначально в порядке 1, 2, 3, 4, …2k-1, 2k, 2k+1 можно расположить в порядке 1, 3, 5, …, 2k-1, 2k+1, 2, 4, …, 2k. Убедиться, что при этом каждый из сидящих получит два новых соседа. Найти новое расположение сидящих за круглым столом (удовлетворяющее условиям задачи) при четном n. 15. Пусть А – n-элементное множество, состоящее из натуральных чисел и S(A) – множество сумм двух различных чисел из А: S(A)={x N: x=a+ a , a A, a  A, a  a }. Пусть ms – число элементов множества S(A). Считая, что n  3, доказать, n(n  1) что каково бы ни было n-элементное множество A  N 2n-3  ms  . 2 Найти какое-либо множество А, для которого ms=2n-3 и какое-либо множестn(n  1) во A , для которого ms= . 2 Указание Расположив числа, составляющее множество А, в порядке возрастания: а1
16. Из n человек (n  4), среди которых есть знакомые и незнакомые между собой лица (отношение знакомства симметрично), выбираются по произволу m человек (3  m
1 2

3

А1,2,3

А1,2 А1

Тогда k1  k+1, k1+m1+1=n. Убедиться, что k1,2+1+ m1  k2, где k2 – число тех из присутствующих, кто знаком со вторым из выбранных лиц (k2  k+1). Оценить величину k1,2 и выбрать из множества А1,2 по произволу третьего из искомой четверки лиц. Пусть k1,2,3 – численность множества А1,2,3 тех из присутствующих, кто знаком со всеми тремя выбранными лицами. Доказать, что k1,2,3+k1 - k1,2+1+ m1  k3, где k3 - число тех из присутствующих, кто знаком с третьим из выбранных лиц (k3  k+1). Убедиться, что k1,2,3  3-r  1 и выбрать из множества А1,2,3 четвертого недостающего. 18. Доказать (индукцией по числу n), что если а1
ва. Под а1, a2, a3, …, an и b1, b2, b3, …, bn пока понимаются натуральные числа). Указание Предварительно установить, что аibk+akbi< аibi+akbk при любых i, k Nnтаких, что i  k. С этой целью, считая, например, что ia+b, то c>a и c-a>b. И обратно: из c>a и c-a>b следует, что с>a+b. При этом c-(a+b)=(c-a)-b (b) Если b>a и c>b-a, то c+a>b. И обратно: из c+a>b и b>a следует, что c>b-a. При этом c-(b-a)=(c+a)-b (c) Если b>a, то c+(b-a)=(c+b)-a. Если и c>a, то (c+b)-a=(c-a)+b. (d) Если b>a, то (b-a)2=(b2+a2)-2ab. Вывести отсюда, что для любых a, b N 2ab  a2+b2, причем равенство имеет место тогда и только тогда, когда a=b. 20. Доказать индукцией по числу n N (n  2), что для любых натуральных чисел а1, a2, a3, …, an (а1+a2+a3+…+an )2= a12 + a22 +…+ an2 +2а1(а2+a3+ +a3+…+an)+ 2а2(а3+a4+…+an)+…+ 2аn-2(аn-1+an)+ 2аn-1аn. Эта формула читается следующим образом: «Квадрат суммы нескольких чисел равен сумме квадратов этих чисел, сложенной с удвоенными произведениями каждого из этих чисел на каждое из последующих. 21. Доказать, что каковы бы ни были натуральное число n и числа (которые пока будем считать натуральными) а1, a2, a3, …, an и b1, b2, b3, …, bn – имеет место неравенство: (а1b1+a2b2+ +a3 b3+ …+an bn)2  ( a12 + a22 +…+ an2 )   ( b12 + b22 +…+ bn2 ) Указание Применить метод математической индукции. Воспользоваться следующей оценкой: (а1b1+a2b2+a3 b3+ …+an bn+an+1 bn+1)2=(а1b1+a2b2+a3b3+ …+anbn)2+2(а1b1+a2b2+a3 b3+ …+an bn) an+1 bn+1+ an21 bn21 =(а1b1+a2b2+a3b3+… …+an bn)2+2 a1bn+1 b1an+1+…+2 anbn+1 bnan+1+ an21 bn21  (а1b1+ …+anbn)2+( a12 + + a22 +…+ an2 ) bn21 +( b12 + b22 +…+ bn2 ) an21 + an21 bn21 (несколько раз использовано неравенство 2ab  a2+b2). Далее использовать предположение индукции. Замечание Доказываемое неравенство есть частный случай (поскольку мы имеем дело пока только с натуральными числами) так называемого неравенства Коши-Буняковского (иногда его называют также неравенством Шварца). Следует обратить внимание на то, что если числа а1, a2, a3, …, an kкратны (при некотором k N) соответственно числам b1, b2, b3, …, bn (т.е. а1=kb1, а2=kb2,…, аn=kbn), то неравенство Коши-Буняковского превращается в равенство (то же - когда числа b1, b2, b3, …, bn k-кратны числам а1, a2, a3, … …, an). 22. Доказать индукцией по числу n N (n  2), что при x>1(x N) имеет место равенство xn-1=(x-1)(xn-1+xn-2+…+x+1) 65

Указание Убедиться, что при любом n N xn+1>xn>1и xn+1-1=(xn+1-xn)+ +(xn-1)=xn(x-1)+(xn-1). Далее воспользоваться предположением индукции. Конец Главы I

66