Специальная математика. Соловьев А.Е. - 13 стр.

  5. Связность ( полнота ): x  y  x  y или y  x (например, для любых двух различных
натуральных чисел: либо x < y, либо y < x)
  6. Транзитивность: x  y , y  z  x  z (например, x = y и у = z  y = z)
 7. Антитранзитивность: x  y, y  z x  z (например, отношение перпендикулярности
 прямых).

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

   Отношение, обладающее одновременно свойствами рефлексивности, симметричности и
транзитивности, называется отношением эквивалентности.
~ - символ отношения эквивалентности.
[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].


                                         — 13 —