∆ Definition 1. Consider a set $M$. Any set $R$ of ordered pairs of elements from $M$, $R\subset\{(a,b)\mid a,b \in M\}$, is called a (binary) relation on $M$. If $(a,b) \in R$, then we write $a \sim_R b$ or simly $a \sim b$.

∆ Definition 2. A relation $\sim$ on $M$ is called 1) reflexive, if for any $a \in M$, we have $a \sim a$; 2) symmetric, if for any $a,b \in M$, we have $a \sim b \Rightarrow b \sim a$; 3) transitive, if for any $a,b,c \in M$ with $a \sim b$ and $b \sim c$, we have $a \sim c$.

Problem 1. How many relations are there on a set of $n$ elements? How many symmetric relations are there on a set of $n$ elements? Send a solution

Problem 2. Give examples of relations that satisfy exactly one, exactly two properties from Definition 2. Send a solution

∆ Definition 3. A relation $\sim$ on $M$ is called an equivalence relation, if it is reflexive, symmetric and transitive.

Problem 3. Which of the following binary relations are reflexive? symmetric? transitive? equivalence relations? (The condition of $a \sim b$ is given in quotation marks.) 1) $a \sim b$ for any $a,b \in M$, on $M$; 2) $\varnothing$ on $M$; 3) "$a\mid b$" on the set of natural numbers; 4) "$a$ and $b$ can be connected by a path" on the set of vertices of a graph; 5) "$A \subset B$" on the set of all subset of a given set; 6) "$a$ and $b$ have the same remainder when dividing by $2$" on the set of natural numbers; 7) "$a$ and $b$ have the same last digit" on the set of natural numbers; 8) "$a$ and $b$ are in the same class" on the set of all students in high school; 9) "$a$ and $b$ were born in the same month" on the set of all people on Earth; 10) "there is a bijection between $a$ and $b$" on the set of all subsets of the natural numbers; 11) "$a>b$" on the set of natural numbers; 12) choose $X \subset M$. "$a \sim b$ if and only if $a,b \in X$", on $M$; 13) "$a$ and $b$ are citizens of the same country" on the set of all people on Earth; 14) "three sides of a triangle are equal to three sides of the other triangle" on the set of all tringles on a plane; 15) relation on the set of natural numbers made up by you; 16) relation on the set of all people on Earth made up by you. Send a solution

Problem 4. Show that an equivalence relation on a set defines an equivalence relation on each of its subsets. Send a solution

∆ Definition 4. Let $\sim$ be an equivalence relation on $M$ and $a \in M$. Set ${N_a=\{x\in M: a \sim x \}}$ is called an equivalece class of $a$.

Problem 5. Show that for any equivalence relation equivalence classes are either disjoint of coincide. Show that each equivalence relation on $M$ partitions $M$ into disjoint equivalence classes. Send a solution

∆ Definition 5. Let $\sim$ be an equivalence relation on $M$. The set of all possible equivalence classes is called the quotient set. Notation: $M/\sim$.

Problem 6. Describe equivalence classes and quotient sets for equivalence relations given in Problem 3. Send a solution

Problem 7. Consider the following equivalence relation on the set of permutations $S_n$: $a\sim b$, if there exists a permutation $c$ such that $c^{-1}ac=b$. 1) Show that this relation is an equivalence relation; 2*) how can we easily decide whether permutations $a$ and $b$ are equivalent? Find permutations in $S_4$ which are equivalent. Send a solution