Свойства отношений

1 2 3 4 5 6 7

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

x r x (например, x = x)

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

ù x r x (например, x < x)

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

x r y Þ y r x (например, x = y Þ y = x)

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

x ¹ y, x r y Þù y r x

(например, x ¹y; y £ x Þù y ³ x)

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

xry Þ ù y r x (например, x < y Þù y < x)

5. Связность(полнота):

x ¹ y Þ x r y или y r x

(например, для любых двух различных натуральных чисел: либо x < y, либо y < x)

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

x r y, y r z Þ x r z

(например, x = y и у = z Þ y = z)

7. Антитранзитивность:

x r y, y r z Þù x r z

(например, отношение перпендикулярности прямых).

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

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

~ - символ отношения эквивалентности.

[x] - множество элементов, эквивалентных x (класс эквивалентности х).

Свойства отношения эквивалентности:

1. x ~ х

2. Если x ~ y Þ [x] = [y]

Доказательство 1-го свойства: Следует из свойства рефлексивности.

Доказательство 2-го свойства:

1. z Î [x] Þ z ~ x, x ~ y Þ z ~ y Þ z Î [y], т.е. [x] Í [y]

2. z Î [y] Þ z ~ y, x ~ y Þ z ~ x Þ z Î [x], т.е. [y] Í [x].

Следовательно [x] = [y]

P(M) - множество-степень множества М есть множество всех подмножеств множества М.

Пример:

М={1, 2, 3}

P(M)={Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

П(M) - покрытием множества М будем называть любое подмножество множества Р(М), такое, что объединение входящих в него элементов совпадает с М.

П(M) = {{1,2}, {2}, {2,3}}

так как {1,2} È {2} È {2,3} = {1, 2,3}

R(M) - разбиением множества М называется такое покрытие множества М, в котором элементы не пересекаются.

Пример разбиения: R = {{1,2}, {3}}

Свойства:

1. Каждый элемент исходного множества М принадлежит какому-либо из множеств, составляющих разбиение.

2. Каждый элемент исходного множества принадлежит строго одному из множеств, составляющих разбиение.

Теорема: Отношение эквивалентности разбивает множество, на котором оно определено на классы эквивалентности.

Доказательство:

1. Очевидно х ~ [x]

2. Предположим, что z Î [x] и z Î [y]. Тогда из x ~ y и z ~ y следует x ~ y и по второму свойству отношения эквивалентности [x] = [y].

Отношения порядка.

Порядок / Свойства	Рефлексивность	Антирефлексивность	Антисимметричность	Полнота	Транзитивность
нестрогий (частичный)	+		+		+
совершенный нестрогий	+		+	+	+
строгий		+	(+)		+
совершенный строгий		+	(+)	+	+