Упорядоченная сумма

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

Упорядоченная сумма семейства попарно непересекающихся частично упорядоченных множеств $\{(A_{i},\leq )\}_{i\in I}$, индексированное некоторым частично упорядоченным множеством $(I,\leq )$, определяется как частично упорядоченное множество $\left(\bigcup _{i\in I}A_{i},\preccurlyeq \right)$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow {\begin{cases}a\leq _{i}b&a\in A_{i},b\in A_{i}\\i\leq j&a\in A_{i},b\in A_{j},i\neq j\end{cases}}$

Обозначение: $\sum _{i\in I}A_{i}$.

Упорядоченную сумму можно рассмотреть для неупорядоченного множества индексов; тогда считается, что множество индексов тривиально упорядочено. Упорядоченную сумму можно рассмотреть и для семейства множеств, в котором некоторые множества пересекаются; тогда обычное объединение в определении нужно заменить на дизъюнктное.

Операция упорядоченной суммы индуцирует операцию на порядковые типы (требуется аксиома выбора); соответствующая операция называется суммой порядковых типов и обозначается аналогично: $\sum _{i\in I}\alpha _{i}$.

Различают два важных частных случая упорядоченной суммы: кардинальная сумма (множество индексов упорядочено тривиально) и ординальная сумма (множество индексов упорядочено линейно). В отличие от общей упорядоченной суммы, которую нельзя рассмотреть как $n$-арную операцию (потому что дополнительно нужно было бы задать, какой из порядков на индексном множестве $\{1,\ldots ,n\}$ используется для суммирования), кардинальные и ординальные суммы можно (поскольку тривиальный порядок единственен, а на множестве $\{1,\ldots ,n\}$ есть естественный линейный порядок, и все остальные линейные порядки ему изоморфны). Для $n$-арной кардинальной суммы используется обозначение $A_{1}+\ldots +A_{n}$, для $n$-арной ординальной суммы может использоваться как обозначение $A_{1}\oplus \ldots \oplus A_{n}$, так и обозначение $A_{1}+\ldots +A_{n}$. Чтобы не путаться, в настоящей статье обозначение через $+$ будет использоваться только для кардинальных сумм.

Некоторые авторы могут использовать термин упорядоченная сумма и для $n$-арной операции; в таких случаях обычно имеется в виду ординальная сумма. Как $n$-арные операции кардинальные и ординальные суммы индуцируют соответствующие операции на порядковые типы уже без зависимости от аксиомы выбора. Для порядковых типов $n$-арная операция сложения определена, и определяется она как операция, индуцированная ординальной суммой. При этом обозначается эта операция обычным знаком $+$, а не $\oplus$. Таким образом, сумма порядковых типов для произвольного семейства индуцируется общей упорядоченной суммой, а для конечного числа аргументов — ординальной суммой. Определение суммы на порядковых типах более соответствует терминологии, при которой $n$-арные ординальные суммы обозначаются через $+$ и называются упорядоченными суммами.

Кардинальная сумма

