Глава 02 - Бинарные операции

Именно на бинарных операциях алгебра обретает точность. Выражение «операция на множестве» обязано означать настоящую функцию $S \times S \to S$, и уже одно это утверждение содержит в себе замкнутость. В этой главе свойства операций выделяются ещё до появления полной системы групповых аксиом.

§2.1 Определение

Определение 2.1 (Бинарная операция)

Бинарной операцией на множестве $S$ называется функция

Для $(a, b) \in S \times S$ результат записывается как $a \ast b$. Требование, чтобы $\ast$ отображала в $S$, означает, что замкнутость встроена в само определение: $a \ast b \in S$ для всех $a, b \in S$.

Замечание 2.2 (Замкнутость не является отдельной аксиомой)

Говоря «$\ast$ — бинарная операция на $S$», мы тем самым уже утверждаем замкнутость. Если предложенное правило выводит какую-то пару за пределы $S$ или не определено на некоторой паре, то это не бинарная операция на $S$. На этом рассмотрение должно прекратиться, ещё до проверки каких-либо дальнейших свойств.

§2.2 Свойства бинарных операций

Определение 2.3 (Коммутативность)

Бинарная операция $\ast$ на $S$ называется коммутативной, если

Определение 2.4 (Ассоциативность)

Бинарная операция $\ast$ на $S$ называется ассоциативной, если

Рисунок: ассоциативность сравнивает два способа перемножить тройку элементов.

Диаграмма утверждает, что независимо от того, объединим ли мы сначала первые два элемента или сначала последние два, мы обязаны прийти к одному и тому же элементу множества $S$.

Определение 2.5 (Нейтральный элемент)

Элемент $e \in S$ называется нейтральным для $\ast$, если

Определение 2.6 (Обратный элемент)

Пусть $\ast$ имеет нейтральный элемент $e$. Элемент $b \in S$ называется обратным к $a \in S$, если

§2.3 Примеры и контрпримеры

Пример 2.7 (Стандартные бинарные операции)

Пример 2.8 (Вычитание не ассоциативно)

На $\mathbb{Z}$ вычитание является бинарной операцией (замкнутость: $a - b \in \mathbb{Z}$), однако:

Поскольку $1 \neq 3$, вычитание не ассоциативно. Кроме того, $0$ является правым нейтральным элементом ($a - 0 = a$), но не левым нейтральным ($0 - a = -a \neq a$ при $a \neq 0$), так что двустороннего нейтрального элемента не существует.

Пример 2.9 (Деление не является бинарной операцией на $\mathbb{Z}$)

Правило $a / b$ не определено при $b = 0$, а даже там, где оно определено, $1/2 \notin \mathbb{Z}$. Поэтому $/ : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ не является функцией. На этом рассмотрение прекращается.

Пример 2.10 (Операция левой проекции)

На произвольном непустом множестве $S$ определим $a \ast b = a$. Это бинарная операция:

• Замкнутость: $a \ast b = a \in S$. Да.
• Ассоциативность: $(a \ast b) \ast c = a \ast c = a$ и $a \ast (b \ast c) = a \ast b = a$. Да.
• Коммутативность: $a \ast b = a$ против $b \ast a = b$; не выполняется, если только $a \neq b$. Не коммутативна (при $|S| \geq 2$).
• Нейтральный элемент: нужно, чтобы $e \ast a = a$ для всех $a$. Но $e \ast a = e$, так что $e = a$ для всех $a$, что невозможно при $|S| \geq 2$. Нейтрального элемента нет.

Этот пример показывает, что одна лишь ассоциативность ничего не влечёт относительно обратимости.

Пример 2.11 (Максимум на $\{0, 1, 2\}$)

На $S = \{0, 1, 2\}$ определим $a \ast b = \max\{a, b\}$. Операция ассоциативна и коммутативна, с нейтральным элементом $0$ ($\max\{0, a\} = a$). Однако обратный элемент имеет только $0$ (он сам), поскольку из $\max\{a, b\} = 0$ следует $a = b = 0$. Это не группа.

§2.4 Таблицы операций для конечных множеств

Определение 2.12 (Таблица операции / таблица Кэли)

Для конечного множества $S = \{a_1, \ldots, a_n\}$ с бинарной операцией $\ast$ таблицей операции (или таблицей Кэли) называется массив размера $n \times n$, у которого элемент в позиции $(i, j)$ равен $a_i \ast a_j$.

Пример 2.13 (Таблица операции для $\mathbb{Z}_4$ относительно сложения)

Как читать таблицу:

• Замкнутость: автоматически (каждый элемент принадлежит $\{0, 1, 2, 3\}$).
• Коммутативность: таблица симметрична относительно главной диагонали.
• Нейтральный элемент: строка для $0$ воспроизводит заголовок, и то же делает столбец.
• Обратные элементы: каждый элемент встречается в каждой строке (свойство латинского квадрата).

Пример 2.14 (Неассоциативная таблица операции)

Определим $\ast$ на $\{a, b\}$ так: $a \ast a = a$, $a \ast b = b$, $b \ast a = b$, $b \ast b = a$.

