Рефлексивное отношение

Бинарное отношение, связывающее каждый элемент с самим собой

В математике бинарное отношение на множестве является рефлексивным , если оно связывает каждый элемент с самим собой. ^{[1] [2]} ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle X}$

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

Определения

Отношение на множестве называется рефлексивным, если для любого , . ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle x\in X}$ ${\displaystyle (x,x)\in R}$

Эквивалентно, обозначим через отношение тождества на , отношение рефлексивно, если . ${\displaystyle \operatorname {I} _{X}:=\{(x,x)~:~x\in X\}}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle \operatorname {I} _{X}\subseteq R}$

Рефлексивное замыкание — это объединение , которое можно эквивалентно определить как наименьшее (по отношению к ) рефлексивное отношение на , которое является надмножеством . Отношение рефлексивно тогда и только тогда, когда оно равно своему рефлексивному замыканию. ${\displaystyle R}$ ${\displaystyle R\cup \operatorname {I} _{X},}$ ${\displaystyle \subseteq }$ ${\displaystyle X}$ ${\displaystyle R.}$ ${\displaystyle R}$

Рефлексивная редукция или иррефлексивное ядро ​​— это наименьшее (по отношению к ) отношение на , имеющее то же рефлексивное замыкание, что и Оно равно Рефлексивную редукцию можно, в некотором смысле, рассматривать как конструкцию, которая является «противоположностью» рефлексивному замыканию Например, рефлексивное замыкание канонического строгого неравенства на действительных числах является обычным нестрогим неравенством, тогда как рефлексивная редукция является ${\displaystyle R}$ ${\displaystyle \subseteq }$ ${\displaystyle X}$ ${\displaystyle R.}$ ${\displaystyle R\setminus \operatorname {I} _{X}=\{(x,y)\in R~:~x\neq y\}.}$ ${\displaystyle R}$ ${\displaystyle R.}$ ${\displaystyle <}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \leq }$ ${\displaystyle \leq }$ ${\displaystyle <.}$

Связанные определения

Существует несколько определений, связанных с рефлексивным свойством. Отношение называется: ${\displaystyle R}$

нерефлексивный ,антирефлексивный илиалиоотносительный

^[3] если оно не связывает ни один элемент с собой; то есть, если выполняется ни для одного Отношение является иррефлексивным тогда и только тогда, когда его дополнение в рефлексивно. Асимметричное отношение обязательно иррефлексивно. Транзитивное и иррефлексивное отношение обязательно асимметрично. ${\displaystyle xRx}$ ${\displaystyle x\in X.}$ ${\displaystyle X\times X}$

левый квазирефлексивный

если когда-либо таковы, что тогда обязательно ^[4] ${\displaystyle x,y\in X}$ ${\displaystyle xRy,}$ ${\displaystyle xRx.}$

правый квазирефлексивный

если когда-либо таковы, что тогда обязательно ${\displaystyle x,y\in X}$ ${\displaystyle xRy,}$ ${\displaystyle yRy.}$

квазирефлексивный

если каждый элемент, являющийся частью некоторого отношения, связан с самим собой. Явно это означает, что всякий раз, когда таковы, что то обязательно и Эквивалентно, бинарное отношение является квазирефлексивным тогда и только тогда, когда оно является как левым квазирефлексивным, так и правым квазирефлексивным. Отношение является квазирефлексивным тогда и только тогда, когда его симметричное замыкание является левым (или правым) квазирефлексивным. ${\displaystyle x,y\in X}$ ${\displaystyle xRy,}$ ${\displaystyle xRx}$ ${\displaystyle yRy.}$ ${\displaystyle R}$ ${\displaystyle R\cup R^{\operatorname {T} }}$

антисимметричный

если когда-либо таковы, что тогда обязательно ${\displaystyle x,y\in X}$ ${\displaystyle xRy{\text{ and }}yRx,}$ ${\displaystyle x=y.}$

корефлексивный

если и когда таковы, что то обязательно ^[5] Отношение является корефлексивным тогда и только тогда, когда его симметричное замыкание является антисимметричным . ${\displaystyle x,y\in X}$ ${\displaystyle xRy,}$ ${\displaystyle x=y.}$ ${\displaystyle R}$

Рефлексивное отношение на непустом множестве не может быть ни иррефлексивным, ни асимметричным ( называется асимметричным, если влечет не ), ни антитранзитивным ( является антитранзитивным, если влечет не ). ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle R}$ ${\displaystyle xRy{\text{ and }}yRz}$ ${\displaystyle xRz}$

