В математике бинарное отношение связывает элементы одного набора, называемого доменом , с элементами другого набора, называемого кодоменом . [1] Бинарное отношение над множествами X и Y — это новый набор упорядоченных пар ( x , y ) , состоящий из элементов x из X и y из Y. [2] Это обобщение более широко понимаемой идеи унарной функции . Он кодирует общую концепцию отношения: элемент x связан с элементом y тогда и только тогда, когда пара ( x , y ) принадлежит множеству упорядоченных пар, которое определяет бинарное отношение . Бинарное отношение — это наиболее изученный частный случай n = 2 n -арного отношения над множествами X 1 , ..., X n , которое является подмножеством декартова произведения [2]
Примером бинарного отношения является отношение « делит » над набором простых чисел и набором целых чисел , в котором каждое простое число p связано с каждым целым числом z , кратным p , но не с целым числом, которое не является кратным p. кратное п . В этом отношении, например, простое число 2 связано с такими числами, как -4, 0, 6, 10, но не с 1 или 9, точно так же, как простое число 3 связано с 0, 6 и 9, но не 4 или 13.
Бинарные отношения используются во многих разделах математики для моделирования самых разных концепций. К ним относятся, среди прочего:
Функция может быть определена как бинарное отношение , удовлетворяющее дополнительным ограничениям. [3] Бинарные отношения также широко используются в информатике .
Бинарное отношение над множествами X и Y является элементом степенного множества Поскольку последнее множество упорядочено включением (⊆), каждое отношение имеет место в решетке подмножеств Бинарное отношение называется однородным отношением, когда X = Ю. _ Бинарное отношение также называется гетерогенным отношением, если не обязательно, чтобы X = Y .
В некоторых системах аксиоматической теории множеств отношения распространяются на классы , которые являются обобщениями множеств. Это расширение необходимо, среди прочего, для моделирования понятий «является элементом» или «является подмножеством» в теории множеств, не сталкиваясь с логическими несоответствиями, такими как парадокс Рассела .
Термины «соответствие» , [7] диадическое отношение и двухместное отношение являются синонимами бинарного отношения, хотя некоторые авторы используют термин «бинарное отношение» для любого подмножества декартова произведения без ссылки на X и Y и оставляют за собой термин «соответствие». " для бинарного отношения со ссылкой на X и Y . [ нужна цитата ]
Определение
Для заданных наборов X и Y декартово произведение определяется как , а его элементы называются упорядоченными парами.
Бинарное отношение R над множествами X и Y является подмножеством [2] [8] Множество X называется областью [2] или множеством отправления R , а множество Y - кодоменом или множеством назначения R . Чтобы указать выбор множеств X и Y , некоторые авторы определяют бинарное отношение или соответствие как упорядоченную тройку ( X , Y , G ) , где G — подмножество, называемое графиком бинарного отношения. Утверждение гласит: « x R - связано с y » и обозначается xRy . [4] [5] [6] [ примечание 1] Область определения или активная область [2] R — это набор всех x таких, что xRy хотя бы для одного y . Кодомен определения , активный кодомен , [2] изображение или диапазон R — это набор всех y таких, что xRy хотя бы для одного x . Поле R представляет собой объединение его области определения и его кодомена определения. [10] [11] [12]
Когда бинарное отношение называется однородным отношением (или эндореляцией ). Чтобы подчеркнуть тот факт, что X и Y могут быть разными, бинарное отношение также называют гетерогенным отношением. [13] [14] [15]
В бинарном отношении важен порядок элементов; if then yRx может быть истинным или ложным независимо от xRy . Например, 3 делит 9, но 9 не делит 3.
Операции
Союз
Если R и S — бинарные отношения над множествами X и Y , то это отношение объединения R и S над X и Y.
Элемент идентификации — это пустое отношение. Например, это объединение < и = и объединение > и =.
Пересечение
Если R и S — бинарные отношения над множествами X и Y , то это отношение пересечения R и S над X и Y.
Элементом идентичности является универсальное отношение. Например, отношение «делится на 6» является пересечением отношений «делится на 3» и «делится на 2».
Состав
Если R — бинарное отношение над множествами X и Y , а S — бинарное отношение над множествами Y и Z , то (также обозначаемое R ; S ) — это отношение композиции R и S над X и Z.
Элементом идентичности является отношение идентичности. Порядок R и S в используемых здесь обозначениях соответствует стандартному порядку обозначений композиции функций . Например, композиция (является родителем) (является матерью) дает (является бабушкой и дедушкой по материнской линии), а композиция (является матерью) (является родителем) дает (является бабушкой). В первом случае, если x является родителем y , а y является матерью z , то x является прародителем z по материнской линии .
Конверсы
Если R является бинарным отношением над множествами X и Y , то это обратное отношение , [ нужна ссылка ] также называемое обратным отношением , [ нужна ссылка ] отношения R над Y и X.
Например, является обратным самому себе, как и и являются обратными друг другу, как и Бинарное отношение равно своему обратному тогда и только тогда, когда оно симметрично .
Дополнить
Если R — бинарное отношение над множествами X и Y , то ( также обозначаемое R или ¬R ) — дополнительное отношение R над X и Y.
Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, т. е. вообще говоря, не равно. Например, ограничение отношения « x является родителем y » женщинами приводит к отношению « x — мать женщины y »; его транзитивное замыкание не связывает женщину с ее бабушкой по отцовской линии. С другой стороны, транзитивное замыкание «является родителем» есть «является предком»; его ограничение на женщин действительно связывает женщину с ее бабушкой по отцовской линии.
Кроме того, различные концепции полноты (не путать с «тотальностью») не переносятся на ограничения. Например, над действительными числами свойство отношения состоит в том, что каждое непустое подмножество с верхней границей имеет наименьшую верхнюю границу (также называемую супремумом) в . Однако для рациональных чисел эта верхняя граница не обязательно является рациональной, поэтому то же свойство не сохраняется и при ограничении отношения к рациональным числам.
Бинарное отношение R над множествами X и Y называетсясодержится в отношенииSнадXиY, записанном, еслиRявляется подмножествомS, то есть для всех,иеслиxRy, тоxSy. ЕслиRсодержится вS, аSсодержится вR, тоRиSназываютсяравнымиипишутR=S. ЕслиRсодержится вS, ноSне содержится вR, тоRназываетсяменьше S, записаноНапример, нарациональныхчислахотношениеменьшеи равно композиции
Матричное представление
Бинарные отношения над множествами X и Y могут быть представлены алгебраически логическими матрицами , индексированными X и Y, с элементами булевого полукольца (сложение соответствует ИЛИ, а умножение И), где сложение матриц соответствует объединению отношений, умножение матриц соответствует композиции отношений (отношения над X и Y и отношения над Y и Z ), [16] произведение Адамара соответствует пересечению отношений, нулевая матрица соответствует пустому отношению, а матрица единиц соответствует универсальному отношению. Однородные отношения (когда X = Y ) образуют матричное полукольцо (действительно, матричную полуалгебру над булевым полукольцом), где единичная матрица соответствует тождественному отношению. [17]
Примеры
Следующий пример показывает, насколько важен выбор кодомена. Предположим, есть четыре объекта и четыре человека. Возможным отношением между A и B является отношение «принадлежит», заданное формулой То есть Джон владеет мячом, Мэри владеет куклой, а Венера владеет машиной. Чашка никому не принадлежит, и Йену ничего не принадлежит; см. 1-й пример. Как набор, R не включает в себя Ian, и поэтому R можно было рассматривать как подмножество, т. е. отношения над A , и см. второй пример. Хотя второй пример отношения является сюръективным (см. ниже), первый — нет.
Пусть A = {Индийский, Арктический, Атлантический, Тихий}, океаны земного шара, и B = {NA, SA, AF, EU, AS, AU, AA}, континенты . Пусть aRb представляет собой океан a, граничащий с континентом b . Тогда логическая матрица для этого отношения:
Связность планеты Земля можно рассматривать через R T и R T R , причем первый представляет собой отношение на A , которое является универсальным отношением ( или логической матрицей всех). Это универсальное соотношение отражает тот факт, что каждый океан отделен от других не более чем одним континентом. С другой стороны, RTR — это отношение , которое не может быть универсальным, поскольку для путешествия из Европы в Австралию необходимо пересечь как минимум два океана .
Визуализация отношений опирается на теорию графов : для отношений на множестве (однородных отношений) ориентированный граф иллюстрирует отношение, а граф — симметричное отношение . Для гетерогенных отношений гиперграф имеет ребра, возможно, с более чем двумя узлами, и его можно проиллюстрировать двудольным графом . Подобно тому, как клика является неотъемлемой частью отношений на множестве, биклики используются для описания гетерогенных отношений; на самом деле, это «концепции», которые создают решетку, связанную с отношением.
Гиперболическая ортогональность : время и пространство — это разные категории, а временные свойства отделены от пространственных свойств. Идея одновременных событий проста в абсолютном времени и пространстве, поскольку каждое время t определяет одновременную гиперплоскость в этой космологии. Герман Минковский изменил это, когда сформулировал понятие относительной одновременности , которая существует, когда пространственные события «нормальны» ко времени, характеризуемому скоростью. Он использовал неопределенное внутреннее произведение и указал, что вектор времени нормален к вектору пространства, когда это произведение равно нулю. Неопределенный скалярный продукт в композиционной алгебре определяется выражением
Геометрическую конфигурацию можно рассматривать как связь между ее точками и линиями. Отношение выражается как инцидентность . Включены конечные и бесконечные проективные и аффинные плоскости. Якоб Штайнер был пионером в каталогизации конфигураций с помощью систем Штейнера , которые имеют набор S из n элементов и набор подмножеств из k-элементов, называемых блоками , так что подмножество с t элементами лежит только в одном блоке. Эти структуры заболеваемости были обобщены с помощью блочных планов . Матрица инцидентности , используемая в этих геометрических контекстах, соответствует логической матрице, обычно используемой с бинарными отношениями.
Структура инцидентности представляет собой тройку D = ( V , B , I ) , где V и B — любые два непересекающихся множества, а I — бинарное отношение между V и B , т. е. элементы V будут называться точками , элементы B — блоками и те, что у меня , флаги . [19]
Конкретные типы бинарных отношений
Некоторые важные типы бинарных отношений R над множествами X и Y перечислены ниже.
Свойства уникальности:
Инъективный (также называемый уникальным слева ): [20] для всех и всех , если xRy и zRy , то x = z . Для такого отношения { Y } называется первичным ключом R. [2] Например, зеленое и синее бинарные отношения на диаграмме являются инъективными, а красное - нет (поскольку оно относится как к -1, так и к 1), а также черное (поскольку оно относится как к -1, так и к 1). до 0).
Одновалентный [6] (также называемый уникальным справа , [20] правоопределенным [21] или функциональным [22] ): для всех и всех, если xRy и xRz , то y = z . Такое бинарное отношение называется частичной функцией . Для такого отношения называется первичным ключом R . [2] Например, красный и зеленый бинарные отношения на диаграмме являются одновалентными, а синий — нет (поскольку он относится 1 как к −1, так и к 1), а также чёрный (поскольку он связывает 0 как с −1, так и с −1). и 1).
Один к одному : инъективный и функциональный. Например, зеленое бинарное отношение на диаграмме является взаимно однозначным, а красное, синее и черное — нет.
Один-ко-многим : инъективный и нефункциональный. Например, синее бинарное отношение на диаграмме является отношением «один ко многим», а красное, зеленое и черное — нет.
Многие-к-одному : функционально, а не инъективно. Например, красное двоичное отношение на диаграмме является отношением многие-к-одному, а зеленое, синее и черное — нет.
Многие-ко-многим : не инъективны и не функциональны. Например, черное бинарное отношение на диаграмме является отношением многие-ко-многим, а красное, зеленое и синее — нет.
Свойства совокупности (определяются только в том случае, если указаны домен X и кодомен Y ):
Тотал (также называемый левым тоталом ): [20] для всех x в X существует y в Y такой, что xRy . Другими словами, область определения R равна X . Это свойство отличается от определения связного (также называемогонекоторыми авторами общим ) [ нужна ссылка ] в разделе «Свойства» . Такое бинарное отношение называется многозначной функцией . Например, красный и зеленый бинарные отношения на диаграмме являются полными, а синий — нет (поскольку он не соотносит −1 с каким-либо действительным числом), а также чёрный (поскольку он не соотносит 2 ни с каким действительным числом). ). Другой пример: > — это тотальное отношение над целыми числами. Но это не тотальное отношение над целыми положительными числами, потому что среди положительных целых чиселнет y такого, что 1 > y . [23] Однако < является тотальным отношением к положительным целым числам, рациональным числам и действительным числам. Каждое рефлексивное отношение тотально: для данного x выберите y = x .
Сюръективный (также называемый тотальным справа [20] или on ): для всех y в Y существует x в X такой, что xRy . Другими словами, кодобласть определения R равна Y . Например, зеленое и синее бинарные отношения на диаграмме являются сюръективными, а красное - нет (поскольку оно не связывает ни одно действительное число с -1), ни черное (поскольку оно не связывает ни одно действительное число с 2). ).
Свойства уникальности и целостности (определяются только в том случае, если указаны домен X и кодомен Y ):
Функция : бинарное отношение , функциональное и тотальное. Например, красные и зеленые бинарные отношения на диаграмме являются функциями, а синие и черные — нет.
Инъекция : функция, которая является инъективной . Например, зеленое бинарное отношение на диаграмме является инъекцией, а красное, синее и черное — нет.
Сюръекция : функция, которая является сюръективной . Например, зеленое бинарное отношение на диаграмме является сюръекцией, а красное, синее и черное — нет.
Биекция : функция, которая является инъективной и сюръективной . Например, зеленое бинарное отношение на диаграмме является биекцией, а красное, синее и черное — нет.
Если отношения над соответствующими классами разрешены:
Подобно множеству (или локально ): для всех x в X класс всех y в Y таких, что yRx , т. е . является набором. Например, отношение является множественным, и каждое отношение на двух множествах является множественным. [24] Обычное упорядочение < по классу порядковых чисел является отношением, подобным множеству, а обратное ему > - нет. [ нужна цитата ]
Наборы против классов
Определенные математические «отношения», такие как «равно», «подмножество» и «член», нельзя понимать как бинарные отношения, определенные выше, поскольку их области определения и кодомены не могут рассматриваться как множества в обычных системах. аксиоматической теории множеств . Например, чтобы смоделировать общую концепцию «равенства» как бинарного отношения, возьмите домен и кодомен как «класс всех множеств», который не является множеством в обычной теории множеств.
В большинстве математических контекстов ссылки на отношения равенства, членства и подмножества безвредны, поскольку их можно неявно понимать как ограниченные некоторым множеством в контексте. Обычный способ решения этой проблемы — выбрать «достаточно большой» набор A , содержащий все интересующие объекты, и работать с ограничением = A вместо =. Аналогичным образом, отношение «подмножество» должно быть ограничено наличием домена и кодомена P( A ) (множества мощности конкретного набора A ): результирующее отношение множества может быть обозначено как Кроме того, отношение «член» должно быть быть ограничено наличием домена A и кодомена P( A ), чтобы получить бинарное отношение , которое является множеством. Бертран Рассел показал, что предположение о том, что оно определено для всех множеств, приводит к противоречию в наивной теории множеств , см. Парадокс Рассела .
Другое решение этой проблемы — использовать теорию множеств с соответствующими классами, такую как NBG или теория множеств Морса-Келли , и позволить домену и кодомену (и, следовательно, графу) быть правильными классами : в такой теории равенство, членство , и subset — это бинарные отношения без специальных комментариев. (Необходимо внести небольшую модификацию в концепцию упорядоченной тройки ( X , Y , G ) , поскольку обычно правильный класс не может быть членом упорядоченного кортежа; или, конечно, можно идентифицировать бинарное отношение с его графиком в [25] С помощью этого определения можно, например, определить бинарное отношение для каждого набора и его набора степеней.
Гомогенное отношение
Однородное отношение над множеством X — это бинарное отношение над X и самим собой, т. е. оно является подмножеством декартова произведения [15] [26] [27] Его также просто называют (бинарным) отношением над X .
Некоторые важные свойства, которыми может обладать однородное отношение R над множеством X :
Рефлексивный : для всех xRx . Например,является рефлексивным отношением, а > нет.
Иррефлексивно : для всехне xRx . Например,является иррефлексивным отношением, нотаковым не является.
Симметрично : для всехесли xRy , то yRx . Например, «кровный родственник» является симметричным отношением.
Антисимметричное : для всех, если xRy и yRx , тоНапример,это антисимметричное отношение. [28]
Асимметричный : для всехесли xRy , то не yRx . Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. [29] Например, > является асимметричным отношением, ноэто не так.
Транзитивно : для всехесли xRy и yRz , то xRz . Транзитивное отношение иррефлексивно тогда и только тогда, когда оно асимметрично. [30] Например, «является предком» является транзитивным отношением, а «является родителем» — нет.
Плотный : для всех, еслитогдасуществует такой, чтои.
Частичный порядок — это отношение, которое является рефлексивным, антисимметричным и транзитивным. Строгий частичный порядок — это отношение, которое является иррефлексивным, асимметричным и транзитивным. Тотальный порядок — это отношение, которое является рефлексивным, антисимметричным, транзитивным и связным. [31] Строгий тотальный порядок — это отношение, которое является иррефлексивным, асимметричным, транзитивным и связным. Отношение эквивалентности — это отношение, которое является рефлексивным, симметричным и транзитивным. Например, « x делит y » — частичный, но не полный порядок натуральных чисел, « x < y » — строгий полный порядок , а « x параллелен y » — отношение эквивалентности на множестве всех строк в Евклидова плоскость .
Все операции, определенные в разделе § Операции, также применимы к однородным отношениям. Помимо этого, однородное отношение над множеством X может подвергаться таким операциям замыкания, как:
В математике гетерогенное отношение — это бинарное отношение, подмножество декартова произведения , где A и B , возможно, являются различными множествами. [32] Приставка гетеро происходит от греческого ἕτερος ( гетерос , «другой, другой, другой»).
Неоднородное отношение было названо прямоугольным отношением [15] , что предполагает, что оно не обладает квадратной симметрией однородного отношения на множестве, где, комментируя развитие бинарных отношений за пределами однородных отношений, исследователи писали: «... развился вариант теории, который с самого начала рассматривает отношения как гетерогенные или прямоугольные , то есть как отношения, в которых в обычном случае они являются отношениями между различными множествами». [33]
Исчисление отношений
Развитие алгебраической логики облегчило использование бинарных отношений. Исчисление отношений включает алгебру множеств , расширенную за счет композиции отношений и использования обратных отношений . Включение, означающее, что aRb влечет aSb , устанавливает сцену в решетке отношений. Но так как символ включения лишний. Тем не менее, композиция отношений и манипулирование операторами в соответствии с правилами Шредера обеспечивают исчисление для работы в степенном наборе
В отличие от однородных отношений, операция композиции отношений представляет собой лишь частичную функцию . Необходимость сопоставления диапазона и области определения составных отношений привела к предположению, что изучение гетерогенных отношений представляет собой главу теории категорий , как и категория множеств , за исключением того, что морфизмы этой категории являются отношениями. Объекты категории Rel являются множествами, а морфизмы отношений составляются по мере необходимости в категории . [ нужна цитата ]
Индуцированная решетка понятий
Бинарные отношения описывались через их индуцированные решетки понятий : Понятие C ⊂ R удовлетворяет двум свойствам: (1) Логическая матрица C является внешним произведением логических векторов.
логические векторы. [ необходимо разъяснение ] (2) C является максимальным и не содержится ни в каком другом внешнем продукте. Таким образом, C описывается как нерасширяемый прямоугольник.
Для данного отношения набор понятий, расширенный за счет их соединений и встреч, образует «индуцированную решетку понятий», причем включение образует предварительный порядок .
Теорема МакНила о пополнении (1937) (о том, что любой частичный порядок может быть вложен в полную решетку ) цитируется в обзорной статье 2013 года «Разложение отношений на решетках понятий». [34] Разложение
где f и g — функции , называемые в этом контексте отображениями или левыми однолистными отношениями. «Индуцированная решетка понятий изоморфна разрезу пополнения частичного порядка E , который принадлежит минимальному разложению ( f, g, E ) отношения R ».
Ниже рассматриваются частные случаи: общий порядок E соответствует типу Феррера, а тождество E соответствует дифункционалу, обобщению отношения эквивалентности на множестве.
Отношения могут быть ранжированы по рангу Шейна , который подсчитывает количество понятий, необходимых для покрытия отношения. [35] Структурный анализ отношений с понятиями обеспечивает подход к интеллектуальному анализу данных . [36]
Особые отношения
Предложение : Если R — серийное отношение , а RT — его транспонирование, то где I — тождественное отношение m × m .
Идея дифункционального отношения заключается в разделении объектов путем различения атрибутов, что является обобщением концепции отношения эквивалентности . Один из способов сделать это – использовать промежуточный набор индикаторов . Отношение разделения — это композиция отношений с использованием однолистных отношений. Жак Риге назвал эти отношения дифункциональными, поскольку композиция FG T включает в себя однолистные отношения, обычно называемые частичными функциями .
В 1950 г. Риге показал, что такие соотношения удовлетворяют включению: [37]
В теории автоматов термин «прямоугольное отношение» также использовался для обозначения дифункционального отношения. Эта терминология напоминает тот факт, что при представлении в виде логической матрицы столбцы и строки дифункционального отношения могут быть организованы как блочная матрица с прямоугольными блоками единиц на (асимметричной) главной диагонали. [38] Более формально, отношение R on является дифункциональным тогда и только тогда, когда его можно записать как объединение декартовых произведений , где они являются разбиением подмножества X и, аналогично, разбиением подмножества Y . [39]
Используя обозначение { y : xRy } = xR , дифункциональное отношение также можно охарактеризовать как отношение R такое, что везде, где x 1 R и x 2 R имеют непустое пересечение, эти два множества совпадают; формально подразумевает [40]
В 1997 году исследователи обнаружили «полезность двоичной декомпозиции, основанной на дифункциональных зависимостях, при управлении базами данных ». [41] Более того, дифункциональные отношения имеют фундаментальное значение при изучении бисимуляций . [42]
Строгий порядок на множестве — однородное отношение, возникающее в теории порядка . В 1951 году Жак Риге принял упорядочение разбиения целого числа, названное диаграммой Феррера , чтобы распространить упорядочение на бинарные отношения в целом. [43]
Соответствующая логическая матрица общего бинарного отношения имеет строки, заканчивающиеся последовательностью единиц. Таким образом, точки диаграммы Феррера заменяются единицами и выравниваются справа в матрице.
Алгебраическое утверждение, необходимое для отношения типа Феррерса R, таково:
Если какое-либо из отношений относится к типу Феррера, то все они таковые.[32]
Контакт
Предположим, что B — это набор степеней A , набор всех подмножеств A. Тогда отношение g является контактным отношением , если оно удовлетворяет трем свойствам:
Отношение принадлежности множества , ε = «является элементом», удовлетворяет этим свойствам, поэтому ε является контактным отношением. Понятие общего контактного отношения было введено Георгом Ауманном в 1970 году. [44] [45]
С точки зрения исчисления отношений, к достаточным условиям контактного отношения относятся:
∈[46] : 280
Предзаказ Р\Р
Каждое отношение R порождает предварительный порядок , который является левым остатком . [47] С точки зрения обратного и дополнения, образуя диагональ , соответствующая строка и столбец будут иметь противоположные логические значения, поэтому диагональ - все нули. Затем
Для данного отношения R подотношение, называемое его границей , определяется как
Когда R является отношением частичной идентичности, дифункциональным или блочно-диагональным отношением, тогда fringe( R ) = R . В противном случае оператор границы выбирает граничное подотношение, описанное в терминах его логической матрицы: fringe( R ) — это боковая диагональ, если R — верхний правый треугольный линейный порядок или строгий порядок . Fringe( R ) является блочной границей, если R иррефлексивно ( ) или верхний правый блочно-треугольный. Fringe( R ) — это последовательность граничных прямоугольников, когда R имеет тип Феррера.
С другой стороны, Fringe( R ) = ∅, когда R — плотный , линейный, строгий порядок. [46]
Математические кучи
Учитывая два множества A и B , набор бинарных отношений между ними может быть снабжен тернарной операцией , где b T обозначает обратное отношение b . В 1953 году Виктор Вагнер использовал свойства этой тернарной операции для определения полукучек, куч и обобщенных куч. [48] [49] Контраст гетерогенных и однородных отношений подчеркивается следующими определениями:
В работах Вагнера существует приятная симметрия между кучами, полукучами и обобщенными кучами, с одной стороны, и группами, полугруппами и обобщенными группами — с другой. По сути, различные типы полукучек появляются всякий раз, когда мы рассматриваем бинарные отношения (и частичные отображения «один-один») между различными множествами A и B , тогда как различные типы полугрупп появляются в случае, когда A = B.
- Кристофер Холлингс, «Математика за железным занавесом: история алгебраической теории полугрупп» [50]
^ Авторы, которые рассматривают бинарные отношения только как частный случай n -арных отношений для произвольного n , обычно пишут Rxy как частный случай Rx 1 ... x n ( префиксная запись ). [9]
Рекомендации
↑ Мейер, Альберт (17 ноября 2021 г.). «MIT 6.042J Математика для информатики, лекция 3T, слайд 2» (PDF) . Архивировано (PDF) из оригинала 17 ноября 2021 г.
^ abcdefgh Кодд, Эдгар Франк (июнь 1970 г.). «Реляционная модель данных для больших общих банков данных» (PDF) . Коммуникации АКМ . 13 (6): 377–387. дои : 10.1145/362384.362685. S2CID 207549016. Архивировано (PDF) из оригинала 8 сентября 2004 г. Проверено 29 апреля 2020 г.
^ «Определение отношения - Math Insight» . mathinsight.org . Проверено 11 декабря 2019 г.
^ Суппес, Патрик (1972) [первоначально опубликовано компанией Д. ван Ностранд в 1960 году]. Аксиоматическая теория множеств . Дувр. ISBN0-486-61630-4.
^ Смуллян, Раймонд М .; Фиттинг, Мелвин (2010) [переработанное и исправленное переиздание работы, первоначально опубликованной в 1996 году издательством Oxford University Press, Нью-Йорк]. Теория множеств и проблема континуума . Дувр. ISBN978-0-486-47484-7.
^ Леви, Азриэль (2002) [переиздание работы, опубликованной Springer-Verlag, Берлин, Гейдельберг и Нью-Йорк в 1979 году]. Базовая теория множеств . Дувр. ISBN0-486-42079-5.
^ Шмидт, Гюнтер ; Стрёлейн, Томас (2012). Отношения и графики: дискретная математика для компьютерных специалистов. Springer Science & Business Media. Определение 4.1.1. ISBN978-3-642-77968-8.
^ Христодулос А. Флудас ; Панос М. Пардалос (2008). Энциклопедия оптимизации (2-е изд.). Springer Science & Business Media. стр. 299–300. ISBN978-0-387-74758-3.
^ abc Майкл Винтер (2007). Категории Гогена: Категорический подход к L-нечетким отношениям . Спрингер. стр. x – xi. ISBN978-1-4020-6164-6.
^ Дросте, М., и Куич, В. (2009). Полукольца и формальный степенной ряд. Справочник по взвешенным автоматам , 3–28. дои : 10.1007/978-3-642-01492-5_1, стр. 7-10.
^ abcd Килп, Кнауэр и Михалев: с. 3. Те же четыре определения встречаются ниже:
Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. п. 506. ИСБН 978-3-540-67995-0.
Эйке Бест (1996). Семантика последовательных и параллельных программ . Прентис Холл. стр. 19–21. ISBN 978-0-13-460643-9.
Роберт-Кристоф Риман (1999). Моделирование параллельных систем: структурные и семантические методы в исчислении сетей Петри высокого уровня . Герберт Утц Верлаг. стр. 21–22. ISBN 978-3-89675-629-9.
^ Мэс, Стефан (2007), «Рассуждения об ограничениях пространственной семантической целостности», Теория пространственной информации: 8-я Международная конференция, COSIT 2007, Мельбурн, Австралия, 19–23 сентября 2007 г., Труды , Конспекты лекций по информатике, том. 4736, Springer, стр. 285–302, номер документа : 10.1007/978-3-540-74788-8_18.
^ А. Сенгупта (2003). «К теории хаоса». Международный журнал бифуркации и хаоса . 13 (11): 3147–3233. дои : 10.1142/S021812740300851X.
^ Яо, ГГ; Вонг, СКМ (1995). «Обобщение грубых наборов с использованием связей между значениями атрибутов» (PDF) . Материалы 2-й ежегодной совместной конференции по информационным наукам : 30–33..
^ Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Северная Голландия. п. 102. ИСБН0-444-85401-0. Збл 0443.03021.
^ Тарский, Альфред ; Гивант, Стивен (1987). Формализация теории множеств без переменных. Американское математическое общество. п. 3. ISBN0-8218-1041-3.
^ М. Е. Мюллер (2012). Открытие реляционных знаний . Издательство Кембриджского университета. п. 22. ISBN978-0-521-19021-3.
^ Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. п. 496. ИСБН978-3-540-67995-0.
^ Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Брукс/Коул, стр. 160, ISBN0-534-39900-2
^ Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, p. 158.
^ Флашка, В.; Ежек, Дж.; Кепка, Т.; Кортелайнен, Дж. (2007). Транзитивные замыкания бинарных отношений I (PDF) . Прага: Школа математики – Физика Карлова университета. п. 1. Архивировано из оригинала (PDF) 2 ноября 2013 г.Лемма 1.1 (iv). Этот источник называет асимметричные отношения «строго антисимметричными».
^ Джозеф Г. Розенштейн, Линейные порядки , Academic Press, 1982, ISBN 0-12-597680-1 , стр. 4
^ аб Шмидт, Гюнтер ; Стрёлейн, Томас (2012). Отношения и графики: дискретная математика для компьютерных специалистов. Springer Science & Business Media. п. 77. ИСБН978-3-642-77968-8.
^ Г. Шмидт, Клаудия Хальтенспергер и Майкл Винтер (1997) «Алгебра гетерогенных отношений», глава 3 (страницы с 37 по 53) в « Реляционных методах в информатике» , «Достижения в области компьютерных наук», книги Springer ISBN 3-211-82971-7
^ Р. Бергхаммер и М. Винтер (2013) «Декомпозиция отношений по решеткам понятий», Fundamenta Informaticae 126 (1): 37–82 doi : 10.3233/FI-2013-871
^ Али Джауа, Рехаб Дувайри, Самир Эллуми и Садок Бен Яхия (2009) «Интеллектуальный анализ данных, рассуждения и дополнительный поиск информации посредством нерасширяемого покрытия прямоугольных отношений», страницы 199–210 в разделе «Отношения и алгебры Клини в информатике» , конспекты лекций в Информатика 5827, Springer MR 2781235
^ Риге, Жак (январь 1950 г.). «Quelques proprietes deslations difonctionelles». Comptes rendus (на французском языке). 230 : 1999–2000.
^Julius Richard Büchi (1989). Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions. Springer Science & Business Media. pp. 35–37. ISBN 978-1-4613-8853-1.
^East, James; Vernitski, Alexei (February 2018). "Ranks of ideals in inverse semigroups of difunctional binary relations". Semigroup Forum. 96 (1): 21–30. arXiv:1612.04935. doi:10.1007/s00233-017-9846-9. S2CID 54527913.
^Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Relational Methods in Computer Science. Springer Science & Business Media. p. 200. ISBN 978-3-211-82971-4.
^Gumm, H. P.; Zarrad, M. (2014). "Coalgebraic Simulations and Congruences". Coalgebraic Methods in Computer Science. Lecture Notes in Computer Science. Vol. 8446. p. 118. doi:10.1007/978-3-662-44124-4_7. ISBN 978-3-662-44123-7.
^Georg Aumann (1971). "Kontakt-Relationen". Sitzungsberichte der mathematisch-physikalischen Klasse der Bayerischen Akademie der Wissenschaften München. 1970 (II): 67–77.
Шмидт, Гюнтер ; Стрёляйн, Томас (2012). «Глава 3: Гетерогенные отношения». Отношения и графы: дискретная математика для компьютерщиков . Springer Science & Business Media. ISBN 978-3-642-77968-8.
Кодд, Эдгар Франк (1990). Реляционная модель управления базами данных: версия 2 (PDF) . Бостон: Аддисон-Уэсли . ISBN 978-0201141924. Архивировано (PDF) из оригинала 9 октября 2022 г.
Килп, Мати; Кнауэр, Ульрих; Михалев, Александр (2000). Моноиды, акты и категории: с приложениями к сплетенным произведениям и графам . Берлин: Де Грюйтер . ISBN 978-3-11-015248-7.
Пирс, Чарльз Сандерс (1873). «Описание обозначений логики родственников, возникающее в результате расширения концепций логического исчисления Буля». Мемуары Американской академии искусств и наук . 9 (2): 317–178. Бибкод : 1873MAAAS...9..317P. дои : 10.2307/25058006. hdl : 2027/hvd.32044019561034 . JSTOR 25058006 . Проверено 5 мая 2020 г.