Шпаргалка (Архив шпаргалок для РК и экзамена)

1. Множества. Операции над множествами. Булева алгебра множеств.

1.1 Булева алгебра множеств

Основными понятиями этой главы являются понятия множества и элемента множества (эти понятия считаем неопределяемыми). Синонимами слова множество являются слова совокупность, набор, коллектив и т.д. Множества мы будем обозначать большими буквами латинского алфавита (X, У, Z,...), элементы множества малыми буквами (х, у, z,...). При­надлежность элемента х множеству X (неопределяемое понятие) будем обозначать х X. Аналогично х X обозначает, что элемент х не принадлежит множеству X.

Определение 1.1. Множество X является подмножеством множества Y (обозначим

X Y), если для любого х X следует, что х Y.

Определение 1.2. Множества Х и Y равны (X = Y) тогда и только тогда, когда X Y и Y Х.

Будем считать, что мы выбрали некоторое достаточно большое множество, называемое универсальным, за пределы которого мы не будем выходить. Понятие универсального множества, обозначим его U также неопределяемое, но любое рассматриваемое нами мно­жество X удовлетворяет условию: X U. Это утверждение мы принимаем без дока­зательства. Заметим, что утверждения, которые считаются верными без доказательства, называются аксиомами.

Определим следующие операции над множествами:

объединением двух множеств Х и Y называется множество Х Y = {х U | х X или х Y}; пересечением двух множеств Х и Y называется множество Х ∩ Y = {х U| х X и х Y}; дополнением множества X называется множество = {х U | х X}.

Определение 1.3. Назовем пустым множеством (множеством, в котором нет ни одного элемента) множество Ø = , то есть дополнение к универсальному множеству.

Рисунки, интерпретирующие операции над множествами, называются диаграммами (кру­гами) Виенна.

Объединение Пересечение Дополнение

Теорема 1.4. Множества относительно операций дополнения, объединения и пересече­ния удовлетворяют следующим равенствам

1. = X - закон двойного отрицания;

2. X Y = Y X - коммутативность;

3. X ∩ Y = Y ∩ X - коммутативность;

4. X (Y Z) = (X Y) Z - ассоциативность;

1. X ∩ (Y ∩ Z) = (X ∩ Y) ∩ Z - ассоциативность;

2. X (Y ∩ Z) = (X Y) ∩ (X Z) - дистрибутивность;

3. X∩ (Y Z) = (X ∩ Y) (X ∩ Z)- дистрибутивность;

8. = ∩ - закон де Моргана;

9. = - закон де Моргана;

1. X X = X- закон идемпотентности;

2. Х∩Х = Х- закон идемпотентности;
   законы нуля и единицы:

3. X U= U;

13. X∩U = X;
14. X Ø = X;

1. X ∩Ø = Ø;

2. X (X∩Y) = X - закон поглощения;

3. X ∩ (X Y) = X - законы поглощения;

4. X = U - законы дополнения;

5. Х ∩ = Ø - законы дополнения.

Все эти равенства следуют непосредственно из определения и демонстрируются с помо­щью кругов Виенна.

Множество с операциями, удовлетворяющими 19 приведенным выше равносильностям, называется булевой алгеброй; сами операции в этом случае называются булевыми. Из теоремы 1.4 следует, что множество всех множеств образует булеву алгебру относительно операций дополнения, объединения и пересечения. Заметим, что в дальнейшем мы будем рассматривать и другие множества, образующие булеву алгебру. Кроме булевых, над множествами определяются следующие операции.

3. Конечные множества. Правила суммы для конечных множеств.

Комбинаторика - это раздел математики, посвященный способам подсчета числа элемен­тов в конечном множестве. В этом параграфе все множества предполагаются конечными, то есть в них конечное число элементов. Будем обозначать |Х| число элементов множества X.

В качестве аксиом в комбинаторике принимаются следующие:

1. Отрезок натурального ряда {1,2,...,п} содержит п элементов.

2. Если существует биективное отображение φ: X → Y, то |Х| =|Y| .

3. |Ø| = 0.

