Альфапедия

Двоичное отношение

редактировать
Связь между двумя наборами, определяемая набором упорядоченных пар

В математике ( в частности теория множеств ), двоичное отношение над устанавливает 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 {\ displaystyle \ mathbb {P}}\mathbb {P} и набор целых чисел Z {\ displaystyle \ mathbb {Z}}\mathbb {Z} в где каждое простое число 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.

Содержание
  • 1 Определение
    • 1.1 Пример
  • 2 Специальные типы двоичных отношений
  • 3 Операции с бинарными отношениями
    • 3.1 Объединение
    • 3.2 Пересечение
    • 3.3 Состав
    • 3.4 Конверс
    • 3.5 Дополнение
    • 3.6 Ограничение
    • 3.7 Представление матрицы
  • 4 Наборы в сравнении с классами
  • 5 Однородное отношение
    • 5.1 Особые однородные отношения
    • 5.2 Свойства
    • 5.3 Операции
    • 5.4 Перечисление
    • 5.5 Примеры
  • 6 См. Также
  • 7 N otes
  • 8 Ссылки
  • 9 Библиография
  • 10 Внешние ссылки
Определение

Для заданных наборов 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.

Пример

2-й пример отношения
ballcardollчашка
Джон+−−−
Мэри−−+−
Венера−+−−
1-й пример отношения
мячмашинакуклачашка
Джон+−−−
Мэри−−+−
Ян−−−−
Венера−+−−

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

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

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

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

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

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

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

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

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

Объединение

Если 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, используемых здесь, соответствует стандартному порядку обозначений для композиции функций. Например, композиция "является матерью" "является родителем" урожайности "является бабушкой и дедушкой по материнской линии", в то время как композиция "является родителем" ", является матерью" урожайности "является бабушкой".

Converse

Если 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 является обратным к дополнению: R T ¯ = R ¯ T. {\ displaystyle {\ overline {R ^ {\ mathsf {T}}}} = {\ bar {R}} ^ {\ mathsf {T}}.}{\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.}

Если 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). Это называется отношением смежности графа.

Набор всех однородных отношений B (X) {\ displaystyle {\ mathcal {B}} (X)}{\displaystyle {\mathcal {B}}(X)}над набором X - это набор 2, которая является булевой алгеброй, дополненной инволюцией отображения отношения на его обратное отношение. Если рассматривать композицию отношений как двоичную операцию на B (X) {\ displaystyle {\ mathcal {B}} (X)}{\displaystyle {\mathcal {B}}(X)}, она образует инверсную полугруппу.

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

  • Плотный : для всех x, y в X таких, что xRy, можно найти некоторый z в X, такой что xRz и zRy. Используется в плотных порядках.
  • Connex : для всех x и y в X, xRy или yRx. Это свойство иногда называют «общим», что отличается от определений «всего», приведенных в разделе Специальные типы бинарных отношений.
  • Semiconnex : для всех x и y в X, если x ≠ y, затем xRy или yRx. Это свойство иногда называют «общим», что отличается от определений «всего», приведенных в разделе Специальные типы бинарных отношений.
  • Трихотомические : для всех x и y в X точно одно из xRy, yRx или x = y. Например,>является трихотомическим отношением, в то время как отношение «делит» на натуральные числа - нет.
  • Правое евклидово (или просто евклидово): для всех x, y и z в X, если xRy и xRz затем yRz. Например, = является евклидовым соотношением, потому что если x = y и x = z, то y = z.
  • Левое евклидово соотношение: для всех x, y и z в X, если yRx и zRx, то yRz.
  • Серийный (или всего слева): для всех x в X существует y в X такое, что xRy. Например,>- это последовательное отношение целых чисел. Но это не последовательное отношение по положительным целым числам, потому что в натуральных числах нет y, такого что 1>y. Однако < is a serial relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given x, choose y = x.
  • подобный множеству (или локальный): для всех x в X, класс всех y, таких что yRx является набором. (Это имеет смысл только в том случае, если разрешены отношения над соответствующими классами.) Например, обычное упорядочение < over the class of порядковых чисел является отношением, подобным множеству, а его обратное>- нет.
  • Хорошо обосновано : каждое непустое подмножество S в X содержит минимальный элемент относительно R. Обоснованность подразумевает условие убывающей цепочки (то есть отсутствие бесконечной цепочки... x n R... Rx 3Rx2Rx1может существовать). Если предполагается аксиома зависимого выбора, оба условия эквивалентны.

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

A частичный порядок, также называемый порядком, является рефлексивным, антисимметричным и транзитивным отношением. строгий частичный порядок, также называемый строгим порядком, - это иррефлексивное, антисимметричное и транзитивное отношение. Общий порядок, также называемый порядком коннекса, линейным порядком, простым порядком или цепочкой, - это отношение, которое является рефлексивным, антисимметричным, транзитивным и коннексным. строгий полный порядок, также называемый строгим полусубъектным порядком, строгим линейным порядком, строгим простым порядком или строгой цепочкой, является отношением, которое является иррефлексивным, антисимметричным, транзитивным и полусоединенным.

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

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

Операции

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

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

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

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

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

Количество n- бинарные отношения элементов разных типов
ЭлементыЛюбые Переходные Рефлексивные Предварительный порядок Частичный порядок Общий предварительный порядок Общий порядок Отношение эквивалентности
011111111
122111111
21613443322
35121716429191365
465,5363,9944,096355219752415
n22∑n. k = 0 k ! S (n, k)n!∑n. k = 0 S (n, k)
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

Примечания:

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

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

Примеры

См. также
Примечания
Ссылки
Библиография
External links
Последняя правка сделана 2021-05-12 06:26:06
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте