WikiDer > Бинарное отношение

В математика (конкретно теория множеств), а бинарное отношение над наборы Икс и Y это подмножество из Декартово произведение Икс × Y; то есть это набор заказанные пары (Икс, у) состоящий из элементов Икс в Икс и у в Y.^[1] Он кодирует информацию о связь: элемент Икс относится к элементу у, если и только если пара (Икс, у) принадлежит набору. Бинарное отношение - наиболее изученный частный случай п = 2 из п-арное отношение над наборами Икс₁, ..., Икс_п, которое является подмножеством декартова произведения Икс₁ × ... × Икс_п.^[1][2]

Примером бинарного отношения является "разделяет"отношение над множеством простые числа ${displaystyle mathbb {P}}$ и набор целые числа ${displaystyle mathbb {Z}}$, в котором каждое простое число п относится к каждому целому числу z это несколько из п, но не до целого числа, не кратного п. В этом отношении, например, простое число 2 связано с такими числами, как -4, 0, 6, 10, но не с 1 или 9, точно так же, как простое число 3 связано с 0, 6 и 9, но не до 4 или 13.

Бинарные отношения используются во многих разделах математики для моделирования самых разных понятий. К ним, среди прочего, относятся:

• "больше, чем", "равно", и" разделяет "отношения в арифметика;
• "конгруэнтно"отношения в геометрия;
• отношение "смежно с" в теория графов;
• это ортогональный к "отношение в линейная алгебра.

А функция можно определить как особый вид бинарных отношений.^[3] Бинарные отношения также широко используются в Информатика.

Бинарное отношение над множествами Икс и Y является элементом набор мощности из Икс × Y. Поскольку последний набор упорядочен включение (⊆) каждое отношение имеет место в решетка подмножеств Икс × Y.

Поскольку отношения являются наборами, ими можно управлять с помощью операций над наборами, включая союз, пересечение, и дополнение, и удовлетворяющие законам алгебра множеств. Помимо этого, такие операции, как разговаривать отношения и состав отношений доступны, удовлетворяя законам исчисление отношений, для которых есть учебники Эрнст Шредер,^[4] Кларенс Льюис,^[5] и Гюнтер Шмидт.^[6] Более глубокий анализ отношений включает разложение их на подмножества, называемые концепции, и поместив их в полная решетка.

В некоторых системах аксиоматическая теория множеств, отношения распространяются на классы, которые являются обобщениями множеств. Это расширение необходимо, среди прочего, для моделирования концепций «является элементом» или «является подмножеством» в теории множеств, не сталкиваясь с логическими несоответствиями, такими как Парадокс Рассела.

Условия переписка,^[7] диадические отношения и двухместное отношение являются синонимами бинарного отношения, хотя некоторые авторы используют термин «бинарное отношение» для любого подмножества декартова произведения. Икс × Y без ссылки на Икс и Y, и зарезервируйте термин "соответствие" для бинарного отношения со ссылкой на Икс и Y.

Определение

Данные наборы Икс и Y, то Декартово произведение Икс × Y определяется как {(Икс, у) | Икс ∈ Икс ∧у ∈ Y}, а его элементы называются упорядоченными парами.

А бинарное отношение р над наборами Икс и Y это подмножество Икс × Y.^[1][8] Набор Икс называется домен^[1] или же набор отправления из р, а множество Y то codomain или же набор пунктов назначения из р. Чтобы указать выбор наборов Икс и Y, некоторые авторы определяют бинарное отношение или же переписка как заказанный тройной (Икс, Y, грамм), куда грамм это подмножество Икс × Y называется график бинарного отношения. Заявление (Икс, у) ∈ р читает "Икс является р-относится к у"и обозначается xRy.^{[4][5][6][примечание 1]} В область определения или же активный домен^[1] из р это набор всех Икс такой, что xRy по крайней мере для одного у. В кодомен определения, активный кодомен,^[1] изображение или же классифицировать из р это набор всех у такой, что xRy по крайней мере для одного Икс. В поле из р является объединением области определения и области определения.^[10][11][12]

Когда Икс = Y, бинарное отношение называется однородное отношение (или же эндорреляция). Чтобы подчеркнуть тот факт, что Икс и Y могут быть разными, бинарное отношение также называется гетерогенное отношение.^[13][14][15]

В бинарных отношениях важен порядок элементов; если Икс ≠ у тогда xRy, но yRx может быть истинным или ложным независимо от xRy. Например, 3 делит 9, но 9 не делит 3.

Пример

Следующий пример показывает, что выбор кодомена важен. Предположим, есть четыре объекта А = {мяч, машина, кукла, чашка} и четыре человека B = {Джон, Мэри, Ян, Венера}. Возможное отношение на А и B это отношение "принадлежит", заданное р = {(мяч, Джон), (кукла, Мэри), (машина, Венера)}. То есть Джон владеет мячом, Мэри - куклой, а Венера - машиной. Никто не владеет чашей, и Ян ничем не владеет. В комплекте, р не вовлекает Яна, и поэтому р можно было бы рассматривать как подмножество А × {Джон, Мэри, Венера}, т.е. отношение над А и {Джон, Мэри, Венера}.

Особые типы бинарных отношений

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

Некоторые важные типы бинарных отношений р над наборами Икс и Y перечислены ниже.

Свойства уникальности:

• Инъекционный (также называемый лево-уникальный^[16]): ∀Икс ∈ Икс ∧ ∀z ∈ Икс ∧ ∀у ∈ Y, если xRy ∧ zRy тогда Икс = z. Для такого отношения {Y} называется а первичный ключ из р.^[1] Например, зеленые и синие бинарные отношения на диаграмме инъективны, а красный - нет (поскольку он связывает и -1, и 1 с 1), ни черный (поскольку он связывает и -1, и 1 с 0). .
• Функциональный (также называемый право-уникальный,^[16] правоопределенный^[17] или же однозначный^[6]): ∀Икс ∈ Икс ∧ ∀у ∈ Y ∧ ∀z ∈ Y, если xRy и xRz тогда у = z. Такое бинарное отношение называется частичная функция. Для такого отношения {Икс} называется первичный ключ из р.^[1] Например, красные и зеленые бинарные отношения на диаграмме являются функциональными, а синее - нет (поскольку оно связывает 1 как с −1, так и с 1), ни с черным (поскольку оно связывает 0 с −1 и 1). .
• Один к одному: инъекционно-функциональный. Например, бинарные отношения зеленого цвета на диаграмме взаимно однозначны, а отношения красного, синего и черного - нет.
• Один ко многим: инъективно и не функционально. Например, синее двоичное отношение на диаграмме - один ко многим, а красный, зеленый и черный - нет.
• Многие к одному: функциональный, а не инъекционный. Например, красное двоичное отношение на диаграмме - «многие к одному», а зеленый, синий и черный - нет.
• Многие-ко-многим: не инъективно и не функционально. Например, черное бинарное отношение на диаграмме - это многие ко многим, а красный, зеленый и синий - нет.

Свойства целостности (определяется, только если домен Икс и codomain Y указаны):

• Серийный (также называемый левый итог^[16]): для всех Икс в Икс существует у в Y такой, что xRy. Другими словами, область определения р равно Икс. Это свойство, хотя его еще называют общий некоторыми авторами,^{[нужна цитата]} отличается от определения Connex (также называемый общий некоторыми авторами)^{[нужна цитата]} в разделе Характеристики. Такое бинарное отношение называется многозначная функция. Например, красные и зеленые двоичные отношения на диаграмме являются последовательными, а синее - нет (поскольку оно не связывает -1 ни с каким действительным числом), ни черное (поскольку оно не связывает 2 ни с одним действительным числом. ).
• Сюръективный (также называемый правильный итог^[16] или же на): для всех у в Y, существует Икс в Икс такой, что xRy. Другими словами, область определения р равно Y. Например, зеленые и синие бинарные отношения на диаграмме сюръективны, а красное - нет (поскольку оно не связывает ни одно действительное число с -1), ни черное (поскольку оно не связывает какое-либо действительное число с 2. ).

Свойства уникальности и полноты (можно определить, только если домен Икс и codomain Y указаны):

• А функция: бинарное отношение, которое является функциональным и последовательным. Например, красные и зеленые бинарные отношения на диаграмме являются функциями, а синие и черные - нет.
• An инъекция: инъективная функция. Например, зеленое двоичное отношение на диаграмме является инъекцией, а красный, синий и черный - нет.
• А сюрприз: сюръективная функция. Например, зеленое бинарное отношение на диаграмме является сюрпризом, а красный, синий и черный - нет.
• А биекция: функция, которая является инъективной и сюръективной. Например, зеленое бинарное отношение на диаграмме является взаимно однозначным, а красный, синий и черный - нет.

Операции над бинарными отношениями

Союз

Если р и S бинарные отношения над множествами Икс и Y тогда р ∪ S = {(Икс, у) | xRy ∨ xSy} это союзные отношения из р и S над Икс и Y.

Элементом идентичности является пустое отношение. Например, ≤ - это объединение <и =, а ≥ - объединение> и =.

Пересечение

Если р и S бинарные отношения над множествами Икс и Y тогда р ∩ S = {(Икс, у) | xRy ∧ xSy} это отношение пересечения из р и S над Икс и Y.

Элемент идентичности - это универсальное отношение. Например, отношение «делится на 6» - это пересечение отношений «делится на 3» и «делится на 2».

Сочинение

Если р является бинарным отношением над множествами Икс и Y, и S является бинарным отношением над множествами Y и Z тогда S ∘ р = {(Икс, z) | там ∃ у ∈ Y такой, что xRy ∧ ySz} (также обозначается р; S) это отношение композиции из р и S над Икс и Z.

Элементом идентичности является отношение идентичности. Получатель чего-то р и S в обозначениях S ∘ р, используемый здесь, соответствует стандартному порядку обозначений для состав функций. Например, композиция "является матерью" "является родителем" урожайности "является бабушкой и дедушкой по материнской линии", в то время как композиция "является родителем" ", является матерью" урожайности "является бабушкой".

Converse

Если р является бинарным отношением над множествами Икс и Y тогда р^Т = {(у, Икс) | xRy} это обратное отношение из р над Y и Икс.

Например, = является обратным самому себе, как и ≠, а <и> являются обратными друг другу, как и ≤ и ≥. Бинарное отношение равно обратному тогда и только тогда, когда оно симметричный.

Дополнение

Если р является бинарным отношением над множествами Икс и Y тогда р = {(Икс, у) | ¬xRy} (также обозначается р или ¬р) это дополнительные отношения из р над Икс и Y.

Например, = и ≠ являются дополнениями друг друга, как и ⊆ и ⊈, ⊇ и ⊉, и ∈ и ∉, а для общее количество заказов, а также <и ≥, а также> и ≤.

Дополнение обратное отношение р^Т является обратным дополнению: ${displaystyle {overline {R ^ {mathsf {T}}}} = {ar {R}} ^ {mathsf {T}}.}$

Если Икс = Y, дополнение обладает следующими свойствами:

• Если отношение симметрично, то и дополнение - тоже.
• Дополнение рефлексивного отношения иррефлексивно - и наоборот.
• Дополнение строгий слабый порядок является полным предварительным заказом, и наоборот.

Ограничение

Если р является бинарным отношением над множеством Икс и S это подмножество Икс тогда р_|S = {(Икс, у) | xRy ∧ Икс ∈ S ∧ у ∈ S} это ограничительное отношение из р к S над Икс.

Если р является бинарным отношением над множествами Икс и Y и S это подмножество Икс тогда р_|S = {(Икс, у) | xRy ∧ Икс ∈ S} это отношение левого ограничения из р к S над Икс и Y.

Если р является бинарным отношением над множествами Икс и Y и S это подмножество Y тогда р^|S = {(Икс, у) | xRy ∧ у ∈ S} это право-ограничение из р к S над Икс и Y.

Если отношение рефлексивный, иррефлексивный, симметричный, антисимметричный, асимметричный, переходный, общий, трихотомический, а частичный заказ, общий заказ, строгий слабый порядок, общий предварительный заказ (слабый порядок) или отношение эквивалентности, то его ограничения тоже.

Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, т.е. в общем случае не равнозначно. Например, ограничение отношения "Икс является родителем у"к самкам дает отношение"Икс мать женщины у"; его переходное закрытие не связывает женщину с ее бабушкой по отцовской линии. С другой стороны, переходное закрытие" является родителем "является" является предком "; его ограничение женщинами действительно связывает женщину с ее бабушкой по отцовской линии.

Кроме того, различные концепции полнота (не путать с «полным») не переносятся на ограничения. Например, над действительные числа свойство отношения ≤ состоит в том, что каждый непустой подмножество S из р с верхняя граница в р имеет наименьшая верхняя граница (также называемый супремумом) в р. Однако для рациональных чисел этот супремум не обязательно является рациональным, поэтому то же свойство не выполняется при ограничении отношения ≤ на рациональные числа.

Бинарное отношение р над наборами Икс и Y как говорят содержал в отношении S над Икс и Y, написано р ⊆ S, если р это подмножество S, то есть, ∀Икс ∈ Икс ∧ у ∈ Y, если xRy, тогда xSy. Если р содержится в S и S содержится в р, тогда р и S называются равный написано р = S. Если р содержится в S но S не содержится в р, тогда р как говорят меньше чем S, написано р ⊊ S. Например, на рациональное число, отношение> меньше ≥ и равно композиции > ∘ >.

Матричное представление

Бинарные отношения над множествами Икс и Y можно представить алгебраически как логические матрицы проиндексировано Икс и Y с записями в Логическое полукольцо (сложение соответствует ИЛИ, а умножение - И), где матрица сложения соответствует союзу отношений, матричное умножение соответствует композиции отношений (отношения над Икс и Y и отношение над Y и Z),^[18] то Произведение Адамара соответствует пересечению отношений, нулевая матрица соответствует пустому отношению, а матрица единиц соответствует универсальному отношению. Однородные отношения (когда Икс = Y) образуют матричное полукольцо (действительно, матричная полуалгебра над булевым полукольцом), где единичная матрица соответствует тождественному отношению.^[19]

Наборы против классов

Определенные математические "отношения", такие как "равно", "подмножество" и "член", не могут пониматься как бинарные отношения, как определено выше, поскольку их домены и домены не могут считаться наборами в обычных системах. из аксиоматическая теория множеств. Например, если мы попытаемся смоделировать общую концепцию «равенства» как бинарное отношение =, мы должны принять домен и домен как «класс всех множеств», что не является множеством в обычной теории множеств.

В большинстве математических контекстов ссылки на отношения равенства, членства и подмножества безвредны, потому что их можно неявно понимать как ограниченные некоторым набором в контексте. Обычный способ решения этой проблемы - выбрать "достаточно большой" набор А, который содержит все интересующие объекты и работает с ограничением =_А вместо =. Точно так же "подмножество" отношения ⊆ должно быть ограничено, чтобы иметь домен и домен P (А) (набор мощности конкретного набора А): полученное отношение множества можно обозначить через ⊆_А. Кроме того, отношение "член" должно быть ограничено, чтобы иметь домен А и кодомен P (А) для получения бинарного отношения ∈_А это набор. Бертран Рассел показал, что предположение, что ∈ определено на всех множествах, приводит к противоречие в наивной теории множеств.

Другое решение этой проблемы - использовать теорию множеств с соответствующими классами, такими как NBG или же Теория множеств Морса – Келли, и разрешить домену и codomain (и, следовательно, графу) быть правильные классы: в такой теории равенство, принадлежность и подмножество являются бинарными отношениями без особых комментариев. (Необходимо внести небольшие изменения в концепцию упорядоченного тройного (Икс, Y, грамм), поскольку обычно правильный класс не может быть членом упорядоченного кортежа; или, конечно, в этом контексте можно идентифицировать бинарное отношение с его графом.)^[20] С помощью этого определения можно, например, определить бинарное отношение для каждого набора и его набора мощности.

Однородное отношение

А однородное отношение (также называемый эндорреляция) над множеством Икс является бинарным отношением над Икс и сам, т.е. это подмножество декартова произведения Икс × Икс.^[15][21][22] Это также просто называют бинарным отношением над Икс. Примером однородного отношения является отношение родство, где отношения над людьми.

Однородное отношение р над набором Икс можно отождествить с ориентированный простой граф, разрешающий петли, или если это симметричный, с неориентированный простой граф, разрешающий циклы, куда Икс - множество вершин и р - множество ребер (есть ребро из вершины Икс к вершине у если и только если xRy). Это называется отношение смежности графа.

Множество всех однородных отношений ${displaystyle {mathcal {B}} (X)}$ над набором Икс это набор 2^{Икс × Икс} который является Булева алгебра дополнен инволюция отображения отношения к его обратное отношение. Учитывая состав отношений как бинарная операция на ${displaystyle {mathcal {B}} (X)}$, он образует инверсная полугруппа.

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

Некоторые важные частные однородные отношения над множеством Икс находятся:

• то пустое отношение E = ∅ ⊆ Икс × Икс;
• то универсальное отношение U = Икс × Икс;
• то отношение идентичности я = {(Икс, Икс) | Икс ∈ Икс}.

Для произвольных элементов Икс и у из Икс:

• xEy не держит никогда;
• xUy держит всегда;
• xIy выполняется тогда и только тогда, когда Икс = у.

Характеристики

Некоторые важные свойства однородного отношения р над набором Икс могут быть:

Рефлексивный

∀Икс ∈ Икс, xRx. Например, ≥ - рефлексивное отношение, а> - нет.

Нерефлексивный (или же строгий)

∀Икс ∈ Икс, ¬xRx. Например,> - это иррефлексивное отношение, а ≥ - нет.

Coreflexive

∀Икс ∈ Икс ∧ ∀у ∈ Икс, если xRy тогда Икс = у.^[23] Например, отношение целых чисел, в котором каждое нечетное число связано с самим собой, является коререфлексивным отношением. Отношение равенства является единственным примером как рефлексивного, так и коререфлексивного отношения, а любое корефлексивное отношение является подмножеством отношения идентичности.

Квазирефлексивный

∀Икс ∈ Икс ∧ ∀у ∈ Икс, если xRy тогда xRx ∧ год.

Предыдущие 4 альтернативы далеко не исчерпывающие; например, красное бинарное отношение у = Икс² приведено в разделе Особые типы бинарных отношений не является ни иррефлексивным, ни корефлексивным, ни рефлексивным, так как содержит пару (0, 0), и (2, 4), но нет (2, 2), соответственно. Последние два факта также исключают квазирефлексивность.

Симметричный

∀Икс ∈ Икс ∧ ∀у ∈ Икс, если xRy тогда yRx. Например, «является кровным родственником» является симметричным отношением, потому что Икс является кровным родственником у если и только если у является кровным родственником Икс.

Антисимметричный

∀Икс ∈ Икс ∧ ∀у ∈ Икс, если xRy ∧ yRx тогда Икс = у. Например, ≥ - антисимметричное отношение; так это>, но бессмысленно (условие в определении всегда ложно).^[24]

Асимметричный

∀Икс ∈ Икс ∧ ∀у ∈ Икс, если xRy тогда ¬yRx. Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно.^[25] Например,> - это асимметричное отношение, а ≥ - нет.

Опять же, предыдущие 3 альтернативы далеко не исчерпывающие; в качестве примера с натуральными числами отношение xRy определяется Икс > 2 не является ни симметричным, ни антисимметричным, не говоря уже об асимметричном.

Переходный

∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если xRy ∧ yRz тогда xRz. Транзитивное отношение иррефлексивно тогда и только тогда, когда оно асимметрично.^[26] Например, «является предком» является транзитивным отношением, а «является родителем» - нет.

Антитранзитивный

∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если xRy и yRz тогда никогда xRz.

Ко-транзитивный

если дополнение р транзитивен. То есть, ∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если xRz, тогда xRy ∨ yRz. Это используется в псевдо-заказы в конструктивной математике.

Квазитранзитивный

∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если xRy ∧ yRz но ни то, ни другое yRx ни zRy, тогда xRz но ¬zRx.

Транзитивность несравнимости

∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если Икс,у несравненные w.r.t. р и у,z есть, тогда Икс,z тоже. Это используется в слабые порядки.

Опять же, предыдущие 5 альтернатив не являются исчерпывающими. Например, отношение xRy если (у = 0 или же у = Икс+1) не удовлетворяет ни одному из этих свойств. С другой стороны, пустое отношение тривиально им всем удовлетворяет.

Плотный

∀Икс ∈ Икс ∧ ∀у ∈ Икс такой, что xRy, немного z ∈ Икс можно найти так, что xRz ∧ zRy. Это используется в плотные заказы.

Connex

∀Икс ∈ Икс ∧ ∀у ∈ Икс, xRy ∨ yRx. Это свойство иногда называют «итоговым», что отличается от определений «всего», приведенных в разделе. Особые типы бинарных отношений.

Semiconnex

∀Икс ∈ Икс ∧ ∀у ∈ Икс, если Икс ≠ у тогда xRy ∨ yRx. Это свойство иногда называют «итоговым», что отличается от определений «всего», приведенных в разделе. Особые типы бинарных отношений.

Трихотомический

∀Икс ∈ Икс ∧ ∀у ∈ Икс, ровно один из xRy, yRx или же Икс = у держит. Например,> - это трихотомическое отношение, а отношение «делится» на натуральные числа - нет.^[27]

Правый евклидов (или просто Евклидово)

∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если xRy ∧ xRz тогда yRz. Например, = - евклидово отношение, потому что если Икс = у и Икс = z тогда у = z.

Левый евклидов

∀Икс ∈ Икс ∧ ∀у ∈ Икс ∧ ∀z ∈ Икс, если yRx ∧ zRx тогда yRz.

Серийный (или же левый итог)

∀Икс ∈ Икс, там ∃ у ∈ Икс такой, что xRy. Например,> - это последовательное отношение целых чисел. Но это не последовательное отношение по положительным целым числам, потому что нет у в натуральных числах такие, что 1 > у.^[28] Однако <является последовательным отношением к положительным целым числам, рациональным числам и действительным числам. Каждое рефлексивное отношение серийно: для данного Икс, выберите у = Икс.

Как набор^{[нужна цитата]} (или же местный)

^{[нужна цитата]} ∀Икс ∈ Икс, то учебный класс из всех у такой, что yRx это набор. (Это имеет смысл только в том случае, если разрешены отношения над соответствующими классами.) Например, обычное упорядочение <над классом порядковые номера является отношением, подобным множеству, а его обратное> - нет.

Обоснованный

каждое непустое подмножество S из Икс содержит минимальный элемент относительно р. Обоснованность подразумевает состояние нисходящей цепочки (то есть бесконечной цепочки нет ... Икс_пр...Rx₃Rx₂Rx₁ может существовать). Если аксиома зависимого выбора Предполагается, что оба условия эквивалентны.^[29][30]

А Предварительный заказ - это отношение рефлексивное и транзитивное. А общий предварительный заказ, также называемый предварительный заказ Connex или же слабый порядок, это отношение рефлексивное, транзитивное и связное.

А частичный заказ, также называемый порядок,^{[нужна цитата]} является отношением рефлексивным, антисимметричным и транзитивным. А строгий частичный порядок, также называемый строгий порядок,^{[нужна цитата]} - это иррефлексивное, антисимметричное и транзитивное отношение. А общий заказ, также называемый заказ Connex, линейный порядок, простой заказ, или же цепь, является отношением рефлексивным, антисимметричным, транзитивным и коннексным.^[31] А строгий общий порядок, также называемый строгий порядок полусложений, строгий линейный порядок, строгий простой порядок, или же строгая цепочка, является отношением, которое является иррефлексивным, антисимметричным, транзитивным и полусоединенным.

А отношение частичной эквивалентности является отношением, которое является симметричным и транзитивным. An отношение эквивалентности - это отношение рефлексивное, симметричное и транзитивное. Это также отношение, которое является симметричным, транзитивным и последовательным, поскольку эти свойства подразумевают рефлексивность.

Последствия и конфликты между свойствами однородных бинарных отношений
Последствия (синий) и конфликты (красный) между свойствами (желтый) однородных бинарных отношений. Например, любое асимметричное отношение иррефлексивно ("ASym ⇒ Irrefl"), и никакое отношение на непустом множестве не может быть одновременно иррефлексивным, и рефлексивным ("Irrefl # Refl"). Отсутствие красных краев приводит к Диаграмма Хассе.

Операции

Если р является однородным отношением над множеством Икс то каждое из следующих соотношений является однородным соотношением над Икс:

• Рефлексивное закрытие: р⁼, определяется как р⁼ = {(Икс, Икс) | Икс ∈ Икс} ∪ р или наименьшее рефлексивное отношение над Икс содержащий р. Можно доказать, что это равно пересечение всех рефлексивных отношений, содержащих р.
• Рефлексивное сокращение: р^≠, определяется как р^≠ = р {(Икс, Икс) | Икс ∈ Икс} или самый большой иррефлексивный отношение по Икс содержалась в р.
• Переходное закрытие: р⁺, определяемое как наименьшее транзитивное отношение над Икс содержащий р. Видно, что это равно пересечению всех транзитивных отношений, содержащих р.
• Рефлексивное переходное закрытие: р*, определяется как р* = (р⁺)⁼, наименьший Предварительный заказ содержащий р.
• Рефлексивное транзитивное симметричное замыкание: р^≡, определяемый как наименьший отношение эквивалентности над Икс содержащий р.

Все операции, определенные в разделе Операции над бинарными отношениями также относятся к однородным отношениям.

Однородные отношения по собственности

	Рефлексивность	Симметрия	Транзитивность	Связь	Символ	Пример
Направленный граф					→
Ненаправленный граф		Симметричный
Зависимость	Рефлексивный	Симметричный
Турнир	Нерефлексивный	Антисимметричный				Иерархия
Предварительный заказ	Рефлексивный		да		≤	Предпочтение
Всего предзаказ	Рефлексивный		да	Connex	≤
Частичный заказ	Рефлексивный	Антисимметричный	да		≤	Подмножество
Строгий частичный заказ	Нерефлексивный	Антисимметричный	да		<	Строгое подмножество
Общий заказ	Рефлексивный	Антисимметричный	да	Connex	≤	Алфавитный порядок
Строгий общий порядок	Нерефлексивный	Антисимметричный	да	Semiconnex	<	Строгий алфавитный порядок
Отношение частичной эквивалентности		Симметричный	да
Отношение эквивалентности	Рефлексивный	Симметричный	да		∼, ≡	Равенство

Перечисление

Количество различных однородных отношений над п- набор элементов 2^п2 (последовательность A002416 в OEIS):

Примечания:

• Количество иррефлексивных отношений такое же, как и количество рефлексивных отношений.
• Количество строгие частичные заказы (иррефлексивные транзитивные отношения) такие же, как у частичных порядков.
• Количество строгих слабых заказов такое же, как и общее количество предварительных заказов.
• Общие заказы - это частичные заказы, которые также являются общими предварительными заказами. Таким образом, количество предварительных заказов, которые не являются ни частичным, ни полным предварительным заказом, равно количеству предварительных заказов минус количество частичных заказов, минус общее количество предварительных заказов плюс общее количество заказов: 0, 0, 0, 3 и 85 соответственно.
• Количество отношений эквивалентности - это количество перегородки, какой Номер звонка.

Однородные отношения можно сгруппировать в пары (отношение, дополнять), за исключением п = 0 отношение является его собственным дополнением. Несимметричные можно сгруппировать в четверки (отношение, дополнение, обратный, обратное дополнение).

Примеры

• Порядковые отношения, включая строгие приказы:
  • Лучше чем
  • Больше или равно
  • Меньше, чем
  • Меньше или равно
  • Разделяет (равномерно)
  • Подмножество из
• Отношения эквивалентности:
  • Равенство
  • Параллельный с (для аффинные пространства)
  • В биекция с
  • Изоморфный
• Отношение толерантности, рефлексивное и симметричное отношение:
  • Отношение зависимости, отношение конечной терпимости
  • Отношение независимости, дополнение некоторого отношения зависимости
• Родственные отношения

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

Примечания

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

Библиография

• Кодд, Эдгар Франк (1990). Реляционная модель для управления базами данных: версия 2 (PDF). Бостон: Эддисон-Уэсли. ISBN 978-0201141924.
• Эндертон, Герберт (1977). Элементы теории множеств. Бостон: Академическая пресса. ISBN 978-0-12-238440-0.
• Килп, Мати; Кнауэр, Ульрих; Михалев, Александр (2000). Моноиды, акты и категории: с приложениями к сплетенным изделиям и графикам. Берлин: Де Грюйтер. ISBN 978-3-11-015248-7.
• Пирс, Чарльз Сандерс (1873). «Описание обозначения логики родственников, являющееся результатом обобщения концепций булевого исчисления логики». Мемуары Американской академии искусств и наук. 9 (2): 317–178. Дои:10.2307/25058006. HDL:2027 / hvd.32044019561034. JSTOR 25058006. Получено 2020-05-05.
• Шмидт, Гюнтер (2010). Реляционная математика. Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-76268-7.

внешняя ссылка

• СМИ, связанные с Бинарные отношения в Wikimedia Commons
• «Бинарное отношение», Энциклопедия математики, EMS Press, 2001 [1994]