Лекция 1. Базовые алгебраические структуры

Лекция строит язык, на котором дальше формулируется линейная алгебра. Векторное пространство — это множество с операциями, которые обязаны выполнять набор аксиом, поэтому заранее нужно понимать: что такое отображение и почему операция — это тоже отображение; что значит «операция замкнута»; что такое группа, кольцо и поле; почему скаляры берутся именно из поля.

Множества и отображения

Этот блок пересекается с вступительной лекцией матана; здесь — только то, что нужно для перестановок и операций.

Определение 1. Декартово произведение множеств $A$ и $B$ — множество всех упорядоченных пар:

$A \times B = \{(a, b) \mid a \in A,\ b \in B\}.$

Например, для $A = \{1, 2\}$ и $B = \{x, y\}$: $A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$. Декартово произведение нужно для определения бинарной операции — она получает на вход пару.

Определение 2. Отображение (функция) $f : A \to B$ ставит каждому $a \in A$ в соответствие ровно один элемент $f(a) \in B$. $A$ — область определения, $B$ — кодомен.

Определение 3. Пусть $f : A \to B$.

• Образ элемента $a \in A$ — это $f(a)$.
• Образ подмножества $X \subseteq A$: $f(X) = \{f(x) \mid x \in X\} \subseteq B$.
• Полный прообраз подмножества $Y \subseteq B$: $f^{-1}(Y) = \{x \in A \mid f(x) \in Y\} \subseteq A$.

Инъекция, сюръекция, биекция

Определение 4. Отображение $f : A \to B$ называется:

• инъективным, если разные элементы не склеиваются: $f(a_1) = f(a_2) \implies a_1 = a_2$ (эквивалентно: $a_1 \ne a_2 \implies f(a_1) \ne f(a_2)$);
• сюръективным, если каждый элемент кодомена достигается: $\forall b \in B\ \exists a \in A : f(a) = b$, то есть $f(A) = B$;
• биективным, если оно одновременно инъективно и сюръективно.

Примеры.

1. $f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n$ — инъекция (из $2n_1 = 2n_2$ следует $n_1 = n_2$), но не сюръекция: у числа $1$ нет прообраза.
2. $f : \mathbb{R} \to [0, +\infty)$, $f(x) = x^2$ — сюръекция (для $y \ge 0$ берём $x = \sqrt{y}$), но не инъекция: $f(1) = f(-1)$.
3. $f : \mathbb{R} \to \mathbb{R}$, $f(x) = x + 1$ — биекция: для каждого $y$ есть единственный $x = y - 1$.

Композиция и обратное отображение

Определение 5. Если $f : A \to B$ и $g : B \to C$, то композиция

$g \circ f : A \to C, \qquad (g \circ f)(x) = g(f(x)).$

Правое отображение выполняется первым.

Определение 6. Если $f : A \to B$ — биекция, то существует обратное отображение $f^{-1} : B \to A$, для которого

$f^{-1} \circ f = \mathrm{id}_A, \qquad f \circ f^{-1} = \mathrm{id}_B,$

где $\mathrm{id}_A(a) = a$ — тождественное отображение.

Бинарная операция

Определение 7. Бинарная операция на множестве $M$ — отображение

$* : M \times M \to M, \qquad (a, b) \mapsto a * b.$

Такое определение автоматически содержит замкнутость: результат снова лежит в $M$.

Пример. Сложение — бинарная операция на $\mathbb{Z}$: $(-7, 3) \mapsto -4$, результат снова целый.

Контрпример. Формула $a * b = \dfrac{a + b}{2}$ не задаёт бинарную операцию на $\mathbb{Z}$: для $a = 0$, $b = 1$ получаем $\tfrac{1}{2} \notin \mathbb{Z}$.

Группа

Определение 8. Пара $(G, *)$ называется группой, если $*$ — бинарная операция на $G$ и выполняются три аксиомы:

