Глава 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\ne 3$, вычитание не ассоциативно. Кроме того, $0$ является правым нейтральным элементом ($a-0=a$), но не левым нейтральным ($0-a=-a\ne a$ при $a\ne 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\ne b$. Не коммутативна (при $|S|\ge 2$).
• Нейтральный элемент: нужно, чтобы $e\ast a=a$ для всех $a$. Но $e\ast a=e$, так что $e=a$ для всех $a$, что невозможно при $|S|\ge 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,\dots ,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 }^{\prime }b){\ast }^{\prime }b=a{\ast }^{\prime }b=b$, но $b{\ast }^{\prime }(b{\ast }^{\prime }b)=b{\ast }^{\prime }a=a$. Не ассоциативно. Внешне правдоподобная таблица не гарантирует ассоциативности.

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

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

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

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

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

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

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

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

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

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

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

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

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

$$a\ast b=b\ast a=e,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$. $■$

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

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

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

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

Пусть $(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$ является также правым нейтральным элементом. $■$

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

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

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