Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математике ( в частности , теории множеств ), в бинарное отношение над множествами X и Y представляет собой подмножество в декартово произведение X × Y ; то есть, она представляет собой набор упорядоченных пар ( х , у ) , состоящих из элементов х в X и Y в Y . [1] Он кодирует общую концепцию соотношения: элемент х является связанной с элементом у ,тогда и только тогда, когда пара ( x , y ) принадлежит набору упорядоченных пар, определяющих бинарное отношение . Бинарное отношение является наиболее изученным частным случаем п = 2 из п -ичного соотношения над множествами Х 1 , ..., Х п , которое является подмножеством декартова произведения X 1 × ... × X п . [1] [2]

Пример бинарного отношения является « делит » отношение над множеством простых чисел и множеством целых чисел , в котором каждый простой р имеет отношение к любому целому числу г , которое является кратным от р , но не является целым числом, которое не кратное p . В этом отношении, например, простое число 2 связано с такими числами, как -4, 0, 6, 10, но не с 1 или 9, так же, как простое число 3 связано с 0, 6 и 9, но не до 4 или 13.

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

Функция может быть определена как особый вид бинарного отношения. [3] Двоичные отношения также широко используются в информатике .

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

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

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

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

Определение [ править ]

С учетом множества Х и Y , то декартово произведение X × Y определяется как {( х , у ) | xX и yY } , а его элементы называются упорядоченными парами.

Бинарное отношение 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 , бинарное отношение называется однородным отношением (или эндорреляцией ). Чтобы подчеркнуть тот факт, что X и Y могут быть разными, бинарное отношение также называется гетерогенным отношением . [13] [14] [15]

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

Пример [ править ]

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

Особые типы бинарных отношений [ править ]

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

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

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

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

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

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

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

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

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

Союз [ править ]

Если R и S - бинарные отношения над множествами X и Y, то RS = {( x , y ) | хКа или вании } является объединение отношения из R и S над X и Y .

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

Пересечение [ править ]

Если R и S - бинарные отношения над множествами X и Y, то RS = {( x , y ) | хКа и вании } является пересечение соотношения из R и S над X и Y .

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

Состав [ править ]

Если R - бинарное отношение над множествами X и Y , а S - бинарное отношение над множествами Y и Z, то SR = {( x , z ) | существует уY такое , что хКа и YSZ } (также обозначается через R ; S ) представляет собой композицию соотношение из R и S над X и Z .

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

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 и YS } является ограничение соотношения из R к S над X .

Если R - бинарное отношение над множествами X и Y, а S - подмножество X, то R | S = {( x , y ) | хКа и хS } является левым ограничения соотношения из R к S над X и Y .

Если R - бинарное отношение над множествами X и Y, а S - подмножество Y, то R | S = {( x , y ) | хКа и уS } является правым ограничением соотношения из R к S над X и Y .

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

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

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

Бинарное отношение R над множествами X и Y , как говорят, содержащимися в отношениях S над X и Y , добавленным RS , если R является подмножеством S , то есть, для всех хX и уY , если xRy , затем xSy . Если R содержится в S, а S содержится в R , то R и Sназываются равно записываются R = S . Если R содержится в S , но S не содержится в R , то R называется меньше , чем S , написанный RS . Например, для рациональных чисел отношение> меньше ≥ и равно композиции > ∘>.

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

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

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

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

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

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

Однородное отношение [ править ]

Однородное отношение (также называемый endorelation ) над множеством X представляет собой бинарное отношение над X и сам, т.е. подмножество декартова произведения X × X . [15] [21] [22] Она также называется просто бинарное отношение над X . Примером гомогенного отношения является отношение родства , где отношение распространяется на людей.

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

Множество всех однородных отношений над множеством X - это множество 2 X × X, которое является булевой алгеброй, дополненной инволюцией отображения отношения в обратное отношение . Рассматривая композицию отношений как бинарную операцию над , она образует полугруппу с инволюцией .

Особые однородные отношения [ править ]

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

  • пустое отношение Е = ∅ ⊆ Х × Х ;
  • универсальное соотношение U = X × X ;
  • тождественное соотношение I = {( х , х ) | xX } .

Для произвольных элементов x и y элемента X :

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

Свойства [ править ]