Если |Х| = п, то элементы множества X можно пронумеровать, то есть определить биек­тивное отображение φ : {1,2,...,п}→ Х и обозначить φ(1) = х₁ φ(2) = х₂,..., φ(п) = х_п. Ясно, что нумерация не однозначна.

Теорема 1.19. Пусть X uY - конечные множества и X ∩ Y = Ø. Тогда |X Y| = |Х| + |Y|.

Доказательство. Действительно, если X = {х₁,х₂, ...,х_п}, Y = {у₁,у₂, ...,у_т}, то X Y =

{х₁, ...,х_п, у₁,..., у_т}. (Мы пронумеровали множества X и Y и воспользовались тем, что

x_i ≠ x_j для любых i {1,…,n}, j {1,…,m}.

Теорема 1.20 (Правило суммы). Пусть X u Y - конечные множества. Тогда |X Y| = |X| + |Y| - |X ∩ Y|

Доказательство. Очевидно, что X Y = X (Y \ X) и X ∩ (Y \ X) = Ø. Тогда |Х Y| = |X| + |Y \ X| по предыдущей теореме. Аналогично, |Y| = |Y \ Х| + |У ∩ Х|. Следовательно |Y \ X| = |Y| - |Y ∩ X| и |X Y| = |X| + |Y| - |X ∩ Y|. Теорема доказана.

Теорема 1.21. Пусть A₁,A₂,... ,А_п - конечные множества. Тогда

|A₁ A₂ . . . A_n| = |A₁| + |A₂| + . . . + |A_n| -

- (|A₁ ∩ A₂| + |A₂ ∩ A₃| + . . . + |A_n−1 ∩ A_n|)+

(|A₁ ∩ A₂ ∩ A₃| + . . . + |A_n−2 ∩ A_n−1 ∩ A_n|)+

. . . + (−1)ⁿ⁻¹ |A₁ ∩ A₂ ∩ . . . ∩ A_n| .

Теорема доказывается с помощью индукции и использования предыдущей теоремы.

4. Декартово произведение множеств. Количество элементов в декартовом произведении конечных множеств.

Определение 1.22. Декартовым произведением двух множеств X uY называется мно­жество пар (х,у) таких, что х X, у Y. Обозначим это множество X × Y.

Итак X × Y = {(х,у) | х X, у Y} . Равенство элементов в множестве X × Y понимается следующим образом: (x₁, y₁) = (x₂, y₂) тогда и только тогда, когда x₁ = х₂ и у₁ = у₂. Очевидно, что X × Y ≠ Y × X, если X ≠ У.

Определение 1.23. Декартовым произведением п множеств {Х₁,Х₂, ...,Х_п} называет­ся множество

X₁ × X₂ × ... × X_n = {(x₁,x₂,...,x_n) | x_i X_i Vi= 1,...,n} ,

то есть множество упорядоченных строк из п элементов.

Заметим, что множество X × X × ... × X обычно обозначают Х^п.

Теорема 1.24. Если X u Y - конечные множества, то X × Y - конечное множество и |Х × Y| = |Х| ∙ |Y|.

Доказательство. Зафиксируем в X нумерацию, то есть X = {х₁,х₂, ...,х_п}. Тогда

X × Y = × Y и (x_i × Y) (x_j × Y) = Ø, если i≠j.

По правилу суммы |Х × Y| = |x_i × Y|. Так как отображение f_i :x_i × Y →Y такое, что f_i((x_i, y)) = y, является биекцией для любого i (i=1,…,n), то |x_i × Y| = |Y| и |Х × Y| = |Х| ∙ |Y|.

Следствие. Если Х₁,Х₂, ...,Х_п - конечные множества, то |Х₁×Х₂×...×Х_п| = |Х₁|∙|Х₂|∙...∙|Х_п|

6. Множество инъективных отображений: In Y^X и |In Y^X|.

7. Множество биективных отображений Bi Y^X и |Bi Y^X|

Определение 1.27. Пусть X и Y непустые множества. Отображение f : X → Y назы­вается иньективным, если из условия х₁ ≠ х₂ (х₁, х₂ - любые элементы множества X) следует, что f{x₁) ≠ f(x₂).

Множество всех инъективных отображений обозначим InY^X

Теорема 1.28. Пусть X uY - конечные непустые множества. Тогда l)InY^X ≠ Ø тогда и только тогда, когда |Y| > |Х|; 2) если |Х| = |Y|, то InY^X = BiY^X.

