ЛИСТОК 11. (Группы) ОТОБРАЖЕНИЯ И ПОДСТАНОВКИ.

Выдан 12.01.85. Закрытие 20.01.85

Отображения.

"Кесарю - кесарево...!"

Говорится, что задано отображение (функция) f из множества A в множество B, если каждому элементу х из A поставлен в соответствие некоторый элемент из В, обозначаемый f(x). f(x) называется образом элемента x. Пусть y ∈ B. Всякий элемент x из A, для которого f(x) = у называется прообразом элемента у.

Опр. 1 Отображение f A→В называется
а) на(ложением, если каждый элемент из B имеет хотя бы один прообраз
б) в(ложением ,----------:---//-----------не более одного---//
в) взаимо-однозначным(обратимым)----//----ровно один ---//----

1. Пусть f ставит в соответствие каждому городу Советского Союза первую букву его названия на русском языке. Будет ли f отображением НА русский алфавит?

2. Расмотрим отображение целых чисел в множество неотрицательных целых чисел:
a) f(n) = n2       b) f(n) = |n|
с) f(n) = { 2n, если n ≥ 0 AND 2|n| - 1, если n < 0 }
Какие из них отображения на, в,обратимые?

3. Привести свои примеры наложений, вложений, взаимо-однозн. отоб.

4.Пусть A - конечно и f:A → A. Тогда f-наложение ⇔ f-вложение. Верна ли зта теорема , если A - бесконечно?

Опр. 2 Бинарным отношением с операцией &, называется отображение & A⊗A в A.

5. На множестве 1) всеч четных 2) всей нечетных 3) всех отрицательных целых чисел расмотрите операцию а) вычитания б)умножения. В каких случаях получается бинарная операция ?

Подстановки.

Опр. 3. Подстановкой называется взаимо-однозначное отображение множества {1, 2, 3,..., n} в себя. Подстановку можно обозначать так
f = 3124
2314
( при этом f(3) = 2, f(1) = 3 и так далее)

6. Являются пи подстановками?

1234
2431
;
4123
1224
;
1432
4513
;
12345
24315
;
3124
3241

Какие из них совпадают? (вспомните,когда две функции равны)

Опр.4 Произведением подстановок f, g называтся их композиция (Последовательное выполнение f, а потом g. У нас (f*g) (x)=g(f(x)). Очевидно, что операция "произведение подстановок" есть бинарное отношение на множестве подстановок одной длины

7. Чему равно: а)
231
321
*
132
321
b)
132
321
*
2312
321
c)
2341
4123
*
2341
4123
Опр 5. Расширением подстановки
123...m
x1x2x3...xm
до любой произвольной длины n ≥ m называется подстановка
123...m m+1m+2...n
x1x2x3...xm m+1m+2...n
В дальнейшем будем формально полагать любую подстановку равной ее расширениям, а операцию * заданой на соответствующим образом расширенных подстановках.

8. Доказать,что "новое" произведение есть биекция множества всех подстановок.

9. Пусть f, g, h - подстановки, которые возможно перемножать. Всегда ли верно a) f*(g*h) = (f*g)*h b) f*g=g*f ?

Опр 6. Подстановка, каждый элемент которой переходит в себя, называется единичной и обозначается е.

10. Известно f * g = e Найти g (обратную), если
f = 1234
3241

11. Доказать, что для каждой f найдется единственная g, такая что f*g = g*f = e. Такая подстановка называется обратной и обозначается f'.

Циклы

Опр 7. Циклом называется подстановка вида:

x1x2 x3...xk-1xk xk+1xk+2... xn
x2x3 x4...xkx1 xk+1xk+2...xn

Обозначение (x1, x2, x3, ..., xk). k - длина цикла

12. Пусть а = (1,2,3); b = (2,4); с=(4,5); Найти a*b b*a а*c c*a.

Циклы (1,2,3) и (4,5) называются независимыми,так как они "передвигают" разные элементы. Ясно, что если a и b независимые то a*b = b*а.

13.Представить подстановку

123456
354126
в виде независимых циклов.

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

Опр 8. Транспозицией называется цикл из 2х элементов.

14. Доказать,что любой цикл можно разложить в произведение транспозиций (и не одним способом). Привести примеры.

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