1. Ассоциативность: $(a * b) * c = a * (b * c)$ для всех $a, b, c \in G$.
2. Нейтральный элемент: существует $e \in G$ такой, что $a * e = e * a = a$ для всех $a \in G$.
3. Обратный элемент: для каждого $a \in G$ существует $a^{-1} \in G$ такой, что $a * a^{-1} = a^{-1} * a = e$.

Интуитивно: ассоциативность позволяет не думать о скобках в длинном произведении, нейтральный элемент «ничего не делает», обратный элемент отменяет действие.

Главный пример: $(\mathbb{Z}, +)$. Здесь $e = 0$, обратный к $a$ — это $-a$:

$(a + b) + c = a + (b + c), \qquad a + 0 = 0 + a = a, \qquad a + (-a) = 0.$

Что не является группой

• $(\mathbb{Z}, \cdot)$: умножение ассоциативно, есть нейтральный элемент $1$, но не у каждого целого есть обратный в $\mathbb{Z}$ — для $2$ потребовалось бы $\tfrac{1}{2} \notin \mathbb{Z}$.
• $(\mathbb{Z}, -)$: вычитание замкнуто, но не ассоциативно: $(5 - 3) - 2 = 0$, а $5 - (3 - 2) = 4$.

Следствия из аксиом группы

Утверждение 1 (единственность нейтрального элемента). Если $e$ и $e'$ оба нейтральные, то $e = e * e' = e'$.

Утверждение 2 (единственность обратного). Пусть $b$ и $c$ — оба обратные к $a$. Тогда

$b = b * e = b * (a * c) = (b * a) * c = e * c = c.$

Утверждение 3 (закон сокращения). В группе из $a * b = a * c$ следует $b = c$.

Доказательство. Домножим слева на $a^{-1}$: $a^{-1} * (a * b) = a^{-1} * (a * c)$. По ассоциативности $(a^{-1} * a) * b = (a^{-1} * a) * c$, то есть $e * b = e * c$ и $b = c$. $\blacksquare$

Именно это сокращение используется дальше в доказательствах свойств кольца.

Абелева группа

Определение 9. Группа $(G, *)$ называется абелевой (коммутативной), если дополнительно $a * b = b * a$ для всех $a, b \in G$.

$(\mathbb{Z}, +)$ — абелева группа. Группа перестановок $S_n$ при $n \ge 3$ неабелева (пример ниже).

Перестановки и симметрическая группа

Определение 10. Перестановка конечного множества $M$ — биективное отображение $\sigma : M \to M$. Для $M = \{1, 2, \dots, n\}$ множество всех перестановок обозначается $S_n$.

Биекция нужна, чтобы «переупорядочить» элементы без потерь и повторов: у каждого элемента ровно один образ и ровно один прообраз. Перестановку записывают двумя строками:

$\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \qquad \text{то есть } \sigma(1) = 2,\ \sigma(2) = 1,\ \sigma(3) = 3.$

Утверждение 4. $(S_n, \circ)$ — группа.

Доказательство. Композиция двух биекций — снова биекция, поэтому $\circ : S_n \times S_n \to S_n$ — бинарная операция. Ассоциативность следует из ассоциативности композиции функций, нейтральный элемент — $\mathrm{id}$, обратный к $\sigma$ — обратная биекция $\sigma^{-1}$. $\blacksquare$

Пример: S₃ неабелева

Пусть

$\beta = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \qquad \gamma = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}.$

Считаем $\gamma \circ \beta$: сначала применяется $\beta$, затем $\gamma$.

$1 \xrightarrow{\beta} 2 \xrightarrow{\gamma} 2, \qquad 2 \xrightarrow{\beta} 1 \xrightarrow{\gamma} 3, \qquad 3 \xrightarrow{\beta} 3 \xrightarrow{\gamma} 1.$

Поэтому

$\gamma \circ \beta = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \qquad \beta \circ \gamma = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}.$

Получили $\gamma \circ \beta \ne \beta \circ \gamma$, значит $S_3$ — не абелева группа.

Перестановка $\beta$ просто меняет местами $1$ и $2$, поэтому применение её дважды возвращает всё обратно: $\beta \circ \beta = \mathrm{id}$, то есть $\beta^{-1} = \beta$.

