Алгебраические структуры

Операции на множестве

Пусть есть какое-то множество $S$ .

$n$ -арной операцией на множестве $S$ называется отображение

\varphi \colon S^n \to S

Если операция бинарная, то есть если $\varphi \colon S \times S \to S$ , то обычно $\varphi(a, b)$ записывают в инфиксной форме как $a \,\varphi\, b$ .

Например, всем известная бинарная операция $+$ на множестве $\RR$ .

С примерами известных тернарных операций посложнее. Но их всегда можно сконструировать. Возьмем, например, операцию $\RR^3 \to \RR$ , при которой $(a, b, c) \mapsto a \cdot b - c$ .

Всем программистам известна условная тернарная операция

a \mathbin{?} b : c \defeq \cases{b & \if a \neq 0 \\ c & \otherwise}

На неявное приведение типа первого аргумента к логическому здесь стоит просто забить.

Алгебра

Множество $S$ вместе с набором операций $\Sigma = \{\varphi_1, \varphi_2, \dotsc, \varphi_k\}$ называется алгеброй.

Здесь $\varphi_i \colon S^{n_i} \to S$ — $n_i$ -арная операция на множестве $S$ .

Множество $S$ называется основой или носителем алгебры, кортеж арностей $(n_1, n_2, \dotsc, n_k)$ называется типом алгебры, а множество операций $\Sigma$ называется сигнатурой алгебры.

Об обозначениях алгебр

Людям (мне в том числе) лень строго прописывать алгебру, явно указывая носитель и сигнатуру. Очень удобно обозначать носитель обычной заглавной буквой, а алгебру этой же буквой, но красивой.

Например, $\AAA$ — алгебра с носителем $A$ . Аналогично, фраза «алгебра $A$ » означает алгебру с носителем $A$ , а сигнатура этой алгебры ясна из контекста.

Запись $a \in \AAA$ означает, что $a \in A$ , то есть $a$ — элемент носителя алгебры $\AAA$ .

На носителе $\RR$ есть алгебра, сигнатура которой состоит из операций $+$ , $-$ , $\times$ , $\div$ , $(a, b) \mapsto a^b$ .

Другой пример. Выберем множество $X$ . На носителе $2^X$ можно задать алгебру, сигнатура которой состоит из операций $\union$ , $\sect$ , $\symdiff$ , $a \mapsto X \without a$ . При этом последняя операция дополнения является унарной.

Свойства операций

Некоторые часто встречаемые свойства операций имеют специальные названия.

Нейтральные элементы

Пусть $(A, \Sigma)$ — алгебра и $\circ \colon A \times A \to A$ — какая-то бинарная операция.

Левым нейтральным элементом называется элемент $\1_L \in A$ такой, что для любого элемента $a \in A$ выполнено

\1_L \circ a = a

Правым нейтральным элементом называется элемент $\1_R \in A$ такой, что для любого элемента $a \in A$ выполнено

a \circ \1_R = a

Нейтральным элементом называется одновременно и правый, и левый нейтральный. То есть такой элемент $\1 \in A$ , что для любого элемента $a \in A$ выполнено

\1 \circ a = a \circ \1 = a

Для операции умножения на $\RR$ нейтральным является элемент $1$ , а для сложения $0$ . При возведении в степень есть правый нейтральный элемент $1$ , ведь $a^1 = a$ , а левого нейтрального элемента нет.

Для коммутативных операций нет разницы между правым и левым нейтральным элементом.

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

Однако, если существуют только правые (или левые) нейтральные элементы, то их может быть сколько угодно.

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

Пусть $(A, \Sigma)$ — алгебра. Пусть $a, b, c \in A$ — любые элементы носителя алгебры.

Бинарная операция $\circ \colon A \times A \to A$ может иметь следующие свойства

Ассоциативность: $a \circ (b \circ c) = (a \circ b) \circ c$
Коммутативность: $a \circ b = b \circ a$
Идемпотентность: $a \circ a = a$

Две бинарные операции $\circ, \diamond \colon A \times A \to A$ могут обладать следующими свойствами

Дистрибутивность $\diamond$ по $\circ$ слева: $a \diamond (b \circ c) = (a \diamond b) \circ (a \diamond c)$
Дистрибутивность $\diamond$ по $\circ$ справа: $(b \circ c) \diamond a = (b \diamond a) \circ (c \diamond a)$
Дистрибутивность $\diamond$ по $\circ$ — выполняется и левая, и правая дистрибутивность.