Дискретная математика — теория групп

Конечное или бесконечное множество ′S′$'S'$ с бинарной операцией ′ omicron′$'\ omicron'$ (Composition) называется полугруппой, если оно одновременно выполняет следующие два условия:

• Замыкание — для каждой пары $(a, b) \ in S \ 🙁 a \ omicron b)$ должно присутствовать в множестве $S$.

• Ассоциативно — для каждого элемента $a, b, c \ in S должно выполняться (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c)$.

Замыкание — для каждой пары $(a, b) \ in S \ 🙁 a \ omicron b)$ должно присутствовать в множестве $S$.

Ассоциативно — для каждого элемента $a, b, c \ in S должно выполняться (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c)$.

пример

Множество натуральных чисел (исключая ноль) с операцией сложения является полугруппой. Например, $S = \ lbrace 1, 2, 3, \ dots \ rbrace$

Здесь свойство замыкания выполняется так же, как и для любой пары $(a, b) \ in S, (a + b)$ присутствует в множестве S. Например, $1 + 2 = 3 \ in S]$

Ассоциативное свойство также справедливо для каждого элемента $a, b, c \ in S, (a + b) + c = a + (b + c)$. Например, $(1 + 2) + 3 = 1 + (2 + 3) = 5$

Monoid

Моноид — это полугруппа с единичным элементом. Элемент идентичности (обозначаемый $e$ или E) множества S — это такой элемент, что $(a \ omicron e) = a$ для каждого элемента $a \ in S$. Элемент идентичности также называется единичным элементом . Таким образом, моноид одновременно обладает тремя свойствами — замыкание, ассоциативность, элемент идентичности .

пример

Множество натуральных чисел (исключая ноль) с операцией умножения является моноидом. $S = \ lbrace 1, 2, 3, \ dots \ rbrace$

Здесь свойство замыкания выполняется так же, как и для любой пары $(a, b) \ in S, (a \ times b)$ присутствует в множестве S. [Например, $1 \ times 2 = 2 \ in S$ и т. Д.]

Ассоциативное свойство также справедливо для каждого элемента $a, b, c \ in S, (a \ times b) \ times c = a \ times (b \ times c)$ [Например, $(1 \ times 2) \ times 3 = 1 \ times (2 \ times 3) = 6$ и т. Д.]

Свойство идентичности также выполняется для каждого элемента $a \ in S, (a \ times e) = a$ [Например, $(2 \ times 1) = 2, (3 \ times 1) = 3$ и т. Д.]. Здесь единичный элемент равен 1.

группа

Группа — это моноид с обратным элементом. Обратный элемент (обозначаемый I) множества S — это такой элемент, что $(a \ omicron I) = (I \ omicron a) = a$ для каждого элемента $a \ in S$. Таким образом, группа обладает четырьмя свойствами одновременно: i) замыкание, ii) ассоциативное, iii) элемент идентичности, iv) обратный элемент. Порядок группы G — это число элементов в G, а порядок элемента в группе — это наименьшее положительное целое число n, такое, что an является единичным элементом этой группы G.

Примеры

Множество $N \ times N$ неособых матриц образуют группу при операции умножения матриц.

Произведение двух $N \ times N$ неособых матриц также является $N \ times N$ неособой матрицей, которая обладает свойством замыкания.

Матричное умножение само по себе является ассоциативным. Следовательно, ассоциативное свойство имеет место.

Множество $N \ times N$ неособых матриц содержит единичную матрицу, содержащую свойство единичного элемента.

Поскольку все матрицы неособы, все они имеют обратные элементы, которые также являются неособыми матрицами. Следовательно, обратное свойство также имеет место.

Абелевская группа

Абелева группа G — это группа, для которой пара элементов $(a, b) \ в G$ всегда имеет коммутативный закон. Таким образом, группа одновременно обладает пятью свойствами: i) замыкание, ii) ассоциативное, iii) элемент идентичности, iv) обратный элемент, v) коммутативность.

пример

Множество натуральных чисел (включая ноль) с операцией сложения является абелевой группой. $G = \ lbrace 0, 1, 2, 3, \ dots \ rbrace$

Здесь свойство замыкания выполняется так же, как и для любой пары $(a, b) \ in S, (a + b)$ присутствует в множестве S. [Например, $1 + 2 = 2 \ in S$ и т. Д.]

Ассоциативное свойство также справедливо для каждого элемента $a, b, c \ in S, (a + b) + c = a + (b + c)$ [Например, $(1 +2) + 3 = 1 + (2 + 3) = 6$ и т. Д.]

Свойство идентичности также выполняется для каждого элемента $a \ in S, (a \ times e) = a$ [Например, $(2 \ times 1) = 2, (3 \ times 1) = 3$ и т. Д.]. Здесь элемент идентичности равен 1.

Коммутативное свойство также выполняется для каждого элемента $a \ in S, (a \ times b) = (b \ times a)$ [Например, $(2 \ times 3) = (3 \ times 2) = 3$ и т. Д. на]

Циклическая группа и подгруппа

Циклическая группа — это группа, которая может быть сгенерирована одним элементом. Каждый элемент циклической группы — это степень некоторого определенного элемента, который называется генератором. Циклическая группа может быть сгенерирована генератором «g», так что любой другой элемент группы может быть записан как степень генератора «g».

пример

Множество комплексных чисел $\ lbrace 1, -1, i, -i \ rbrace$ при операции умножения является циклической группой.

Есть два генератора — $i$ и $–i$ как $i ^ 1 = i, i ^ 2 = -1, i ^ 3 = -i, i ^ 4 = 1$, а также $(- i) ^ 1 = -i, (–i) ^ 2 = -1, (–i) ^ 3 = i, (–i) ^ 4 = 1$, что охватывает все элементы группы. Следовательно, это циклическая группа.

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

Подгруппа H является подмножеством группы G (обозначается как $H ≤ G$), если она одновременно удовлетворяет четырем свойствам — Замыканию, Ассоциативности, Элементу идентичности и Обратному .

Подгруппа H группы G, не включающая всю группу G, называется собственной подгруппой (обозначается через $H <G$). Подгруппа циклической группы является циклической, и абелева подгруппа также абелева.

пример

Пусть группа $G = \ lbrace 1, i, -1, -i \ rbrace$

Тогда некоторые подгруппы являются $H_1 = \ lbrace 1 \ rbrace, H_2 = \ lbrace 1, -1 \ rbrace$,

Это не подгруппа — $H_3 = \ lbrace 1, i \ rbrace$, потому что $(i) ^ {- 1} = -i$ не входит в $H_3$

Частично заказанный набор (POSET)

Частично упорядоченный набор состоит из набора с бинарным отношением, которое является рефлексивным, антисимметричным и транзитивным. «Частично упорядоченный набор» сокращенно обозначен как ПОЗЕТ.

Примеры

• Множество действительных чисел при бинарной операции, меньше или равное $(\ le)$, является набором.

  Пусть множество $S = \ lbrace 1, 2, 3 \ rbrace$ и операция равна $\ le$

  Соотношения будут $\ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace$

  Это отношение R рефлексивно как $\ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R$

  Это отношение R антисимметрично, так как

  $\ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ и \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R$

  Это отношение R также транзитивно как $\ lbrace (1,2), (2,3), (1,3) \ rbrace \ in R$.

  Следовательно, это посет .

• Множество вершин ориентированного ациклического графа в операции «достижимость» — это множество.

Множество действительных чисел при бинарной операции, меньше или равное $(\ le)$, является набором.

Пусть множество $S = \ lbrace 1, 2, 3 \ rbrace$ и операция равна $\ le$

Соотношения будут $\ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace$

Это отношение R рефлексивно как $\ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R$

Это отношение R антисимметрично, так как

$\ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ и \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R$

Это отношение R также транзитивно как $\ lbrace (1,2), (2,3), (1,3) \ rbrace \ in R$.

Следовательно, это посет .

Множество вершин ориентированного ациклического графа в операции «достижимость» — это множество.

Диаграмма Хассе

Диаграмма Хассе для Poset — это ориентированный граф, вершинами которого являются элементы этого набора, а дуги покрывают пары (x, y) в poset. Если в poset $x <y$, то точка x оказывается ниже, чем точка y на диаграмме Хассе. Если $x <y <z$ в poset, то стрелка не показана между x и z, поскольку она неявная.

пример

Множество подмножеств $\ lbrace 1, 2, 3 \ rbrace = \ lbrace \ emptyset, \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace, \ lbrace 1, 2 \ rbrace, \ lbrace 1 , 3 \ rbrace, \ lbrace 2, 3 \ rbrace, \ lbrace 1, 2, 3 \ rbrace \ rbrace$ показаны следующей диаграммой Хассе —

Линейно упорядоченный набор

Линейно упорядоченный набор или Всего упорядоченный набор является частичным набором порядка, в котором каждая пара элементов сопоставима. Элементы $a, b \ in S$ называются сравнимыми, если выполняется либо $a \ le b$, либо $b \ le a$. Закон трихотомии определяет это общее упорядоченное множество. Полностью упорядоченное множество может быть определено как дистрибутивная решетка, имеющая свойство $\ lbrace a \ lor b, a \ land b \ rbrace = \ lbrace a, b \ rbrace$ для всех значений a и b в множестве S.

пример

Множество степеней в $\ lbrace a, b \ rbrace$, упорядоченных по \ subseteq, является полностью упорядоченным множеством, поскольку все элементы степенного множества $P = \ lbrace \ emptyset, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace a, b \ rbrace \ rbrace$ сравнимы.

Пример набора неполных заказов

Множество $S = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace$ при операции x делит y не является полным упорядоченным множеством.

Здесь для всех $ (x, y) \ in S, x | у $ надо держать, но это не правда, что 2 | 3, поскольку 2 не делит 3 или 3 не делит 2. Следовательно, это не полный упорядоченный набор.

решетчатый

Решетка — это множество $(L, \ le)$, для которого каждая пара $\ lbrace a, b \ rbrace \ in L$ имеет наименьшую верхнюю границу (обозначаемую $a \ lor b$) и наибольшую нижнюю границу ( обозначается как $a \ land b$). LUB $(\ lbrace a, b \ rbrace)$ называется объединением a и b. GLB $(\ lbrace a, b \ rbrace)$ называется собранием a и b.

пример

Этот рисунок выше является решеткой, потому что для каждой пары $\ lbrace a, b \ rbrace \ in L$ существует GLB и LUB.

Этот рисунок не является решеткой, поскольку $GLB (a, b)$ и $LUB (e, f)$ не существует.

Некоторые другие решетки обсуждаются ниже —

Ограниченная решетка

Решетка L становится ограниченной решеткой, если она имеет наибольший элемент 1 и наименьший элемент 0.

Дополненная решетка

Решетка L становится дополненной решеткой, если она является ограниченной решеткой и если у каждого элемента в решетке есть дополнение. Элемент x имеет дополнение x ‘, если $\ существует x (x \ land x' = 0 и x \ lor x '= 1)$

Распределительная решетка

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

• $a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c)$

• $a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c)$

$a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c)$

$a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c)$

Модульная решетка

Если решетка удовлетворяет следующему свойству, она называется модульной решеткой.

$a \ land (b \ lor (a \ land d)) = (a \ land b) \ lor (a \ land d)$

Свойства решеток

Идемпотент Свойства

• $a \ lor a = a$

• $a \ land a = a$

$a \ lor a = a$

$a \ land a = a$

Абсорбционные свойства

• $a \ lor (a \ land b) = a$

• $a \ land (a \ lor b) = a$

$a \ lor (a \ land b) = a$

$a \ land (a \ lor b) = a$

Коммутативные свойства

• $a \ lor b = b \ lor a$

• $a \ land b = b \ land a$

$a \ lor b = b \ lor a$

$a \ land b = b \ land a$

Ассоциативные свойства

• $a \ lor (b \ lor c) = (a \ lor b) \ lor c$

• $a \ land (b \ land c) = (a \ land b) \ land c$

$a \ lor (b \ lor c) = (a \ lor b) \ lor c$

$a \ land (b \ land c) = (a \ land b) \ land c$

Двойной Решетки

Двойственность решетки получается путем взаимного обмена операциями ‘$\ lor$‘ и ‘$\ land$‘.

пример

Двойственное из $\ lbrack a \ lor (b \ land c) \ rbrack \ is \ \ lbrack a \ land (b \ lor c) \ rbrack$