Кольцо

В разных учебниках разные соглашения: одни требуют единицу уже в определении кольца, другие выделяют «кольцо с единицей» отдельно. На лекции используется второй вариант.

Определение 11. Кольцо $(K, +, \cdot)$ — множество $K$ с двумя бинарными операциями, для которых:

1. $(K, +)$ — абелева группа;
2. умножение ассоциативно: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$;
3. выполняются обе дистрибутивности: $a \cdot (b + c) = a \cdot b + a \cdot c, \qquad (a + b) \cdot c = a \cdot c + b \cdot c.$

Из того, что $(K, +)$ — абелева группа, автоматически существуют ноль $0$ (такой, что $a + 0 = a$) и противоположный элемент $-a$ (такой, что $a + (-a) = 0$).

Определение 12. Кольцо называется коммутативным, если $a \cdot b = b \cdot a$ для всех $a, b \in K$.

Определение 13. Кольцо называется кольцом с единицей, если существует $1 \in K$ такое, что $1 \cdot a = a \cdot 1 = a$ для всех $a \in K$. Для нетривиального кольца предполагают $1 \ne 0$.

Примеры.

• $(\mathbb{Z}, +, \cdot)$ — коммутативное кольцо с единицей.
• Матрицы $n \times n$ над $\mathbb{R}$ образуют кольцо $\mathrm{M}_n(\mathbb{R})$. При $n \ge 2$ в общем случае $AB \ne BA$, так что это кольцо некоммутативно.

Домашнее задание: умножение на ноль

Правило «при умножении на ноль получается ноль» не входит в аксиомы кольца — оно из них выводится.

Утверждение 5. В любом кольце $a \cdot 0 = 0 \cdot a = 0$ для всех $a \in K$.

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

Поскольку $0 + 0 = 0$, имеем $a \cdot 0 = a \cdot (0 + 0)$. По дистрибутивности

$a \cdot (0 + 0) = a \cdot 0 + a \cdot 0, \qquad \text{значит} \qquad a \cdot 0 = a \cdot 0 + a \cdot 0.$

Прибавим к обеим частям противоположный элемент $-(a \cdot 0)$ и получим $0 = a \cdot 0$.

Второе равенство аналогично: $0 \cdot a = (0 + 0) \cdot a = 0 \cdot a + 0 \cdot a$, после сокращения $0 \cdot a = 0$. $\blacksquare$

Использованы только дистрибутивность и сокращение по сложению, которое следует из групповых аксиом для $(K, +)$.

Делители нуля и область целостности

Определение 14. В коммутативном кольце ненулевой элемент $a \ne 0$ называется делителем нуля, если существует $b \ne 0$ такое, что $a \cdot b = 0$.

Пример. В кольце вычетов $\mathbb{Z}_6$ элементы $2$ и $3$ ненулевые, но $2 \cdot 3 = 6 \equiv 0 \pmod 6$. Значит, $2$ и $3$ — делители нуля.

Определение 15. Область целостности (целостное кольцо) — коммутативное кольцо с единицей $1 \ne 0$, в котором нет делителей нуля.

$\mathbb{Z}$ — область целостности, $\mathbb{Z}_6$ — нет.

Утверждение 6 (сокращение в области целостности). Если $a \ne 0$ и $ab = ac$, то $b = c$.

Доказательство. $ab - ac = 0 \implies a(b - c) = 0$. Делителей нуля нет и $a \ne 0$, поэтому $b - c = 0$. $\blacksquare$

Поле

Определение 16. Поле $F$ — коммутативное кольцо с единицей $1 \ne 0$, в котором каждый ненулевой элемент обратим:

$\forall a \in F,\ a \ne 0 \quad \exists a^{-1} \in F : \quad a a^{-1} = a^{-1} a = 1.$

Классические примеры: $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$. А $\mathbb{Z}$ — не поле: у $2$ нет обратного целого.

Домашнее задание: все 10 аксиом поля

