ИФПМ (ПРИТ) / Учебник

Аналогично можно рассматривать суперпозицию трѐх отображений и т.д. Нетруд-

но проверить, что операция суперпозиции отображений удовлетворяет закону ассоциа-

тивности, т.е. ( fg)h f (gh) .

Определение 13. Отображение f : A A , для которого f (x) x для всех x A ,

называется тождественным и обозначается 1A или e .

Определение 14. Обратным для отображения f : A B называется такое отображение g : B A , что fg 1B и gf 1A . Обратное отображение часто обознача-

ют f 1 .

Пример 4. Пусть A 1, 2, 3 и

Определение 15. Пусть 2 – множество точек плоскости. Взаимно однознач-

ное отображение f : 2 2 , сохраняющее расстояния между точками, называется движением.

Примерами движений на плоскости являются параллельный перенос, поворот,

симметрия относительно некоторой прямой. Можно показать, что любое движение на плоскости можно представить в виде суперпозиции этих преобразований.

Определение 16. Точка A называется неподвижной для движения f , если f ( A) A . Движение, для которого все точки являются неподвижными, называется то-

ждественным. В дальнейшем тождественное движение будет обозначаться буквой e .

Можно показать, что движение, имеющее три неподвижных точки, не лежащие на одной прямой, является тождественным.

14.A 0,1 , B 0, 2 .

15.A 2,3 , B 4,7 .

16.A 3,6 , B 1,3 .

17.A 0,1, 1 , 1 , 1 ,..., 1 ,... , B 1, 1 , 1 , 1 ,..., 1 ,... .

2 3 4 n 2 3 4 n

18.A 0,1 , B 0,1 .

19.A 0,1 , B 0,1 .

20.A 0,1 , B .

21.Докажите, что суперпозиция двух движений является движением.

12

22.Докажите, что параллельный перенос, поворот относительно некоторой точки на некоторый угол и симметрия относительно некоторой прямой являются движениями.

23.Докажите, что если – это симметрия относительно некоторой прямой, то

2 e .

24.Пусть движение f имеет две неподвижные точки A и B . Докажите, что тогда вся прямая AB является неподвижной для преобразования f .

25.Пусть движение f имеет неподвижную прямую a и точку C a . Докажите,

что либо точка f (C) симметрична точке C относительно прямой a , либо f (C) C .

26. Докажите, что если f – движение, имеющее три неподвижные точки, не лежа-

щие на одной прямой, то f e .

27. Докажите, что если f – движение, имеющее неподвижную прямую a и не яв-

ляющееся тождественным отображением, то f – симметрия относительно прямой a .

28. Докажите, что суперпозиция двух параллельных переносов также является па-

раллельным переносом.

29. Пусть – симметрия на плоскости относительно прямой a , а – симметрия относительно прямой b . Пусть прямые a и b пересекаются и угол между ними равен .

Что собой представляют преобразования в ?

30. Пусть – симметрия на плоскости относительно прямой a , а – симметрия относительно прямой b . Пусть прямые a и b параллельны и расстояние между ними рав-

но d . Что собой представляют преобразования в в этом случае?

31. Пусть a – это поворот относительно точки A на угол , а b – это поворот от-

носительно точки B на угол . Докажите, что суперпозиция ab также будет с поворотом на угол . Где будет находиться центр этого поворота?

32. Докажите, что любое движение плоскости можно представить в виде суперпо-

зиции параллельного переноса, поворота и симметрии относительно некоторой прямой.

33. Докажите, что любое движение плоскости можно представить в виде суперпо-

зиции некоторого количества симметрий.

1.2. Бинарные отношения, их свойства. Отношения эквивалентности и порядка

Определение 1. Бинарным отношением на множестве A называется любое подмножество A A . Условимся писать a b , если a,b .

13

Пример 1. На множестве A 1;2;3 рассмотрим отношение порядка

1 1;1 , 1;2 , 1;3 , 2;2 , 2;3 , 3;3 .

Пример 2. На множестве натуральных чисел рассмотрим отношение делимо-

сти 2 . Будем считать, что n 2m n, m , если n делится на m . Например, 15 2 3 .

Пример 3. Пусть имеется функция f (x) , заданная на . Для x, y будем счи-

тать, что x f y , если y f (x) . Множество всех x,t f является графиком функции f (x) .

Пример 4. На множестве M2 ( ) матриц размера 2 2 с действительными коэф-

фициентами рассмотрим бинарное отношение 4 :

A 4 B , если det(A) det(B) A, B M2 ( ) .

Определение 2. Бинарное отношение на множестве A называется рефлек-

сивным, если каждый элемент множества A состоит сам с собой в бинарном отноше-

нии .

Определение 3. Бинарное отношение на множестве A называется симмет-

ричным, если a,b тогда и только тогда, когда b, a .

Определение 4. Бинарное отношение на множестве A называется антисим-

метричным, если a,b и b, a может быть только в том случае, когда a b .

Определение 5. Бинарное отношение на множестве A называется транзи-

тивным, если всегда, когда a,b и b, a , пара a,c также принадлежит .

