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

Элементы теории множеств.

Бинарное отношение на множестве Х – любое подмножество декартового квадрата множества Х. .

Декартово произведение множеств: , для n множеств .

Если то ~ .

Свойства бинарного отношения:

1. Рефлексивность:

2. Симметричность:

3. Транзитивность:

4. Ассимитричность:

Отношение эквивалентности: если оно рефлексивно, симметрично, транзитивно.

Отношение порядка: если оно рефлексивно, транзитивно, ассимитрично.

(Строгого порядка – если 3.)

Пример 1: отношение равенства – отношение эквивалентности.

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

Пример 3: R с < - выполняется только 3.

Пример 4: Выполняется 3, 4 и не выполняется 1, 2.

X={1,2,3}; p={(1,2),(2,3),(1,3)}

4 выполняется автоматически, так как нет пар (a,b),(b,a).

Теорема 1:

Опр: Пусть р – отношение эквивалентности на Х, тогда множество элементов - класс эквивалентных элементов для элемента а по отношению р.

1. Пусть р – отношение эквивалентности на Х, тогда множество Х представляется в виде пересечения попарно не пересекающихся классов эквивалентности.

2. Любое разбиение множества Х на не пересекающиеся подмножества задает отношение эквивалентности на Х.

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

От противного: Пусть

В другую сторону: Пусть

Определим отношение эквивалентности:

- покажем, что это отношение эквивалентности:

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

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

3. Транзитивность: Пусть т.к. по условию все не пересекаются попарно.

Будем говорить, что а делится на в с остатком, если .

Будем говорить, что a, b – сравнимы по mod n, если остатки от деления a, b на n совпадают:

Отношение сравнимости по любому mod n на множестве Z – отношение эквивалентности.

Основные алгебраические структуры.

Опр: Отображение множества Х в множество Y – закон по которому каждому ставится в соответствие некоторый .

Заметим, что бинарное отношение .

Свойства отображений:

1. Сюръективность.

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

3. Биективность.

Опр: Бинарная операция на множестве Х – отображение декартового квадрата множества Х в себя:

Свойства операций:

1. Коммутативность (обозначим +): , если .

2. Ассоциативность (*):

3. Дистрибутивность (*,0):

Опр: Множество Х с бинарной операцией * - полугруппа (Хб*)

• Пример (N, )

Опр: Пусть (Х,*) – полугруппа, элемент е-еденичный, если

Опр: Для элемент - обратный, если

Опр: Полугруппа (Х,*) – группа, если существует е относительно * и для каждого

Пример: (Z,+)

Опр: Пусть на множестве Х введены две операции: (Х,+,0) – множество Х с двумя бинарными операциями – кольцо, если:

1. (Х,+) – абелева группа.

2. - дистрибутивно относительно +.

Пример: (Z,+, ) – множество квадратных матриц (nxn) над полем Z.

Опр: Поле – коммутативное кольцо с е, в котором каждый ненулевой элемент имеет обратный по умолчанию.

Опр: Гомоморфизм – группы - такое отображение множества G в K, при котором . Если - биективное отображение G K, то - изоморфизм группы и гомоморфизм колец

Утв: Пусть - изоморфизм тогда:

Доказательство:

1. Пусть , т.к. - биекция.

Опр: Конгруэнция на множестве Х с операцией * - (Х,*) – отношение эквивалентности р на Х со свойствами: . Говорят, что отношение р согласовано с операцией *.

Утв: Пусть р – отношение эквивалентности на множестве (Х,*), тогда определим операцию на классах эквивалентности, положив результат: [a]p*[b]p=[a*b]p, тогда данная операция определена корректно, т.е. не зависит от выбора элементов из [a]p, [b]p.

Доказательство: Пусть надо показать, что [x*y]p=[a*b]p.

, т.к. р – конгруэнция , т.к. р – отношение эквивалентности, а по Т1

Теорема: Пусть - гоморфизм тогда:

1. - группа

2. р на G вида: конгруэнция

3. , тогда (* - оператор на классах)

Доказательство:

1. 1. , т.е. задана операция.

   2. Она ассоциативна т.к. , а К – группа

   3. - единица

2. р – отношение эквивалентности на G:

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

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

Проверим согласованность р со *:

т.к р – конгруэнция.

1. , где - покажем что это отображение задано корректно:

   1. , т.е. отображение задано корректно.

   2. - изоморфизм?

, т.е. - гомоморфизм.

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

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

От противного: Пусть - изоморфизм

Следствие: - группа, т.к. изоморфно

Элементы теории групп.

Опр: Пусть - группа: е – определен однозначно и - однозначен.

Доказательство:

1. Пусть е1, е2 – единичные элементы, тогда е1=е1*е2=е2

2. обратные к х, тогда х*х1=е, х*х2=е => х*х1=х*х2

Опр: Пусть - группа, тогда Н – подгруппа группы G, если:

2. - сама группа.

Пример: Z<Q<R<C

Теорема: Пусть - группа, тогда подмножество H<G - “Критерий быть подгруппой”.

Доказательство:

1. - группа

2. Обратно:

   1. т.к. ассоциативность из G в Н, т.е

   2. е группы . Пусть a=e, b=x

   3. Замкнутость: Пусть

Теорема: Множество G с внутренней бинарной ассоциативной операцией – группа. Тогда, когда в этом множестве однозначно разрешимы уравнения: ax=b, ya=b.

Доказательство:

1. ax=b; - однозначно, т.к. - однозначны.

2. Обратно:

   1. Пусть bx=b, т.к е1 – решение этого уравнения

   2. , т.е оба решения совпадают: е1=е2=е, т.е.

   3. - решения. Покажем, что

т.е.

1. единственность е и , т.к. уравнения разрешимы однозначно: ах=а, е – решение => е – однозначно, ах=е, - решение => - однозначно.

Свойства отображений конечных множеств.

Пусть - множество, .

Опр: Пусть - отображения - композиция если т.е. ; т.е.

Произведение отображений: - полугруппа.

Утв: Операция: композиция отображения – на некотором множестве - ассоциативна, т.е. .

Док-во:

т.е. отображения совпадают.

Следствие: Множество (Ф,о) – полугруппа с е. е тождественное отображение.

Теорема: Пусть В – множество взаимно однозначных отображений множества , т.е. (В,о) => (В,о) – группа.

Док-во:

1. (В,о) – полугруппа

2. Отображение элементов? Пусть если .

Задача: Равенство – БО, удовлетворяющее 1 – 4?

Задача: БО не удовлетворяет 1 – 4? X={1, 2, 3}; p={(1,1),(2,3),(3,2),(1,3)}.

1. Не выполняется т.к. нет (2,2) – хотя бы.

2. Не выполняется т.к. нет (3,1) – хотя бы.

3. Не выполняется т.к. нет (1,3),(3,2) => (1,2)

4. Не выполняется т.к. нет (3,2),(2,3) => (2,2)

Задача: Мультипликативная группа положительных вещественных чисел изоморфна аддитивной группе всех вещественных чисел?

1. - изоморфизм, или f(x)=lnx; ln(x+y)=lnx+lny.

2. - группа по сложению. По умножению нет! (не замкнута).

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

1. Замкнутость очевидна т.к. res < n.

2. Ассоциативность:

а т.к.

1. e - ? => e=0, т.к.

2. Обратно: е=0, т.к. т.к.

Задача: Изоморфизм этой группы с группой всех корней энной степени из 1.

Пусть

1. Взаимное соответствие – в обоих по n элементов.