Некоторые важные свойства, которыми может обладать однородное отношение R над множеством X :

Рефлексивный
для всех xX , xRx . Например, ≥ - рефлексивное отношение, а> - нет.
Нерефлексивный (или строгий )
для всех xX , а не xRx . Например,> - иррефлексивное отношение, а ≥ - нет.
Coreflexive
для всех x , yX , если xRy, то x = y . [23] Например, отношение целых чисел, в котором каждое нечетное число связано с самим собой, является коререфлексивным отношением. Отношение равенства - единственный пример как рефлексивного, так и корефлексивного отношения, а любое корефлексивное отношение является подмножеством отношения идентичности.
Квазирефлексивный
для всех x , yX , если xRy, то xRx и yRy .

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

Левый квазирефлексивный
для всех x , yX , если xRy, то xRx .
Правый квазирефлексивный
для всех x , yX , если xRy, то yRy .

Бинарное отношение квазирефлексивно тогда и только тогда, когда оно одновременно квазирефлексивно слева и квазирефлексивно справа.

Симметричный
для всех x , yX , если xRy, то yRx . Например, «является кровным родственником» является симметричным отношением, потому что x является кровным родственником y тогда и только тогда, когда y является кровным родственником x .
Антисимметричный
для всех x , yX , если xRy и yRx, то x = y . Например, ≥ - антисимметричное отношение; так есть>, но бессмысленно (условие в определении всегда ложно). [24]
Асимметричный
для всех x , yX , если xRy, то не yRx . Отношение асимметрично тогда и только тогда, когда оно одновременно антисимметрично и иррефлексивно. [25] Например,> - это асимметричное отношение, а ≥ - нет.

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

Переходный
для всех x , y , zX , если xRy и yRz, то xRz . Транзитивное отношение иррефлексивно тогда и только тогда, когда оно асимметрично. [26] Например, «является предком» является транзитивным отношением, а «является родителем» - нет.
Антитранзитивный
для всех x , y , zX , если xRy и yRz, то никогда не xRz .
Ко-транзитивный
если дополнение к R транзитивно. То есть для всех x , y , zX , если xRz , то xRy или yRz . Это используется в псевдопорядках в конструктивной математике.
Квазитранзитивный
для всех x , y , zX , если xRy и yRz, но не yRx и zRy , то xRz, но не zRx .
Транзитивность несравнимости
для всех х , у , гX , если х и у не сравнимы по отношению к R , и если то же самое можно сказать и о у и г , то х и г , также несравнима по отношению к R . Это используется в слабом порядке .

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

Плотный
для всех x , yX таких, что xRy , существует некоторый zX такой, что xRz и zRy . Это используется в плотных заказах .
Connex
для всех x , yX , xRy или yRx . Это свойство иногда называют «общим», что отличается от определений «всего», приведенных в разделе « Особые типы бинарных отношений» .
Semiconnex
для всех x , yX , если xy, то xRy или yRx . Это свойство иногда называют «общим», что отличается от определений «всего», приведенных в разделе « Особые типы бинарных отношений» .
Трихотомический
для всех x , yX выполняется ровно одно из xRy , yRx или x = y . Например,> - это трихотомическое отношение, в то время как отношение «делится» на натуральные числа - нет. [27]
Право евклидово (или просто евклидово )
для всех x , y , zX , если xRy и xRz, то yRz . Например, = является евклидовым соотношением, потому что если x = y и x = z, то y = z .
Левый евклидов
для всех x , y , zX , если yRx и zRx, то yRz .
Последовательный (или слева )
для всех xX существует yX такое, что xRy . Например,> - это последовательное отношение над целыми числами. Но это не последовательное отношение по положительным целым числам, потому что в натуральных числах нет y, такого что 1> y . [28] Однако <является последовательным отношением над целыми положительными числами, рациональными числами и действительными числами. Каждое рефлексивное отношение серийно: для данного x выберите y = x .
Как набор[ необходима цитата ] (или местный )
[ необходимая цитата ] для всех xX , класс всех y таких, что yRx является множеством. (Это имеет смысл только в том случае, если разрешены отношения над соответствующими классами.) Например, обычное упорядочение <над классом порядковых чисел является отношением, подобным множеству, а его обратное> - нет.
Обоснованный
каждое непустое подмножество S из X содержит минимальный элемент по отношению к R . Обоснованность подразумевает условие убывающей цепи (то есть, бесконечная цепь ... x n R ... Rx 3 Rx 2 Rx 1 существовать не может). Если принять аксиому зависимого выбора , оба условия эквивалентны. [29] [30]

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

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

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

