Свойства бинарных отношений

Пусть задано на множестве , .

1. Рефлексивность: .

Отношение rна множестве X называется рефлексивным, если для любого имеет место ,то есть каждый элемент находится в отношении r к самому себе.

Матрица рефлексивного отношения имеет единичную главную диагональ, а граф рефлексивного отношения – имеет петлю возле каждого своего элемента.

Например:

,

,

,

.

На множестве людей: “быть родственником”, ”обучаться в одной студенческой группе ”.

На множестве множеств: A Í B, A=B.

2. Антирефлексивность: .

Отношение rна множестве X называется антирефлексивным, если не существует хÎХтакого, чтоимеет место хrх,то есть ни один элемент не находится в отношении rк самому себе.

Матрица антирефлексивного отношения имеет нулевую главную диагональ, а граф – не имеет ни одной петли.

Например:

,

,

.

На множестве людей: “быть родителем”, ”быть ребенком”.

На множестве множеств: A Ì B, A¹B.

3. Нерефлексивность: .

4. Симметричность: .

Отношение rна множестве X называется cимметричным, если для всех хи yизХ,из принадлежности(x,y)отношению rследует, что и (y,x)принадлежит отношению r.

Матрица симметричного отношения симметрична относительно главной диагонали, а граф – для каждой дуги (x,y)существует обратная дуга (y,x).

Например:

,

,

.

На множестве людей: “быть родственником”, ”обучаться в одной студенческой группе ”.

Отношение " брат " является симметричным на множестве мужчин и не является симметричным на множестве всех людей.

На множестве множеств: , .

5. Антисимметричность: .

Отношение r на множестве X называется антиcимметричным, если для всех хи yизХ,из принадлежности(x,y)и (y,x)отношению rследует, что .

Матрица антисимметричного отношения не имеет ни одной симметричной единицы относительно главной диагонали, а граф – для каждой дуги (x,y)не существует обратная дуга (y,x)и наоборот.

Свойства симметричности и антисимметричности не являются взаимоисключающими, примером может служить отношения равенства на множестве натуральных чисел.

Например:

,

,

,

,

.

На множестве людей: “быть выше”, ”быть равным”.

На множестве множеств: , , .

6. Транзитивность: .

Отношение rна множестве X называется транзитивным, если для всех х,y,zизХ,из принадлежности (x,y)и (y,z)отношению rследует, что (x,z)также принадлежитr.

Например:

,

,

,

,

,

.

На множестве людей: “быть выше”, ”обучаться в одной студенческой группе”.

На множестве множеств: , , .

Отношение rна множестве X не является транзитивным, если существует хотя бы один пример того, что для некоторых х,y,zмножества Хиз принадлежности (x,y)и (y,z)отношениюrне следует, что (x,z)также принадлежитr.

Например.

1) .

Отношение не является транзитивным, потому что из принадлежности этому отношению пар и , не следует, что и пара принадлежит отношению .

2) Пусть задано двухэлементное множество определим все бинарные отношения на этом множестве:

.

Для всех отношений, заданных на множестве , определить наличие или отсутствие свойств: рефлексивность, антирефлексивность, симметричность и антисимметричность, транзитивность.

Введем следующие обозначения:

а) рефлексивность – Р;

б) антирефлексивность – АР;

в) симметричность – С;

г) антисимметричность – АС;

д) транзитивность – Т.

№		Р	АР	С	АС	Т
		-	+	+	+	+
		-	-	+	+	+
		-	+	-	+	+
		-	+	-	+	+
		-	-	+	+	+
		-	-	-	+	+
		-	-	-	+	+
		+	-	+	+	+
		-	+	+	-	-
		-	-	-	+	+
		-	-	-	+	+
		-	-	+	-	-
		+	-	-	+	+
		+	-	-	+	+
		-	-	+	-	-
		+	-	+	-	+

Отношение порядка – антисимметрично, транзитивно.

Отношение нестрого порядка ( ) – рефлексивно,
антисимметрично,
транзитивно.

,

.

На множестве множеств: , .

Отношение строгого порядка ( ) – антирефлексивно,
антисимметрично,
транзитивно.

,

.

На множестве множеств:“ ”.

- “xпредшествуетyв смысле отношения строгого порядка”,

- “xпредшествуетyв смысле отношения нестрогого порядка”.

Два элемента и некоторого упорядоченного множества (множества, на котором существует отношение порядка) сравнимы между собой, если предшествует , и/или предшествует в смысле отношения порядка.

Если в упорядоченном множестве существует пара элементов xиy, для которой ни не предшествует , ни не предшествует , тогда говорят, что эти два элемента не сравнимы между собой в смысле этого.

В отношениях полного порядка все элементы сравнимы между собой, а в отношениях частичного порядка не все элементы сравнимы между собой.

Например:

Отношения полного порядка:

,

.

Отношения частичного порядка:

,

,

на множестве множеств:

,

,

.

Отношение эквивалентности ( ~ )– рефлексивно,
симметрично,
транзитивно.

Класс эквивалентности для х: .

Например:

,

r= { (x, y) | x=y(mod m), x,y Î N }.

На множестве людей: “иметь одно имя”, ”обучаться в одной студенческой группе”.

На множестве множеств: .

Отношение эквивалентности разбивает – множество, на котором задано отношение на непересекающиеся, которые называют классами эквивалентности.

Элементы, принадлежащие одному классу, находятся между собой в отношении эквивалентности, элементы из разных классов в отношении эквивалентности между собой не находятся.

Например:

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

.

Область определения: .

Область значений: .

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

Классы эквивалентности:

.

Например:

Отношение .

Это отношение называют отношением сравнения по модулю на множестве натуральных чисел.

означает, что и имеют одинаковый остаток при делении на .

Отрезок натурального ряда .

Отношение сравнения по модулю 3 на :

.

Область определения и область значений: .

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

Отношение – отношение эквивалентности.

Классы эквивалентности: .

Пусть – некоторое бинарное отношение.