ЛИСТОК 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) всех отрицательных целых чисел расмотрите операцию а) вычитания б)умножения. В каких случаях получается бинарная операция ?

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

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

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

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

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

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

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

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

Циклы

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

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

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

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

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

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