Доказательство. Пусть X = {x₁,x₂ ,…,х_т} и Y = {y₁,y₂ ,…,y_m}.

Докажем =>. Итак, InY^x ≠ Ø. Тогда существует инъективное отображение f : X → У.

Следовательно f(X) = {f(x₁), f(x₂),…, f(x_m)} Y и |f(Х)| = |Х| < |У|. Заметим, что мы использовали инъективность отображения f : f(x_i) ≠ f(x_j), если x_i ≠ x_j.

Пусть теперь п > т. Тогда мы можем построить такое отображение из множества X в множество Y: f(x_i) = у_i если i {1,2,...,m}. Так как f InY^X, то InY^X Ø.

2)Очевидно, что, если п = m, то любое инъективное отображение будет биективным.

Теорема 1.29. Пусть X ,Y - конечные непустые множества и |Y| > |Х|. Пусть |Х| = т, |Y| = п. Тогда

|InY^X| =n ∙ (п- 1) ∙ ... ∙ (п – т + 1)

Доказательство. Пусть X = {х₁,х₂,... ,х_т}, Y = {у1, y₂,,…, у_п}. Любое отображение f : X → Y определяется тем, куда попадет каждый элемент множества X, то есть на­бором элементов {f(x₁), f(x₂),..., f(x_m)} из множества Y. При этом отображения f и g различны, если f(x_i) ≠ g(x_i) хотя бы для одного i {1, 2,..., m}. Будем считать элементы множества Y ячейками.

Так как мы рассматриваем инъективные отображения множества X в множество Y, то два разных элемента множества X при любом отображении попадут в две разные ячейки. Задача о нахождении InY^X превращается в задачу о нахождении количества способов размещения элементов {х₁,х₂ ,..., х_т} по п различным ячейкам. Зафиксируем элемент х₁.

Существует п различных способов размещения этого элемента, так как он может попасть в любую из ячеек {y₁, у₂ ,...,у_п}. Предположим, что элемент х₁ в ячейку y_j. Тогда элемент x₂ может попасть при размещении в любую ячейку, за исключением у_j. Таким образом получаем п ∙ (п — 1) различных способов размещения элементов {х₁,x₂}. При размещении элементов {х₁, x₂, х₃} мы получаем п ∙ (п — 1) ∙ (п — 2) различных способа размещения, так как элемент x₃ можно разместить в любой из (п — 2) ячеек (две ячейки уже заняты элементами х₁ и x₂). Продолжая этот процесс, получаем, что число различных размещений т элементов по п ячейкам вычисляется по формуле: n ∙ (п- 1) ∙ ... ∙ (п – т + 1).

В комбинаторике это число обозначается и называется числом размещений длины т на множестве из п элементов (число ячеек). Итак, мы доказали, что |InY^X| = = n ∙ (п- 1) ∙ ... ∙ (п – т + 1) =n!/(n-m)!.

Следствие. Пусть X и Y такие множества, что |Х| = |Y|. Если обозначить BiY^X мно­жество всех биективных отображений из множества X в множество Y, то |BiY ^X| = n!

Доказательство. Действительно, если существует биективное отображение из множества X в множество Y, то |Х| = |У| = n |BiY ^X |= n!/(n-m)! = п!. Заметим, что в этом случае BiY^X = InY^X.

Каждое биективное отображение множества X = {х₁,х₂,..., х_п} в множество Y = {y₁,y₂,,…, у_п} является некоторым размещением элементов {x₁, x₂,..., х_п} по ячейкам {у₁, у₂,..., у_п}, то есть некоторой перестановкой элементов множества X. Число всех перестановок п раз­личных элементов обозначают Р_п, таким образом Р_п = п!.

Очевидно, что имеют место следующие равенства:

1)Х\Ø = Х; 2) X\U = Ø; 3) Ø\Х = Ø; 4)Х\Х= Ø;5)U\X = ; 6) X ΔY = Y Δ Х;

7) X Δ U = ; 8) X \ Ø = X

Рассмотрим более подробно свойства подмножеств данного множества.

Теорема 1.7. Пусть X и Y - множества. Тогда X Y тогда и только тогда, когда X\Y = Ø

Теорема 1.8. Пусть X, Y, Z - множества. Тогда:

1. X X - рефлексивность;

2. из (X Y) и (Y Z) следует X Z - транзитивность;

3. из (X Y) и (Y X) следует X = Y - антисимметричность.

Доказательства приведенных выше теорем следуют непосредственно из определений. Замечание: понятия коммутативности, ассоциативности, дистрибутивности, рефлексивно­сти, транзитивности и антисимметричности будут подробно рассмотрены в последующих главах этой книги.

2. Отображения множеств. Типы отображений. Композиция. Обратимость отображений.

Определение 1.9. Пусть X и Y - множества. Отображением f из множества X в множество Y мы будем называть правило, по которому каждому элементу х множе­ства X ставится в соответствие вполне определенный (единственный) элемент y = f(x) множества Y. Обозначать данное отображение будем f: X → Y.

Заметим, что отображение надо обязательно понимать как набор из трех элементов (X, Y, f), где X и Y - множества, f - закон.

Определение 1.10. Пусть f: X → Y - отображение, А X, В У. Тогда:

1) образом множества А при отображении f называется множество f(A)= {f(x ) | x A};

2) прообразом множества В при отображении f называется множество f ^-1 (B) = {x X | f(x) B}.

Теорема 1.11. Пусть f : X → Y - отображение; А₁, А₂ X; B_1; B₂ Y. Тогда:

1) f(A₁ A₂) = f(A₁) f(A₂); 2) f ⁻¹(B₁ B₂) = f ⁻¹(B₁) f ⁻¹(B₂);

3) f(A₁ ∩ A₂) f(A₁) ∩ f(A₂); 4) f ⁻¹(B₁ ∩ B₂) = f ⁻¹(B₁) ∩ f ⁻¹(B₂).

Доказательство. Приведем доказательство утверждений 1) и 3), утверждения 2) и 4) доказываются аналогично 1). Итак, пусть у f(A₁ А₂). Это равносильно тому, что су­ществует х А₁ А₂ такой, что f(x) = у, то есть или существует х А₁ или существует х А₂ с условием у = f(x). Но это равносильно тому, что или у f(A₁) или у f(A₂), то есть у f(A₁) f(A₂). Первое утверждение теоремы доказано. Пусть теперь х - произволь­ ный элемент множества А₁ ∩ А₂. Тогда элемент х одновременно принадлежит множествам А₁ и А₂, и следовательно элемент f(x) одновременно принадлежит множествам f(A₁) и
f(A₂), но по определению это и означает, что f(x) f(A₁) ∩ f(A₂). Таким образом дока­зали 3), то есть f(A₁ ∩ А₂) f(A₁) ∩ f(A₂). Обратное включение в общем случае неверно, что показывает следующий пример.

Пример. Пусть f: R→R такое отображение, что f(x) = sin x; A₁ = [0,π], А₂ = [2π,3π]. Тогда

А₁ ∩ А₂ = Ø, следовательно и f(A₁ ∩ А₂) = Ø но f(F₁) ∩ f(А₂) = [0,1] Ø.

Определение 1.12. Отображение f : X → Y называется инъективным, если для любых x₁ ≠ x₂ из множества X следует, что f(x₁) ≠ f(x₂).

Определение 1.13. Отображение f : X → Y называется сюрьективным, если для любо­го элемента у из множества Y существует непустой прообраз, то есть f ^-1(y )≠ Ø

Определение 1.14. Отображение f : X → Y называется биективным, если оно инъективно и сюръективно.

Примеры.

Отображение f : R → {0,1} такое, что f(n) = (1+(-1)ⁿ)/2 является сюръективным, но не инъективным. Заметим, что множество {0,1} обычно обозначают Е₂.

