1.1.2 Отношения на множествах. Основные понятия и определения. Однородные отношения. Отношения эквивалентности и порядка. Отношения на базах данных. Замыкание отношения.
Отношение — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов (арность) и собственным свойствам (симметричность, транзитивность и пр.). В математике примерами отношений являются равенство, коллинеарность, делимость и т. д.
Отношение может также означать результат операции деления, например:
двойное отношение,
отношение направленных отрезков.
Бинарным
отношением на множестве
называется
подмножество
;
вместо
часто пишут
.
Бинарное отношение на множестве - любое свойство, которым обладают любые два упорядоченных элемента этого множества.
Бинарное
отношение
на
множестве
называется
отношением
эквивалентности,
если выполнены следующие свойства:
(рефлексивность)
для
всех
;(симметричность)
для
всех
;(транзитивность)
для
любых элементов
.
(а) Если множество разбито в объединение непересекающихся подмножеств, то отношение "лежать в одном подмножестве" является отношением эквивалентности.
(б) Всякое отношение эквивалентности получается описанным способом из некоторого разбиения.
Бинарное
отношение
на
множестве
называется отношением
частичного порядка,
если выполнены такие свойства:
(рефлексивность)
для
всех
;
(антисимметричность)
для
всех
;
(транзитивность)
для
всех
.
Множество с заданным на нем отношением частичного порядка называют частично упорядоченным.
Говорят,
что два элемента
частично
упорядоченного множества сравнимы,
если
или
.
Заметим, что определение частичного
порядка не требует, чтобы любые два
элемента множества были сравнимы.
Добавив это требование, мы получим
определение линейного
порядка
(линейно
упорядоченного множества).
Область определения отношения (левая область отношения) - множество всех первых элементов пар отношения.
Область значений отношения (правая область отношения) - множество всех вторых элементов пар отношения.
Поле отношения - сумма левой и правой областей отношения.
Рефлексивное отношение на множестве - отношение, которое справедливо для каждого элемента множества как отношение этого элемента к самому себе. Например: - рефлексивные, - нерефлексивные.
Симметричное отношение - отношение, результат которого не меняется при перестановке операндов.
Транзитивное отношение на множестве - такое отношение, из справедливости которого для первого и второго операнда и справедливости для второго и третьего операнда следует справедливость этого отношения для первого и третьего операндов, при условии, что все операнды являются любыми элементами множества .
Отношение эквивалентности - отношение, являющееся одновременно рефлексивным, симметричным и транзитивным.
Класс эквивалентности - набор элементов множества, для которых эквивалентное отношение будет давать одинаковый результат.
Отношение
равенства двух операндов по модулю
- указывает, что разность операндов
делится на
.
Является эквивалентным. Число классов
эквивалентности равно
.
Антисимметричное отношение - бинарное отношение, из справедливости которого для двух операндов независимо от порядка их следования, следует равенство этих операндов. Например: ³
Рефлексивное отношение частичного порядка - отношение, являющееся одновременно рефлексивным, антисимметричным и транзитивным.
Частично упорядоченное множество - множество вместе с рефлексивным отношением частичного порядка на нём. Например, отношение "делится на" на множестве натуральных чисел.
Соседние двоичные наборы (пары) - двоичные наборы, отличающиеся значением только одного элемента (либо левого, либо правого).