Примеры

Примеры рефлексивных отношений включают в себя:

• "равно" ( равенство )
• «является подмножеством » (включение множества)
• «делит» ( делимость )
• "больше или равно"
• "меньше или равно"

Примеры нерефлексивных отношений включают в себя:

• "не равно"
• « взаимно прост » для целых чисел больше 1
• "является собственным подмножеством "
• "больше чем"
• "меньше чем"

Примером иррефлексивного отношения, которое означает, что оно не связывает ни один элемент с самим собой, является отношение "больше, чем" ( ) на действительных числах . Не каждое отношение, которое не является рефлексивным, является иррефлексивным; можно определить отношения, в которых некоторые элементы связаны с собой, а другие нет (то есть, ни все, ни ни один не связаны). Например, бинарное отношение "произведение и четно" рефлексивно на множестве четных чисел , иррефлексивно на множестве нечетных чисел и ни рефлексивно, ни иррефлексивно на множестве натуральных чисел . ${\displaystyle x>y}$ ${\displaystyle x}$ ${\displaystyle y}$

Примером квазирефлексивного отношения является отношение «имеет тот же предел, что и» на множестве последовательностей действительных чисел: не каждая последовательность имеет предел, и, таким образом, отношение не является рефлексивным, но если последовательность имеет тот же предел, что и некоторая последовательность, то она имеет тот же предел, что и она сама. Примером левого квазирефлексивного отношения является левое евклидово отношение , которое всегда является левым квазирефлексивным, но не обязательно правым квазирефлексивным, и, таким образом, не обязательно квазирефлексивным. ${\displaystyle R}$

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

Число рефлексивных отношений

Число рефлексивных отношений на -элементном множестве равно ^[6] ${\displaystyle n}$ ${\displaystyle 2^{n^{2}-n}.}$

Обратите внимание, что S ( n , k ) относится к числам Стирлинга второго рода .

Философская логика

Авторы философской логики часто используют разную терминологию. Рефлексивные отношения в математическом смысле в философской логике называются тотально рефлексивными , а квазирефлексивные отношения называются рефлексивными . ^{[7] [8]}

Примечания

1. Леви 1979, стр. 74
2. Шмидт 2010
3. Этот термин принадлежит К. С. Пирсу ; см. Russell 1920, стр. 32. Рассел также вводит два эквивалентных термина , содержащихся в разнообразии или подразумевающих его .
4. Энциклопедия «Британника» называет это свойство квазирефлексивностью.
5. Фонсека де Оливейра и Перейра Кунья Родригес 2004, с. 337
6. Онлайновая энциклопедия целочисленных последовательностей A053763
7. Хаусман, Кахане и Тидман 2013, стр. 327–328
8. Кларк и Белинг 1998, стр. 187

Ссылки

• Кларк, Д.С.; Белинг, Ричард (1998). Дедуктивная логика – Введение в методы оценки и логическую теорию . University Press of America. ISBN 0-7618-0922-8.
• Фонсека де Оливейра, Хосе Нуну; Перейра Кунья Родригес, Сезар де Жезус (2004), «Транспонирование отношений: от функций Maybe к хеш-таблицам», Математика построения программ , Springer: 334–356
• Хаусман, Алан; Кахане, Ховард; Тидман, Пол (2013). Логика и философия – Современное введение . Уодсворт. ISBN 1-133-05000-X.
• Леви, А. (1979), Базовая теория множеств , Перспективы математической логики, Довер, ISBN 0-486-42079-5
• Лидл, Р.; Пильц, Г. (1998), Прикладная абстрактная алгебра , Тексты для бакалавров по математике , Springer-Verlag, ISBN 0-387-98290-6
• Куайн, У. В. (1951), Математическая логика , пересмотренное издание, переиздано в 2003 г., Harvard University Press, ISBN 0-674-55451-5
• Рассел, Бертран (1920). Введение в математическую философию (PDF) (2-е изд.). Лондон: George Allen & Unwin, Ltd. (Исправленное интернет-издание, февраль 2010 г.)
• Шмидт, Гюнтер (2010), Реляционная математика , Cambridge University Press, ISBN 978-0-521-76268-7

Внешние ссылки

• «Рефлексивность», Энциклопедия математики , EMS Press , 2001 [1994]