Состав отношений - Composition of relations

в математика из бинарные отношения, то композиционные отношения это концепция формирования новых отношений р ; S из двух данных отношений р и S. Состав отношений называется относительное умножение^[1] в исчисление отношений. Композиция тогда относительный продукт^[2]:40 факторных отношений. Состав функций является частным случаем композиции отношений.

Слова дядя и тетя указывают на сложное отношение: чтобы человек был дядей, он должен быть братом родителя (или сестрой тети). В алгебраическая логика говорят, что отношение дяди ( xUz ) является составом отношений "является братом" ( xBy ) и «является родителем» ( yPz ).

${displaystyle U=BPquad equiv quad xByPziff xUz.}$

Начиная с Огастес Де Морган,^[3] традиционная форма рассуждения силлогизм был включен в реляционные логические выражения и их состав.^[4]

Определение

Если ${displaystyle Rsubseteq X imes Y}$ и ${displaystyle Ssubseteq Y imes Z}$ являются двумя бинарными отношениями, их композиция ${displaystyle R;S}$ это отношение

${displaystyle R;S={(x,z)in X imes Zmid exists yin Y:(x,y)in Rland (y,z)in S}.}$

Другими словами, ${displaystyle R;Ssubseteq X imes Z}$ определяется правилом, которое гласит ${displaystyle (x,z)in R;S}$ тогда и только тогда, когда есть элемент ${displaystyle yin Y}$ такой, что ${displaystyle x,R,y,S,z}$ (т.е. ${displaystyle (x,y)in R}$ и ${displaystyle (y,z)in S}$).^[5]:13

Варианты обозначений

Точка с запятой как инфиксная запись для построения отношений восходит к Эрнст Шредер учебник 1895 г.^[6] Гюнтер Шмидт возобновил использование точки с запятой, особенно в Реляционная математика (2011).^[2]:40[7] Использование точки с запятой совпадает с обозначением функциональной композиции, используемым (в основном компьютерными учеными) в теория категорий,^[8] а также обозначение динамического соединения в лингвистическом динамическая семантика.^[9]

Маленький круг ${displaystyle (Rcirc S)}$ использовался для инфиксной записи композиции отношений Джон М. Хауи в своих книгах учитывая полугруппы отношений.^[10] Однако маленький кружок широко используется для обозначения состав функций ${displaystyle g(f(x)) = (gcirc f)(x)}$ который переворачивает текстовая последовательность из последовательности операций. Маленький кружок использовался на вводных страницах Графики и отношения^[5]:18 пока он не был отброшен в пользу сопоставления (без инфиксной записи). Сопоставление ${displaystyle (RS)}$ обычно используется в алгебре для обозначения умножения, а также для обозначения относительного умножения.

Кроме того, при обозначении кружков можно использовать индексы. Некоторые авторы^[11] предпочитаю писать ${displaystyle circ _{l}}$ и ${displaystyle circ _{r}}$ явно, когда необходимо, в зависимости от того, какое отношение применяется первым: левое или правое. Еще одна разновидность информатики - это Обозначение Z: ${displaystyle circ }$ используется для обозначения традиционной (правой) композиции, но ⨾ (жирная открытая точка с запятой с кодовой точкой Unicode U + 2A3E) обозначает левую композицию.^[12][13]

Бинарные отношения ${displaystyle Rsubseteq X imes Y}$ иногда рассматриваются как морфизмы ${displaystyle Rcolon X o Y}$ в категория Rel который имеет наборы как объекты. В Rel, композиция морфизмов - это в точности композиция отношений, как определено выше. Категория Набор наборов является подкатегорией Rel с теми же объектами, но с меньшим количеством морфизмов.

Свойства

• Состав отношений ассоциативный: ${displaystyle R;(S;T) = (R;S);T.}$
• В обратное отношение из р ; S является (р ; S)^Т = S^Т ; р^Т. Это свойство делает набор всех бинарных отношений на множестве полугруппа с инволюцией.
• Состав (частичные) функции (т.е. функциональные отношения) снова (частичная) функция.
• Если р и S находятся инъективный, тогда р ; S инъективно, что, наоборот, влечет только инъективность р.
• Если р и S находятся сюръективный, тогда р ; S сюръективно, что, наоборот, подразумевает только сюръективность S.
• Множество бинарных отношений на множестве Икс (т.е. отношения из Икс к Икс) вместе с (левой или правой) композицией отношения образует моноид с нулем, где тождественное отображение на Икс это нейтральный элемент, а пустое множество - это нулевой элемент.

Состав в терминах матриц

