ЛИСТОК 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) = n² 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 =	3	1	2	4
f =	2	3	1	4

( при этом f(3) = 2, f(1) = 3 и так далее)

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

1	2	3	4
2	4	3	1

;

4	1	2	3
1	2	2	4

;

1	4	3	2
4	5	1	3

;

1	2	3	4	5
2	4	3	1	5

;

3	1	2	4
3	2	4	1

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

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

7. Чему равно: а)

2	3	1
3	2	1

1	3	2
3	2	1

1	3	2
3	2	1

2	3	12
3	2	1

2	3	4	1
4	1	2	3

2	3	4	1
4	1	2	3

Опр 5. Расширением подстановки

1	2	3	...	m
x₁	x₂	x₃	...	x_m

до любой произвольной длины n ≥ m называется подстановка

1	2	3	...	m	m+1	m+2	...	n
x₁	x₂	x₃	...	x_m	m+1	m+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 =	1	2	3	4
f =	3	2	4	1

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

Циклы

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

x₁	x₂	x₃	...	x_k-1	x_k	x_k+1	x_k+2	...	x_n
x₂	x₃	x₄	...	x_k	x₁	x_k+1	x_k+2	...	x_n

Обозначение (x₁, x₂, x₃, ..., x_k). 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.Представить подстановку

1	2	3	4	5	6
3	5	4	1	2	6

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

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

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

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

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