1. Отображение f : R → R такое, что f(x) = х² не является ни инъективным, ни сюръективным.

2. Отображение f : N → N такое, что f(n) = п² является инъективным, но не сюръективным.

3. Отображение f : R → R такое, что f(x) = х³ является биективным отображением.

Определение 1.15. Пусть f : X → Y, g : Y → Z - отображения, тогда композицией этих отображений называется отображение g о f : X → Z такое, что для любого элемента х из множества X его образ в множестве Z определен следующим образом (g o f)(x) = g(f(x)).

Теорема 1.16 (ассоциативность композиции отображений). Если f : X → Y, g : Y → Z,

h : Z → V — отображения, то справедливо следующее равенство: h о (g о f) = (h о g) о f.

Доказательство. Действительно, для любого х X справедливо:

(h o (g o f))(x) = h((g о f)(x)) = h(g(f(x))), ((h о g) о f)(x) = (h о g)(f(x)) = h(g(f(x))).

Определение 1.17. Тождественным отображением множества X на себя называется отображение e_X : X →X такое, что для любого х из множества X выполняется равенство e_X(x) = х.

Теорема 1.18. Если f : X →Y - биективное отображение, то существует такое биективное отображение g : Y→X, что:

1) для любого элемента х из множества X вып-ся равенство х = (д о f)(x), то есть g о f = е_Х,

2)для любого элемента у из множества Y вып-ся равенство у = (f о д)(у), то есть f о g = е_Y,

Отображение g в этом случае называют обратным отображением к отображению f и обо­значают f ^-1.

Доказательство. Искомое отображение f : Y → X определим следующим образом: g(у) = х, где х прообраз элемента у в множестве X. Этот прообраз существует и единстве­нен для любого элемента у из множества Y, так как отображение f - биективно. Таким образом отображение g определено, и биективность его очевидна. Из определения отображения g получаем 1) g(f(x)) = х. Аналогично выполняется 2) (f оg)(у)= f(g(y))= f(x) = y

5. Множество Y^X, и количество элементов |Y^X| в этом множестве.

Определение 1.25. Пусть X и Y - непустые множества. Множество всех отображений из X в Y назовем множество степень и обозначим Y^X, то есть Y^X = {f | f : X → Y} .

Теорема 1.26. Пусть X uY - конечные непустые множества. Тогда |Y^X| = |Y|^|X|.

Доказательство. Для доказательства теоремы применим индукцию по количеству элементов в множестве X. Пусть |Х| = 1, то есть X = {х}, Y = {y₁,y₂,…,y_m}. Каждое отображение f : X → Y определяется тем, куда попадет элемент х. В этом случае все раз­личные отображения из множества X в множество Y можно просто перечислить: f₁ - такое отображение, что f₁(x) = y₁; f₂ - такое, что f₂ (x) = у₂; ...; f_m - такое, что f_m(x) = у_m. Ясно, что все эти отображения разные и |Y^X| = m¹ = |Y|^|X|. Предположим далее, что для любого множества X такого, что |Х| < п. Пусть теперь |Х| = п, то есть X = {x₁,x₂ ,…,x_n}. Множество Y^X разобьем на непересекающиеся подмножества: Y^X = A₁ A₂ ... A_m, где m = |Y|, Y = {y₁, y₂,…,y_m}. A_j = {f : X → Y | f(x₁) = y_j }. Ясно, число A_j ∩ A_k = Ø, если j ≠ k. По правилу суммы |Y^X| = |А₁| + |А₂| + ... + |А_т|. Посчитаем теперь количество элементов в каждом множестве A_j. При любом отображении f Aj образ элемента х₁ фиксирован (f(x₁) = y_j), следовательно отображение f определя­ется только тем, куда попадут элементы множества Х \ {x₁}. Таким образом отображение f однозначно определяется своим ограничением на Х \ {х₁}, поэтому для любого j количе­ство элементов в множестве A_j совпадает с количеством всех различных отображений из множества Х \ {х₁} в множество Y. По предположению индукции |A_j| = |Y ^X\{x1}| = mⁿ⁻¹.

