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

Reversal of the order of elements of a binary relation

В математике обратным бинарному отношению является отношение, которое возникает, когда порядок элементов в отношении меняется . Например, обратным отношению отношения «дочерний элемент» является отношение «родительский элемент». Формально, если и являются множествами и является отношением от до , то это отношение определяется так, что тогда и только тогда, когда в обозначениях построителя множеств , ${\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 является многозначной . Этого условия достаточно для того, чтобы быть частичной функцией , и ясно, что тогда она является (полной) функцией тогда и только тогда, когда она сюръективна . В этом случае, что означает, что если является биективным , можно назвать обратной функцией ${\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. К.И. Льюис (1918) Обзор символической логики, стр. 273, Интернет-архив
4. Шмидт, Гюнтер (2010). Реляционная математика. Кембридж: Издательство Кембриджского университета . п. 39. ИСБН 978-0-521-76268-7.
5. Гюнтер Шмидт; Томас Стрёлейн (1993). Отношения и графики: дискретная математика для компьютерщиков . Шпрингер Берлин Гейдельберг. стр. 9–10. ISBN 978-3-642-77970-1.
6. Селестина Котти Ферреро; Джованни Ферреро (2002). Неринги: некоторые события, связанные с полугруппами и группами . Академическое издательство Клувер. п. 3. ISBN 978-1-4613-0267-4.
7. Дэниел Дж. Веллеман (2006). Как это доказать: структурированный подход. Издательство Кембриджского университета. п. 173. ИСБН 978-1-139-45097-3.
8. Шломо Штернберг; Линн Лумис (2014). Продвинутое исчисление . Мировое научное издательство. п. 9. ISBN 978-9814583930.
9. Розен, Кеннет Х. (2017). Справочник по дискретной и комбинаторной математике. Розен, Кеннет Х., Шайер, Дуглас Р., Годдард, Уэйн. (Второе изд.). Бока-Ратон, Флорида. п. 43. ИСБН 978-1-315-15648-4. ОКЛК  994604351.{{cite book}}: CS1 maint: location missing publisher (link)
10. Джерард О'Реган (2016): Руководство по дискретной математике: доступное введение в историю, теорию, логику и приложения ISBN 9783319445618 
11. Питер Дж. Фрейд и Андре Щедров (1990) Категории, аллегории, стр. 79, ISBN Северной Голландии 0-444-70368-3 
12. Иоахим Ламбек (2001). «Отношения старые и новые». В Еве Орловской ; Анджей Салас (ред.). Реляционные методы для приложений информатики . Springer Science & Business Media. стр. 135–146. ISBN 978-3-7908-1365-4.
13. Гюнтер Шмидт и Майкл Винтер (2018) Реляционная топология , Конспекты лекций Springer по математике № 2208, страница 8, ISBN 978-3-319-74450-6 

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