Обратное отношение

Изменение порядка элементов бинарного отношения на обратный

В математике обратным бинарным отношением является отношение, которое возникает, когда порядок элементов в отношении меняется. Например, обратным отношением отношения «ребенок» является отношение «родитель». Формально, если и являются множествами и является отношением от до , то это отношение определяется так, что если и только если В нотации конструктора множеств , ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle L\subseteq X\times Y}$ ${\displaystyle X}$ ${\displaystyle Y,}$ ${\displaystyle L^{\operatorname {T} }}$ ${\displaystyle yL^{\operatorname {T} }x}$ ${\displaystyle xLy.}$

${\displaystyle L^{\operatorname {T} }=\{(y,x)\in Y\times X:(x,y)\in L\}.}$

Поскольку отношение может быть представлено логической матрицей , а логическая матрица обратного отношения является транспонированием исходного , обратное отношение ^{[1] [2] [3] [4]} также называется транспонированным отношением . ^[5] Его также называют противоположным или дуальным исходному отношению, ^[6] обратным исходному отношению, [ ^{7] [8] [9] [10]} или обратным отношению ^[11]. ${\displaystyle L^{\circ }}$ ${\displaystyle L.}$

Другие обозначения для обратного отношения включают или ^{[ необходима ссылка ]} ${\displaystyle L^{\operatorname {C} },L^{-1},{\breve {L}},L^{\circ },}$ ${\displaystyle L^{\vee }.}$

Обозначение аналогично обозначению для обратной функции . Хотя многие функции не имеют обратной функции, каждое отношение имеет уникальное обратное. Унарная операция , которая отображает отношение в обратное отношение, является инволюцией , поэтому она индуцирует структуру полугруппы с инволюцией на бинарных отношениях на множестве или, в более общем смысле, индуцирует категорию кинжала на категории отношений, как подробно описано ниже. Как унарная операция , взятие обратного (иногда называемого преобразованием или транспозицией ) ^{[ требуется ссылка ]} коммутирует с операциями, связанными с порядком исчисления отношений, то есть она коммутирует с объединением, пересечением и дополнением.

Примеры

Для обычных (возможно, строгих или частичных) отношений порядка обратным является наивно ожидаемый «противоположный» порядок, например, ${\displaystyle {\leq ^{\operatorname {T} }}={\geq },\quad {<^{\operatorname {T} }}={>}.}$

Отношение может быть представлено логической матрицей, например: $${\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}}.}$$

