В математике , А бинарное отношение R над множеством X является рефлексивным , если оно относится каждый элемент X к себе. Формально, это может быть записано ∀ х ∈ X : х R х , или как I ⊆ R , где я есть тождественное соотношение на X .

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

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

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

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

Отношение ~ на множестве X называется квазирефлексивным, если каждый элемент, связанный с некоторым элементом, формально связан с самим собой: ∀ x , y ∈ X : x ~ y ⇒ ( x ~ x ∧ y ~ y ) . Примером может служить отношение «имеет тот же предел, что и» на множестве последовательностей действительных чисел: не каждая последовательность имеет предел, и, следовательно, отношение не является рефлексивным, но если последовательность имеет тот же предел, что и некоторая последовательность, тогда она имеет тот же предел, что и он сам. Имеет смысл различать левую и правую квазирефлексивность , определяемую ∀ x , y ∈ X : x ~ y ⇒ x ~ x и ∀ x , y ∈ X : x ~ y ⇒ y ~ y , соответственно. Например, левое евклидово отношение всегда является левым, но не обязательно правым, квазирефлексивным. Отношение R квазирефлексивно тогда и только тогда, когда его симметричное замыкание R ∪ R T квазирефлексивно слева (или справа).

Отношение ~ на множестве X называется корефлексивным, если для всех x и y в X выполняется, что если x ~ y, то x = y . Примером корефлексивного отношения является отношение целых чисел, в котором каждое нечетное число связано с самим собой и нет других отношений. Отношение равенства является единственным примером как рефлексивного, так и корефлексивного отношения, а любое корефлексивное отношение является подмножеством отношения идентичности. Союз корефлексивного и транзитивного отношения всегда транзитивен. Отношение R корефлексивно тогда и только тогда, когда его симметричное замыкание антисимметрично .

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

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

Примеры

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

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

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

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

Количество рефлексивных отношений на n -элементном множестве равно 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		2 п 2 — п			∑п к = 0 к ! S ( п , к )	п !	∑п к = 0 S ( п , к )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

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

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

Ссылки

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

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

Язык T-SQL в SQL Server базируется на стандартном языке SQL, основанном на реляционной модели, которая, в свою очередь, базируется на математических основаниях, таких как теория множеств и логика предикатов. В данной статье рассматривается фундаментальная тема из теории множеств: свойства отношений на множествах. Предлагаемые коды T-SQL читатели смогут использовать для проверки наличия определенных свойств тех или иных отношений. Но можно еще попробовать написать собственные версии сценариев (чтобы определить, обладает ли отношение конкретным свойством), прежде чем применять описанные в статье решения.

Множества и отношения

Георг Кантор, создатель теории множеств, определяет множество как «объединение в некое целое M совокупности определенных хорошо различимых объектов m нашего созерцания или мышления (которые будут называться элементами множества M)». Элементами множества могут быть объекты произвольной природы: люди, цифры и даже сами множества. Символы ∈ и ∉ обозначают, соответственно операторы, отражающие принадлежность (вхождение, членство) и непринадлежность элемента множеству. Так, запись x ∈ V означает, что x является элементом множества V, а запись x ∉ V — что x не является элементом V.

Свойства отношений на множествах

Теперь, когда мы освежили наши представления о множествах и отношениях, приступим к теме статьи — свойствам отношений на множествах. В качестве данных для примера обратимся к кодам листинга 1, чтобы создать таблицы V и R. V будет представлять множество, а R — бинарное отношение на нем. Используйте код листинга 2 для создания процедуры ClearTables, с помощью которой сможете очистить от записей обе эти таблицы перед их заполнением новыми образцами данных. Наконец, используйте коды листингов 3, 4 и 5 для наполнения таблиц V и R различными наборами данных для тестирования (будем их называть примерами данных 1, 2 и 3 соответственно).

Рефлексивность. Отношение R на множестве V является рефлексивным, если для любого элемента v множества V, v ∈ V, следует, что (v, v) ∈ R, то есть пара (v, v) всегда принадлежит R. А отношение R на V не рефлексивно, если найдется такой элемент v ∈ V, что пара (v, v) ∉ R. Вновь рассмотрим пример множества F — членов моей семьи.

Приступим к написанию T-SQL запроса к таблицам V и R (представляющим множество и отношение на этом множестве), проверяющего, обладает ли R свойством рефлексивности:

Первый подзапрос в операции EXCEPT возвращает набор всех упорядоченных пар (v, v) для всех строк таблицы V. Второй подзапрос возвращает набор упорядоченных пар (r1, r2) — всех строк таблицы R. Операция EXCEPT, таким образом, вернет все упорядоченные пары, встречающиеся в первом и отсутствующие во втором наборе. Предикат EXISTS нужен для проверки существования хотя бы одной записи в результирующем наборе. Если найдется хотя бы одна такая запись, то выражение CASE возвратит нам «Нет» (нет рефлексивности), но и «Да» — в противном случае (есть рефлексивность).

Взгляните на три примера наборов данных в листингах 3, 4 и 5 и попытайтесь определить без запуска запроса, в каких из них отношение будет рефлексивным. Ответы даются далее в тексте статьи.

Следующий запрос является проверочным — будет ли отношение R на V иррефлексивным:

SELECT
CASE
WHEN EXISTS
(SELECT * FROM dbo.R
WHERE r1 = r2)
THEN ‘Нет’
ELSE ‘Да’
END AS irreflexive

Внешние ключи в определении таблицы R были введены для обеспечения того, что лишь элементы V смогут составить атрибуты r1 и r2 записи R. Таким образом, остается только проверить, нет ли в R записей с совпадающими атрибутами r1 и r2. Если такая запись найдется, отношение R не иррефлексивно, если записи нет, оно иррефлексивно.

Следующий запрос является проверочным — будет ли отношение R на V симметричным:

Код запроса использует операцию EXCEPT. Первый подзапрос операции EXCEPT возвращает набор упорядоченных пар (r1, r2) — записей таблицы R, а второй — набор упорядоченных пар (r2, r1) по каждой записи R. Если отношение R на множестве V не симметрично, то операция EXCEPT вернет непустой результирующий набор, а предикат EXISTS, соответственно, значение TRUE и, наконец, выражение CASE вернет «Нет».

Если отношение симметрично, то выражение CASE даст «Да».

Асимметричность. Отношение R на множестве V асимметрично (не следует путать это свойство с несимметричностью), если для каждого набора (r1, r2) ∈ R, в котором r1 ≠ r2, справедливо, что (r2, r1) ∉ R. Примером асимметричного отношения на множестве F членов семьи автора будет отношение «являться родителем», которое было описано выше. В качестве упражнения постарайтесь придумать пример отношения на непустом множестве, которое одновременно является симметричным и асимметричным. Проверьте пример данных в этой статье в качестве решения.

В коде используется операция INTERSECT. Первый подзапрос в этой операции возвращает упорядоченную пару (r1, r2) для каждой записи таблицы R, в которой r1 r2.

Второй подзапрос операции INTERSECT возвращает упорядоченную пару (r2, r1) для каждой записи таблицы R, в которой r1 r2. Если в результирующий набор (результат пересечения этих множеств) входит хотя бы одна запись, это будет означать, что R не асимметрично; в противном случае R асимметрично.

Транзитивность. Отношение R на множестве V является транзитивным, если из включений (a, b) ∈ R и (b, c) ∈ R, всегда вытекает, что и (a, c) ∈ R. Примером транзитивного отношения на множестве членов семьи F будет отношение «является братом или сестрой», которое было рассмотрено выше.

Приведенный ниже код проверяет транзитивность отношения R:

В коде, во‑первых, используется внутренняя связь (inner join) между двумя экземплярами R, для того чтобы отбирать лишь те строки, в которых r2 в первом экземпляре совпадает с r1 на втором экземпляре. Во‑вторых, в коде применяется левая внешняя связь (left outer join) с третьим экземпляром таблицы R, в соответствии с которой r1 первого экземпляра R совпадает с r1 третьего экземпляра, а r2 второго экземпляра совпадает с r2 третьего. Если существует хотя бы одна результирующая строка во внутреннем подзапросе (условие отбора для третьего экземпляра: r1 есть Null), это означает, что отношение не транзитивно; в противном случае отношение R транзитивно.

Отношение эквивалентности. Отно­ше­нием эквивалентности является такое отношение, которое одновременно обладает свойствами рефлексивности, симметричности и транзитивности. Можно использовать запросы, предложенные выше для раздельной проверки наличия каждого свойства: если отношение обладает всеми тремя, то следует заключить, что имеет место отношение эквивалентности. Кроме того, вы можете использовать коды листинга 6 для проверки всех свойств отношения R на множестве V, которые ранее обсуждались в статье, в том числе проверку свойства быть отношением эквивалентности. Если провести прогонку листинга 6 для примеров данных 1, 2 и 3 (полученных на основе листингов 3, 4 и 5 соответственно), то получатся результаты, приведенные в таблицах 1, 2 и 3 соответственно.

Возвращаясь к основам T-SQL

Таким образом, мы рассмотрели фундаментальную тему из математической теории множеств: свойства отношений на множествах. Я предложил проверочные коды T-SQL для контроля свойств некоторого отношения, представленного таблицей R (упорядоченных пар элементов), на множестве элементов, представленных таблицей V.

Использование основных конструкций T-SQL помогло нам правильно настроить и применить средства этого языка для лучшего понимания свойств отношений на множествах.

Ицик Бен-Ган (Itzik@SolidQ.com) — преподаватель и консультант, автор книг по T-SQL, имеет звание SQL Server MVP

Таблица 1. Результат запроса для примера данных 1

Рефлексивность	Иррекфлексивность	Симметрия	Асимметрия	Транзитивность	Эквивалентность
Да	Нет	Нет	Да	Да	Нет

Таблица 2. Результат запроса для примера данных 2

Рефлексивность	Иррекфлексивность	Симметрия	Асимметрия	Транзитивность	Эквивалентность
Да	Нет	Да	Нет	Да	Да

Таблица 3. Результат запроса для примера данных 3

Рефлексивность	Иррекфлексивность	Симметрия	Асимметрия	Транзитивность	Эквивалентность
Нет	Да	Да	Да	Да	Нет

Смотреть лекцию на: ИНТУИТ | youtube.com

Если проблемы с видео, нажмите выше ссылку youtube

Рассмотрим — бинарное отношение из в (бинарное отношение на множестве ).

Отношение обладает свойством рефлексивности, если:

Отношение обладает свойством симметричности, если:

Отношение обладает свойством транзитивности, если:

Отношение называется отношением эквивалентности, если оно симметрично, рефлексивно и транзитивно.

Заметьте, отношение «имеет брата» не является ни рефлексивным, ни симметричным, ни транзитивным. Отношение «имеет брата или сестру» является симметричным отношением, но не является ни рефлексивным, ни транзитивным.

Рассмотрим отношение равенства на множестве целых чисел. Это отношение является отношением эквивалентности — оно симметрично, рефлексивно и транзитивно.

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

Отношения и арность

Бинарное отношение – это отношение арности 2, — оно связывает элементы двух множеств. Нетрудно определить отношение произвольной арности , которое связывает элементы множеств.

Отношением арности n называется подмножество декартова произведения множеств:

Пример:

Определим отношение «семья» арности 3 – тернарное отношение на декартовом произведении множеств для множества P из предыдущих примеров. Содержательно, первый элемент тройки задает отца семьи, второй – мать, третий – это множество детей в семье.

Для нашего примера тернарное отношение «семья» включает три элемента:

Особый случай представляет отношение арности 1. Наше общее определение отношения говорит, что отношение арности 1 – это подмножество множества . Содержательно, отношение арности 1 задает некоторое свойство элементов множества . Например, на множестве целых чисел можно выделить подмножество нечетных чисел, или подмножество простых чисел. Эти подмножества можно рассматривать как отношения арности 1. На множестве , которое неоднократно фигурировало в наших примерах, можно выделить подмножество со свойством «быть школьником», которое в нашем примере может состоять из двух элементов \{Владимир, Николай\} — детей Елены и Василия.

Графическое представление отношения

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

Рис. 5.1. Графический образ отношения «иметь брата»