Тогда |Y ^X| = m · mⁿ⁻¹ = mⁿ = |Y |^|X|, что и требовалось доказать.

8. Число сочетаний из n элементов по m элементам (C_n^m)

Число различных m-элементных подмножеств множества, состоящего из п элементов, называют числом сочетаний длины т из п элементов и обозначают . Итак, = n!/(m!(n-m)!) - число различных m-элементных подмножеств множества, состоящего из п эле­ментов.

Следствие. Пусть |Х| = п. Тогда число всех различных подмножеств множества X равно

Теорема 1.30. Число сочетаний с повторениями длины п из т видов равно . При доказательстве используется та же схема, что и при решении предыдущей задачи.

11. Кольца. Поля. Определение и примеры.

12. Кольцо Z_m и кольцо Z_p.

Определение 2.13. Алгебраическая система (К, +, ∙) с двумя бинарными операциями, сложением и умножением, называется кольцом, если:

1. (К, +) - абелева группа;

2. {К,∙) - полугруппа;

3. операция умножения дистрибутивна относительно операции сложения, то есть:

а ∙ (b + с) = а ∙ b + а ∙ с, (b + с) ∙ а = b ∙ а + с ∙ а, Vа, b,с К.

Если в кольце К есть 1 по умножению так, что а ∙ 1 = 1 ∙ а = а для любого элемента а из К, то К называют кольцом с единицей; если операция умножения в кольце К - коммутативна, то есть а∙b = b∙ а для любых элементов а и b из К, то кольцо К называют коммутативным.

Примеры.

1. Алгебраические системы (Z, +, ∙), (Q, +, ∙), (Е, +, ∙) являются коммутативными кольца­ми с единицей.

2. Алгебраические системы (Mat_n×n(Z), +, ∙), (Mat_n×n(Q),+,∙), (Mat_n×n(R), +, ∙) являются кольцами с 1, но не являются коммутативными кольцами. ( Mat_n×n(P) - это множество матриц размера п × п над Р).

3)Пусть п - натуральное число. На множестве Z определим отношение эквивалентности:

z₁ ~ z₂ тогда и только тогда, когда z₁ — z₂ = п ∙ z для некоторого z Z.

Тогда множество Z разобьется на непересекающиеся классы эквивалентности:

Z = nZ (1 + nZ) ... ((n - 1) + nZ), (m + nZ = {m + nz | z Z}.)

Класс эквивалентности m + nZ обозначим для т {0,1,... ,п — 1}, то есть = m + nZ. Кольцом классов вычетов по модулю п назовем множество Z_n={ , ,..., }co следующими операциями сложения и умножения:

Заметим, что операции заданы корректно, так как для любого числа к Z найдется такое число т {0,1,..., п — 1}, что k = nq + m, q Z, следовательно k + nZ = т + nZ = т. Кольцо Z_n - это коммутативное кольцо с единицей. Нулем в этом кольце будет элемент , а единицей – эл. .

Определение 2.14. 1) Элемент к ≠ 0 в кольце К называется делителем 0, если в кольце К найдется такой элемент b ≠ 0, что b∙k = 0 или k∙b = 0. 2) Элемент k ≠ 0 в кольце К называется нильпотентным, если k^п = 0 для некоторого n N.

Примеры.

1. В кольце Z₆ элементы и являются делителями 0, так как .

2. В кольце Z₄ элемент является нильпотентным элементом и делителем 0, так как .

Заметим, что в кольце с единицей делители нуля и нильпотентные элементы не могут быть обратимыми.

Определение 2.15. Ненулевое коммутативное кольцо Р с единицей называется полем, если любой его ненулевой элемент - обратим.

Примеры.

1. (Q, +, ∙) - поле рациональных чисел.

2. (R, +, ∙) - поле действительных чисел.

3. (С, +, ∙) - поле комплексных чисел.

4. (Z₂, +, ∙) - поле классов вычетов по модулю 2.

Обобщим последний пример.

Теорема 2.16. Кольцо Z_n будет полем тогда и только тогда, когда п - простое число.

Доказательство. => Пусть Z_n - поле и п = k∙т, где k,т N, k, т ≠ 1, n. Тогда и элемент k не может быть обратим. Действительно, предположив, что существует элемент такой, что , получим

,

то есть и т = п. Итак, если п - составное число, п = k∙т, то элемент - необратим, что противоречит условию: Z_n - поле.

<= Пусть р - простое число. Докажем, что Z_p - поле. Так как известно, что Z_p - комму­тативное кольцо с единицей, достаточно доказать, что любой ненулевой элемент в Z_p -обратим. Пусть - произвольный элемент из Z_p. Так как т < р и р - простое чис­ло, то натуральные числа тир- взаимно просты. Тогда, используя алгоритм Евклида, можно найти такие числа a ,b N, что а ∙ т + b∙ р = 1. Следовательно

и элемент т - обратим. Заметим, что единичный элемент всегда обратим.

Без доказательства сформулируем следующую теорему.

Теорема 2.17. Пусть 1 и 0 - единица и нуль поля Р. Тогда либо п ∙ 1 ≠ 0 для любого натурального числа п, либо существует простое натуральное число р такое, что р ∙ 1 = 0. Впервом случае говорят, что поле Р имеет нулевую характеристику и пишут charP = 0; во втором случае, говорят, что поле Р имеет характеристику р и пишут charP = p, в этом случае аддитивная группа, или группа по сложению, порожденная элементом 1, изоморфна полю Z_p и состоит из элементов k ∙ 1, k {0,1,... ,р — 1}.

9. Множество с операциями. Алгебраические структуры. Полугруппа. Моноид. Группа. Определение и примеры.

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

Определение 2.1. Бинарной операцией на множестве X называется правило, по кото­рому любым двум элементам x, y из множества X ставится в соответствие некоторый, однозначно определенный, элемент из X, обозначаемый х * у.

Заметим, что на множестве X могут быть определены и так называемые унарные опе­рации: каждому элементу множества X ставится в соответствие некоторый, однозначно определенный, элемент множества X. Таким образом задание унарной операции - это задание некоторого отображения f : X —> X. Точно также на множестве определяют­ся нуль-арные операции: выделение какого-то элемента множества. По аналогии можно определить п-арную операцию на множестве X как некоторое отображение f : Х^п → X.

На одном и том же множестве могут быть определены несколько операций. Например, на множестве Z определены две бинарные операции: сложение и умножение; унарная операция: каждому элементу z множества Z ставится в соответствие элемент (—z); две нуль-арные операции: выделение 0 и 1.

Определение 2.2. Операция * на множестве X называется

1) ассоциативной, если для любых элементов х, у, z X выполняется равенство (x*y)*z=х* (y*z);

2)коммутативной, если для любых элементов х,у X выполняется равенство х*у = у*х.

Определение 2.3. Элемент e в множестве X называется нейтральным, единицей, от­носительно операции * на X, если для любого элемента х из множества X выполняется равенство х*е=е*х= х.

Заметим, что выделение нейтрального элемента в множестве задает нуль-арную операцию на этом множестве. Если операция * - обычное умножение на множестве N, Z или R, то е = 1 называют единицей; если же * - обычное сложение, то е = 0 называют нулем.

Примеры.

1) Бинарные операции сложения и умножения на множестве Z - ассоциативны и комму­тативны. Нейтральным эл-ом относительно операции сложения яв-ся 0, а относи­тельно умножения – 1.

2) Рассмотрим множество матриц порядка 2×2 (таблица, состоящая из действительных чисел), такое множество обычно обозначают M₂(R). На этом множестве определены две бинарные операции: сложение и умножение. Операция сложения - ассоциативна и комму­тативна; операция умножения - ассоциативна, но не коммутативна. Нейтральным элемен­том относительно сложения является матрица

Определение 2.4. Непустое множество X с заданной на нем ассоциативной операцией *, обозначаем (X, *), называется полугруппой. Полугруппу (X, *), в которой относительно операции * существует нейтральный элемент, называют моноидом.