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

показывать Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

В математике бинарное отношение $R$ на съемочной площадке $X$ является рефлексивным, если оно связывает каждый элемент $X$ самому себе.

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

Определения

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

Отношение $R$ называется рефлексивным, если $xRx$ для каждого $x\in X$ или эквивалентно, если $\operatorname {I} _{X}\subseteq R$ где $\operatorname {I} _{X}:=\{(x,x)~:~x\in X\}$ обозначает тождественное отношение на $X.$ Рефлекторное закрытие ​ $R$ это союз $R\cup \operatorname {I} _{X},$ что эквивалентно можно определить как наименьшее (по отношению к $\subseteq$) рефлексивное отношение на $X$ это надмножество ​ $R.$ Отношение $R$ рефлексивно тогда и только тогда, когда оно равно своему рефлексивному замыканию.

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

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

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

бездумный , антирефлексивный или родственник алиора

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

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

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

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

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

квазирефлекторно

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

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

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

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

если когда-нибудь $x,y\in X$ таковы, что $xRy,$ тогда обязательно $x=y.$ Отношение $R$ является корефлексивным тогда и только тогда, когда его симметричное замыкание антисимметрично .

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

Примеры

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

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

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

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

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

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

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

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

Число рефлексивных отношений на $n$- набор элементов $2^{n^{2}-n}.$

Количество n -элементных бинарных отношений разных типов

Elem­ents	Любой	Переходный	Рефлексивный	Симметричный	Предварительный заказ	Частичный заказ	Общий предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
н	2 н 2		2 п ( п -1)	2 п ( п +1)/2			∑ н к = 0 к ! С ( п , к )	н !	∑ н k =0 S ( n , k )
ОЭИС	А002416	А006905	А053763	А006125	А000798	А001035	А000670	А000142	А000110

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

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

Авторы философской логики часто используют разную терминологию.Рефлексивные отношения в математическом смысле называются в философской логике тотально рефлексивными , а квазирефлексивные отношения — рефлексивными .

Ссылки

• Кларк, Д.С.; Белинг, Ричард (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-е изд.). Лондон: George Allen & Unwin, Ltd. (исправленное онлайн-издание, февраль 2010 г.)
• Шмидт, Гюнтер (2010), Реляционная математика , Издательство Кембриджского университета, ISBN  978-0-521-76268-7

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

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