В математике, двоичное отношение R в наборе X является рефлексивным, если он связывает каждый элемент X с собой. Формально это может быть записано ∀ x ∈ X: x R x или как I ⊆ R, где I - тождественное отношение на X.
Пример Рефлексивное отношение - это отношение «равно » на множестве действительных чисел, поскольку каждое действительное число равно самому себе. Говорят, что рефлексивное отношение обладает рефлексивным свойством или, как говорят, обладает рефлексивностью . Наряду с симметрией и транзитивностью рефлексивность является одним из трех свойств, определяющих отношения эквивалентности.
Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Знак «✓» указывает, что свойство столбца требуется в определении строки.. Например, определение отношения эквивалентности требует, чтобы оно было симметричным.. Все определения неявно требуют транзитивности и рефлексивности. |
Бинарное отношение называется иррефлексивным или антирефлексивный, если он не связывает с ним ни одного элемента я. Примером является отношение «больше чем» (x>y) для вещественных чисел. Не всякое отношение, которое не является рефлексивным, является иррефлексивным; можно определить отношения, в которых одни элементы связаны сами с собой, а другие - нет (т. е. ни все, ни ни один). Например, бинарное отношение «произведение x и y четно» рефлексивно на множестве четных чисел, нерефлексивно на множестве нечетных чисел и не рефлексивно или нерефлексивно на множестве натуральные числа. Однако отношение является иррефлексивным тогда и только тогда, когда, его дополнение является рефлексивным.
Отношение ~ на множестве X называется квазирефлексивным, если каждый элемент, связанный с некоторым элементом, также относится к самому себе, формально: ∀ x, y ∈ X: x ~ у ⇒ (х ~ х ∧ у ~ у). Примером может служить отношение «имеет тот же предел, что и» на множестве последовательностей действительных чисел: не каждая последовательность имеет предел, и, следовательно, отношение не является рефлексивным, но если последовательность имеет тот же предел, что и некоторая последовательность, тогда она имеет тот же предел, что и он сам. Имеет смысл различать левую и правую квазирефлексивность, определяемую ∀ x, y ∈ X: x ~ y ⇒ x ~ x и ∀ x, y ∈ X: x ~ y ⇒ y ~ y соответственно. Например, левое евклидово отношение всегда левое, но не обязательно правое, квазирефлексивное. Отношение R квазирефлексивно тогда и только тогда, когда его симметричное замыкание R∪R квазирефлексивно слева (или справа).
Отношение ~ на множестве X называется coreflexive, если для всех x и y в X выполняется, что если x ~ y, то x = y. Примером корефлексивного отношения является отношение целых чисел, в котором каждое нечетное число связано с самим собой, и нет никаких других отношений. Отношение равенства является единственным примером как рефлексивного, так и корефлексивного отношения, а любое корефлексивное отношение является подмножеством отношения идентичности. Союз корефлексивного и транзитивного отношения всегда транзитивен. Отношение R корефлексивно, если и только если его симметричное замыкание антисимметрично.
Рефлексивное отношение на непустом множестве X не может быть ни иррефлексивным, ни асимметричным, ни антитранзитивное.
рефлексивное замыкание ≃ бинарного отношения ~ на множестве X - это наименьшее рефлексивное отношение на X, которое является надмножеством отношения ~. Эквивалентно, это объединение ~ и тождественного отношения на X, формально: (≃) = (~) ∪ (=). Например, рефлексивное замыкание (<) is (≤).
рефлексивной редукции или иррефлексивного ядра бинарного отношения ~ на множестве X является наименьшим отношением ≆ таким, что ≆ разделяет то же рефлексивное замыкание, что и ~. Его можно рассматривать как противоположность рефлексивному замыканию. Это эквивалентно дополнению отношения тождества на X относительно ~, формально: (≆) = (~) \ (=). То есть это эквивалентно ~, за исключением случаев, когда x ~ x истинно. Например, рефлексивное сокращение (≤) равно (<).
Примеры рефлексивных отношений включают:
Примеры нерефлексивных отношений включают:
Количество рефлексивных отношений в n-элементном наборе равно 2.
Элементы | Любые | Транзитивные | Рефлексивный | Предварительный заказ | Частичный заказ | Общий предварительный заказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
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 |
n | 2 | 2 | ∑n. k = 0 k! S (n, k) | n! | ∑n. k = 0 S (n, k) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Авторы философской логики часто используют другую терминологию. Рефлексивные отношения в математическом смысле называются полностью рефлексивными в философской логике, а квазирефлексивные отношения называются рефлексивными .