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

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

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

$a\preccurlyeq b\iff \{\begin{array}{cc}a{\le }_{i}b& a\in A_i,b\in A_i\\ i\le j& a\in A_i,b\in A_j,i\ne j\end{array}$

Обозначение: $\sum _{i\in I}{A}_i$Шаблон:Sfn.

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

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

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

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

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

Кардинальная сумма двух непересекающихся упорядоченных множеств $(A_1,{\le }_1)$ и $(A_2,{\le }_2)$ определяется как упорядоченное множество $(A_1\cup A_2,\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\iff (a,b\in A_1\wedge a{\le }_{1}b)\vee (a,b\in A_2\wedge a{\le }_{2}b)$

Обозначение: $A_1+A_2$Шаблон:SfnШаблон:Sfn.

Кардинальная сумма попарно непересекающихся упорядоченных множеств $(A_1,{\le }_1),\dots ,(A_n,{\le }_n)$ определяется как упорядоченное множество $(A_1\cup \dots \cup A_n,\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\iff (a,b\in A_1\wedge a{\le }_{1}b)\vee \dots \vee (a,b\in A_n\wedge a{\le }_{n}b)$

Обозначение: $A_1+\dots +A_n$.

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

$a\preccurlyeq b\iff \mathrm{\exists }i\in I(a,b\in A_i\wedge a{\le }_{i}b)$

Обозначение: $\sum _{i\in I}{A}_i$.Шаблон:Sfn

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

Свойства:

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

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

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

Ординальная сумма двух непересекающихся упорядоченных множеств $(A_1,{\le }_1)$ и $(A_2,{\le }_2)$ определяется как упорядоченное множество $(A_1\cup A_2,\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\iff \{\begin{array}{cc}a{\le }_{i}b& a\in A_i,b\in A_i\\ i\le j& a\in A_i,b\in A_j,i\ne j\end{array}$

Обозначение: $A_1\oplus A_2$Шаблон:SfnШаблон:Sfn.

Ординальная сумма попарно непересекающихся упорядоченных множеств $(A_1,{\le }_1),\dots ,(A_n,{\le }_n)$ определяется как упорядоченное множество $(A_1\cup \dots \cup A_n,\preccurlyeq )$, где отношение $\preccurlyeq$ определяется следующим образом:

$a\preccurlyeq b\iff \{\begin{array}{cc}a{\le }_{i}b& a\in A_i,b\in A_i\\ i\le j& a\in A_i,b\in A_j,i\ne j\end{array}$

Обозначение: $A_1\oplus \dots \oplus A_n$.

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

$a\preccurlyeq b\iff \{\begin{array}{cc}a{\le }_{i}b& a\in A_i,b\in A_i\\ i\le j& a\in A_i,b\in A_j,i\ne j\end{array}$

Обозначение: $\sum _{i\in I}{A}_i$Шаблон:Sfn.

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

$1+\omega =\omega \ne \omega +1$Шаблон:Sfn

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

Свойства:

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

Литература

• Шаблон:Из
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга