Гетерогенное отношение - Heterogeneous relation

В математика, а гетерогенное отношение это бинарное отношение, а подмножество из Декартово произведение А × B, куда А и B - разные множества.^[1] Префикс гетеро происходит от греческого ἕτερος (гетеросексуалы, «другой, другой, другой»).

Гетерогенные отношения получили название прямоугольное отношение,^[2] предполагая, что он не имеет квадратной симметрии однородное отношение на множестве куда А = B. Комментируя развитие бинарных отношений за пределами однородных отношений, исследователи писали: «... возникла разновидность теории, которая с самого начала рассматривает отношения как неоднородный или же прямоугольный, т. е. как отношения, которые обычно являются отношениями между различными наборами ".^[3]

События в алгебраическая логика облегчили использование бинарных отношений. В исчисление отношений включает алгебра множеств, продлен на состав отношений и использование обратные отношения. Включение р ⊆ S, означающий, что aRb подразумевает aSb, устанавливает сцену в решетка отношений. Но с тех пор ${\displaystyle P\subseteq Q\equiv (P\cap {\bar {Q}}=\varnothing )\equiv (P\cap Q=P),}$ символ включения лишний. Тем не менее, составление отношений и манипулирование операторами согласно Правила Шредера, обеспечивает исчисление для работы в набор мощности из А × B.

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

Примеры

Океаны и континенты

Океан граничит с континентом

	NA	SA	AF	Европа	В КАЧЕСТВЕ	OC	AA
Индийский	0	0	1	0	1	1	1
Арктический	1	0	0	1	1	0	0
Атлантический	1	1	1	1	0	0	1
Тихий океан	1	1	0	0	1	1	1

1) Пусть А = {Индийская, Арктическая, Атлантическая, Тихоокеанская}, океаны земного шара, и B = {NA, SA, AF, EU, AS, OC, AA}, континенты. Позволять aRb представляют этот океан а границы континента б. Тогда логическая матрица для этого отношения:

${\displaystyle R={\begin{pmatrix}0&0&1&0&1&1&1\\1&0&0&1&1&0&0\\1&1&1&1&0&0&1\\1&1&0&0&1&1&1\end{pmatrix}}.}$

Связность планеты Земля можно увидеть через R R^Т и р^Т р, причем первое является соотношением 4 × 4 на А, которое является универсальным соотношением (А × А или логическая матрица всех единиц). Это универсальное отношение отражает тот факт, что каждый океан отделен от других не более чем одним континентом. С другой стороны, р^Т р это отношение на B × B который терпит неудачу чтобы быть универсальным, потому что по крайней мере два океана должны быть пересечены для плавания из Европа к Океания.

2) Визуализация отношений опирается на теория графов: Для отношений на множестве (однородных отношений) a ориентированный граф иллюстрирует отношение и график симметричное отношение. Для гетерогенных отношений a гиперграф имеет ребра, возможно, с более чем двумя узлами, и может быть проиллюстрировано двудольный граф.

Так же, как клика является неотъемлемой частью отношений на множестве, поэтому биклики используются для описания разнородных отношений; действительно, это «концепции», которые порождают решетку, связанную с отношением.

Различные т оси представляют время для наблюдателей в движении, соответствующие Икс оси - их линии одновременности

3) Гиперболическая ортогональность: Время и пространство - разные категории, а временные свойства отделены от пространственных свойств. Идея одновременные события просто в абсолютное время и пространство так как каждый раз т определяет одновременное гиперплоскость в этой космологии. Герман Минковский изменил это, когда сформулировал понятие относительная одновременность, который существует, когда пространственные события "нормальны" времени, характеризуемого скоростью. Он использовал неопределенное внутреннее произведение и указал, что вектор времени нормален к пространственному вектору, когда это произведение равно нулю. Неопределенный внутренний продукт в композиционная алгебра дан кем-то

${\displaystyle <x,z>\ =\ x{\bar {z}}+{\bar {x}}z}$ где черта сверху означает сопряжение.

Как связь между некоторыми временными событиями и некоторыми пространственными событиями, гиперболическая ортогональность (как найдено в разделенные комплексные числа ) - неоднородное отношение.^[4]

4) А геометрическая конфигурация можно рассматривать как отношение между его точками и его линиями. Отношение выражается как заболеваемость. Включены конечные и бесконечные проективные и аффинные плоскости. Якоб Штайнер пионер каталогизации конфигураций с Системы Штайнера S (т, к, п), которые имеют набор из n элементов S и набор k-элементных подмножеств, называемых блоки, такое что подмножество с т элементы находятся всего в одном блоке. Эти структуры падения были обобщены с блочные конструкции. В матрица инцидентности используемый в этих геометрических контекстах соответствует логической матрице, обычно используемой с бинарными отношениями.

Структура инцидентности - тройная D = (V, B, я) куда V и B - любые два непересекающихся множества и я это бинарное отношение между V и B, т.е. я ⊆ V × B. Элементы V будет называться точки, те из B блоки и те из Я флаги.^[5]

Решетка индуцированных концепций

Гетерогенные отношения были описаны через их индуцированные концептуальные решетки: А концепция C ⊂ р удовлетворяет двум свойствам: (1) логическая матрица C это внешний продукт логических векторов

${\displaystyle C_{ij}\ =\ u_{i}v_{j},\quad u,v}$ логические векторы. (2) C максимально, не содержится ни в каком другом внешнем продукте. Таким образом C описывается как неувеличиваемый прямоугольник.

Для данного отношения р: Икс → Yмножество понятий, расширенное их объединениями и встречами, образует «индуцированную решетку понятий», включающую ${\displaystyle \sqsubseteq }$ формирование Предварительный заказ.

В Теорема МакНейла о пополнении (1937) (что любой частичный порядок может быть встроен в полная решетка ) цитируется в обзорной статье 2013 года «Декомпозиция отношений на решетках понятий».^[6] Разложение

${\displaystyle R\ =\ f\ E\ g^{T},}$ куда ж и грамм находятся функции, называется сопоставления или лево-тотальные, однолистные отношения в этом контексте. Решетка индуцированных понятий изоморфна разрезному пополнению частичного порядка E которое принадлежит минимальному разложению (f, g, E) отношения р."

Ниже рассматриваются частные случаи: E общий заказ соответствует типу Феррерса, а E идентичность соответствует дифункциональному, обобщению отношение эквивалентности по набору.

Отношения могут быть ранжированы по Ранг Шайна который подсчитывает количество понятий, необходимых для охвата отношения.^[7] Структурный анализ отношений с концепциями дает подход к сбор данных.^[8]

Особые отношения

• Предложение: Если р это полное отношение и R^Т это его транспонирование, тогда ${\displaystyle I\subseteq R^{T}R}$ где я м × м отношения идентичности.
• Предложение: Если р это сюръективное отношение, тогда ${\displaystyle I\subseteq RR^{T}}$ где я п × п отношения идентичности.

Дифункциональный

Среди однородных отношений на множестве отношения эквивалентности отличаются своей способностью разбивать множество на части. Идея гетерогенных отношений состоит в том, чтобы разделить объекты с помощью различения атрибутов. Один из способов сделать это - использовать промежуточный набор Z = {х, у, г, ...} из индикаторы. Отношение разделения р = F G^Т это состав отношений с помощью однозначный связи F ⊆ А × Z и грамм ⊆ B × Z.

В логическая матрица такого отношения р может быть преобразован в блочная матрица с блоками единиц по диагонали. С точки зрения исчисления отношений, в 1950 г. Жак Риге показал, что такие отношения удовлетворяют включению

${\displaystyle R\ R^{T}\ R\ \subseteq \ R.}$^[9]

Он назвал эти отношения дифункциональный так как композиция F G^Т включает однозначные отношения, обычно называемые функции.

Используя обозначение {у: xRy} = xR, дифункциональное отношение также можно охарактеризовать как отношение р такой, что где бы Икс₁р и Икс₂р имеют непустое пересечение, то эти два множества совпадают; формально Икс₁р ∩ Икс₂р ≠ ∅ подразумевает Икс₁р = Икс₂р.^[10]

В 1997 году исследователи обнаружили «полезность бинарной декомпозиции на основе дифункциональных зависимостей в база данных управление."^[11] Более того, дифункциональные отношения имеют фундаментальное значение при изучении бизимуляции.^[12]

В контексте однородных отношений a отношение частичной эквивалентности дифункциональна.

В теория автоматов, период, термин прямоугольное отношение также использовался для обозначения дифункционального отношения. Эта терминология напоминает тот факт, что, когда они представлены в виде логической матрицы, столбцы и строки дифункционального отношения могут быть расположены как блочно-диагональная матрица с прямоугольными блоками истинности на (асимметричной) главной диагонали.^[13]

Тип Феррера

А строгий порядок на множестве - однородное отношение, возникающее в теория порядка В 1951 г. Жак Риге принял приказ раздел целого числа, называемого Диаграмма Феррерса, распространить упорядочение на гетерогенные отношения.^[14]

