Всякое отношение эквивалентности но множестве М определяет разбиение множества М,причем среди элементов разбиения нет пустых; и обратно, всякое разбиение множества М, не содержащее пустых элементов, определяет эквиваленость на множестве М.[1]

Рис. 0

Эту Формулу ...можно не декодировать.

Нравится , о чем это вообще ? Эквивалентность эквивалентна разбиению, которое вообще-то тоже эквивалентность ,которая... и.т.д ? Временно отложим эту замечательную книжку в сторону ...

Я начал разбирать это с понятия отношений. Ниже представлено отношение 5 элементов в виде таблицы :

Рис. 1

Бинарным отношением между множествами А и В называется подмножество R прямого произведения A на B. В том случае , когда A = B ( наш случай) мы просто говорим об отношении R на A ( R на X) [2]

Это должно означать, что множество всех черных точек на представленном графике это как раз множество R. Есть 25 возможных позиций где могли бы встать эти точки, это прямое произведение X на X. Множество X состоит из 5 элементов. Есть другой способ представить это же отношение с помощью графов:

Рис.2

Отношение может быть задано с помощью формулы :

R = {(x,y): x -- < наименование отношения > к y} определяет отношение на множестве X = {1,2,3,4,5}

Отношение может быть задано с помощью упорядоченных пар:

отношение R состоит из пар (1,2) (2,3) (3,4) (4,5) (5,1) или R = {(1,2) , (2,3) , (3,4) , (4,5) (5,1)}

Рассматриваемое отношение может быть представлено как подстановка:

Рис. 3

Все отношения характеризуются свойствами :

Это не все свойства отношений. Отношение на Рис.1 Рефлексивно, Симметрично, и может быть транзитивно ( В зависимости от того что понимается под отношением). Отношение Рис.2 Также Рефлексивно ( круглые стрелочки вокруг вершин) Симметрично (стрелочке туда, соответствует стрелочка обратно). Отношение на Рис.2 НЕ транзитивно, т.к "В месте со стрелками из вершины x в y и из y в x у него будет стрелка из x в z"[2]

Правда то, что представлено на Рис.2 это цепь, а множество вершин R образуют компоненту связности. А значит это разбиение, т.е эквивалентность. А значит отношение всетаки таки транзитивено [3]( не знаю как тут быть...)

[ Мне кажется что если это отношение " НЕНАВИСТЬ на множестве людей", то конечно НЕ ТРАНЗИТИВНО. Но Если Это например "... имеет те же углы что ..." на множестве всеx треугольников, то ТРАНЗИТИВЕН без сомнения.] (4)

Обозначим наше множество через A = {1,2,3,4,5}

1. ....по-проще :
   Разбиением множества A называется совокупность не пустых подмножеств

   A₁ A₂ A_{3 ...} A_n Где
   1. A = A₁ U A₂ U A₃ U _... U A_n
   2. A_i не пересекает A _j , при i <> j

2. Более строгое определение - Семейство множеств такое, что :

   Где I (1) это множество индексов при при том , что A_i это подмножество X, и i ринадлежит множеству индексов I. Называется разбиением. [3]

   
   

   

   Рис. 4
   

   • П = {<1,2,3,4,5>} это разбиение
   • П = {<>} это не разбиение по условию (1)
   • П = {<1,2,3,4,5> , <1>} это не разбиение по условию (2,3)
   • П = {<1,2,3,4,5> , <>} это не разбиение по условию (1,3)
   • П = {<1>,<2>,<3>,<4>,<5> } это разбиение
   • П = {<1,2>,<3,4>,<5> } это разбиение

Еще одно определение :

разбиением множества М называется множество непересекающихся, непустых подмножеств, объеденение которых совпадает с М. [4]

Бинарное отношение , определенное на множестве S называется отношением эквивалентности если оно удовлетворяет свойствам :

1. рефлексивности
2. симметричности
3. транзитивности

   Все элементы из множества S эквивалентные данному s_i, образуют множество S_i, которое называется классом эквивалентности... (Все что принадежит множеству и соотносится с вершиной x, а также удовлетворяет трем вышеперечисленым свойствам, это класс эквивалентности).
   

   

   
   

   Таким образом определенное на множестве S отношение выполняет разложение его на непересекающиеся классы (эквивалентности), которые являются разбиениями. И удовлетворяют свойствам разбиений.[5]

1. Отношение "... Имеет тот же возраст , что и ..." на множестве всех людей . “ЭКВИВАЛЕНТНЫЕ” люди принадлежат к одной и той же возрастной группе.
2. Если у людей глаза одинакового цвета то эквивалентны, в отношении цвета глаз.
3. Отношение “... Имеет те же углы что ...” на множестве всех треугольников Очевидно , треугольники эквивалентны тогда и только тогда когда они подобны.
4. Если две прямые паралельны или совпадают, то пишем D || D'; очевидно || это отношение эквивалентности.
5. Отношение R заданное условием x R y, если только xy > 0 на множестве ненулевых целых чисел является отношением эквивалентности. При этом эквивалентные числа имеют одинаковый знак.

• [1] Ф.А.Новиков Дискретная математика для программистов (учебник)
• [2] Р.Хаггарти Дискретная математика для программистов
• [3] К. Берж Теория графов и ее применение
• [4] Ю.Г Карпов Теория автоматов (учебник для вузов)
• [5] Б.Н.Иванов Дискретная математика (алгоритмы и программы)

(c) A/KRYL 2004. Разрешается перепечатка и распространение c разрешения автора. Krylll@mail.ru (Если вы увидели ошибки, или что-то имеете сказать пишите...)