Определение 6. Бинарное отношение , обладающее свойствами рефлексивно-

сти, симметричности и транзитивности, называется отношением эквивалентности.

Для элемента a A множество S(a) x A x a называется смежным классом отноше-

ния , содержащим a .

Определение 7. Бинарное отношение , обладающее свойствами рефлексивно-

сти, антисимметричности и транзитивности, называется отношением порядка. Мно-

жество с заданным на нѐм отношением порядка называется частично упорядоченным.

Два элемента, состоящие в отношении , называются сравнимыми.

Отметим, что отношения 1, 2 , 4 являются рефлексивными. Отношение f явля-

ется рефлексивным только в случае f (x) x . Отношение 4 симметрично, а 1, 2 – нет.

14

Отношения 1, 2 антисимметричны, а 4 – нет. Отношения 1, 2 , 4 транзитивны.

Отношение 4 является отношением эквивалентности, а 1, 2 – отношениями порядка.

Пример 5. Рассмотрим множество C a,b всех непрерывных функций на отрезке

a,b . Будем считать, что f (x) g(x) x a,b f (x) g(x) . Тогда множество C a,b бу-

дет частично упорядоченным.

Определение 8. Частично упорядоченное множество A , в котором любые два элемента сравнимы, называется линейно упорядоченным.

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

нейно упорядоченным, а множество C a,b из примера 5 – нет.

Определение 9. Разбиением множества A называется любое семейство под-

множеств Ai i I , обладающее двумя свойствами

1)i j Ai Aj ;

2)i I Ai A .

Предложение. Пусть – отношение эквивалентности на множестве A . Тогда семейство всех его смежных классов является разбиением множества A .

Обратно. Для любого разбиения множества A существует единственное отно-

шение эквивалентности на множестве A , для которого каждое из подмножеств раз-

биения является смежным классом отношения .

Доказательство. Пусть – отношение эквивалентности на множестве A . По-

скольку a S(a) , то объединение всех смежных классов отношения даст A . Осталось только показать, что любые два смежных класса либо не пересекаются, либо совпадают.

Рассмотрим S(a) и S(b) . Допустим, что S(a) S(b) . Покажем, что S(a) S(b) .

Действительно, пусть c S(a) S(b) и x S(a) . Тогда x a, a c,c b x b x S(b) . Та-

ким образом, S(a) S(b) . Аналогично S(b) S(a) , откуда S(a) S(b) .

Обратно. Пусть имеется разбиение Ai i I множества A . Определим следую-

щим образом: и y принадлежат одному и тому же подмножеству Ai данного разбиения. Очевидно, отношение обладает свойствами рефлексивности, симметрично-

сти и транзитивности и, значит, является отношением эквивалентности. Единственность отношения также очевидна.

15

Предложение доказано.

Определение 10. Пусть имеется множество A , на котором задано отношение эквивалентности . Тогда можно образовать новое множество, элементами которого будут являться классы эквивалентности отношения . Это множество будет назы-

ваться фактор-множеством множества A по отношению и обозначаться A / .

Пример 6. Пусть A – множество целых чисел. Зададим отношение следую-

щим образом. Для n, m A будем считать, что n m , если n m делится на 5. Несложно проверить, что будет отношением эквивалентности. Фактор-множество A / будет со-

стоять из пяти элементов. Одним из элементов будет являться множество всех целых чи-

сел, делящихся на 5. Другой элемент будет образовывать множество целых чисел, кото-

рые при делении на 5 дают в остатке 1, и т.д.

Задачи

1.Сколько существует бинарных отношений на множестве из трѐх элементов?

2.Сколько существует рефлексивных бинарных отношений на множестве из трѐх элементов?

3.Сколько существует симметричных бинарных отношений на множестве из трѐх элементов?

4.Сколько существует антисимметричных бинарных отношений на множестве из трѐх элементов?

5.Приведите пример рефлексивного, симметричного, но не транзитивного бинар-

ного отношения на множестве из трѐх элементов.

6. Приведите пример рефлексивного, транзитивного, но не симметричного бинар-

ного отношения на множестве из трѐх элементов.

7. Приведите пример симметричного, транзитивного, но не рефлексивного бинар-

4)транзитивным? Будет ли отношением эквивалентности или порядка?

8.m n m n – чѐтно.

9.m n m n – нечѐтно.

10.m n mn – чѐтно.

11.m n mn – нечѐтно.

16

12.m n m n 100 .

13.m n mn – целое чѐтное.

14.m n mn 2k , k – целое.

15.m n mn 2k , k – целое положительное.

16.m n m делит n .

17.m n m, n 1, где m, n – наибольший общий делитель чисел m и m .

18.m n m, n 1.

19.Сколько существует отношений эквивалентности на множестве из двух элемен-

тов?

20. Сколько существует отношений эквивалентности на множестве из трѐх элемен-

тов?

21. Сколько существует отношений эквивалентности на множестве из четырѐх эле-

ментов?

22.Сколько существует отношений порядка на множестве из двух элементов?

23.Сколько существует отношений порядка на множестве из трѐх элементов?

