ALG#02 (Лекции Кузьмина)

Задача: , если , то группа кососимметрична, иначе не кососимметрична.

1. Пусть , тогда либо либо

2. Пусть , тогда не кососимметрична.

Задача: Доказать, что - инъективное, суръективное, биективное => - взаимно однозначное.

1. Аналогично второму.

2. Пусть - суръективно тогда надо доказать инъективность: Пусть не инъективное т.к. а с другой стороны - противоречит.

Пример1: - инъективно, но не серъективно.

Пример2: - суръективно, но не инъективно.

Свойства подгрупп.

Опр: Мощность (порядок) группы – число ее элементов.

Теорема “Лагранжа”: Пусть

Док-во: Введем на множестве элементов группы БО:

1. БО: - отношение эквивалентности.

   1. - рефлективно.

   2. Пусть - симметрично.

   3. Пусть - транзитивно.

Следовательно, все множество G разбивается на классы эквивалентности:

1. где [a]p – класс эквивалентности. Пусть

2. где [a]p=Ha; [b]p=Hb; Пусть - взаимно однозначное отображение т.к.:

   1. Суръективно: Пусть

   2. Инъективно: Пусть

3. Мощности всех смежных классов равны между собой и равны |H|. .

Опр: Пусть задана (G, ), подгруппа, порожденная множеством М: т.е. объединения всех подгрупп, содержащих М как подмножество. (т.е. самая маленькая подгруппа, содержащая М).

Утв: Объединение двух подгрупп группы G – само является подгруппой в G.

Док-во:

т.к. т.к.

Утв: Пусть G – группа, - подмножество: M={a1,…,at}

Док-во:

1. Покажем, что это множество само является подгруппой.

2. Любая подгруппа группы G содержит это множество, т.е. эту подгруппу, значит она сама является объединением.

. Пусть .

Опр: Пусть порядок элемента : где . - d элементов => все различны. =>

Утв: Порядок любого элемента делит порядок группы.

Док-во: по Т. Лагранжа d делит |G|.

Утв: Для элемента конечной группы справедливо:

Док-во:

2. Если т.к. или - противоречит с определением порядка

3. Пусть Пусть т.к. из условия

Опр: Экспонента группы – наименьшее натуральное число:

Теорема: Пусть G – абелева группа

Док-во:

1. Пусть а т.к. . Аналогично

2. Пусть - попарно различные простые числа. Покажем, что . Пусть в этом разложении то Или покажем, что . Докажем исходное утверждение от противного: (*) Пусть - неверное предположение, значит верно наше утверждение.

3. Посмотрим элемент у которого ordg=expG

   1. - из 2). Пусть т.к. из 1)

Группы подстановок.

Будем рассматривать только конечные множества.

Опр: Пусть ; группа подстановок на множестве - это группа взаимно однозначного отображения множества в себя.

- пример. Sn – симметричная группа.

Умножение подстановок: слева направо.

;

Теорема: Любая подстановка Sn однозначно представляется в виде произведения независимых циклов с точностью до циклической перестановки элементов в каждом цикле.

Циклы независимы, если множество элементов не пересекается.

Док-во: (индукцией по n):

1. - базис индукции.

2. Пусть теореме верна для любого n<t

3. St-? Пусть

Строим последовательность элементов: ; т.к. в этой последовательности встретится 2 одинаковых элемента: Пусть Выбираем минимальное - все различны (попарно) т.к. Пусть a S – min! – противоречит.

если аналогично: … Пока не исчерпаем все элементы множества шагов не больше t, т.к. тогда получим: Это не разложение в независимые циклы: Если есть произведение независимых циклов, то они перестановочны, т.е. (123)(46)=(46)(123).

Опр: Транспозиция – подстановка, переставляющая только 2 элемента.

Теорема: Любая подстановка может быть представлена в виде произведения транспозиций.

Док-во: Надо доказать, что любой цикл можно представить в виде произведения транспозиций.

Следствие: Множество транспозиций порождает симметричную группу Sn.

Опр: Пусть задана - число циклов длинны j в разложении подстановки g в произведения независимых циклов. - цикловая структура р.

Опр: Постановки g1, g2 – сопряженные, если

Теорема: Цикловые структуры сопряженных подстановок совпадают.

Док-во: т.к.

Понятие транзитивности группы подстановок.

Пусть G<Sn.

Опр: Группа подстановок G – транзитивная на множестве , если

Опр: - множество всех элементов, получаемых при действии подстановок из g на элемент - это орбита элемента .

Утв1: Группа G – транзитивна

Док-во: - фиксируем:

1. Из транзитивности:

2. В другую сторону: Пусть . Пусть попадают в т.к. т.к. - транзитивна по определению.

Опр: Группа подстановок G – к-транзитивная если и существует одна подстановка (При к=1 – просто транзитивность.) Т.е. любая пара может перейти в любую – 2-транзитивность.

Утв2: Если группа G, действующая на множестве из к элементов, к-транзитивна, то

Док-во: т.к. - фиксированы, не превосходящая & все gi, различны и их столько сколькими способами можно выбрать набор :

Примитивность группы подстановок.

Опр: Множество - блок импримитивности если для выполняется одно из условий:

Опр: Транзитивная группа G – примитивная если у нее не существует блоков импримитивности.

Утв: Если группа не является транзитивной, то орбиты элементов являются блоком импримитивности.

Док-во: (перебирая все g, переберем все ) т.е.

Утв: Если - блок импримитивности группы G, то для любой подстановки - блок импримитивности.

Опр (эквивалентное условие для определения блока импримитивности): - блок, если для

Док-во: Если - блок то .

Пусть они пересекаются где Теорема: Пусть G – транзитивная группа подстановок, значит мощность блока импримитивности:

Док-во: т.к. G – транзитивная группа, т.е. перебирая ко всем р, мы переберем все т.е. покроем все элементы даже не по одному разу. но т.к. - это элементы , то больше чем мы не можем получить .

Согласно доказанному утверждению, все множества, которые объединяются – блоками импримитивности, полученные из одного и того же блока под действием различных подстановок G => все эти блоки либо не пересекаются,