∆ Определение 1. Пусть $M$ — множество. Произвольное множество $R\subset\{(a,b)\mid a,b \in M\}$ упорядоченных пар элементов $M$ называется (бинарным) отношением на $M$. Если $(a,b) \in R$, то пишут $a \sim_R b$, или просто $a \sim b$.

∆ Определение 2. Отношение $\sim$ на $M$ называется 1) рефлексивным, если $a \in M \Rightarrow a \sim a$; 2) симметричным, если для любых $a,b \in M$ выполнено $a \sim b \Rightarrow b \sim a$; 3) транзитивным, если для любых $a,b,c \in M$ из $a \sim b$ и $b \sim c$ следует $a \sim c$.

Задача 1. Сколько существует отношений на множестве из $n$ элементов? Сколько существует симметричных отношений на множестве из $n$ элементов? Отправить решение

Задача 2. Приведите примеры отношений, которые удовлетворяют ровно одному, ровно двум свойствам из определения 2 . Отправить решение

∆ Определение 3. Отношение $\sim$ на $M$ называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Задача 3. Укажите, какие из следующих отношений являются рефлексивными, симметричными, транзитивными, отношениями эквивалентности. (в кавычках указано условие, при котором $a \sim b$) 1) $a \sim b$ для всех $a,b \in M$, на множестве $M$; 2) $\varnothing$ на множестве $M$; 3) "$a\mid b$" на множестве натуральных чисел; 4) "$a$ и $b$ можно соединить путём" на множестве вершин графа; 5) "$A \subset B$" на множестве всех подмножеств данного множества; 6) "$a$ и $b$ имеют один и тот же остаток при делении на 2" на множестве натуральных чисел; 7) "$a$ и $b$ имеют одну и ту же последнюю цифру" на множестве натуральных чисел; 8) "$a$ и $b$ учатся в одном классе" на множестве всех учеников одной школы; 9) "$a$ и $b$ родились в одном месяце" на множестве всех людей на земле; 10) "между $a$ и $b$ существует биекция" на множестве всех подмножеств множества натуральных чисел; 11) "$a>b$" на множестве натуральных чисел; 12) фиксируем $X \subset M$. Отношение зададим правилом "$a \sim b$, если и только если $a,b \in X$", на множестве $M$; 13) "$a$ и $b$ являются гражданами одного государства" на множестве людей на Земле; 14) "три стороны одного треугольника равны трём сторонам второго треугольника" на множестве всех треугольников на плоскости; 15) придуманное Вами отношение на множестве натуральных чисел; 16) придуманное Вами отношение на множестве всех людей на земле. Отправить решение

Задача 4. Докажите, что отношение эквивалентности на множестве задаёт отношение эквивалентности на каждом его подмножестве. Отправить решение

∆ Определение 4. Пусть $\sim$ — отношение эквивалентности на $M$, $a \in M$. Множество ${N_a=\{x\in M: a \sim x \}}$ называется классом эквивалентности элемента $a$.

Задача 5. Докажите, что для любого отношения эквивалентности классы эквивалентности либо не пересекаются, либо совпадают. Докажите, что каждое отношение эквивалентности на $M$ задаёт разбиение множества $M$ на непересекающиеся классы эквивалентности. Отправить решение

∆ Определение 5. Пусть $\sim$ — отношение эквивалентности на $M$. Множество классов эквивалентности называется фактормножеством и обозначается $M/\sim$.

Задача 6. Опишите классы эквивалентности и фактормножества для отношений эквивалентности задачи 3 . Отправить решение

Задача 7. Рассмотрим следующее отношение на множестве $S_n$: $a\sim b$, если существует такая подстановка $c$, что $c^{-1}ac=b$. 1) Докажите, что это отношение является отношением эквивалентности; 2*) придумайте простой способ проверки, эквивалентны ли подстановки $a$ и $b$ и выясните, какие из подстановок в $S_4$. Отправить решение