Соответствующая логическая матрица гетерогенного отношения имеет строки, заканчивающиеся невозрастающей последовательностью единиц. Таким образом, точки диаграммы Феррера заменяются на точки и выравниваются по правому краю матрицы.

Алгебраическое утверждение, необходимое для отношения типа Феррерса R, имеет вид

${\displaystyle R{\bar {R}}^{T}R\subseteq R.}$

Если какое-либо из отношений ${\displaystyle R,\ {\bar {R}},\ R^{T}}$ относится к типу Феррерса, то все они.^[1]

Контакт

Предполагать B это набор мощности из А, набор всех подмножества из А. Затем контактные отношения грамм удовлетворяет трем свойствам: (1) ∀ Икс в А, Y = {Икс} подразумевает х г Y. (2) Y ⊆ Z и х г Y подразумевает х г Z. (3) ∀ у в Y, г г Z и х г Y подразумевает х г Z. В установить членство отношение, ε = "является элементом", удовлетворяет этим свойствам, поэтому ε является отношением контакта. Понятие общего контактного отношения было введено Георг Ауманн в его книге Kontakt-Relationen (1970).^[15]

С точки зрения исчисления отношений, достаточные условия для отношения контакта включают

${\displaystyle C^{T}{\bar {C}}\ \subseteq \ \ni {\bar {C}}\ \ \equiv \ C\ {\overline {\ni {\bar {C}}}}\ \subseteq \ C,}$ куда ${\displaystyle \ni }$ является обратным к множеству принадлежностей (∈).^[16]:280

Предзаказ R R

Каждое отношение р генерирует Предварительный заказ R R какой левый остаток.^[17] Что касается обратного и дополнительного, ${\displaystyle R\backslash R\ \equiv \ {\overline {R^{T}{\bar {R}}}}.}$ Формируя диагональ ${\displaystyle R^{T}{\bar {R}}}$, соответствующая строка р^Т и столбец ${\displaystyle {\bar {R}}}$ будут иметь противоположные логические значения, поэтому на диагонали все нули. потом

${\displaystyle R^{T}{\bar {R}}\subseteq {\bar {I}}\ \implies \ I\subseteq {\overline {R^{T}{\bar {R}}}}\ =\ R\backslash R,}$ так что R R это рефлексивное отношение.

Показывать транзитивность, требуется, чтобы (R R)(R R) ⊂ R R. Напомним, что Икс = R R - наибольшее отношение такое, что R X ⊂ р. потом

${\displaystyle R(R\backslash R)\subseteq R}$

${\displaystyle R(R\backslash R)(R\backslash R)\subseteq R}$ (повторение)

${\displaystyle \equiv R^{T}{\bar {R}}\subseteq {\overline {(R\backslash R)(R\backslash R)}}}$ (Правило Шредера)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq {\overline {R^{T}{\bar {R}}}}}$ (дополнение)

${\displaystyle \equiv (R\backslash R)(R\backslash R)\subseteq R\backslash R.}$ (определение)

В включение соотношение Ω на набор мощности из U можно получить таким образом из отношение членства ∈ на подмножествах U:

${\displaystyle \Omega \ =\ {\overline {\ni {\bar {\in }}}}\ =\ \in \backslash \in .}$^[16]:283

Граница отношений

Учитывая отношение р, вложенное отношение называется его челка определяется как

${\displaystyle \operatorname {fringe} (R)=R\cap {\overline {R{\bar {R}}^{T}R}}.}$

Когда р является отношением частичной идентичности, дифункциональным или блочно-диагональным отношением, тогда бахрома (р) = р. В противном случае оператор fringe выбирает граничное подотношение, описанное в терминах его логической матрицы: fringe (р) - боковая диагональ, если р верхний правый треугольник линейный порядок или же строгий порядок. Челка(р) является блочной полосой, если R иррефлексивно (${\displaystyle R\subseteq {\bar {I}}}$) или верхний правый блок треугольный. Челка(р) - последовательность граничных прямоугольников, когда р относится к типу Феррерса.

С другой стороны, Fringe (р) = ∅, когда р это плотный, линейный, строгий порядок.^[16]

Математические кучи

Основная статья: Куча (математика)

Учитывая два набора А и B, множество бинарных отношений между ними ${\displaystyle {\mathcal {B}}(A,B)}$ может быть оснащен тернарная операция ${\displaystyle [a,\ b,\ c]\ =\ ab^{T}c}$ куда б^Т обозначает обратное отношение из б. В 1953 г. Виктор Вагнер использовал свойства этой тернарной операции для определения полукучей, куч и обобщенных куч.^[18][19] Контраст гетерогенных и однородных отношений подчеркивается этими определениями:

