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

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

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

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

Определения

Пусть — бинарное отношение на множестве , которое по определению является просто подмножеством. Для любого обозначение означает, что в то время как «не » означает, что ${\displaystyle R}$ ${\displaystyle X,}$ ${\displaystyle X\times X.}$ ${\displaystyle x,y\in X,}$ ${\displaystyle xRy}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle xRy}$ ${\displaystyle (x,y)\not \in R.}$

Отношение называется рефлексивным, если для каждого , или, что то же самое, если где обозначает тождественное отношение на . Рефлексивное замыкание - это объединение , которое эквивалентно можно определить как наименьшее (относительно ) рефлексивное отношение на том , что является надмножеством Отношения является рефлексивным. тогда и только тогда, когда оно равно своему рефлексивному замыканию. ${\displaystyle R}$ ${\displaystyle xRx}$ ${\displaystyle x\in X}$ ${\displaystyle \operatorname {I} _{X}\subseteq R}$ ${\displaystyle \operatorname {I} _{X}:=\{(x,x)~:~x\in X\}}$ ${\displaystyle X.}$ ${\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] если он не связывает ни один элемент с самим собой; то есть, если не выполняется ни одно отношение A является иррефлексивным тогда и только тогда, когда его дополнение в рефлексивно. Асимметричное отношение обязательно иррефлексивно. Транзитивное и иррефлексивное отношение обязательно асимметрично. ${\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. Этот термин принадлежит К.С. Пирсу ; см. Рассел 1920, с. 32. Рассел также вводит два эквивалентных термина, которые включаются в разнообразие или подразумевают его .
4. Британская энциклопедия называет это свойство квазирефлексивностью.
5. Фонсека де Оливейра и Перейра Кунья Родригес 2004, с. 337
6. Интернет-энциклопедия целочисленных последовательностей A053763
7. Хаусман, Кахане и Тидман, 2013, стр. 327–328.
8. Кларк и Белинг 1998, с. 187

Рекомендации

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

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

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