Конечные бинарные отношения представлены логические матрицы. Элементы этих матриц равны нулю или единице, в зависимости от того, является ли представленное отношение ложным или истинным для строки и столбца, соответствующих сравниваемым объектам. Работа с такими матрицами включает булеву арифметику с 1 + 1 = 1 и 1 × 1 = 1. Запись в матричный продукт двух логических матриц будет 1, тогда только если умноженная строка и столбец имеют соответствующую единицу. Таким образом, логическая матрица композиции отношений может быть найдена путем вычисления матричного произведения матриц, представляющих факторы композиции. "Матрицы представляют собой метод для вычисление выводы, традиционно сделанные с помощью гипотетических силлогизмов и соритов ».^[14]

Гетерогенные отношения

Основная статья: Гетерогенное отношение

Рассмотрим неоднородное отношение р ⊆ А × B. Затем, используя композицию отношения р с этими разговаривать р^Т, существуют однородные отношения R R^Т (на А) и р^Т р (на B).

Если ∀Икс ∈ А ∃y ∈ B xRy (р это полное отношение ), то ∀Икс xRR^ТИкс так что R R^Т это рефлексивное отношение или я ⊆ R R^Т где I - тождественное отношение {ИксяИкс : Икс ∈ А}. Аналогично, если р это сюръективное отношение тогда

р^Т р ⊇ I = {ИксяИкс : Икс ∈ B}. В таком случае р ⊆ R R^Т р. Противоположное включение имеет место для дифункциональный связь.

Сочинение ${displaystyle {ar {R}}^{T}R}$ используется для различения отношений типа Феррера, удовлетворяющих ${displaystyle R{ar {R}}^{T}R=R.}$

пример

Состав р с участием р^Т дает связь с этим графиком, Швейцария связана с другими странами (петли не показаны).

Позволять А = {Франция, Германия, Италия, Швейцария} и B = {Французский, немецкий, итальянский} с отношением р данный aRb когда б это Национальный язык из а. В логическая матрица для р дан кем-то

${displaystyle {egin{pmatrix}1&0&0�&1&0�&0&11&1&1end{pmatrix}}.}$ С использованием обратное отношение р^Т, можно ответить на два вопроса: "Есть ли переводчик?" есть ответ ${displaystyle R^{T}R=B imes B,}$ то универсальное отношение на B. Международный вопрос: «Говорит ли он на моем языке?» отвечает ${displaystyle RR^{T}={egin{pmatrix}1&0&0&1�&1&0&1�&0&1&11&1&1&1end{pmatrix}}.}$ Эта симметричная матрица, представляющая однородное отношение на А, связан с звездный график S₃ дополненный петля на каждом узле.

Правила Шредера

Для данного набора V, собрание всех бинарные отношения на V образует Логическая решетка заказан включение (⊆). Напомним, что дополнение отменяет включение:${displaystyle Asubset Bimplies B^{complement }subseteq A^{complement }.}$ в исчисление отношений^[15] обычно дополняют набор чертой сверху: ${displaystyle {ar {A}}=A^{complement }.}$

Если S является бинарным отношением, пусть ${displaystyle S^{T}}$ представляют обратное отношение, также называемый транспонировать. Тогда правила Шредера таковы:

${displaystyle QRsubseteq Squad equiv quad Q^{T}{ar {S}}subseteq {ar {R}}quad equiv quad {ar {S}}R^{T}subseteq {ar {Q}}.}$

На словах одна эквивалентность может быть получена из другой: выберите первый или второй фактор и переставьте его; затем дополните два других отношения и переставьте их.^[5]:15–19

Хотя это преобразование включения композиции отношений было подробно описано Эрнст Шредер, по факту Огастес Де Морган впервые сформулировал преобразование как теорему K в 1860 году.^[4] Он написал

${displaystyle LMsubseteq Nimplies {ar {N}}M^{T}subseteq {ar {L}}.}$^[16]

С помощью правил Шредера и дополнения можно найти неизвестное отношение Икс в отношении включений, таких как

${displaystyle RXsubseteq Squad { ext{and}}quad XRsubseteq S.}$

Например, по правилу Шредера ${displaystyle RXsubseteq Simplies R^{T}{ar {S}}subseteq {ar {X}},}$ и дополнение дает ${displaystyle Xsubseteq {overline {R^{T}{ar {S}}}},}$ который называется левая невязка S на R .

Коэффициенты

Подобно тому, как композиция отношений представляет собой тип умножения, в результате которого получается продукт, некоторые композиции сравниваются с делением и производят частные. Здесь представлены три частных: левая невязка, правая невязка и симметричное частное. Левый остаток двух отношений определяется исходя из предположения, что они имеют один и тот же домен (источник), а правый остаток предполагает один и тот же кодомен (диапазон, цель). Симметричное частное предполагает, что два отношения разделяют домен и домен.

