Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивности и рефлексивности . |
В математике , А бинарное отношение над множествами X и Y представляет собой подмножество в декартово произведение X × Y ; то есть, она представляет собой набор упорядоченных пар ( х , у ) , состоящих из элементов х в X и Y в Y . [1] Он кодирует общую концепцию соотношения: элемент х имеет связанный с элементом у , тогда и только тогда , когда пара (x , y ) принадлежит набору упорядоченных пар, определяющих бинарное отношение . Бинарное отношение является наиболее изученным частным случаем п = 2 из п -ичного соотношения над множествами Х 1 , ..., Х п , которое является подмножеством декартова произведения X 1 × ... × X п . [1] [2]
Примером бинарного отношения является отношение « делит » над множеством простых чисел. и набор целых чисел , В которой каждый простой р связан с каждым целым числом г , которое является кратным от р , но не является целым числом, которое не является кратным р . В этом отношении, например, простое число 2 связано с такими числами, как -4, 0, 6, 10, но не с 1 или 9, так же, как простое число 3 связано с 0, 6 и 9, но не до 4 или 13.
Бинарные отношения используются во многих разделах математики для моделирования самых разных понятий. К ним, среди прочего, относятся:
- « больше », « равно » и «делит» отношения в арифметике ;
- отношение « конгруэнтно » в геометрии ;
- отношение «смежно с» в теории графов ;
- отношение « ортогонально » в линейной алгебре .
Функция может быть определена как особый вид бинарного отношения. [3] Двоичные отношения также широко используются в информатике .
Бинарное отношение над множествами X и Y представляет собой элемент из набора мощности из X × Y . Поскольку последнее множество упорядочено включением (⊆), каждое отношение имеет место в решетке подмножеств X × Y . Бинарное отношение - это либо однородное, либо гетерогенное отношение, в зависимости от того, X = Y или нет.
Поскольку отношения являются наборами, ими можно манипулировать, используя операции над наборами, включая объединение , пересечение и дополнение , а также выполнение законов алгебры множеств . Кроме того, операции , такие как обратные от соотношения и состав отношений доступны, удовлетворяющие законы исчисления отношений , для которых Есть учебники по Эрнсту Шрёдеру , [4] Кларенс Льюис , [5] и Гюнтер Шмидт . [6] Более глубокий анализ отношений включает разложение их на подмножества, называемые концепциями , и размещение их в полной решетке .
В некоторых системах аксиоматической теории множеств отношения распространяются на классы , которые являются обобщениями множеств. Это расширение необходимо, среди прочего, для моделирования концепций «является элементом» или «является подмножеством» в теории множеств, не сталкиваясь с логическими противоречиями, такими как парадокс Рассела .
Термины соответствие , [7] диадическое отношение и двухместное отношение являются синонимами бинарного отношения, хотя некоторые авторы используют термин «бинарное отношение» для любого подмножества декартова произведения X × Y без ссылки на X и Y , и оставляют за собой термин «соответствие» для бинарного отношения со ссылкой на X и Y . [ необходима цитата ]
Определение
С учетом множества Х и Y , то декартово произведение X × Y определяется как {( х , у ) | x ∈ X и y ∈ Y } , а его элементы называются упорядоченными парами.
Бинарное отношение R над множествами X и Y представляет собой подмножество X × Y . [1] [8] Множество Х называется область [1] или набор вылета из R , а множество Y кообласть или набор назначения из R . Чтобы указать выбор множеств X и Y , некоторые авторы определяют бинарное отношение или соответствие как упорядоченную тройку ( X , Y , G ) , где G - подмножество X × Y, называемое графом бинарного отношения. Утверждение ( x , y ) ∈ R читается как « x R- связано с y » и обозначается xRy . [4] [5] [6] [примечание 1] область определения или активной области [1] из R представляет собой множество всех х таких , что хКу по крайней мере , одного у . Кообласть определения , активные области значений , [1] изображения или диапазон из R представляет собой множество всех у такого , что хКа , по крайней мере , одного х . Поле из R является объединением своей области определения и его кообласти определения. [10] [11] [12]
Когда X = Y , бинарное отношение называется однородным отношением (или эндорреляцией ). В противном случае это неоднородные отношения . [13] [14] [15]
В бинарных отношениях важен порядок элементов; если x ≠ y, то yRx может быть истинным или ложным независимо от xRy . Например, 3 делит 9, но 9 не делит 3.
Примеры
А B ′ | мяч | машина | кукла | чашка |
---|---|---|---|---|
Джон | + | - | - | - |
Мэри | - | - | + | - |
Венера | - | + | - | - |
А B | мяч | машина | кукла | чашка |
---|---|---|---|---|
Джон | + | - | - | - |
Мэри | - | - | + | - |
Ян | - | - | - | - |
Венера | - | + | - | - |
1) Следующий пример показывает, что выбор кодомена важен. Предположим, есть четыре объекта A = {мяч, машина, кукла, чашка} и четыре человека B = {Джон, Мэри, Ян, Венера} . Возможное отношение на A и B - это отношение «принадлежит», задаваемое R = {(мяч, Джон), (кукла, Мэри), (машина, Венера)} . То есть Джон владеет мячом, Мэри владеет куклой, а Венера владеет машиной. Никто не владеет чашей, и Ян ничего не владеет, см. 1-й пример. Как набор, R не включает Яна, и поэтому R можно было бы рассматривать как подмножество A × {John, Mary, Venus} , то есть отношение над A и {John, Mary, Venus}, см. 2-й пример. В то время как 2-й пример отношения сюръективен (см. Ниже ), 1-й - нет.
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 |
2) Пусть A = {Индийский, Арктический, Атлантический, Тихий}, океаны земного шара, и B = {NA, SA, AF, EU, AS, OC, AA}, континенты . Пусть ARB представляет этот океан на границах континент б . Тогда логическая матрица для этого отношения:
Связность планеты Земля можно рассматривать через RR T и R T R , первое из которых является отношением 4 × 4 на A , которое является универсальным отношением ( A × A или логической матрицей всех единиц). Это универсальное отношение отражает тот факт, что каждый океан отделен от других не более чем одним континентом. С другой стороны, R T R - это отношение на B × B, которое не может быть универсальным, потому что для путешествия из Европы в Океанию необходимо пересечь по крайней мере два океана .
3) Визуализация отношений опирается на теорию графов : для отношений на множестве (однородные отношения) ориентированный граф иллюстрирует отношение, а граф - симметричное отношение. Для гетерогенных отношений гиперграф имеет ребра, возможно, с более чем двумя узлами, и может быть проиллюстрирован двудольным графом .
Как клика является неотъемлемой частью отношений на множестве, так и биклики используются для описания гетерогенных отношений; действительно, это «концепции», которые порождают решетку, связанную с отношением.
4) Гиперболическая ортогональность : время и пространство - разные категории, а временные свойства отделены от пространственных свойств. Идея одновременных событий проста в абсолютном времени и пространстве, поскольку каждый момент времени t определяет одновременную гиперплоскость в этой космологии. Герман Минковский изменил это, когда сформулировал понятие относительной одновременности , которое существует, когда пространственные события «нормальны» по отношению ко времени, характеризуемому скоростью. Он использовал неопределенное внутреннее произведение и указал, что вектор времени нормален к пространственному вектору, когда этот продукт равен нулю. Неопределенный скалярный продукт в композиционной алгебре задается формулой
- где черта сверху означает сопряжение.
Как отношение между некоторыми временными событиями и некоторыми пространственными событиями, гиперболическая ортогональность (как обнаруживается в расщепленных комплексных числах ) является неоднородным отношением. [16]
5) Геометрическую конфигурацию можно рассматривать как отношение между ее точками и ее линиями. Отношение выражается как частота . Включены конечные и бесконечные проективные и аффинные плоскости. Якоб Штайнер первым начал каталогизацию конфигураций с помощью систем Штейнера S ( t, k, n ), которые имеют n-элементный набор S и набор k-элементных подмножеств, называемых блоками , так что подмножество с t элементами лежит только в одном блоке. . Эти структуры инцидентности были обобщены с помощью блочных конструкций . Матрица частоты , используемая в этих геометрических контекстах соответствуют логической матрице используется в основном с бинарными отношениями.
- Структура заболеваемости является тройной D = ( V , B , I ) , где V и B являются любые два множества не пересекаются и я бинарное отношение между V и B , т.е. I ⊆ V × B . Элементы V будем называть точками , элементы блоков B и элементы I флагов . [17]
Особые типы бинарных отношений
Некоторые важные типы бинарных отношений R над множествами X и Y перечислены ниже.
- Как набор[ необходима цитата ] (или местный )
- для всех х ∈ X , то класс всех у таких , что угх представляет собой набор. (Это имеет смысл только в том случае, если разрешены отношения над соответствующими классами.) Например, обычное упорядочение <над классом порядковых чисел является отношением, подобным множеству, а его обратное> - нет.
Свойства уникальности:
- Инъективный (также называемый уникальным слева ): [18] для всех x , z ∈ X и всех y ∈ Y , если xRy и zRy, то x = z . Для получения такого соотношения, { Y } называется на первичный ключ из R . [1] Например, зеленые и синие бинарные отношения на диаграмме инъективны, а красный - нет (поскольку он связывает и -1, и 1 с 1), ни черный (поскольку он связывает и -1, и 1. до 0).
- Функциональный (также называемый единственно справа , [18] определенным справа [19] или однолистным ): [6] для всех x ∈ X и всех y , z ∈ Y , если xRy и xRz, то y = z . Такое бинарное отношение называется частичной функцией . Для получения такого соотношения, { X } называется первичным ключом из R . [1] Например, красные и зеленые бинарные отношения на диаграмме являются функциональными, а синее - нет (поскольку оно связывает 1 как с -1, так и с 1), ни с черным (поскольку оно связывает 0 с обоими -1. и 1).
- Один к одному : инъективный и функциональный. Например, бинарные отношения зеленого цвета на диаграмме взаимно однозначны, а отношения красного, синего и черного - нет.
- Один ко многим : инъективный и нефункциональный. Например, синее двоичное отношение на диаграмме - один ко многим, а красный, зеленый и черный - нет.
- Многие к одному : функциональные, а не инъекционные. Например, красное бинарное отношение на диаграмме - «многие к одному», а зеленый, синий и черный - нет.
- Многие-ко-многим : не инъективны и не функциональны. Например, черные бинарные отношения на диаграмме - это многие ко многим, а красные, зеленые и синие - нет.
Свойства целостности (можно определить, только если указаны домен X и домен Y ):
- Серийный (также называемый тотальным слева ): [18] для всех x в X существует y в Y такое, что xRy . Другими словами, область определения R равен X . Это свойство, хотя некоторые авторы также называют его полным , [ необходима ссылка ] отличается от определения связанного (также называемого некоторыми авторами общим ) [ необходима ссылка ] в Свойствах . Такое бинарное отношение называется многозначной функцией . Например, красные и зеленые бинарные отношения на диаграмме являются последовательными, а синее - нет (поскольку оно не связывает -1 ни с каким действительным числом), ни черное (поскольку оно не связывает 2 ни с одним действительным числом. ). Другой пример:> - это последовательное отношение над целыми числами. Но это не последовательная связь по положительным целым числам, потому что в натуральных числах нет y, такого что 1> y . [20] Однако <является последовательным отношением к положительным целым числам, рациональным числам и действительным числам. Каждое рефлексивное отношение серийно: для данного x выберите y = x .
- Сюръективный (также называемый право-тотальным [18] или на ): для всех y в Y существует x в X такое, что xRy . Другими словами, кообласть определения R равен Y . Например, зеленые и синие бинарные отношения на диаграмме сюръективны, а красное - нет (поскольку оно не связывает ни одно действительное число с −1), ни черное (поскольку оно не связывает какое-либо действительное число с 2. ).
Свойства уникальности и полноты (можно определить, только если заданы домен X и домен Y ):
- Функции : бинарное отношение , что является функциональным и серийным. Например, красные и зеленые бинарные отношения на диаграмме являются функциями, а синие и черные - нет.
- Инъекции : функция , которая инъективна. Например, зеленое двоичное отношение на диаграмме является инъекцией, а красный, синий и черный - нет.
- Сюръекция : функция , которая сюръективна. Например, зеленое бинарное отношение на диаграмме является сюрпризом, а красный, синий и черный - нет.
- Биекция : функция, инъективно и сюръективно. Например, зеленое бинарное отношение на диаграмме является взаимно однозначным, а красный, синий и черный - нет.
Операции над бинарными отношениями
Союз
Если R и S - бинарные отношения над множествами X и Y, то R ∪ S = {( x , y ) | хКа или вании } является объединение отношения из 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, то S ∘ R = {( x , z ) | существует у ∈ Y такое , что хКа и YSZ } (также обозначается через R ; S ) представляет собой композицию соотношение из R и S над X и Z .
Элементом идентичности является отношение идентичности. Порядок R и S в обозначениях S ∘ R , используемых здесь, согласуется со стандартным порядком обозначений для композиции функций . Например, композиция "является матерью" "является родителем" урожайности "является бабушкой и дедушкой по материнской линии", в то время как композиция "является родителем" ", является матерью" урожайности "является бабушкой". В первом случае, если x - родитель y, а y - мать z , то x - прародитель z по материнской линии .
Converse
Если R - бинарное отношение над множествами X и Y, то R T = {( y , x ) | хКу } является обратным соотношением из R над Y и X .
Например, = является обратным самому себе, как ≠, а <и> являются обратными друг другу, как и ≤ и ≥. Бинарное отношение равно своему обратному тогда и только тогда, когда оно симметрично .
Дополнение
Если R - бинарное отношение над множествами X и Y, то R = {( x , y ) | не хКа } (также обозначается через R или ¬ R ) является комплементарным отношением из R над X и Y .
Например, = и ≠ являются дополнениями друг друга, как и ⊆ и ⊈, ⊇ и ⊉, и ∈ и ∉, а для общего количества заказов также <и ≥, и> и ≤.
Дополнение обратного отношения R T является обратным дополнению:
Если X = Y , дополнение имеет следующие свойства:
- Если отношение симметрично, то и дополнение - тоже.
- Дополнение рефлексивного отношения иррефлексивно - и наоборот.
- Дополнение к строгому слабому заказу - это полный предварительный заказ, и наоборот.
Ограничение
Если R - бинарное однородное отношение над множеством X и S - подмножество X, то R | S = {( x , y ) | хКа и х ∈ S и Y ∈ S } являетсяограничение соотношения изRкSнадX.
Если R - бинарное отношение над множествами X и Y и если S - подмножество X, то R | S = {( x , y ) | xRy и x ∈ S } - этолевое ограничение соотношение изRкSнадXиY.
Если R - бинарное отношение над множествами X и Y и если S - подмножество Y, то R | S = {( x , y ) | xRy и y ∈ S } - этоправое ограничение соотношение изRкSнадXиY.
Если отношение является рефлексивным , иррефлексивным, симметричным , антисимметричным , асимметричным , транзитивным , полным , трихотомическим , частичным , полным порядком , строгим слабым порядком , полным предварительным порядком (слабым порядком) или отношением эквивалентности , то то же самое относится к его ограничениям.
Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, т. Е. В общем случае не равнозначно. Например, ограничение отношения « x является родителем y » женщинами дает отношение « x - мать женщины y »; его переходное закрытие не связывает женщину с бабушкой по отцовской линии. С другой стороны, транзитивное закрытие "является предком" является "является предком"; его ограничение женщинами действительно связывает женщину с ее бабушкой по отцовской линии.
Кроме того, различные концепции полноты (не путать с « полнотой ») не переносятся на ограничения. Так , например, над действительными числами свойство отношения ≤ является то , что каждое непустое подмножество S из R с верхней границей в R имеет минимум верхнюю границу (также называемый супремума) в R . Однако для рациональных чисел этот супремум не обязательно является рациональным, поэтому то же свойство не выполняется при ограничении отношения ≤ на рациональные числа.
Бинарное отношение R над множествами X и Y называется {{em | содержащееся в отношении S над X и Y , записываетсяесли R - подмножество S , то есть для всех а также если xRy , то xSy . Если R содержится в S и S содержится в R , то R и S , называются равно письменное R = S . Если R содержится в S, но S не содержится в R , то R называетсяменьше , чемS, написанный R ⊊ S . Например, длярациональных чиселотношение> меньше ≥ и равно композиции> ∘>.
Матричное представление
Бинарные отношения над множествами X и Y могут быть представлены алгебраически логическими матрицами, проиндексированными X и Y с элементами в булевом полукольце (сложение соответствует ИЛИ, а умножение - И), где сложение матриц соответствует объединению отношений, умножение матриц соответствует составу отношений (отношения над X и Y и отношения над Y и Z ), [21] произведение Адамара соответствует пересечению отношений, нулевая матрица соответствует пустому отношению, а матрица единиц соответствует универсальному отношению. Однородные отношения (когда X = Y ) образуют матричное полукольцо (действительно, матричную полуалгебру над булевым полукольцом), где единичная матрица соответствует единичному отношению. [22]
Наборы против классов
Определенные математические "отношения", такие как "равно", "подмножество" и "член", не могут пониматься как бинарные отношения, как определено выше, потому что их домены и домены не могут считаться наборами в обычных системах. из аксиоматической теории множеств . Например, если мы попытаемся смоделировать общую концепцию «равенства» как бинарное отношение =, мы должны принять домен и домен как «класс всех множеств», что не является множеством в обычной теории множеств.
В большинстве математических контекстов ссылки на отношения равенства, членства и подмножества безвредны, потому что их можно неявно понимать как ограниченные некоторым набором в контексте. Обычный способ решения этой проблемы - выбрать «достаточно большой» набор A , содержащий все интересующие объекты, и работать с ограничением = A вместо =. Аналогичным образом , «подмножество» Связь ⊆ потребностей должно быть ограничено , чтобы иметь домен и кообласть P ( A ) (набор мощности определенного множества А ): результирующий набор соотношение может обозначать ⊆ A . Кроме того, отношение «член» должно быть ограничено доменом A и доменом P ( A ), чтобы получить бинарное отношение ∈ A, которое является набором. Бертран Рассел показал, что предположение, что ∈ определено на всех множествах, приводит к противоречию в наивной теории множеств.
Другое решение этой проблемы - использовать теорию множеств с соответствующими классами, такую как NBG или теория множеств Морса – Келли , и позволить области и области (и, следовательно, графу) быть собственными классами : в такой теории равенство, принадлежность , и подмножество являются бинарными отношениями без специальных комментариев. (Незначительная модификация должна быть внесена в концепцию упорядоченной тройки ( X , Y , G ) , поскольку обычно правильный класс не может быть членом упорядоченного кортежа; или, конечно, можно идентифицировать двоичное отношение с его графом в этот контекст.) [23] С помощью этого определения можно, например, определить бинарное отношение для каждого набора и его набора мощности.
Однородное отношение
Однородное отношение над множеством X представляет собой бинарное отношение над X и само по себе, т.е. является подмножеством декартова произведения X × X . [15] [24] [25] Она также называется просто (двоичный) отношение над X .
Однородное отношение R над множеством X можно отождествить с ориентированным простым графом, допускающим петли , где X - множество вершин, а R - множество ребер (существует ребро от вершины x до вершины y тогда и только тогда, когда xRy ) . Множество всех однородных отношенийнад множеством X есть множество 2 X × X, которое является булевой алгеброй, дополненной инволюцией отображения отношения в обратное отношение . Рассматривая композицию отношений как бинарную операцию над, он образует полугруппу с инволюцией .
Некоторые важные свойства, которыми может обладать однородное отношение R над множеством X :
- Рефлексивный : для всех x ∈ X , xRx . Например, ≥ - рефлексивное отношение, а> - нет.
- Безрефлексивный : для всех x ∈ X , а не xRx . Например,> - иррефлексивное отношение, а ≥ - нет.
- Симметричный : для всех x , y ∈ X , если xRy, то yRx . Например, «кровный родственник» - это симметричное отношение.
- Антисимметричный : для всех x , y ∈ X , если xRy и yRx, то x = y . Например, ≥ - антисимметричное отношение. [26]
- Асимметричный : для всех x , y ∈ X , если xRy, то не yRx . Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. [27] Например,> - это асимметричное отношение, а ≥ - нет.
- Транзитивный : для всех x , y , z ∈ X , если xRy и yRz, то xRz . Транзитивное отношение иррефлексивно тогда и только тогда, когда оно асимметрично. [28] Например, «является предком» является транзитивным отношением, а «является родителем» - нет.
- Связано : для всех x , y ∈ X , если x ≠ y, то xRy или yRx .
- Сильно связно : для всех x , y ∈ X , xRy или yRx .
Частичный порядок является отношение , которое является рефлексивным, антисимметричным и транзитивным. Строгий частичный порядок является отношением , что иррефлексивно, антисимметричным и транзитивным. Общий порядок является отношение , которое является рефлексивным, антисимметричным, транзитивным и подключен. [29] строгие общий порядок представляет собой отношение, иррефлексивен, антисимметричные, транзитивные и подключены. Отношение эквивалентности есть отношение, которое рефлексивно, симметрично и транзитивно. Так , например, « х делит у » представляет собой частичный, но не полный заказ на ℕ , « х < у » строгий общий порядок на ℕ, а « х параллельно у » является отношением эквивалентности на множестве всех прямые на евклидовой плоскости .
Все операции, определенные в разделе Операции с бинарными отношениями, также применимы к однородным отношениям. Помимо этого, однородное отношение над множеством X может подвергаться закрывающим операциям, например:
- Рефлексивное замыкание : (единственное) рефлексивное отношение над X, содержащее R ,
- Транзитивное замыкание : наименьшее транзитивное отношение над X, содержащее R ,
- Эквивалентность замыкание : наименьшее отношение эквивалентности над X , содержащей R .
Гетерогенное отношение
В математике , А гетерогенное отношение является бинарным отношением , A подмножеством из декартово произведения × B , где и B различны множества. [30] Приставка гетеро происходит от греческого ἕτερος ( гетерос , «другой, другой, другой»).
Гетерогенное отношение было названо прямоугольным отношением , [31] предполагая , что он не имеет квадратную-симметрию однородного отношения на множестве , где A = B . Комментируя развитие бинарных отношений за пределами однородных отношений, исследователи писали: «... развился вариант теории, который с самого начала рассматривает отношения как гетерогенные или прямоугольные , то есть как отношения, в которых нормальным случаем является то, что они являются отношениями между разные наборы ". [32]
Исчисление отношений
Развитие алгебраической логики облегчило использование бинарных отношений. Исчисление отношений включает в себя алгебру множеств , продолженный составом отношений и использование обратных отношений . Включение R ⊆ S , означающее, что aRb влечет aSb , устанавливает сцену в решетке отношений. Но с тех порсимвол включения лишний. Тем не менее, состав отношений и манипуляций с операторами в соответствии с правилами Шредера , обеспечивает исчисление для работы в наборе мощности от A × B .
В отличие от однородных отношений, операция композиции отношений является лишь частичной функцией . Необходимость сопоставления диапазона и области составных отношений привела к предположению, что изучение гетерогенных отношений является главой теории категорий, как и в категории множеств , за исключением того, что морфизмы этой категории являются отношениями. В объектах категории Rel являются множествами, и отношение-морфизмы сочинить , как требуется в категории .
Решетка индуцированных концепций
Бинарные отношения были описаны через их индуцированные решетки понятий : понятие C ⊂ R удовлетворяет двум свойствам: (1) логическая матрица C - это внешнее произведение логических векторов
- логические векторы. (2) C является максимальным, не содержится ни в каком другом внешнем продукте. Таким образом, C описывается как нерасширяемый прямоугольник.
Для данного отношения R : X → Y множество понятий, расширенное их соединениями и встречами, образует «индуцированную решетку понятий» с включениемформирование предзаказа .
Теорема Мак-Нейла о пополнении (1937 г.) (о том, что любой частичный порядок может быть вложена в полную решетку ) цитируется в обзорной статье 2013 г. «Разложение отношений на решетках понятий». [33] Разложение
- где f и g - функции , называемые в данном контексте отображениями или левыми однолистными отношениями. «Решетка индуцированных понятий изоморфна разрезанному пополнению частичного порядка E, который принадлежит минимальному разложению ( f, g, E ) отношения R ».
Ниже рассматриваются частные случаи: полный порядок E соответствует типу Феррерса, а тождество E соответствует дифункциональному, обобщению отношения эквивалентности на множестве.
Отношения могут быть ранжированы по шкале Schein, которая подсчитывает количество концепций, необходимых для охвата отношения. [34] Структурный анализ отношений с концепциями обеспечивает подход к интеллектуальному анализу данных . [35]
Особые отношения
- Утверждение : если R - последовательное отношение, а R T - его транспонирование, то где это м × м тождественное соотношение.
- Предложение : если R - сюръективное отношение , то где является тождественным отношением n × n .
Дифункциональный
Среди однородных отношений на множестве отношения эквивалентности выделяются своей способностью разбивать множество. Идея бинарных отношений в целом состоит в том, чтобы разделить объекты с помощью различения атрибутов. Один из способов сделать это - использовать промежуточный набор индикаторов Z = { x, y, z , ...} . Секционирование отношение R = ФГ Т представляет собой композицию отношений с использованием одновалентных отношений F ⊆ × Z и G ⊆ B × Z .
Логическая матрица такого отношения R может быть повторно выполнена в виде блока матрицы с блоками единиц по диагонали. В терминах исчисления отношений Жак Риге в 1950 году показал, что такие отношения удовлетворяют включению
- [36]
Он назвал эти отношения дифункциональными, поскольку композиция FG T включает однолистные отношения, обычно называемые функциями .
Используя обозначение { y : xRy } = xR , дифункциональное отношение также можно охарактеризовать как отношение R такое, что везде, где x 1 R и x 2 R имеют непустое пересечение, эти два множества совпадают; формально х 1 R ∩ X 2 R ≠ ∅ влечет х 1 Р = х 2 R . [37]
В 1997 году исследователи обнаружили «полезность двоичной декомпозиции на основе дифункциональных зависимостей в управлении базами данных ». [38] Кроме того, дифункциональные отношения имеют фундаментальное значение при изучении бисимуляций . [39]
В контексте однородных отношений отношение частичной эквивалентности является дифункциональным.
В теории автоматов термин прямоугольное отношение также использовался для обозначения дифункционального отношения. Эта терминология напоминает тот факт, что, когда они представлены в виде логической матрицы, столбцы и строки дифункционального отношения могут быть расположены в виде блочно-диагональной матрицы с прямоугольными блоками истинности на (асимметричной) главной диагонали. [40]
Тип Феррера
Строгий порядок на множестве является однородным отношением , возникающим в теории порядка . В 1951 году Жак Риге принял порядок разбиения целого числа, названный диаграммой Феррерса , чтобы распространить упорядочение на бинарные отношения в целом. [41]
Соответствующая логическая матрица общего бинарного отношения имеет строки, заканчивающиеся последовательностью единиц. Таким образом, точки диаграммы Феррера заменяются на точки и выравниваются по правому краю матрицы.
Алгебраическое утверждение, необходимое для отношения R типа Феррерса, имеет следующий вид:
Если одно из отношений относится к типу Феррерса, то все они. [30]
Контакт
Предположим , что В представляет собой силовой агрегат из А , множество всех подмножеств из А . Тогда отношение g является контактным, если оно удовлетворяет трем свойствам:
- ∀ х в А , У = { х } означает XG Y .
- Y ⊆ Z и XG Y означает XG Z .
- ∀ у в Y , YG Z и XG Y означает XG Z .
Отношение принадлежности к множеству , ε = "является элементом", удовлетворяет этим свойствам, поэтому ε является отношением контакта. Понятие общего контактного отношения было введено Георгом Ауманом в 1970 году. [42] [43]
С точки зрения исчисления отношений, достаточные условия для отношения контакта включают:
- где является обратным к множеству принадлежностей (∈). [44] : 280
Предзаказ R \ R
Каждое отношение R порождает предпорядок R \ R, который является левой невязкой . [45] Что касается обратного и дополнительного, Формируя диагональ , соответствующая строка R T и столбец матрицыбудут иметь противоположные логические значения, поэтому на диагонали все нули. потом
- так что R \ R - рефлексивное отношение .
Для того, чтобы показать транзитивности , один требует , чтобы ( R \ R ) ( R \ R ) ⊂ R \ R . Напомним , что X = R \ R является крупнейшим отношение такое , что RX ⊂ R . потом
- (повторить)
- (Правило Шредера)
- (дополнение)
- (определение)
Включение соотношение Ω на множестве мощности из U можно получить таким образом от членства относительно Е на подмножества U :
- [44] : 283
Граница отношения
Для отношения R подотношение, называемое его бахромой , определяется как
Когда R является отношение частичной идентичности, бифункциональное, или блок по диагонали отношение, то бахрома ( R ) = R . В противном случае оператор бахромы выбирает граничное подотношение, описанное в терминах его логической матрицы: бахрома ( R ) - это боковая диагональ, если R - верхний правый треугольный линейный порядок или строгий порядок . Бахрома ( R ) - это бахрома блока, если R иррефлексивно () или верхний правый блок треугольный. Бахрома ( R ) - это последовательность граничных прямоугольников, когда R относится к типу Феррера.
С другой стороны, Fringe ( R ) =, когда R - плотный , линейный, строгий порядок. [44]
Математические кучи
Для двух наборов A и B набор бинарных отношений между нимиможет быть оснащен троичной операцией где b T обозначает обратное отношение к b . В 1953 году Виктор Вагнер использовал свойства этой троичной операции для определения полукучей, куч и обобщенных куч. [46] [47] Контраст гетерогенных и однородных отношений подчеркивается этими определениями:
В работах Вагнера есть приятная симметрия между кучами, полукучками и обобщенными кучами, с одной стороны, и группами, полугруппами и обобщенными группами, с другой. По существу, различные типы полугруды появляются всякий раз , когда мы рассматриваем бинарные отношения (и частичное взаимно однозначное отображения) между разными множествами A и B , в то время как различные типы полугрупп появляются в том случае , когда = B .
- Кристофер Холлингс, «Математика через железный занавес: история алгебраической теории полугрупп» [48]
Смотрите также
- Система рерайтинга тезисов
- Аддитивное отношение , многозначный гомоморфизм между модулями
- Аллегория (теория категорий)
- Категория отношений , категория, имеющая множества как объекты и бинарные отношения как морфизмы.
- Confluence (переписывание терминов) , обсуждает несколько необычных, но фундаментальных свойств бинарных отношений.
- Соответствие (алгебраическая геометрия) , бинарное отношение, определяемое алгебраическими уравнениями
- Диаграмма Хассе , графическое средство для отображения отношения порядка
- Структура заболеваемости, неоднородное отношение между множеством точек и линий
- Логика родственников , теория отношений Чарльза Сандерса Пирса
- Теория порядка , исследует свойства отношений порядка.
Заметки
- ^ Авторы, которые рассматривают бинарные отношения только как частный случай n -арных отношений для произвольного n, обычно пишут Rxy как частный случай Rx 1 ... x n ( префиксная запись ). [9]
Рекомендации
- ^ a b c d e f g h Кодд, Эдгар Франк (июнь 1970 г.). «Реляционная модель данных для больших общих банков данных» (PDF) . Коммуникации ACM . 13 (6): 377–387. DOI : 10.1145 / 362384.362685 . S2CID 207549016 . Проверено 29 апреля 2020 .
- ^ «Окончательный словарь высшего математического жаргона - отношения» . Математическое хранилище . 2019-08-01 . Проверено 11 декабря 2019 .
- ^ «Определение отношения - Math Insight» . mathinsight.org . Проверено 11 декабря 2019 .
- ^ a b Эрнст Шредер (1895) Алгебра и логика относительного , через Интернет-архив
- ^ a b К. И. Льюис (1918) Обзор символической логики , страницы 269–279, через Интернет-архив
- ^ a b c Гюнтер Шмидт , 2010. Реляционная математика . Издательство Кембриджского университета, ISBN 978-0-521-76268-7 , гл. 5
- ^ Джейкобсон, Натан (2009), Базовая алгебра II (2-е изд.) § 2.1.
- ^ Enderton 1977 , Ч. 3. стр. 40
- ^ Ганс Гермес (1973). Введение в математическую логику . Hochschultext (Springer-Verlag). Лондон: Спрингер. ISBN 3540058192. ISSN 1431-4657 . Раздел II.§1.1.4
- ^ Суппес, Патрик (1972) [первоначально опубликовано D. van Nostrand Company в 1960 году]. Аксиоматическая теория множеств . Дувр. ISBN 0-486-61630-4.
- ^ Смуллян, Раймонд М .; Фиттинг, Мелвин (2010) [пересмотренное и исправленное переиздание работы, первоначально опубликованной в 1996 году издательством Oxford University Press, Нью-Йорк]. Теория множеств и проблема континуума . Дувр. ISBN 978-0-486-47484-7.
- ^ Леви, Азриэль (2002) [переиздание работы, опубликованной Springer-Verlag, Берлином, Гейдельбергом и Нью-Йорком в 1979 году]. Основная теория множеств . Дувр. ISBN 0-486-42079-5.
- ^ Шмидт, Гюнтер ; Стрёляйн, Томас (2012). Отношения и графы: дискретная математика для компьютерных ученых . Определение 4.1.1 .: Springer Science & Business Media. ISBN 978-3-642-77968-8.CS1 maint: location ( ссылка )
- ^ Христодулос А. Флудас ; Панос М. Пардалос (2008). Энциклопедия оптимизации (2-е изд.). Springer Science & Business Media. С. 299–300. ISBN 978-0-387-74758-3.
- ^ а б Майкл Винтер (2007). Категории Гогена: категориальный подход к L-нечетким отношениям . Springer. стр. x – xi. ISBN 978-1-4020-6164-6.
- ^ Относительная одновременность в Викиучебнике
- ^ Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1986). Теория дизайна . Издательство Кембриджского университета . п. 15.. 2-е изд. (1999) ISBN 978-0-521-44432-3
- ^ a b c d Килп, Кнауэр и Михалев: с. 3. Те же четыре определения используются ниже:
- Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. п. 506. ISBN. 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 г., Proceedings , Lecture Notes in Computer Science, 4736 , Springer, . С. 285-302, DOI : 10.1007 / 978-3-540-74788-8_18
- ^ Яо, ГГ; Вонг, СКМ (1995). «Обобщение приблизительных наборов с использованием отношений между значениями атрибутов» (PDF) . Труды 2-й Ежегодной совместной конференции по информационным наукам : 30–33..
- ^ Джон К. Баэз (6 ноября 2001 г.). «Квантовая механика над коммутативной оснасткой» . Группа новостей : sci.physics.research . Usenet: [email protected] . Проверено 25 ноября 2018 года .
- ^ Droste, М., & Kuich, W. (2009). Полукольца и формальные степенные ряды. Справочник по взвешенным автоматам , 3–28. DOI : 10.1007 / 978-3-642-01492-5_1 , стр. 7-10
- ^ Тарский, Альфред ; Гивант, Стивен (1987). Формализация теории множеств без переменных . Американское математическое общество. п. 3 . ISBN 0-8218-1041-3.
- ^ М.Э. Мюллер (2012). Открытие реляционных знаний . Издательство Кембриджского университета. п. 22. ISBN 978-0-521-19021-3.
- ^ Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. п. 496. ISBN. 978-3-540-67995-0.
- ^ Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Брукс / Коул, стр. 160, ISBN 0-534-39900-2
- ^ Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, стр. 158.
- ^ Флашка, В .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007). Транзитивные замыкания двоичных отношений I (PDF) . Прага: Школа математики - Карлов университет физики. п. 1. Архивировано из оригинального (PDF) 02.11.2013.Лемма 1.1 (iv). В этом источнике асимметричные отношения называются «строго антисимметричными».
- ↑ Джозеф Г. Розенштейн, Линейные порядки , Academic Press, 1982, ISBN 0-12-597680-1 , стр. 4
- ^ а б Шмидт, Гюнтер ; Стрёляйн, Томас (2012). Отношения и графы: дискретная математика для компьютерных ученых . Springer Science & Business Media. п. 77. ISBN 978-3-642-77968-8.
- ^ Майкл Винтер (2007). Категории Гогена: категориальный подход к L-нечетким отношениям . Springer. стр. x – xi. ISBN 978-1-4020-6164-6.
- ^ Г. Шмидт, Клаудиа Халтенспергер и Майкл Винтер (1997) «Алгебра гетерогенных отношений», глава 3 (страницы 37–53) в реляционных методах в компьютерных науках , достижениях в области компьютерных наук, книгах Спрингера.ISBN 3-211-82971-7
- ^ R. Berghammer & M. Winter (2013) "Распад отношений на концепции решеток", Fundamenta Informaticae 126 (1): 37-82 DOI : 10,3233 / FI-2013-871
- ^ Ki Повесьте Ким (1982) Логическая Теория матрицы и приложение , стр 37, Marcel DekkerISBN 0-8247-1788-0
- ^ Али Джауа, Рехаб Дувайри, Самир Эллуми и Садок Бен Яхия (2009) «Интеллектуальный анализ данных, рассуждения и дополнительный поиск информации посредством нерасширяемого прямоугольного покрытия отношения», страницы 199–210 в Отношениях и алгебрах Клини в информатике , Лекционные заметки в Компьютерные науки 5827, Springer MR2781235
- ^ Жак Riguet (1950) "Quelques propriétés де difonctionelles отношения", Comptes Rendus 230: 1999-2000
- ^ Крис Бринк; Вольфрам Каль; Гюнтер Шмидт (1997). Реляционные методы в информатике . Springer Science & Business Media. п. 200. ISBN 978-3-211-82971-4.
- ^ Али Jaoua, Надин Belkhiter, Хабиб Ounalli, и Теодор Moukam (1997) "Базы данных", страницы 197-210 в реляционные методы в области компьютерных наук ,редакцией Криса Brink, Wolfram Кэхлом, и Гюнтер Шмидт , Springer Science & Business MediaISBN 978-3-211-82971-4
- ^ Гамм, HP; Заррад, М. (2014). «Коалгебраические симуляции и сравнения». Коалгебраические методы в компьютерных науках . Конспект лекций по информатике . 8446 . п. 118. DOI : 10.1007 / 978-3-662-44124-4_7 . ISBN 978-3-662-44123-7.
- ^ Юлиус Рихард Бючи (1989). Конечные автоматы, их алгебры и грамматики: к теории формальных выражений . Springer Science & Business Media. С. 35–37. ISBN 978-1-4613-8853-1.
- ^ J. Riguet (1951) "Les Relations de Ferrers", Comptes Rendus 232: 1729,30
- ^ Георг Ауманн (1971). «Контакт-Реляционен» . Sitzungsberichte der Mathematisch-Physikalischen Klasse der Bayerischen Akademie der Wissenschaften München . 1970 (II): 67–77.
- Перейти ↑ Anne K. Steiner (1970) Review: Kontakt-Relationen from Mathematical Reviews
- ^ a b c Гюнтер Шмидт (2011) Relational Mathematics , страницы 211-15, Cambridge University PressISBN 978-0-521-76268-7
- ^ В этом контексте символ ""не означает" установить разницу ".
- ^ Виктор Вагнер (1953) "Теория обобщенных куч и обобщенных групп", Математический сборник 32 (74): 545–632 MR.0059267
- ^ CD Холлингс и М. В. Лоусон (2017) Теория Вагнера обобщенных куч , книги СпрингераISBN 978-3-319-63620-7 MR3729305
- ^ Кристофер Холлингс (2014) Математика через железный занавес: история алгебраической теории полугрупп , стр. 265, История математики 41, Американское математическое обществоISBN 978-1-4704-1493-1
Библиография
- Шмидт, Гюнтер ; Стрёляйн, Томас (2012). «Глава 3: Гетерогенные отношения» . Отношения и графы: дискретная математика для компьютерных ученых . Springer Science & Business Media. ISBN 978-3-642-77968-8.
- Эрнст Шредер (1895) Algebra der Logik, Band III , через Интернет-архив
- Кодд, Эдгар Франк (1990). Реляционная модель для управления базами данных: версия 2 (PDF) . Бостон: Эддисон-Уэсли . ISBN 978-0201141924.
- Эндертон, Герберт (1977). Элементы теории множеств . Бостон: Academic Press . ISBN 978-0-12-238440-0.
- Килп, Мати; Кнауэр, Ульрих; Михалев, Александр (2000). Моноиды, акты и категории: с приложениями к сплетенным изделиям и графам . Берлин: Де Грюйтер . ISBN 978-3-11-015248-7.
- Пирс, Чарльз Сандерс (1873). "Описание обозначения логики родственников, являющееся результатом обобщения представлений логического исчисления Буля" . Воспоминания Американской академии искусств и наук . 9 (2): 317–178. DOI : 10.2307 / 25058006 . hdl : 2027 / hvd.32044019561034 . JSTOR 25058006 . Проверено 5 мая 2020 .
- Шмидт, Гюнтер (2010). Реляционная математика . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-76268-7.
Внешние ссылки
- СМИ, связанные с бинарными отношениями на Викискладе?
- "Бинарные отношения" , Энциклопедия математики , EMS Press , 2001 [1994]