Какие из следующих бинарных отношений на множестве C a,b всех непрерыв-

ных функций на отрезке a,b являются отношениями порядка?

24. f (x) g(x) x a,b f (x) g(x) . 25. f (x) g(x) x a,b f (x) g(x) .

26. f (x) g(x) max f (x) max g(x) .

x a,b x a,b

ется отношением порядка. Этот порядок называется лексикографическим, потому что в этом порядке располагаются слова в словарях и энциклопедиях.

17

1.3. Понятие группы. Примеры групп

Определение 1. Пусть G – некоторое множество. Бинарной операцией на G

называется произвольное отображение G G G . Если g1, g2 G1 G2 , то результат

бинарной операции чаще всего будем обозначать g1 g2 , где ( ) – знак бинарной операции.

Определение 2. Множество G с бинарной операцией ( ) называется группой,

если

1)g1, g2 , g3 G (g1 g2 ) g3 g1 (g2 g3 ) ;

2)e G : e g g e g , этот элемент e будем называть единицей группы G ;

3) g G g 1 G : g g 1 g 1 g e , элемент g 1 для элемента g будем называть обратным к g .

Если к условиям 1) – 3) добавить условие

4) g1, g2 G g1 g2 g2 g1 , то группа G называется абелевой, или коммутатив-

ной. В этом случае знак бинарной операции чаще обозначают ( ) , что мы и будем де-

лать.

Результат бинарной операции ( ) в дальнейшем будем называть произведением.

Прежде всего отметим, что благодаря условию 1) произведение нескольких элементов группы можно записывать без скобок.

Предложение 1. Единица в группе может быть только одна.

Доказательство. Действительно, если два элемента e1,e2 G обладают свойством

2), то e1 e1 e2 e2 .

Предложение доказано.

Предложение 2. В группе элемент, обратный к данному элементу g , может

быть только один.

Доказательство. Если два элемента g1 1 и g2 1 обладают свойством 3) для элемен-

та g , то

g1 1 g1 1 e g1 1 g g2 1 g2 1 .

Предложение доказано.

Приведѐм примеры групп.

Пример 1. Множества целых чисел , рациональных чисел , действительных чисел с обычной операцией сложения ( ) являются абелевыми группами.

18

Пример 2. Множества положительных рациональных чисел , положительных действительных чисел с обычной операцией умножения ( ) являются абелевыми группами.

Пример 3. Множество GL(n, ) всех n m -матриц с действительными элементами

и с отличным от нуля определителем образует группу относительно операции произведения матриц (но уже не абелеву).

Пример 4. Пусть n – фиксированное натуральное число больше единицы. Рас-

смотрим множество символов 0, 1,..., n 1 . На этом множестве определим операцию ( ) .

Положим k l r , где r – остаток от деления числа k l на n . Нетрудно проверить, что

получится абелева группа. Она называется группой вычетов по модулю n и обозначается символом n . Например, в группе 7

(§ 1.1, определение 11 и пример 4). Роль операции играет суперпозиция отображе-

ний. Отметим, что суперпозиция действует справа налево. Например, если a и b – под-

становки, а i A , то (ab)(i) a(b(i)) , т.е. сначала на элемент i действует b , а потом a . Еди-

ницей является тождественное отображение e . Легко убедиться, что каждая подстановка имеет обратную. Кроме того, суперпозиция отображений всегда обладает свойством ассо-

циативности. Поэтому подстановки образуют группу, которую будем называть группой подстановок Sn или симметрической группой. Эта группа некоммутативна. Число под-

ножение на (–1) соответствует смене знака. Если под i, j, k понимать орты координатных осей Ox, Oy, Oz декартовой системы координат в пространстве, то умножение элементов i, j, k соответствует векторному произведению ортов. Эта группа называется группой ква-

тернионов и обозначается Q8 .

Сформулируем понятие группы движений геометрической фигуры.

19

Определение 3. Пусть F – некоторая фигура на плоскости, которую понимаем как множество точек. Будем говорить, что движение плоскости f оставляет фигуру

F на месте, если для любой точки A F точка f ( A) также принадлежит F . Или, более формально, если

A 2 A F f (A) F .

Множество всех движений, оставляющих фигуру F на месте, образует группу,

которая называется группой движений фигуры F .

Пример 7. Группа движений правильного n -угольника обозначается Dn .

Рассмотрим группу D3 движений правильного треугольника. Пусть ABC – пра-

вильный треугольник на плоскости (рис.1.1).

Существует 6 движений, оставляющих треугольник ABC на месте:

– поворот на 120 вокруг центра треугольника точки O против часовой стрелки;

2 – поворот на 240 ;

a– симметрия относительно прямой, проходящей через точки A и O ;

b– симметрия относительно прямой BO ;

c– симметрия относительно прямой CO ;

e – тождественное преобразование.

Каждая конечная группа может быть задана таблицей умножения, которая иначе называется таблицей Кэли. Для составления таблицы элементы группы выписываются по горизонтали и вертикали в определѐнном порядке. В клетке на пересечении строки g G и h G пишется элемент gh . Выпишем таблицу Кэли для группы D3 :

20