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

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

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

Определения [ править ]

Бинарные отношения

	Симметричный	Антисимметричный	Connex	Обоснованный	Присоединяется	Встречается
Отношение эквивалентности	✓	✗	✗	✗	✗	✗
Предзаказ (квазипорядок)	✗	✗	✗	✗	✗	✗
Частичный заказ	✗	✓	✗	✗	✗	✗
Всего предзаказ	✗	✗	✓	✗	✗	✗
Общий заказ	✗	✓	✓	✗	✗	✗
Предварительный заказ	✗	✗	✓	✓	✗	✗
Хорошо-квазиупорядоченный	✗	✗	✗	✓	✗	✗
Хороший порядок	✗	✓	✓	✓	✗	✗
Решетка	✗	✓	✗	✗	✓	✓
Соединение-полурешетка	✗	✓	✗	✗	✓	✗
Встреча-полурешетка	✗	✓	✗	✗	✗	✓

« ✓ » указывает на то, что свойство столбца требуется в определении строки.
Например, определение отношения эквивалентности требует, чтобы оно было симметричным.
Все определения неявно требуют транзитивности и рефлексивности .

Позвольте быть бинарным отношением над множеством, которое по определению является лишь подмножеством For any, обозначение означает, что в то время как «не » означает, что ${\ 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.}$

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

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

Связанные определения [ править ]

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

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

Левый квазирефлексивный: Если когда-либо таковы, то обязательно ^[3] $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$ $yRx,$ $x=y.$

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

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

Примеры [ править ]

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

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

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

"не равно"
" взаимно просто с" (для целых чисел> 1, поскольку 1 взаимно проста с собой)
"является правильным подмножеством"
"больше, чем"
"меньше чем"

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

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

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

Количество рефлексивных отношений [ править ]

Количество рефлексивных отношений на n -элементном множестве равно 2 ^{n ² - n} . ^[5]

Количество n -элементных бинарных отношений разных типов
Элементы	Любой	Переходный	Рефлексивный	Предварительный заказ	Частичный заказ	Всего предзаказ	Общий заказ	Отношение эквивалентности
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65 536	3,994	4096	355	219	75	24	15
п	2 ^{п ²}		2 ^{п ² - п}			$\sum п к = 0 к! S (п, к)$	п !	$\sum п к = 0 S (п, к)$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Философская логика [ править ]

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

Примечания [ править ]

↑ Леви 1979: 74
^ Реляционная математика, 2010
^ Encyclopedia Britannica называет это свойство квази-рефлексивность.
Перейти ↑ Fonseca de Oliveira, JN, & Pereira Cunha Rodrigues, CDJ (2004). Перенос отношений: от функций Maybe к хеш-таблицам. По математике построения программ (с. 337).
^ Интернет -энциклопедия целочисленных последовательностей A053763
↑ Алан Хаусман; Говард Кахане; Пол Тидман (2013). Логика и философия - современное введение . Уодсворт. ISBN 1-133-05000-Х. Здесь: с.327-328
^ DS Кларк; Ричард Белинг (1998). Дедуктивная логика - Введение в методы оценки и логическую теорию . Университетское издательство Америки. ISBN 0-7618-0922-8. Здесь: с.187

Ссылки [ править ]

Леви А. (1979) Основная теория множеств , Перспективы математической логики, Springer-Verlag. Перепечатано в 2002 г., Дувр. ISBN 0-486-42079-5
Лидл, Р. и Пилц, Г. (1998). Прикладная абстрактная алгебра , Тексты для студентов по математике , Springer-Verlag. ISBN 0-387-98290-6
Куайн, Западная Вирджиния (1951). Математическая логика , переработанное издание. Перепечатано в 2003 году, издательство Гарвардского университета. ISBN 0-674-55451-5
Гюнтер Шмидт, 2010. Реляционная математика . Издательство Кембриджского университета, ISBN 978-0-521-76268-7 .

Внешние ссылки [ править ]

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

[1] Леви 1979: 74

[2] Реляционная математика, 2010

[Britannica-3] Encyclopedia Britannica называет это свойство квази-рефлексивность.

[4] Перейти ↑ Fonseca de Oliveira, JN, & Pereira Cunha Rodrigues, CDJ (2004). Перенос отношений: от функций Maybe к хеш-таблицам. По математике построения программ (с. 337).

[5] ^ Интернет -энциклопедия целочисленных последовательностей A053763

[6] Алан Хаусман; Говард Кахане; Пол Тидман (2013). Логика и философия - современное введение . Уодсворт. ISBN 1-133-05000-Х. Здесь: с.327-328

[7] DS Кларк; Ричард Белинг (1998). Дедуктивная логика - Введение в методы оценки и логическую теорию . Университетское издательство Америки. ISBN 0-7618-0922-8. Здесь: с.187

[1]