Определения:

• Левый остаток: ${displaystyle Aackslash B = {overline {A^{T}{ar {B}}}}}$
• Правый остаток: ${displaystyle D/C = {overline {{ar {D}}C^{T}}}}$
• Симметричное частное: ${displaystyle operatorname {syq} (E,F)={overline {E^{T}{ar {F}}}}cap {overline {{ar {E}}^{T}F}}}$

Используя правила Шредера, ТОПОР ⊆ B эквивалентно Икс ⊆ А${displaystyle ackslash }$B. Таким образом, левая невязка - это наибольшее отношение, удовлетворяющее ТОПОР ⊆ B. Аналогично включение YC ⊆ D эквивалентно Y ⊆ D/C, а правая невязка - наибольшее отношение, удовлетворяющее YC ⊆ D.^[2]:43–6

Присоединиться: другая форма композиции

Оператор вилки (<) был введен для объединения двух отношений c: ЧАС → А и d: ЧАС → B в c(<)d: ЧАС → А × B.Строительство зависит от проекций. а: А × B → А и б: А × B → B, понимаемые как отношения, означающие, что существуют обратные отношения а^Т и б^Т. Тогда вилка из c и d дан кем-то

${displaystyle c(<)d := c;a^{T}cap d;b^{T}.}$^[17]

Еще одна форма построения отношений, относящаяся к общим п-местные отношения для п ≥ 2, является присоединиться операция по реляционная алгебра. Обычная композиция двух бинарных отношений, как определено здесь, может быть получена путем их соединения, ведущего к тернарному отношению, за которым следует проекция, удаляющая средний компонент. Например, в языке запросов SQL есть операция Присоединиться (SQL).

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

• Демоническая композиция
• Друг друга

Заметки

1. Бьярни Йонссен (1984) "Максимальные алгебры бинарных отношений", в Вклад в теорию групп, К. Редактор Appel Американское математическое общество ISBN  978-0-8218-5035-0
2. Гюнтер Шмидт (2011) Реляционная математика, Энциклопедия математики и ее приложений, т. 132, Издательство Кембриджского университета ISBN  978-0-521-76268-7
3. А. Де Морган (1860) "О силлогизме: IV и о логике отношений"
4. Дэниел Д. Меррилл (1990) Огастес де Морган и логика отношений, стр. 121, Kluwer Academic ISBN  9789400920477
5. Гюнтер Шмидт И Томас Стрёляйн (1993) Отношения и графики, Книги Springer
6. Эрнст Шредер (1895) Алгебра и логика относительного
7. Пол Тейлор (1999). Практические основы математики. Издательство Кембриджского университета. п. 24. ISBN  978-0-521-63107-5. Бесплатная HTML-версия книги доступна по адресу http://www.cs.man.ac.uk/~pt/Practical_Foundations/
8. Майкл Барр и Чарльз Уэллс (1998) Категория Теория для компьютерных ученых В архиве 2016-03-04 в Wayback Machine, стр. 6, из Университет Макгилла
9. Рик Ноувен и другие (2016) Динамическая семантика §2.2, из Стэнфордская энциклопедия философии
10. Джон М. Хауи (1995) Основы теории полугрупп, стр. 16, Монография LMS № 12, Clarendon Press ISBN  0-19-851194-9
11. Килп, Кнауэр и Михалев, стр. 7
12. ISO / IEC 13568: 2002 (E), стр. 23
13. Символ Юникода: реляционная композиция обозначений Z из FileFormat.info
14. Ирвинг Копиловиш (Декабрь 1948 г.) «Матричное развитие исчисления отношений», Журнал символической логики 13(4): 193–203 Ссылка Jstor, цитата со страницы 203
15. Вон Пратт Истоки исчисления отношений, от Стэндфордский Университет
16. Де Морган указал противоположное строчными буквами, преобразование как M⁻¹, и включение с)), поэтому его обозначения были ${displaystyle nM^{-1})) l.}$
17. Гюнтер Шмидт и Майкл Винтер (2018): Реляционная топология, стр. 26, Конспект лекций по математике т. 2208, г. Книги Springer, ISBN  978-3-319-74451-3

использованная литература

• М. Килп, У. Кнауэр, А.В. Михалев (2000) Моноиды, акты и категории с приложениями к сплетенным изделиям и графам, De Gruyter Expositions in Mathematics vol. 29, Вальтер де Грюйтер,ISBN  3-11-015248-7.