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

В математика, а бинарное отношение р через набор Икс является рефлексивный если он связывает каждый элемент Икс себе.^[1][2] Формально это можно записать ∀Икс ∈ Икс : x R x, или как я р где я отношение идентичности на Икс.

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

Связанные термины

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

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

Отношение ~ на множестве Икс называется квазирефлексивный если каждый элемент, связанный с каким-либо элементом, также относится к самому себе, формально: ∀ Икс, у ∈ Икс : Икс ~ у ⇒ (Икс ~ Икс ∧ у ~ у). Примером может служить отношение "имеет тот же предел, что и" на множестве последовательностей действительных чисел: не каждая последовательность имеет предел, и, следовательно, отношение не является рефлексивным, но если последовательность имеет тот же предел, что и некоторая последовательность, тогда она имеет тот же предел, что и он сам. Есть смысл различать оставили и правая квазирефлексивность, определяется ∀ Икс, у ∈ Икс : Икс ~ у ⇒ Икс ~ Икс^[3] и ∀ Икс, у ∈ Икс : Икс ~ у ⇒ у ~ у, соответственно. Например, левый Евклидово отношение всегда левый, но не обязательно правый, квазирефлексивный. Отношение р квазирефлексивен тогда и только тогда, когда его симметричное закрытие р∪р^Т квазирефлексивен слева (или справа).

Отношение ~ на множестве Икс называется coreflexive если для всех Икс и у в Икс он считает, что если Икс ~ у тогда Икс = у.^[4] Примером корефлексивного отношения является отношение на целые числа в котором каждое нечетное число связано с собой и нет никаких других отношений. Отношение равенства является единственным примером как рефлексивного, так и коререфлексивного отношения, а любое корефлексивное отношение является подмножеством отношения идентичности. Объединение корефлексивного отношения и транзитивного отношения на одном и том же множестве всегда транзитивно. Отношение р является корефлексивным тогда и только тогда, когда его симметричное замыкание равно антисимметричный.

Рефлексивное отношение на непустом множестве Икс не может быть иррефлексивным, ни асимметричный, ни антитранзитивный.

В рефлексивное закрытие Бинарного отношения ~ на множестве Икс наименьшее рефлексивное отношение на Икс это суперсет из ~. Эквивалентно, это объединение ~ и отношение идентичности на Икс, формально: (≃) = (~) ∪ (=). Например, рефлексивное замыкание (<) равно (≤).

В рефлексивное сокращение, или же иррефлексивное ядро, бинарного отношения ~ на множестве Икс это наименьшее отношение ≆ такое, что ≆ имеет то же рефлексивное замыкание, что и ~. Это можно рассматривать как противоположность рефлексивному закрытию. Это эквивалентно дополнению тождественного отношения на Икс что касается ~, формально: (≆) = (~) (=). То есть он эквивалентен ~ за исключением тех случаев, когда Икс~Икс правда. Например, рефлексивное сокращение (≤) равно (<).

Примеры

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

• "равно" (равенство )
• "это подмножество из "(установить включение)
• "делит" (делимость )
• "Больше или равно"
• "меньше или равно"

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

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

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

Количество рефлексивных отношений на п- набор элементов 2^п2−п.^[5]

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

Элементы	Любой	Переходный	Рефлексивный	Предварительный заказ	Частичный заказ	Всего предзаказ	Общий заказ	Отношение эквивалентности
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	4,096	355	219	75	24	15
п	2п^2		2п^2−п			∑п k=0  k! S (п, k)	п!	∑п k=0  S (п, k)
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

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

Примечания

1. Леви 1979: 74
2. Реляционная математика, 2010 г.
3. В Энциклопедия Британника называет это свойство квазирефлексивностью.
4. Фонсека де Оливейра, Дж. Н. и Перейра Кунья Родригес, К. Д. Дж. (2004). Перенос отношений: от функций Maybe к хеш-таблицам. По математике построения программ (с. 337).
5. Он-лайн энциклопедия целочисленных последовательностей A053763
6. Алан Хаусман; Говард Кахане; Пол Тидман (2013). Логика и философия - современное введение. Уодсворт. ISBN  1-133-05000-Х. Здесь: с.327-328
7. Д.С. Кларк; Ричард Белинг (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 году, издательство Harvard University Press. ISBN  0-674-55451-5
• Гюнтер Шмидт, 2010. Реляционная математика. Издательство Кембриджского университета, ISBN  978-0-521-76268-7.

внешняя ссылка

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