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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

${\displaystyle 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)}$

Обозначение: ${\displaystyle A_{1}+A_{2}}$^[5][9].

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

${\displaystyle 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)}$

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

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

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

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

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

Свойства:

1. ${\displaystyle (A+B)+C=A+(B+C)}$ (ассоциативность);
2. ${\displaystyle A+B=B+C}$ (коммутативность);
3. ${\displaystyle |A+B|=|A|+|B|}$^[11]

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

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

${\displaystyle 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}}}$

Обозначение: ${\displaystyle A_{1}\oplus A_{2}}$^[8][9].

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

${\displaystyle 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}}}$

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

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

${\displaystyle 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}}}$

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

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

${\displaystyle 1+\omega =\omega \neq \omega +1}$^[6]

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

Свойства:

1. ${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$ (ассоциативность);
2. ${\displaystyle |A\oplus B|=|A|+|B|}$^[12]

• Упорядоченная сумма — статья из Математической энциклопедии. Т. С. Фофанова
• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа (рус.). — Москва: Наука, 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.