Операции [ править ]

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

  • Рефлексивное замыкание : R = , определяемое как R = = {( x , x ) | хХ } ∪ R или наименьшее рефлексивное отношение над X , содержащей R . Это может быть доказаночтобы быть равным пересечение всех рефлекторных отношенийсодержащих R .
  • Рефлексивная редукция : R , определяемая как R = R \ {( x , x ) | хХ } или по величине иррефлексивного отношения над X , содержащимся в R .
  • Переходная замыкание : R + , определяется как наименьшее транзитивное отношение над X , содержащей R . Это можно видеть, равно пересечению всех транзитивных отношенийсодержащих R .
  • Рефлексивное транзитивное замыкание : R *, определяется как R * = ( R + ) = наименьшее предпорядок , содержащий R .
  • Возвратное транзитивен симметричное замыкание : R , определяется как наименьшее отношение эквивалентности над X , содержащей R .

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

Перечисление [ править ]

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

Примечания:

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

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

Примеры [ править ]

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

См. Также [ править ]

  • Система рерайтинга аннотаций
  • Аддитивное отношение , многозначный гомоморфизм между модулями
  • Категория отношений , категория, имеющая множества как объекты и разнородные бинарные отношения как морфизмы.
  • Confluence (переписывание терминов) , обсуждает несколько необычных, но фундаментальных свойств бинарных отношений.
  • Соответствие (алгебраическая геометрия) , бинарное отношение, определяемое алгебраическими уравнениями
  • Диаграмма Хассе , графическое средство для отображения отношения порядка
  • Структура заболеваемости, неоднородное отношение между множеством точек и линий
  • Логика родственников , теория отношений Чарльза Сандерса Пирса
  • Теория порядка , исследует свойства отношений порядка.

Заметки [ править ]

  1. ^ Авторы, которые рассматривают бинарные отношения только как частный случай n -арных отношений для произвольного n, обычно пишут Rxy как частный случай Rx 1 ... x n ( префиксная запись ). [9]

Ссылки [ править ]

  1. ^ a b c d e f g h Кодд, Эдгар Франк (июнь 1970 г.). «Реляционная модель данных для больших общих банков данных» (PDF) . Коммуникации ACM . 13 (6): 377–387. DOI : 10.1145 / 362384.362685 . S2CID  207549016 . Проверено 29 апреля 2020 .
  2. ^ "Окончательный словарь высшего математического жаргона - отношения" . Математическое хранилище . 2019-08-01 . Проверено 11 декабря 2019 .
  3. ^ «Определение отношения - Math Insight» . mathinsight.org . Проверено 11 декабря 2019 .
  4. ^ a b Эрнст Шредер (1895) Алгебра и логика относительного , через Интернет-архив
  5. ^ a b К. И. Льюис (1918) Обзор символической логики , страницы 269–279, через Интернет-архив
  6. ^ a b c Гюнтер Шмидт , 2010. Реляционная математика . Издательство Кембриджского университета, ISBN 978-0-521-76268-7 , гл. 5 
  7. ^ Джейкобсон, Натан (2009), Базовая алгебра II (2-е изд.) § 2.1.
  8. ^ Enderton 1977 , Ч. 3. стр. 40
  9. Ганс Гермес (1973). Введение в математическую логику . Hochschultext (Springer-Verlag). Лондон: Спрингер. ISBN 3540058192. ISSN  1431-4657 . Раздел II.§1.1.4
  10. ^ Суппес, Патрик (1972) [первоначально опубликовано D. van Nostrand Company в 1960 году]. Аксиоматическая теория множеств . Дувр. ISBN 0-486-61630-4.
  11. ^ Smullyan, Раймонд М .; Фиттинг, Мелвин (2010) [пересмотренное и исправленное переиздание работы, первоначально опубликованной в 1996 году издательством Oxford University Press, Нью-Йорк]. Теория множеств и проблема континуума . Дувр. ISBN 978-0-486-47484-7.
  12. ^ Леви, Азриэль (2002) [переиздание работы, опубликованной Springer-Verlag, Берлином, Гейдельбергом и Нью-Йорком в 1979 году]. Основная теория множеств . Дувр. ISBN 0-486-42079-5.
  13. ^ Шмидт, Гюнтер ; Стрёляйн, Томас (2012). Отношения и графы: дискретная математика для компьютерных ученых . Определение 4.1.1 .: Springer Science & Business Media. ISBN 978-3-642-77968-8.CS1 maint: location (link)
  14. ^ Христодулос А. Флудас ; Панос М. Пардалос (2008). Энциклопедия оптимизации (2-е изд.). Springer Science & Business Media. С. 299–300. ISBN 978-0-387-74758-3.
  15. ^ a b Майкл Винтер (2007). Категории Гогена: категориальный подход к L-нечетким отношениям . Springer. стр. x – xi. ISBN 978-1-4020-6164-6.
  16. ^ 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.
  17. ^ MAS, Стефан (2007), «Рассуждение о пространственной Семантическом Ограничении целостности», пространственная теория информации: 8 - я Международная конференция, ЦОСИТ 2007, Мельбурн, Австралия, 19-23 сентября, 2007, Труды , Лекции по информатике, 4736 , Springer ., стр 285-302, DOI : 10.1007 / 978-3-540-74788-8_18
  18. Джон К. Баэз (6 ноября 2001 г.). «Квантовая механика над коммутативной оснасткой» . Группа новостейsci.physics.research . Usenet: [email protected] . Проверено 25 ноября 2018 года . 
  19. ^ Droste, М., & Kuich, W. (2009). Полукольца и формальные степенные ряды. Справочник по взвешенным автоматам , 3–28. DOI : 10.1007 / 978-3-642-01492-5_1 , стр. 7-10
  20. ^ Тарский, Альфред ; Гивант, Стивен (1987). Формализация теории множеств без переменных . Американское математическое общество. п. 3 . ISBN 0-8218-1041-3.
  21. Перейти ↑ ME Müller (2012). Открытие реляционных знаний . Издательство Кембриджского университета. п. 22. ISBN 978-0-521-19021-3.
  22. ^ Питер Дж. Пал; Рудольф Дамрат (2001). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. п. 496. ISBN. 978-3-540-67995-0.
  23. Перейти ↑ Fonseca de Oliveira, JN, & Pereira Cunha Rodrigues, CDJ (2004). Перенос отношений: от функций Maybe к хеш-таблицам . По математике построения программ (стр. 337).
  24. ^ Смит, Дуглас; Эгген, Морис; Сент-Андре, Ричард (2006), Переход к высшей математике (6-е изд.), Брукс / Коул, стр. 160, ISBN 0-534-39900-2
  25. ^ Нивергельт, Ив (2002), Основы логики и математики: приложения к информатике и криптографии , Springer-Verlag, стр. 158.
  26. ^ Flaška, V .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007). Транзитивные замыкания двоичных отношений I (PDF) . Прага: Школа математики - Карлов университет физики. п. 1. Архивировано из оригинального (PDF) 02.11.2013. Лемма 1.1 (iv). В этом источнике асимметричные отношения называются «строго антисимметричными».
  27. ^ Поскольку ни 5 делит 3, ни 3 делит 5, ни 3 = 5.
  28. ^ Яо, ГГ; Вонг, СКМ (1995). «Обобщение приблизительных наборов с использованием отношений между значениями атрибутов» (PDF) . Труды 2-й Ежегодной совместной конференции по информационным наукам : 30–33. .
  29. ^ "Условие для обоснованности" . ProofWiki . Проверено 20 февраля 2019 .
  30. ^ Fraisse, R. (15 декабря 2000). Теория отношений, том 145 - 1-е издание (1-е изд.). Эльзевир. п. 46. ISBN 9780444505422. Проверено 20 февраля 2019 .
  31. ^ Джозеф Г. Розенштейн, Линейные порядки ,Academic Press, 1982, ISBN 0-12-597680-1 , стр. 4 

Библиография [ править ]

  • Кодд, Эдгар Франк (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]