Определения (Алгебра)

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

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

Декартово произведение множеств: , для 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Пример (N, )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

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

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

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

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

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

Пусть G<Sn.

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

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

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

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

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

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

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

Кольцо целых чисел.

Опр: Число a делится на число b: b|a если .

Опр: Деление с остатком а на b – это представление а в виде: a=bq+r, .

Опр: Числа a,b – сравнимы по modn, если остатки от деления a,b на n совпадают. .

Обозначение: .

NOD, NOK целых чисел.

Опр: NOD целых чисел a,b(a,b)=d – натуральное число

1. d|a, d|b;

2. (т.е. d – max).

Опр: NOK

1. a|D,b|D;

2. (т.е. D – min).

Опр: a,b – взаимнопросты .

Опр: – простое – если оно делится только на 1 и само на себя.

Опр: b – собственный делитель а, если b|a, 1<b<|a|. Другими словами р – простое, если оно не имеет собственных делителей.

Опр: Представление целого числа n в виде произведения степеней попарно различных простых чисел – каноническое разложение числа n.

Кольцо вычетов целых чисел.

- конгруэнция на Z. Пусть [a]n – класс эквивалентных элементов относительно ; а остатков: - разные классы.

- множество + операции: . В силу теоремы, что - конгруэнция, введенные операции – введены корректно. - это множество с этими операциями – это кольцо из n элементов.

Для простоты: - наименьший неотрицательный элемент из класса [a] .

Идеалы колец.

Опр: Пусть - кольцо - идеал кольца R, если .

Пример: R=Z, J – четные числа .

Рассматриваем свойства коммутативных колец.

Опр: Идеал I – максимальный идеал, если из условия, что либо J=R.

Опр: Пусть - сравнение по модулю идеала I:

Идеалы кольца целых чисел.

Теорема: Все идеалы кольца целых чисел исчерпываются множествами вида: .

Теорема: .

Решение сравнения в кольце целых чисел Zn.

Пусть - обозначение. Дано: Zn; [a][x]=[b]; ; Пусть - сравнение по модулю n, здесь решений бесконечное множество т.к. в Zn.

Теорема:

1. В Zn сравнение: имеет решение (a,n)|b

2. Если (a,n)|b, то сравнение имеет (a,n)=d различных по модулю n решений вида: - некоторое фиксированное решение.

Пример1:

1. (a,6)=1 Пусть a=5;

2. 5U+6V=1; U=-1

Пример2: . Найти обратный к элементу [4]?

нет решений. Пусть есть решение.

Пусть

Конечные поля.

Простейшие свойства полей: Р – поле – это коммутативное К с е, в котором каждый ненулевой элемент обратим. .

Свойства:

1. (P,+) – коммутативная группа G

   3. a+b=b+a

3. т.к. К – коммутативно значит ab=ba

Пример1: рациональные действия, комплексные числа – поля.

Пример2: GF(2) – поле Галуа (конечное поле)

- такое множество элементов {0,e} – поле.

Пример3: Zp (если р – простое) – поле.

Пример4: - множество таких чисел образует поле. Оно больше Q, но меньше поля R.

Опр: Характеристика поля Р – минимальное натуральное число р. . Если такого р не существует, по определению полагают р=0.

Пример5: GF(2), т.к. e+e=0, т.е. 2e=0, a .

Пример6: R .

Пусть Р – конечное поле. Построим последовательность: e,2e,3e,…,ne, т.к. в поле конечное число элементов значит где-то есть повторения: (Пусть k>j)

Пусть ke=je; (k-j)e=0. (k-j) – какое-то натуральное число, пусть не min, т.е. это верхняя граница значит есть min. Значит если Р – конечно, то , т.е. конечное поле имеет конечную характеристику.

Замечание: Обратное не верно, существуют бесконечные поля, имеющие конечную характеристику.

Опр.: Поле называется простым, если оно не содержит собственных подполей, т.е. если Q<P значит Q=P (более простых полей, чем Р в нем нет).

Опр.: В конечном поле элемент с таким свойством называется примитивным

Т.е. в конечном поле существует примитивный элемент, где 0, ¹, ², …, ^|P|-1 – все различные элементы поля Р

{В абелевой группе существует : ord =expG}

expG=min{t : G, ^t=e}

Кольцо многочленов над полем

Пусть Р – поле;

Обозначим: Р - множество носителей с элементами из Р; (а₀ а₁ а₂ … ), а_j Р

Р : если (а₀ … а_n …) , то k : а_j=0, для j k, т.е. начиная с какого-то номера они все нули.

Определим на множестве : + = , c_k=a_k+b_k