В работах Вагнера есть приятная симметрия между кучей, полукучками и обобщенными кучами, с одной стороны, и группами, полугруппами и обобщенными группами, с другой. По сути, различные типы полукучей появляются всякий раз, когда мы рассматриваем бинарные отношения (и частичные отображения один-один) между разные наборы А и B, а различные типы полугрупп возникают в случае, когда А = B.^[20]

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

• Категория отношений
• Аллегория (теория категорий)

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

1. Шмидт, Гюнтер; Стрёляйн, Томас (2012). Отношения и графы: дискретная математика для компьютерных ученых. Springer Science & Business Media. п. 77. ISBN  978-3-642-77968-8.
2. Майкл Винтер (2007). Категории Гогена: категориальный подход к L-нечетким отношениям. Springer. стр. x – xi. ISBN  978-1-4020-6164-6.
3. Г. Шмидт, Клаудиа Халтенспергер и Майкл Винтер (1997) «Алгебра гетерогенных отношений», глава 3 (страницы 37–53) в Реляционные методы в информатике, Достижения в области компьютерных наук, Книги Springer ISBN  3-211-82971-7
4. Относительная одновременность в Викиучебнике
5. Бет, Томас; Юнгникель, Дитер; Ленц, Ханфрид (1986). Теория дизайна. Издательство Кембриджского университета. п. 15.. 2-е изд. (1999) ISBN  978-0-521-44432-3
6. Р. Бергаммер И М. Винтер (2013) "Разложение отношений на решетках понятий", Fundamenta Informaticae 126(1): 37–82 Дои:10.3233 / FI-2013-871
7. Ки Ханг Ким (1982) Теория логических матриц и приложения, стр. 37, Марсель Деккер ISBN  0-8247-1788-0
8. Али Джауа, Рехаб Дувайри, Самир Эллуми и Садок Бен Яхия (2009) «Интеллектуальный анализ данных, рассуждения и дополнительный поиск информации посредством нерасширяемого прямоугольного покрытия отношения», страницы 199–210 в Отношения и алгебры Клини в информатике, Конспект лекций по информатике 5827, Springer МИСТЕР2781235
9. Жак Риге (1950) "Quelques proprietes des Relations difonctionelles", Comptes Rendus 230: 1999–2000
10. Крис Бринк; Вольфрам Каль; Гюнтер Шмидт (1997). Реляционные методы в информатике. Springer Science & Business Media. п. 200. ISBN  978-3-211-82971-4.
11. Али Джауа, Надин Белхитер, Хабиб Оуналли и Теодор Мукам (1997) «Базы данных», страницы 197–210 в Реляционные методы в информатике, под редакцией Криса Бринка, Вольфрама Кала и Гюнтер Шмидт, Springer Science & Business Media ISBN  978-3-211-82971-4
12. Gumm, H.P .; Заррад, М. (2014). «Коалгебраические моделирования и сравнения». Коалгебраические методы в компьютерных науках. Конспект лекций по информатике. 8446. п. 118. Дои:10.1007/978-3-662-44124-4_7. ISBN  978-3-662-44123-7.
13. Юлиус Рихард Бючи (1989). Конечные автоматы, их алгебры и грамматики: к теории формальных выражений. Springer Science & Business Media. С. 35–37. ISBN  978-1-4613-8853-1.
14. Ж. Риге (1951) "Отношения Ферреров", Comptes Rendus 232: 1729,30
15. Энн К. Штайнер (1970) Рассмотрение:Kontakt = Relationen из Математические обзоры
16. Гюнтер Шмидт (2011) Реляционная математика, страницы 211-15, Издательство Кембриджского университета ISBN  978-0-521-76268-7
17. В этом контексте символ "${\displaystyle \backslash }$"не означает" установить разницу ".
18. Виктор Вагнер (1953) «Теория обобщенных груд и обобщенных групп», Математический сборник 32 (74): с 545 до 632 МИСТЕР0059267
19. CD. Холлингс и М.В. Лоусон (2017) Теория обобщенных груд Вагнера, Книги Springer ISBN  978-3-319-63620-7 МИСТЕР3729305
20. Кристофер Холлингс (2014) Математика за железным занавесом: история алгебраической теории полугрупп, стр. 265, История математики 41, Американское математическое общество ISBN  978-1-4704-1493-1

• Шмидт, Гюнтер; Стрёляйн, Томас (2012). «Глава 3: Гетерогенные отношения». Отношения и графы: дискретная математика для компьютерных ученых. Springer Science & Business Media. ISBN  978-3-642-77968-8.
• Эрнст Шредер (1895) Алгебра логики, группа III, через Интернет-архив