Несвязный союз - Disjoint union

Эта статья про работу с наборами. Чтобы узнать о значении этого термина в информатике, см. Tagged union. Для работы с графиками см. несвязное объединение графов.

Не путать с Дизъюнктивный союз.

В математика, а несвязный союз (или же размеченный союз) семьи ${\displaystyle (A_{i}\colon i\in I)}$ наборов это набор ${\displaystyle A=\bigsqcup _{i\in I}A_{i},}$ с инъективная функция каждого ${\displaystyle A_{i}}$ в А, так что союз изображений этих инъекций образуют раздел из А (то есть каждый элемент А принадлежит ровно одному из этих изображений).

Непересекающийся союз семьи попарно непересекающиеся множества это их совокупное объединение.

С точки зрения теория категорий, несвязное объединение - это сопродукт из категория наборов.

Таким образом, дизъюнктное объединение определяется вплоть до биекция.

Стандартный способ построения дизъюнктного объединения - определить А как набор заказанные пары (Икс, я) такой, что ${\displaystyle x\in A_{i},}$ и инъективные функции ${\displaystyle A_{i}\to A}$ к ${\displaystyle x\mapsto (x,i).}$

Пример

Рассмотрим множества ${\displaystyle A_{0}=\{5,6,7\}}$ и ${\displaystyle A_{1}=\{5,6\}}$. Мы можем индексировать элементы набора в соответствии с источником набора, формируя связанные наборы

${\displaystyle {\begin{aligned}A_{0}^{*}&=\{(5,0),(6,0),(7,0)\}\\A_{1}^{*}&=\{(5,1),(6,1)\},\end{aligned}}}$

где второй элемент в каждой паре соответствует нижнему индексу исходного набора (например, ${\displaystyle 0}$ в ${\displaystyle (5,0)}$ соответствует нижнему индексу в ${\displaystyle A_{0}}$, так далее.). Несвязный союз ${\displaystyle A_{0}\sqcup A_{1}}$ затем можно рассчитать следующим образом:

${\displaystyle A_{0}\sqcup A_{1}=A_{0}^{*}\cup A_{1}^{*}=\{(5,0),(6,0),(7,0),(5,1),(6,1)\}.}$

Определение теории множеств

Формально пусть {А_я : я ∈ я} быть семейство наборов проиндексировано я. В несвязный союз из этой семьи набор

${\displaystyle \bigsqcup _{i\in I}A_{i}=\bigcup _{i\in I}\{(x,i):x\in A_{i}\}.}$

Элементами дизъюнктного объединения являются заказанные пары (Икс, я). Здесь я служит вспомогательным индексом, указывающим, какие А_я элемент Икс пришли из.

Каждый из наборов А_я канонически изоморфно множеству

${\displaystyle A_{i}^{*}=\{(x,i):x\in A_{i}\}.}$

Благодаря этому изоморфизму можно считать, что А_я канонически вложено в дизъюнктное объединение. я ≠ j, наборы А_я* и А_j* не пересекаются, даже если множества А_я и А_j не.

В крайнем случае, когда каждый из А_я равно некоторому фиксированному множеству А для каждого я ∈ я, несвязное объединение - это Декартово произведение из А и я:

${\displaystyle \bigsqcup _{i\in I}A_{i}=A\times I.}$

Иногда можно увидеть обозначения

${\displaystyle \sum _{i\in I}A_{i}}$

для несвязного объединения семейства множеств, или обозначение А + B для несвязного объединения двух множеств. Это обозначение должно наводить на мысль о том, что мощность дизъюнктного союза сумма мощности членов семьи. Сравните это с обозначением для Декартово произведение семейства наборов.

Непересекающиеся союзы также иногда пишутся ${\displaystyle \biguplus _{i\in I}A_{i}}$ или же ${\displaystyle \ \cdot \!\!\!\!\!\bigcup _{i\in I}A_{i}}$.

На языке теория категорий, несвязное объединение - это сопродукт в категория наборов. Следовательно, он удовлетворяет ассоциированному универсальная собственность. Это также означает, что непересекающееся объединение является категоричный дуальный из Декартово произведение строительство. Видеть сопродукт Больше подробностей.

Для многих целей конкретный выбор вспомогательного индекса не важен, а в упрощении злоупотребление обозначениями индексированное семейство можно рассматривать просто как набор наборов. В этом случае ${\displaystyle A_{i}^{*}}$ называется копировать из ${\displaystyle A_{i}}$ и обозначение ${\displaystyle {\underset {A\in C}{\,\,\bigcup \nolimits ^{*}\!}}A}$ иногда используется.

Точка зрения теории категорий

В теория категорий дизъюнктное объединение определяется как сопродукт в категории наборов.

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

Этот категоричный аспект несвязного союза объясняет, почему ${\displaystyle \coprod }$ часто используется вместо ${\displaystyle \bigsqcup }$, чтобы обозначить сопродукт.

Смотрите также

• Копродукт
• Несвязное объединение (топология)
• Непересекающееся объединение графов
• Перегородка набора
• Тип суммы
• Tagged union
• Союз (информатика)

Рекомендации

• Ланг, Серж (2004), Алгебра, Тексты для выпускников по математике, 211 (Исправленное четвертое издание, исправленное третье издание), Нью-Йорк: Springer-Verlag, p. 60, ISBN  978-0-387-95385-4
• Вайсштейн, Эрик В. «Несвязный союз». MathWorld.