Глава 1. Алгебраические структуры
Теория групп – это важный раздел алгебры, имеющий много приложений. Группы служат инструментом для изучения симметрии объекта и используются кроме самой математики в кристаллографии, квантовой механике, физике твердого тела и во многих других областях, в которых симметрия играет значительную роль. Понятие группы возникло в работах французского математика Эвариста Галуа (1811 – 1832), связавшего его с возможностью выразить корни алгебраического уравнения через его коэффициенты.
Мы начнем наше изложение с таких основополагающих понятий как множество, отображение, бинарное отношение, которые потребуются нам в дальнейшем. Хотя многие из обсуждаемых понятий обычно проходят в начале курса математического анализа, тем не менее для полноты изложения мы приведем здесь все необходимые формулировки.
§ 1. 1. Множества и отображения
Договоримся обозначать множества большими латинскими буквами A, B, …, Z. Элементы этих множеств будем, как правило, обозначать маленькими латинскими буквами a, b, c, …, z. Тот факт, что a есть элемент множества A, будем записывать с помощью следующего обозначения: a A.
Определение. Если каждый элемент множества A принадлежит множеству B, то будем говорить, что множество A вложено в множество B и обозначать:AB.
Если ab, но ab , будем говорить, что a – строгое подмножество множества b.
Определение. Пусть имеются два множества A и B. Их объединением будем называть множество, элементами которого являются все элементы множества A и множества B. Объединение множеств A и B обозначается символом AB.
Определение. Пересечением множеств A и B будем называть множество, элементами которого являются все элементы, принадлежащие A и B одновременно. Пересечение множеств обозначается символом A B.
Определение. Разностью множеств A и B , будем называть множество, состоящее из всех тех элементов множества A, которые не принадлежат B. Разность множеств обозначается символом AB.
Определение. Множество, в котором нет элементов, будем называть пустым и обозначать символом . Считается, что пустое множество является подмножеством любого множества.
Определение. В случае, если множество A конечно, число его элементов будем обозначать символом |A|. В случае, когда множество A бесконечно, будем писать |A|=.
Определение.
Пусть все
рассматриваемые множества содержатся
в некотором одном множестве X,
которое мы будем называть универсальным,
и A
X
– одно из них. Тогда множество XA
будем называть дополнением множества
A
и обозначать символом
.
Например, если мы рассматриваем множества на плоскости, то роль X будет играть вся плоскость, а множество будет состоять из всех точек плоскости, не принадлежащих A.
Определение.
Пусть
имеются два множества A
и B.
Их декартовым произведением будем
называть множество A
B,
элементами которого являются пары
(a,b),
где a
A,
b
B.
Если имеется n
множеств A1,
A2,…,
An
, то
аналогично можно образовать их декартово
произведение
Если все множества
совпадают,
то декартово произведение
называют декартовой степенью множества
A
и обозначают
.
Задача 1.1.1. Для
следующих множеств A
и B
и универсального множества X
найдите множества
а) A={ , , , }, B={ , , }, X={ – альфа, – бета, – гамма, – дельта, – эпсилон, – дзета, – эта, – тэта, – йота, – каппа, – лямбда, – мю } – первые 12 букв греческого алфавита.
б) A={, , , , }, B={ , , , }, X={ – ню, – кси, – омикрон, – пи, – ро, – сигма, – тау, – ипсилон, – фи, – хи, – пси, – омега } – последние 12 букв греческого алфавита.
Ответ а)
{
,
,
,
,
},
{
,
},
{
,
},
{
},
=
{ ,
,
,
,
,
,
,
},
=
{,
,
,
,
,
,
,
,
},
{(,
),
( ,
), (,
),
(,
),
(,
),
(,),
(,
),
(,
),
(,
),
(,
),
(,
),
(,
)}.
б) Решите самостоятельно.
Задача 1.1.2. Для
следующих множеств A
и B
и универсального множества X
найдите множества
а)
.
б)
.
Ответ а):
б) Решите самостоятельно.
Если множества
и
конечны, то
Аналогично, если множества
конечны, то
В частности,
Например, если
множество
,
а множество
,
то множество
состоит из 6 элементов:
.
Задача 1.1.3.a) Допустим, что у вас есть три свитера, четверо брюк и две пары туфель. Каким числом способов вы можете одеться? б) Обед состоит из 1-го, 2-го и 3-го блюд. В столовой имеются три варианта 1-го блюда, пять вариантов 2-го и четыре варианта 3-го. Каким числом способов можно выбрать 3 блюда на обед?
а)
Число
способов одеться равно числу элементов
декартова произведения трех множеств
A,B
и C,
где A
– множество свитеров, B
– множество брюк и C
– множество пар туфель. Поскольку
то
б) Решите самостоятельно.
Определение. Множество B={0,1}, состоящее из двух элементов: нуля и единицы, называется булеаном.
Из формулы для числа элементов декартова произведения следует, что число двоичных последовательностей длины n равно 2n.
Двоичную
последовательность можно рассматривать
как двоичное число. Если
B,
то двоичное число
понимается как
Чтобы отличить двоичное число от
десятичного, справа внизу от числа
ставится цифра 2.
Задача 1.1.4. Переведите следующие двоичные числа в десятичные:
a)
б)
в)
г)
а)
б) - г) Решите самостоятельно.
Обратно, если нужно десятичное число перевести в двоичное, то мы делим десятичное число на 2 с остатком до тех пор, пока неполное частное не будет равно 0. Тогда остатки от деления, записанные справа налево, дадут двоичную запись этого десятичного числа.
Задача 1.1.5. Переведите следующие десятичные числа в двоичные а) 100;б) 128; в) 233; г) 500.
а)
Пусть
– неполное частное при делении на 2, а
– остаток,
.
Таким образом,
б) - г) Решите самостоятельно.
Определение.
Пусть
имеются два множества
и
Если
каждому элементу
поставлен
в соответствие какой-то элемент
то
говорят, что задано отображение f
из множества
в множество
Этот
факт обозначается следующим образом:
Если элементу поставлен в соответствие элемент то b называют образом элемента a и обозначают символом f(a). Элемент a при этом называют прообразом элемента b.
Каждый элемент при отображении f имеет ровно один образ, в то время как элемент множества B может иметь несколько прообразов. Множество прообразов может быть также и пустым.
Задать отображение означает, во-первых, указать множества A и B, и, во-вторых, каким-то образом определить элемент f(a) для каждого элемента .
Приведем некоторые примеры отображений.
Пример 1. Пусть
– множество целых чисел. Отображение
определим
формулой
Тогда, например,
Пример 2.
Отображение
определим
следующим образом:
Пример 3.
Отображение
зададим
таблицей.
-
a
b
c
d
Здесь в первой строке таблицы указаны элементы множества A, а во второй строке под каждым элементом из A указан его образ.
Множество всех
отображений
обозначим
.
Если множества
A
и B
конечны, то
. Действительно,
каждое такое отображение можно задать
таблицей как в примере 3. Каждую клетку
нижней строки этой таблицы можно
заполнить
способами. Поскольку таких клеток
штук и каждому варианту заполнения
нижней строки однозначно соответствует
некоторое отображение
,
то число
отображений будет
.
Задача 1.1.6. a) Каким числом способов можно разложить шесть разных предметов по четырем ящикам стола, если каждый предмет можно положить в любой ящик? Допускается, что все передметы могут быть положены в один ящик, места там хватит.
б) Для награждения пяти победителей школьной олимпиады выделены книги трех наименований. Каждый победитель может выбрать одну книгу по своему желанию. Имеется достаточное количество экземпляров книг каждого наименования, так что при желании все школьники могут выбрать книги одного наименования. Каким числом способов победители олимпиады могут выбрать себе книги?
а)
Каждый
срособ разложить предметы означает
задание отображения из множества
предметов в множество ящиков. Поскольку
первое множество состоит из 6 предметов,
а второе из 4, то число способов равно
б) Решите самостоятельно.
Определение.
Отображение
называется
инъективным, если образы разных элементов
из множества A
всегда различны. Другими словами если
и
,
то и
.
Определение.
Отображение
называется
сюръективным, если для любого элемента
найдется
такой элемент
,
что
,
т.е. если каждый элемент из B
имеет хотя бы один прообраз.
Определение. Отображение называется взаимно однозначным, если оно инъективно и сюръективно.
Отображение f
из примера
2 инъективно, но не сюръективно. Отображение
f
из примера
3, напротив, сюръективно, но не инъективно.
Если множества A
и B
конечны и
существует взаимно однозначное
отображение
,
то отсюда следует, что количество
элементов в множествах
A
и B
одно и то
же. Для бесконечных множеств, однако,
взаимно однозначное отображение
может
существовать даже если A
строгое
подмножество в B.
Например,
– множество всех действительных чисел
из отрезка
,
,
определено
формулой
.
Если
,
то число всех взаимно однозначных
отображений
равно
Действительно,
если
– элементы множества A,
а
– элементы множества B,
то элемент
можно отобразить в множество B
n
способами.
Если образ
элемента
уже выбран, то элемент
можно отобразить n-1
способом, а элемент
n-2
способами и т.д.. Число взаимно однозначных
отображений, таким образом, будет равно
Задача 1.1.7. a)
Пусть
Сколько существует инъективных
отображений
?
б) Пусть
Сколько существует сюръективных
отображений
?
а)
Элемент
x
можно
отобразить в любой из пяти элементов
множества B.
Если образ
элемента x
уже выбран,
то элемент y
можно
отобразить в любой из оставшихся четырех
элементов. Если уже выбраны образы
элементов x
и
y,
то элемнт z
можно
отобразить тремя способами. В результате
получается
инъективных отображений.
б) Решите самостоятельно.
Задача 1.1.8.
Существует
ли взаимно однозначное отображение
,
если
A
и
B
– следующие
отрезки на числовой прямой a)
б)
?
а)
Да,
например,
б) Решите самостоятельно.
Определение.
Множество
всех подмножеств множества A
обозначается символом
Если множество A
конечно, то
Действительно, пусть
и
– все элементы множества A.
Тогда каждому подмножеству подмножеству
можно сопоставить последовательность
из нулей и единиц. В нижней строке
следующей таблицы мы поставим 1 под
элементом, если данный элемент входит
в данное подмножество, и 0 в противном
случае.
|
|
|
|
|
|
|
|
Тем самым мы
установили взаимно однозначное
соответствие между всеми подмножествами
множества A
и всеми
двоичными последовательностями длины
n.
Поскольку число двоичных последовательностей
длины n
равно
,
то и число подмножеств будет таким же
Определение.
Пусть
Отображение
,
для которого
будем
обозначать следующим образом
Если f взаимно однозначно, будем называть его подстановкой.
Определение.
Если имеются
отображения
и g
: B
C,
то можно образовать отображение gf
: A
C,
определенное формулой (gf)(x)=g(f)x))
для всех
Отображение gf
будем называть суперпозицией f
и g.
Как следует из определения, суперпозиция суперпозиция двух отображений всегда действует справа налево, т.е., чтобы найти (gf)(x) , нужно сначала к элементу x применить отображение f , а потом g.
Аналогично можно рассматривать суперпозицию трех отображений и т.д.. Нетрудно проверить, что операция суперпозиции отображений удовлетворяет закону ассоциативности, т.е. (fg)h=f(gh).
Определение.
Отображение
,
для которого f(x)=x
для всех
называется тождественным и обозначается
или e.
Определение.
Обратным
для отображения
называется
такое отображение
что
и
.
Обратное отображение часто обозначают
Задача 1.1.9. а)
Пусть
,
Найдите
б) Пусть
,
Найдите
а)
Аналогично,
В результате
Аналогично,
Поскольку
то
Аналогично,
В итоге
б) Решите самостоятельно.
Определение. Пусть R2 – множество точек плоскости. Взаимно однозначное отображение f : R2 R2, сохраняющее расстояние между точками, будем называть движением.
Примерами движений на плоскости являются параллельный перенос, поворот, симметрия относительно некоторой прямой. Можно показать, что любое движение на плоскости можно представить в виде суперпозиции этих преобразований.
Определение. Точка A называется неподвижной для движения f, если f(A)=A. Движение, для которого все точки являются неподвижными, называется тождественным. В дальнейшем тождественное движение будет обозначаться буквой e.
Можно показать, что движение, имеющее три неподвижные точки не лежащие на одной прямой, является тождественным.
Ответы
1.1.1.б)
1.1.2.б)
1.1.3.б) 60.
1.1.4.б) 170;
в) 256;
г) 1023.
1.1.5.б) 10000000;
в) 11101001;
г) 111110100.
1.1.6.б) 243.
1.1.7.б) 30.
1.1.8.б) Да,
например,
1.1.9.б)
