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

Транзитивные бинарные отношения

	Симметричный	Антисимметричный	Связаны	Обоснованный	Присоединяется	Встречается	Рефлексивный	Нерефлексивный	Асимметричный
Также известный как:			Итого, Semiconnex					Антирефлексивный
Отношение эквивалентности	✓	✗	✗	✗	✗	✗	✓	✗	✗
Предзаказ (Квазипорядок)	✗	✗	✗	✗	✗	✗	✓	✗	✗
Частичный заказ	✗	✓	✗	✗	✗	✗	✓	✗	✗
Всего предзаказ	✗	✗	✓	✗	✗	✗	✓	✗	✗
Общий заказ	✗	✓	✓	✗	✗	✗	✓	✗	✗
Предварительный заказ	✗	✗	✓	✓	✗	✗	✓	✗	✗
Хорошо-квазиупорядоченный	✗	✗	✗	✓	✗	✗	✓	✗	✗
Хороший порядок	✗	✓	✓	✓	✗	✗	✓	✗	✗
Решетка	✗	✓	✗	✗	✓	✓	✓	✗	✗
Соединение-полурешетка	✗	✓	✗	✗	✓	✗	✓	✗	✗
Встреча-полурешетка	✗	✓	✗	✗	✗	✓	✓	✗	✗


Строгий частичный заказ	✗	✗	✗	✗	✗	✗	✗	✓	✓
Строгий слабый порядок	✗	✗	✗	✗	✗	✗	✗	✓	✓
Строгий общий порядок	✗	✗	✓	✗	✗	✗	✗	✓	✓
	Симметричный	Антисимметричный	Связаны	Обоснованный	Присоединяется	Встречается	Рефлексивный	Нерефлексивный	Асимметричный
Определения: ${\ displaystyle \ scriptstyle {{\ text {Для всех}} \, a, b \, {\ text {and}} \, S \ neq \ varnothing:}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$	${\ displaystyle \ scriptstyle {aRb \, {\ text {and}} \, bRa \ Rightarrow a = b}}$	${\ displaystyle \ scriptstyle {a \ neq b \ Rightarrow aRb \, {\ text {или}} \, bRa}}$	${\ displaystyle \ scriptstyle {\ min S \, {\ text {exists}}}}$	${\ displaystyle \ scriptstyle {a \ vee b \, {\ text {exists}}}}$	${\ displaystyle \ scriptstyle {a \ wedge b \, {\ text {exists}}}}$	${\ displaystyle \ scriptstyle {aRa}}$	${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$

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

{\ displaystyle R}

{\ displaystyle \ scriptstyle {{\ text {Для всех}} \, a, b, c, {\ text {if}} aRb {\ text {and}} bRc {\ text {then}} aRc}.}

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

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

Определения

Позвольте быть бинарным отношением на множестве , которое по определению является лишь подмножеством 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 рефлексивных закрытия из является объединение , которое эквивалентно , может быть определенно как наималейшие (относительно ) рефлексивным отношение на том , что является подмножество из А относительно рефлексивно тогда и только тогда, когда он равен своему рефлексивному замыканию. ${\ displaystyle R}$ ${\ displaystyle xRx}$ ${\ displaystyle x \ in X}$ ${\ displaystyle \ operatorname {I} _ {X} \ substeq R}$ ${\ displaystyle \ operatorname {I} _ {X}: = \ {(x, x) ~: ~ x \ in X \}}$ ${\ displaystyle X.}$ ${\ displaystyle R}$ ${\ displaystyle R \ cup \ operatorname {I} _ {X},}$ ${\ displaystyle \, \ substeq}$ ${\ displaystyle X}$ ${\ displaystyle R.}$ ${\ displaystyle R}$

Рефлексивное сокращение или иррефлексивное ядра из является наималейшим (относительно ) отношение на том , что имеет такое же рефлексивное замыкание , как она равна The иррефлексивного ядро может, в некотором смысле, можно рассматривать как конструкцию , которая является «противоположностью» рефлексивное замыкание Так , например, возвратное замыкание канонического строгого неравенства на переАльсе является обычным нестрогим неравенством , тогда как рефлексивном сокращения IS ${\ displaystyle R}$ ${\ displaystyle \, \ substeq}$ ${\ 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}$

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

Левый квазирефлексивный: Если когда-либо таковы, то обязательно ${\ 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 \ чашка R ^ {\ operatorname {T}}}$

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

Количество 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 ^{п ² - п}			${\ textstyle \ sum _ {k = 0} ^ {n} k!}$	п !	${\ textstyle \ сумма _ {к = 0} ^ {п}}$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

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

Примечания

использованная литература

Леви А. (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]

Languages

In other projects