В соглашении лекции замкнутость уже включена в слова «$+$ и $\cdot$ — бинарные операции», поэтому отдельной аксиомой не считается.

Список аксиом

Пусть $F$ — множество с бинарными операциями $+$ и $\cdot$. Для любых $a, b, c \in F$:

Сложение

1. Ассоциативность: $(a + b) + c = a + (b + c)$.
2. Коммутативность: $a + b = b + a$.
3. Существование нуля: $\exists 0 \in F : a + 0 = 0 + a = a$.
4. Существование противоположного: $\forall a \in F\ \exists (-a) \in F : a + (-a) = 0$.

Умножение

5. Ассоциативность: $(ab)c = a(bc)$.
6. Коммутативность: $ab = ba$.
7. Существование единицы, отличной от нуля: $\exists 1 \in F,\ 1 \ne 0 : a \cdot 1 = 1 \cdot a = a$.
8. Существование обратного для ненулевых: $\forall a \ne 0\ \exists a^{-1} \in F : a a^{-1} = 1$.

Связь сложения и умножения

9. Левая дистрибутивность: $a(b + c) = ab + ac$.
10. Правая дистрибутивность: $(a + b)c = ac + bc$.

Итого $4 + 4 + 2 = 10$ аксиом.

Кольца вычетов по модулю n

Два целых числа сравнимы по модулю $n$, если имеют одинаковый остаток при делении на $n$:

$a \equiv b \pmod n \iff n \mid (a - b).$

Множество классов вычетов $\mathbb{Z}_n = \mathbb{Z} / n\mathbb{Z}$ можно представлять числами $\{0, 1, \dots, n - 1\}$, а операции выполнять с последующим взятием остатка. Например, в $\mathbb{Z}_5$:

$4 + 3 = 7 \equiv 2 \pmod 5, \qquad 3 \cdot 4 = 12 \equiv 2 \pmod 5.$

Теорема 1. $\mathbb{Z}_n$ является полем тогда и только тогда, когда $n$ — простое число.

Доказательство. Пусть $p$ простое и $a \not\equiv 0 \pmod p$. Тогда $\gcd(a, p) = 1$, и по соотношению Безу существуют $u, v \in \mathbb{Z}$ такие, что $au + pv = 1$. По модулю $p$ получаем $au \equiv 1 \pmod p$, то есть $u$ — обратный к $a$ в $\mathbb{Z}_p$.

Пусть теперь $n = rs$ составное, $1 \lt r, s \lt n$. Тогда в $\mathbb{Z}_n$ классы $[r] \ne [0]$ и $[s] \ne [0]$, но $[r][s] = [n] = [0]$. Это делители нуля, а в поле их быть не может. $\blacksquare$

Конечное поле из p элементов и пример F₅

Для простого $p$ пишут $\mathbb{F}_p \cong \mathbb{Z}_p$: поле из $p$ элементов реализуется как остатки $0, 1, \dots, p - 1$ с арифметикой по модулю $p$.

Таблица умножения F₅

Например, $2 \cdot 3 = 6 \equiv 1 \pmod 5$, поэтому $2^{-1} = 3$ и $3^{-1} = 2$. Также $1^{-1} = 1$ и $4^{-1} = 4$, поскольку $4 \cdot 4 = 16 \equiv 1 \pmod 5$.

Для сравнения: почему Z₆ не поле

В $\mathbb{Z}_6$ выполняется $2 \cdot 3 \equiv 0 \pmod 6$ при $2 \ne 0$ и $3 \ne 0$, то есть есть делители нуля. Кроме того, у $2$ нет обратного: ни одно из чисел $0, \dots, 5$ при умножении на $2$ не даёт остаток $1$.

Иерархия структур

Всю лекцию полезно видеть как лестницу требований: каждая следующая структура добавляет условие к предыдущей.

Утверждение 7. Поле автоматически является областью целостности.

Доказательство. Если $ab = 0$ и $a \ne 0$, домножаем на $a^{-1}$ и получаем $b = 0$. $\blacksquare$