Тогда обратное отношение представляется его транспонированной матрицей : $${\displaystyle {\begin{pmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&1&0&1\end{pmatrix}}.}$$

Обратные отношения родства называются: « является ребенком «имеет отношение», « является родителем «. « является племянником или племянницей « имеет отношение», « является дядей или тетей «. Отношение « является братом или сестрой « является своим собственным обратным отношением, поскольку является симметричным отношением. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$

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

В моноиде бинарных эндоотношений на множестве (с бинарной операцией над отношениями, являющейся композицией отношений ), обратное отношение не удовлетворяет определению обратного из теории групп, то есть, если является произвольным отношением на , то не равно отношению тождества на в общем случае. Обратное отношение удовлетворяет (более слабым) аксиомам полугруппы с инволюцией : и ^[12] ${\displaystyle L}$ ${\displaystyle X,}$ ${\displaystyle L\circ L^{\operatorname {T} }}$ ${\displaystyle X}$ ${\displaystyle \left(L^{\operatorname {T} }\right)^{\operatorname {T} }=L}$ ${\displaystyle (L\circ R)^{\operatorname {T} }=R^{\operatorname {T} }\circ L^{\operatorname {T} }.}$

Поскольку в общем случае можно рассматривать отношения между различными множествами (которые образуют категорию , а не моноид, а именно категорию отношений Rel ), в этом контексте обратное отношение соответствует аксиомам категории кинжала (также известной как категория с инволюцией). ^[12] Отношение, равное своему обратному, является симметричным отношением ; на языке категорий кинжала оно является самосопряженным .

Более того, полугруппа эндореляций на множестве также является частично упорядоченной структурой (с включением отношений как множеств), и фактически инволютивным кванталом . Аналогично, категория гетерогенных отношений , Rel также является упорядоченной категорией. ^[12]

В исчислении отношений преобразование (унарный метод взятия обратного отношения) коммутирует с другими бинарными операциями объединения и пересечения. Преобразование также коммутирует с унарной операцией дополнения , а также с взятием супремумов и инфимумов. Преобразование также совместимо с упорядочением отношений включением. ^[5]

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

Обратные

Если представляет собой отношение тождества, то отношение может иметь обратное следующим образом: называется ${\displaystyle I}$ ${\displaystyle R}$ ${\displaystyle R}$

правообратимый

если существует отношение, называемое ${\displaystyle X,}$правая обратная кэтому удовлетворяет ${\displaystyle R,}$ ${\displaystyle R\circ X=I.}$

левообратимый

если существует отношение, называемое ${\displaystyle Y,}$левое обратное ,удовлетворяющее ${\displaystyle R,}$ ${\displaystyle Y\circ R=I.}$

обратимый

если он является как обратимым вправо, так и обратим влево.

Для обратимого однородного отношения все правые и левые обратные совпадают; этот уникальный набор называется его ${\displaystyle R,}$Обратное и обозначаетсяВ этом случаевыполняется.^{[5] : 79} ${\displaystyle R^{-1}.}$ ${\displaystyle R^{-1}=R^{\operatorname {T} }}$

Обратное отношение функции

Функция обратима тогда и только тогда , когда ее обратное отношение является функцией, и в этом случае обратное отношение является обратной функцией.

Обратное отношение функции — это отношение, определяемое соотношением ${\displaystyle f:X\to Y}$ ${\displaystyle f^{-1}\subseteq Y\times X}$ ${\displaystyle \operatorname {graph} \,f^{-1}=\{(y,x)\in Y\times X:y=f(x)\}.}$

Это не обязательно функция: Одним из необходимых условий является то, что она инъективна , поскольку else многозначна . Этого условия достаточно для того, чтобы быть частичной функцией , и ясно, что then является (полной) функцией тогда и только тогда, когда является сюръективной . В этом случае, имея в виду, что if является биективной , можно назвать обратной функцией ${\displaystyle f}$ ${\displaystyle f^{-1}}$ ${\displaystyle f^{-1}}$ ${\displaystyle f^{-1}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f^{-1}}$ ${\displaystyle f.}$

Например, функция имеет обратную функцию ${\displaystyle f(x)=2x+2}$ ${\displaystyle f^{-1}(x)={\frac {x}{2}}-1.}$

Однако функция имеет обратную связь , которая не является функцией, будучи многозначной. ${\displaystyle g(x)=x^{2}}$ ${\displaystyle g^{-1}(x)=\pm {\sqrt {x}},}$

Состав с отношением

Используя композицию отношений , обратное может быть составлено с исходным отношением. Например, отношение подмножества, составленное со своим обратным, всегда является универсальным отношением:

∀A ∀B ∅ ⊂ A ∩B ⇔ A ⊃ ∅ ⊂ B ⇔ A ⊃ ⊂ B. Аналогично,

Для U = вселенная , A ∪ B ⊂ U ⇔ A ⊂ U ⊃ B ⇔ A ⊂ ⊃ B.

Теперь рассмотрим отношение принадлежности множеству и его обратное.

${\displaystyle A\ni z\in B\Leftrightarrow z\in A\cap B\Leftrightarrow A\cap B\neq \emptyset .}$

Таким образом, противоположная композиция есть всеобщее отношение. ${\displaystyle A\ni \in B\Leftrightarrow A\cap B\neq \emptyset .}$ ${\displaystyle \in \ni }$

Композиции используются для классификации отношений по типу: для отношения Q , когда отношение тождества на области Q содержит Q ^T Q , то Q называется однозначным . Когда отношение тождества на области Q содержится в QQ ^T , то Q называется полным . Когда Q является как однозначным, так и полным, то это функция . Когда Q ^T однозначен, то Q называется инъективным . Когда Q ^T является полным, Q называется сюръективным . ^[13]

Если Q одновалентен, то QQ ^T является отношением эквивалентности на области определения Q , см. Транзитивное отношение#Связанные свойства .

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

• Двойственность (теория порядка)  – Термин в математической области теории порядка.
• Транспонированный граф  – ориентированный граф с обратными ребрами

Ссылки

1. Эрнст Шредер , (1895), Algebra der Logik (Exakte Logik) Dritter Band, Algebra und Logik der Relative , Лейбциг: Б. Г. Тойбнер через Интернет-архив , страница 3 Konversion
2. Бертран Рассел (1903) Принципы математики, стр. 97 через Интернет-архив
3. CI Lewis (1918) Обзор символической логики, стр. 273 через интернет-архив
4. Шмидт, Гюнтер (2010). Реляционная математика. Кембридж: Cambridge University Press . стр. 39. ISBN 978-0-521-76268-7.
5. Гюнтер Шмидт; Томас Штрёляйн (1993). Отношения и графы: Дискретная математика для компьютерных ученых . Springer Berlin Heidelberg. стр. 9–10. ISBN 978-3-642-77970-1.
6. Селестина Котти Ферреро; Джованни Ферреро (2002). Nearrings: Some Developments Linked to Semigroups and Groups . Kluwer Academic Publishers. стр. 3. ISBN 978-1-4613-0267-4.
7. Дэниел Дж. Веллеман (2006). Как это доказать: структурированный подход. Cambridge University Press. стр. 173. ISBN 978-1-139-45097-3.
8. Шломо Стернберг; Линн Лумис (2014). Advanced Calculus . World Scientific Publishing Company. стр. 9. ISBN 978-9814583930.
9. Розен, Кеннет Х. (2017). Справочник по дискретной и комбинаторной математике. Розен, Кеннет Х., Шайер, Дуглас Р., Годдард, Уэйн. (Второе изд.). Бока-Ратон, Флорида. стр. 43. ISBN 978-1-315-15648-4. OCLC  994604351.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
10. Джерард О'Реган (2016): Руководство по дискретной математике: доступное введение в историю, теорию, логику и приложения ISBN 9783319445618 
11. Питер Дж. Фрейд и Андре Скедров (1990) Категории, аллегории, стр. 79, ISBN Северной Голландии 0-444-70368-3 
12. Joachim Lambek (2001). "Старые и новые отношения". В Ewa Orłowska ; ​​Andrzej Szalas (ред.). Relational Methods for Computer Science Applications . Springer Science & Business Media. стр. 135–146. ISBN 978-3-7908-1365-4.
13. Гюнтер Шмидт и Майкл Винтер (2018) Реляционная топология , Springer Lecture Notes in Mathematics #2208, стр. 8, ISBN 978-3-319-74450-6 

• Халмош, Пол Р. (1974), Наивная теория множеств , Springer, стр. 40, ISBN 978-0-387-90092-6