Это выглядит как таблица группы (и в самом деле является $\mathbb{Z}_2$): при отождествлении $a \mapsto 0$, $b \mapsto 1$ операция $\ast$ есть сложение по модулю $2$. Групповые аксиомы можно также прочитать прямо из таблицы: $a$ является нейтральным элементом (его строка и столбец воспроизводят заголовок), и каждый элемент обратен самому себе ($a \ast a = a$, $b \ast b = a$).

Но изменим одну ячейку: положим $b \ast a = a$ вместо прежнего.

Теперь проверим: $(b \ast' b) \ast' b = a \ast' b = b$, но $b \ast' (b \ast' b) = b \ast' a = a$. Не ассоциативно. Внешне правдоподобная таблица не гарантирует ассоциативности.

Замечание 2.15 (Ассоциативность нельзя прочитать из таблицы с первого взгляда)

Замкнутость, нейтральный элемент, обратные элементы и коммутативность — всё это можно проверить непосредственно по таблице Кэли. Ассоциативность — нельзя: она требует проверки $n^3$ троек. Для малых таблиц проверку проводят вручную; для бóльших структур ассоциативность наследуется от известной ассоциативной объемлющей операции.

§2.5 Единственность нейтрального и обратного элемента

Теорема 2.16 (Единственность нейтрального элемента)

Если бинарная операция $\ast$ на $S$ имеет двусторонний нейтральный элемент, то он единствен.

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

Пусть $e$ и $f$ — два двусторонних нейтральных элемента. Тогда:

$$e = e \ast f = f,$$

где первое равенство использует то, что «$f$ — правый нейтральный элемент», а второе — то, что «$e$ — левый нейтральный элемент». Следовательно, $e = f$. $\blacksquare$

Теорема 2.17 (Единственность обратного элемента в ассоциативной структуре)

Если $\ast$ ассоциативна и имеет нейтральный элемент $e$, а элемент $a \in S$ имеет двусторонний обратный, то этот обратный единствен.

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

Пусть $b$ и $c$ — два двусторонних обратных к $a$:

$$a \ast b = b \ast a = e, \qquad a \ast c = c \ast a = e.$$

Тогда:

$$b = b \ast e = b \ast (a \ast c) = (b \ast a) \ast c = e \ast c = c.$$

Средний шаг использует ассоциативность. Следовательно, $b = c$. $\blacksquare$

Замечание 2.18 (Ассоциативность существенна для единственности обратных элементов)

Без ассоциативности обратные элементы могут не быть единственными. В приведённом доказательстве ассоциативность используется ровно в одном месте: при перегруппировке $b \ast (a \ast c) = (b \ast a) \ast c$. Если она не выполняется, рассуждение рушится.

§2.6 Односторонние данные могут вынуждать двусторонние

Теорема 2.19 (Левый нейтральный + левые обратные $\implies$ группа)

Пусть $(S, \ast)$ — ассоциативная бинарная структура с левым нейтральным элементом $e$ (то есть $e \ast x = x$ для всех $x$) и левыми обратными (для каждого $a$ существует $\ell$, для которого $\ell \ast a = e$). Тогда $e$ является двусторонним нейтральным элементом, и каждый левый обратный является двусторонним обратным.

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

Зафиксируем $a \in S$ с левым обратным $\ell$ ($\ell \ast a = e$). Пусть $m$ — левый обратный к $\ell$ ($m \ast \ell = e$). Тогда:

$$a = e \ast a = (m \ast \ell) \ast a = m \ast (\ell \ast a) = m \ast e = m.$$

Это рассуждение слишком поспешно, поскольку на данном этапе мы ещё не доказали, что $e$ — правый нейтральный элемент. Поэтому начнём заново с вычисления, которое использует только данные нам предположения.

Имеем $\ell \ast a = e$ и $m \ast \ell = e$. Вычислим:

$$a \ast \ell = (e) \ast (a \ast \ell) = (m \ast \ell) \ast (a \ast \ell) = m \ast (\ell \ast a) \ast \ell = m \ast e \ast \ell = m \ast (e \ast \ell) = m \ast \ell = e.$$

Итак, $\ell$ является также правым обратным к $a$. Теперь:

$$a \ast e = a \ast (\ell \ast a) = (a \ast \ell) \ast a = e \ast a = a.$$

Итак, $e$ является также правым нейтральным элементом. $\blacksquare$

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

Контрольный список освоения

• Сформулировать определение бинарной операции и объяснить, почему замкнутость является частью определения, а не отдельной аксиомой.
• Различать ассоциативность и коммутативность на примерах, где одно свойство выполняется, а другое — нет.
• Привести контрпример, в котором предложенное правило не является бинарной операцией (нарушается замкнутость).
• Доказать единственность нейтрального элемента.
• Доказать единственность обратных элементов при наличии ассоциативности.
• Прочитать таблицу Кэли и извлечь нейтральный элемент, обратные элементы и коммутативность; объяснить, почему ассоциативность нельзя по ней прочитать.
• Сформулировать и объяснить теорему о «левом нейтральном + левых обратных» (Теорема 2.19).