Связь с векторными пространствами

Теперь видно, зачем поле появилось в начале курса.

Определение 17. Векторное пространство $V$ над полем $F$ — множество с операциями $+ : V \times V \to V$ и $\cdot : F \times V \to V$, такими, что $(V, +)$ — абелева группа и для всех $\lambda, \mu \in F$, $u, v \in V$:

$\lambda(u + v) = \lambda u + \lambda v, \qquad (\lambda + \mu) v = \lambda v + \mu v, \qquad (\lambda \mu) v = \lambda (\mu v), \qquad 1 \cdot v = v.$

Например, $\mathbb{R}^n$ — векторное пространство над $\mathbb{R}$, а $\mathbb{C}^n$ — над $\mathbb{C}$. Линейную алгебру можно строить и над конечными полями $\mathbb{F}_p$ — это важно в кодировании и дискретной математике.

Частые вопросы

Почему операция — это отображение? Операция должна каждому набору аргументов однозначно назначать результат. У бинарной операции два аргумента, поэтому её область определения — $M \times M$.

Почему у группы не требуют коммутативность? Потому что важные естественные группы некоммутативны: уже $S_3$ показывает, что композиция преобразований зависит от порядка.

Почему в поле обратный требуется только для $a \ne 0$? Если бы существовал $0^{-1}$, то $0 \cdot 0^{-1} = 1$. Но в любом кольце $0 \cdot x = 0$, и получилось бы $0 = 1$.

Почему $\mathbb{Z}$ — кольцо, но не поле? Для поля нужно делить на любой ненулевой элемент, оставаясь внутри множества. В $\mathbb{Z}$ у $2$ нет обратного: $\tfrac{1}{2}$ не целое.

Почему $\mathbb{Q}$ — поле? Для любой ненулевой дроби $\tfrac{a}{b}$ обратная $\tfrac{b}{a}$ тоже рациональна.

Чем область целостности отличается от поля? В области целостности нет делителей нуля, но обратные могут отсутствовать ($\mathbb{Z}$). В поле обратный есть у каждого ненулевого элемента — это более сильная структура.

Мини-тренажёр

Сначала решите сами, потом откройте ответ.

1. Является ли $a * b = a - b$ бинарной операцией на $\mathbb{Z}$? А групповой операцией?
2. Является ли $a * b = a / b$ бинарной операцией на $\mathbb{R}$?
3. Классифицируйте $f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = n + 5$: инъекция, сюръекция, биекция?
4. Классифицируйте $g : \mathbb{R} \to \mathbb{R}$, $g(x) = x^2$.
5. Найдите обратную к перестановке $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$.
6. Является ли $(\mathbb{R} \setminus \{0\}, \cdot)$ группой? Абелевой?
7. Является ли $\mathbb{Z}_7$ полем?
8. Найдите $3^{-1}$ в $\mathbb{Z}_7$.
9. Есть ли делители нуля в $\mathbb{Z}_8$? Приведите пример.
10. Докажите, что в поле из $ab = 0$ следует $a = 0$ или $b = 0$.

Ответы

1. Бинарная операция — да (разность целых целая), групповая — нет: вычитание неассоциативно.
2. Нет: выражение не определено при $b = 0$.
3. Биекция, обратная $f^{-1}(m) = m - 5$.
4. Ни инъекция ($g(1) = g(-1)$), ни сюръекция на $\mathbb{R}$ (нет отрицательных значений).
5. $\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$.
6. Да, абелева группа: нейтральный элемент $1$, обратный к $x \ne 0$ равен $1/x$.
7. Да, потому что $7$ простое.
8. $3^{-1} = 5$, так как $3 \cdot 5 = 15 \equiv 1 \pmod 7$.
9. Да: $2 \cdot 4 = 8 \equiv 0 \pmod 8$, хотя $2 \ne 0$ и $4 \ne 0$.
10. Если $a \ne 0$, умножаем $ab = 0$ на $a^{-1}$: $b = a^{-1} \cdot 0 = 0$.

Шпаргалка