В математике ( в частности теория множеств ), двоичное отношение над устанавливает X и Y является подмножеством декартова произведения X × Y; то есть это набор упорядоченных пар (x, y), состоящих из элементов x в X и y в Y. Он кодирует информацию отношения : элемент x связан элементу y, тогда и только тогда, когда пара (x, y) принадлежит множеству. Бинарное отношение является наиболее изученным частным случаем n = 2 n-арного отношения над множествами X 1,…, X n, которое является подмножеством декартова произведения X 1 ×… × X n.
Примером двоичного отношения является отношение «делит » по набору простых чисел и набор целых чисел в где каждое простое число p связано с каждым целым числом z, которое является кратным числа p, но не с целым числом, не кратным p. В этом отношении, например, простое число 2 связано с такими числами, как -4, 0, 6, 10, но не с 1 или 9, точно так же, как простое число 3 связано с 0, 6 и 9, но не на 4 или 13.
Бинарные отношения используются во многих разделах математики для моделирования самых разных понятий. К ним относятся, среди прочего:
A функция может быть определена как особый вид бинарного отношения. Двоичные отношения также широко используются в информатике.
Бинарное отношение над множествами X и Y является элементом набора степеней из X × Y. Поскольку последний набор упорядочен по включение (⊆), каждое отношение имеет место в решетке подмножеств X × Y.
Поскольку отношения являются наборами, ими можно манипулировать с помощью операций над наборами, включая объединение, пересечение и дополнение и удовлетворение законам алгебры множеств. Кроме того, доступны такие операции, как обратное отношения и композиция отношений, удовлетворяющих законам исчисления отношений, для которых есть учебники Авторы: Эрнст Шредер, Кларенс Льюис и Гюнтер Шмидт. Более глубокий анализ отношений включает разложение их на подмножества, называемые концептами, и их размещение в полной решетке.
В некоторых системах теории аксиоматических множеств отношения расширяются до классов, которые являются обобщениями множеств. Это расширение необходимо, среди прочего, для моделирования понятий «является элементом» или «является подмножеством» в теории множеств, не сталкиваясь с логическими несоответствиями, такими как парадокс Рассела.
Термины соответствие, двоичное отношение и двухместное отношение являются синонимами двоичного отношения, хотя некоторые авторы используют термин «двоичное отношение» для любого подмножества декартова произведения X × Y без ссылки на X и Y и зарезервируйте термин «соответствие» для бинарного отношения со ссылкой на X и Y.
Для заданных наборов X и Y декартово произведение X × Y определяется как {( х, у) | x в X и y в Y}, а его элементы называются упорядоченными парами.
A бинарное отношение R над множествами X и Y является подмножеством X × Y. Множество X называется областью или набором отправления R, а набор Y codomain или набором назначения R. чтобы указать выбор наборов X и Y, некоторые авторы определяют бинарное отношение или соответствие как упорядоченную тройку (X, Y, G), где G - подмножество X × Y называется графиком бинарного отношения. Выражение (x, y) в R читается как «x связано с R с y» и обозначается xRy. Область определения или активная область R - это множество всех x таких, что xRy по крайней мере для одного y. Кодомен определения, активный кодомен, изображение или диапазон R - это набор всех y таких, что xRy по крайней мере для одного x. Поле R является объединением его области определения и его содомена определения.
Когда X = Y, бинарное отношение называется однородным отношением (или эндорреляцией). Чтобы подчеркнуть тот факт, что X и Y могут быть разными, бинарное отношение также называется гетерогенным отношением.
В бинарном отношении важен порядок элементов; если x ≠ y, то xRy, но yRx может быть истинным или ложным независимо от xRy. Например, 3 делит 9, но 9 не делит 3.
ball | car | doll | чашка | |
---|---|---|---|---|
Джон | + | − | − | − |
Мэри | − | − | + | − |
Венера | − | + | − | − |
мяч | машина | кукла | чашка | |
---|---|---|---|---|
Джон | + | − | − | − |
Мэри | − | − | + | − |
Ян | − | − | − | − |
Венера | − | + | − | − |
Следующий пример показывает, что выбор кодомена важен. Предположим, есть четыре объекта A = {мяч, машина, кукла, чашка} и четыре человека B = {Джон, Мэри, Ян, Венера}. Возможное отношение на A и B - это отношение «принадлежит», задаваемое R = {(мяч, Джон), (кукла, Мэри), (машина, Венера)}. То есть Джон владеет мячом, Мэри - куклой, а Венера - машиной. Никто не владеет чашей, и Ян ничем не владеет. Как набор, R не включает Яна, и поэтому R можно было бы рассматривать как подмножество A × {John, Mary, Venus}, то есть отношение над A и {John, Mary, Venus}.
Некоторые важные типы бинарных отношений R над множествами X и Y перечислены ниже.
Свойства уникальности:
Свойства целостности (можно определить, только если заданы домен X и codomain Y):
Свойства уникальности и совокупности (можно определить, только если заданы домен X и домен Y):
Если R и S являются бинарные отношения над множествами X и Y, то R ∪ S = {(x, y) | xRy или xSy} - это отношение объединения R и S над X и Y.
Элемент идентичности - это пустое отношение. Например, ≤ - это объединение < and =, and ≥ is the union of>и =.
Если R и S являются бинарными отношениями над множествами X и Y, то R ∩ S = {(x, y) | xRy и xSy} - это отношение пересечения R и S над X и Y.
Элемент идентичности - это универсальное отношение. Например, отношение «делится на 6» - это пересечение отношений «делится на 3» и «делится на 2».
Если R - бинарное отношение над множествами X и Y, а S - бинарное отношение над множествами Y и Z, то R ∘ S = {(x, z) | существует y в Y такой, что xRy и ySz} (также обозначаемый R; S) является отношением композиции R и S над X и Z.
Элемент идентичности - это отношение идентичности. Порядок R и S в обозначениях S ∘ R, используемых здесь, соответствует стандартному порядку обозначений для композиции функций. Например, композиция "является матерью" "является родителем" урожайности "является бабушкой и дедушкой по материнской линии", в то время как композиция "является родителем" ", является матерью" урожайности "является бабушкой".
Если R - бинарное отношение над множествами X и Y, то R = {(y, x) | xRy} является обратным отношением R над Y и X.
Например, = является обратным самому себе, как ≠, а < and>являются обратными друг другу, как ≤ и ≥. Бинарное отношение равно своему обратному тогда и только тогда, когда оно симметрично.
Если R - бинарное отношение над множествами X и Y, то R = {(x, y) | не xRy} (также обозначается Rили ¬R) является дополнительным отношением R по отношению к X и Y.
Например, = и ≠ являются дополнениями друг друга, как и ⊆ и ⊈, ⊇ и ⊉, а также ∈ и ∉, а также для общих заказов также < and ≥, and>и ≤.
Дополнение к обратному отношению R является обратным к дополнению:
Если X = Y, дополнение имеет следующие свойства :
Если R - бинарное отношение над множеством X, а S - подмножество X, то R | S = {(x, y) | xRy и x в 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 = {( х, у) | xRy и y в S} - это отношение правого ограничения R к S над X и Y.
Если отношение рефлексивное, иррефлексивное, симметричное, антисимметричный, асимметричный, транзитивный, общий, трихотомический, частичный порядок, общий порядок, строгий слабый порядок, общий предварительный порядок (слабый порядок) или отношение эквивалентности, то же самое относится и к его ограничениям.
Однако транзитивное замыкание ограничения является подмножеством ограничения транзитивного замыкания, то есть в общем случае не равнозначно. Например, ограничение отношения «x является родителем y» женщинами дает отношение «x - мать женщины y»; его переходное закрытие не связывает женщину с бабушкой по отцовской линии. С другой стороны, транзитивное закрытие "является предком" является "является предком"; его ограничение женщинами действительно связывает женщину с бабушкой по отцовской линии.
Кроме того, различные концепции полноты (не путать с «полнотой») не переносятся на ограничения. Например, для вещественных чисел свойство отношения ≤ состоит в том, что каждое непустое подмножество S из R с верхней границей в R имеет наименьшую верхнюю границу (также называемую супремумом) в R . Однако для рациональных чисел этот супремум не обязательно рациональный, поэтому то же свойство не имеет места при ограничении отношения ≤ на рациональные числа.
Бинарное отношение R над множествами X и Y называется содержащимся в отношении S над X и Y, записывается R ⊆ S, если R является подмножеством S, то есть для всех x в X и y в Y, если 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) произведение Адамара соответствует пересечению отношений, нулевая матрица соответствует пустому отношению, а матрица единиц соответствует универсальное отношение. Однородные отношения (когда X = Y) образуют матричное полукольцо (действительно, матричную полуалгебру над булевым полукольцом), где единичная матрица соответствует единичному отношению.
Определенные математические «отношения», такие как «равно», «подмножество» и «член», не могут пониматься как бинарные отношения, как определено выше, потому что их области и области не могут быть приняты за множества в обычных системах аксиоматической теории множеств. Например, если мы попытаемся смоделировать общую концепцию «равенства» как бинарное отношение =, мы должны принять домен и домен как «класс всех множеств», что не является множеством в обычной теории множеств.
В большинстве математических контекстов ссылки на отношения равенства, членства и подмножества безвредны, потому что их можно неявно понимать как ограниченные некоторым набором в контексте. Обычный способ решения этой проблемы - выбрать «достаточно большой» набор A, содержащий все интересующие объекты, и работать с ограничением = A вместо =. Точно так же "подмножество" отношения ⊆ должно быть ограничено, чтобы иметь домен и домен P (A) (набор мощности определенного набора A): результирующее отношение набора может быть обозначено как ⊆ A. Кроме того, отношение «член» должно быть ограничено доменом A и доменом P (A), чтобы получить двоичное отношение ∈ A, которое является набором. Бертран Рассел показал, что предположение, что ∈ определено на всех множествах, приводит к противоречию в наивной теории множеств.
Другое решение этой проблемы - использовать теорию множеств с соответствующими классами, такими как NBG или теория множеств Морса – Келли, и разрешить область и область значений ( и, следовательно, граф) должен быть надлежащими классами : в такой теории равенство, членство и подмножество являются бинарными отношениями без специального комментария. (Незначительная модификация должна быть внесена в концепцию упорядоченной тройки (X, Y, G), поскольку обычно правильный класс не может быть членом упорядоченного кортежа; или, конечно, можно идентифицировать двоичное отношение с его графом в этот контекст.) С помощью этого определения можно, например, определить бинарное отношение для каждого набора и его набора мощности.
A однородное отношение (также называемое эндорреляцией ) над множеством X является бинарным отношением над X и самим собой, то есть это подмножество декартова произведения X × X. Это также просто называется бинарным отношением над X. Примером однородного отношения является отношение родства, где отношение распространяется на людей.
Однородное отношение R над множеством X может быть отождествлено с ориентированным простым графом, допускающим циклы, или, если оно симметричным, с неориентированным простым графом. граф, разрешающий петли, где X - множество вершин, а R - множество ребер (есть ребро от вершины x к вершине y тогда и только тогда, когда xRy). Это называется отношением смежности графа.
Набор всех однородных отношений над набором X - это набор 2, которая является булевой алгеброй, дополненной инволюцией отображения отношения на его обратное отношение. Если рассматривать композицию отношений как двоичную операцию на , она образует инверсную полугруппу.
Некоторые важные частные однородные отношения над множеством X:
Для произвольных элементов x и y из X:
Некоторые важные свойства, которые может иметь однородное отношение R над множеством X:
Предыдущие 4 альтернативы далеко не исчерпывающие; например, красное бинарное отношение y = x, данное в разделе Специальные типы бинарных отношений, не является ни иррефлексивным, ни корефлексивным, ни рефлексивным, поскольку оно содержит пару (0, 0) и (2, 4), но не (2, 2) соответственно. Последние два факта также исключают квазирефлексивность.
Опять же, предыдущие 3 альтернативы далеко не исчерпывающие; в качестве примера для натуральных чисел отношение xRy, определяемое x>2, не является ни симметричным, ни антисимметричным, не говоря уже об асимметричном.
. Опять же, предыдущие 5 альтернатив не являются исчерпывающими. Например, отношение xRy if (y = 0 или y = x + 1) не удовлетворяет ни одному из этих свойств. С другой стороны, пустое отношение тривиально им всем удовлетворяет.
A preorder - это отношение, которое является рефлексивным и транзитивным. Общий предварительный заказ , также называемый предварительным порядком коннекса или слабым порядком, - это отношение, которое является рефлексивным, транзитивным и коннексным.
A частичный порядок, также называемый порядком, является рефлексивным, антисимметричным и транзитивным отношением. строгий частичный порядок, также называемый строгим порядком, - это иррефлексивное, антисимметричное и транзитивное отношение. Общий порядок, также называемый порядком коннекса, линейным порядком, простым порядком или цепочкой, - это отношение, которое является рефлексивным, антисимметричным, транзитивным и коннексным. строгий полный порядок, также называемый строгим полусубъектным порядком, строгим линейным порядком, строгим простым порядком или строгой цепочкой, является отношением, которое является иррефлексивным, антисимметричным, транзитивным и полусоединенным.
A отношение частичной эквивалентности - это отношение, которое является симметричным и транзитивным. Отношение эквивалентности - это отношение, которое является рефлексивным, симметричным и транзитивным. Это также отношение, которое является симметричным, транзитивным и последовательным, поскольку эти свойства подразумевают рефлексивность.
Последствия и конфликты между свойствами однородных бинарных отношений |
---|
Последствия (синий) и конфликты (красный) между свойствами (желтый) однородных бинарных отношений. Например, любое асимметричное отношение является иррефлексивным («ASym ⇒ Irrefl»), и никакое отношение на непустом множестве не может быть одновременно иррефлексивным и рефлексивным («Irrefl # Refl»). Отсутствие красных краев приводит к диаграмме Хассе. |
Если R является однородным отношением над множеством X, то каждое из следующих отношений является однородным отношением над X:
Все операции, определенные в разделе Операции с бинарными отношениями также применимы к однородным отношениям.
Рефлексивность | Симметрия | Транзитивность | Связность | Символ | Пример | |
---|---|---|---|---|---|---|
Направленный граф | → | |||||
Ненаправленный граф | Симметричный | |||||
Зависимость | Рефлексивная | Симметричная | ||||
Турнирная | Иррефлексивная | Антисимметричная | Порядок иерархии | |||
Предварительный заказ | Рефлексивная | Да | ≤ | Предпочтение | ||
Общий предварительный заказ | Рефлексивный | Да | Connex | ≤ | ||
Частичный порядок | Рефлексивный | Антисимметричный | Да | ≤ | Подмножество | |
Строгий частичный порядок | нерефлексивный | антисимметричный | да | < | строгий подмножество | |
общий порядок | рефлексивный | антисимметричный | да | Connex | ≤ | В алфавитном порядке |
Строгий общий порядок | Безрефлексивный | Антисимметричный | Да | Semiconnex | < | Строгий алфавитный порядок |
Отношение частичной эквивалентности | Симметричное | Да | ||||
Отношение эквивалентности | Рефлексивное | Симметричное | Да | ∼, ≡ | Равенство |
Количество различных однородных отношений в наборе из n элементов равно 2 (последовательность A002416 в OEIS ):
Элементы | Любые | Переходные | Рефлексивные | Предварительный порядок | Частичный порядок | Общий предварительный порядок | Общий порядок | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 355 | 219 | 75 | 24 | 15 |
n | 2 | 2 | ∑n. k = 0 k ! S (n, k) | n! | ∑n. k = 0 S (n, k) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Примечания:
. Однородные отношения могут быть сгруппированы в пары ( отношение, дополнение ), за исключением того, что для n = 0 отношение является его собственным дополнением. Несимметричные могут быть сгруппированы в четверки (отношение, дополнение, обратное, обратное дополнение).