Кардинальная сумма двух непересекающихся упорядоченных множеств $(A_{1},\leq _{1})$ и $(A_{2},\leq _{2})$ определяется как упорядоченное множество $(A_{1}\cup A_{2},\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow (a,b\in A_{1}\land a\leq _{1}b)\lor (a,b\in A_{2}\land a\leq _{2}b)$

Обозначение: $A_{1}+A_{2}$.

Кардинальная сумма попарно непересекающихся упорядоченных множеств $(A_{1},\leq _{1}),\ldots ,(A_{n},\leq _{n})$ определяется как упорядоченное множество $(A_{1}\cup \ldots \cup A_{n},\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow (a,b\in A_{1}\land a\leq _{1}b)\lor \ldots \lor (a,b\in A_{n}\land a\leq _{n}b)$

Обозначение: $A_{1}+\ldots +A_{n}$.

Пусть $I$ — произвольное множество, $\{A_{i}\}_{i\in I}$ — семейство попарно непересекающихся упорядоченных множеств, индексированное множеством $I$. Тогда кардинальная сумма этого семейства определяется как упорядоченное множество $\left(\bigcup _{i\in I}A_{i},\preccurlyeq \right)$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow \exists i\in I\ (a,b\in A_{i}\land a\leq _{i}b)$

Обозначение: $\sum _{i\in I}A_{i}$.

Данное определение является частным случаем общего определения упорядоченной суммы, если на $I$ задать тривиальный порядок. Поэтому упорядоченную сумму для неупорядоченного множества индексов определяют как обычную упорядоченную сумму для множества $I$ с тривиальным порядком. Кардинальную сумму можно понимать как упорядоченную сумму с тривиально упорядоченным множеством индексов, так и как упорядоченную сумму с неупорядоченным множеством индексов. $n$-арные кардинальные суммы соответствуют упорядоченным суммам с конечными множествами индексов с тривиальным порядком. $n$-арные кардинальные суммы не зависят от порядка слагаемых.

Свойства:

1. $(A+B)+C=A+(B+C)$ (ассоциативность);
2. $A+B=B+C$ (коммутативность);
3. $|A+B|=|A|+|B|$

Кардинальная сумма может быть определена на случай пересекающихся слагаемых, если в определении заменить обычное объединение на дизъюнктное.

Ординальная сумма

Ординальная сумма двух непересекающихся упорядоченных множеств $(A_{1},\leq _{1})$ и $(A_{2},\leq _{2})$ определяется как упорядоченное множество $(A_{1}\cup A_{2},\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow {\begin{cases}a\leq _{i}b&a\in A_{i},b\in A_{i}\\i\leq j&a\in A_{i},b\in A_{j},i\neq j\end{cases}}$

Обозначение: $A_{1}\oplus A_{2}$.

Ординальная сумма попарно непересекающихся упорядоченных множеств $(A_{1},\leq _{1}),\ldots ,(A_{n},\leq _{n})$ определяется как упорядоченное множество $(A_{1}\cup \ldots \cup A_{n},\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow {\begin{cases}a\leq _{i}b&a\in A_{i},b\in A_{i}\\i\leq j&a\in A_{i},b\in A_{j},i\neq j\end{cases}}$

Обозначение: $A_{1}\oplus \ldots \oplus A_{n}$.

Пусть $(I,\leq )$ — линейно упорядоченное множество, $\{A_{i}\}_{i\in I}$ — семейство попарно непересекающихся упорядоченных множеств, индексированное множеством $I$. Тогда ординальная сумма этого семейства определяется как упорядоченное множество $\left(\bigcup _{i\in I}A_{i},\preccurlyeq \right)$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\Leftrightarrow {\begin{cases}a\leq _{i}b&a\in A_{i},b\in A_{i}\\i\leq j&a\in A_{i},b\in A_{j},i\neq j\end{cases}}$

Обозначение: $\sum _{i\in I}A_{i}$.

$n$-арные ординальным суммы соответствуют упорядоченным суммам с множеством $\{1,\ldots ,n\}$ в качестве множества индексов и стандартным порядком на нём. $n$-арные ординальные суммы зависят от порядка слагаемых: это можно видеть на примере известного неравенства арифметики ординалов:

$1+\omega =\omega \neq \omega +1$

Ординальная сумма линейно упорядоченных множеств — линейно упорядоченное множество.

Свойства:

1. $(A\oplus B)\oplus C=A\oplus (B\oplus C)$ (ассоциативность);
2. $|A\oplus B|=|A|+|B|$

Литература

• Упорядоченная сумма — статья из Математической энциклопедии. Т. С. Фофанова
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа (рус.). — Москва: Наука, 1976. — 543 с.
• Скорняков Л. А. Элементы теории структур (рус.). — Москва: Наука, 1970. — 148 с.
• Just W., Weese M. Discovering Modern Set Theory. I: The Basics (англ.). — American Mathematical Societ, 1996. — 210 p.
• Биркгоф Г. Теория решёток = Lattice Theory (рус.). — Москва: Наука, 1984. — 568 с.
• Neggers L., Kim H. S. Basic Posets (англ.). — World Scientific, 1998. — ISBN 9789810235895.
• Harzheim E. Ordered Sets (англ.). — Springer, 2005. — ISBN 9789810235895.