V. Exercises: Partitions and Equivalence Relations

Reference: Topology and Modern Analysis, G. F. Simmons, Tata McGraw Hill Publications, India.

Let $f: X \rightarrow Y$ be an arbitrary mapping. Define a relation in X as follows: $x_{1} \sim x_{2}$ means that $f(x_{1})=f(x_{2})$ . Prove that this is an equivalence relation and describe the equivalent sets.

Proof : HW. It is easy. Try it. 🙂

2. In the set $\Re$ of real numbers, let $x \sim y$ means that $x-y$ is an integer. Prove that this is an equivalence relation and describe the equivalence sets.

Proof: HW. It is easy. Try it. 🙂

3. Let I be the set of all integers, and let m be a fixed positive integer. Two integers a and b are said to be congruent modulo m — symbolized by $a \equiv b \pmod {m}$ — if a-b is exactly divisible by m, that is, if $a-b$ is an integral multiple of m. Show that this is an equivalence relation, describe the equivalence sets, and state the number of distinct equivalence sets.

Proof: HW. It is easy. Try it. 🙂

4. Decide which one of the three properties of reflexivity, symmetry and transitivity are true for each of the following relations in the set of all positive integers: $m \leq n$ , $m < n$ , $m|n$ . Are any of these equivalence relations?

Proof. HW. It is easy. Try it. 🙂

5. Give an example of a relation which is (a) reflexive, but not symmetric or transitive. (b) symmetric but not reflexive or transitive. (c) transitive but not reflexive or symmetric (d) reflexive and symmetric but not transitive (e) reflexive and transitive but not symmetric. (f) symmetric and transitive but not reflexive.

Solutions. (i) You can try to Google (ii) Consider complex numbers (iii) there are many examples given in the classic text “Discrete Mathematics” by Rosen.

6) Let X be a non-empty set and $\sim$ a relation in X. The following purports to be a proof of the statement that if this relation is symmetric and transitive, then it is necessarily reflexive: $x \sim y \Longrightarrow y \sim x$ ; $x \sim y$ and $y \sim x \Longrightarrow x$ ; therefore, $x \sim x$ for every x. In view of problem 5f above, this cannot be a valid proof. What is the flaw in the reasoning? 🙂

7) Let X be a non-empty set. A relation $\sim$ in X is called circular if $x \sim y$ and $y \sim x \Longrightarrow z \sim x$ , and triangular if $x \sim y and x \sim z \Longrightarrow y \sim z$ . Prove that a relation in X is an equivalence relation if and only if it is reflexive and circular if and only if it is reflexive and triangular.

HW: Try it please. Let me know if you need any help.

Regards,

Nalin Pithwa.

PS: There are more examples on this topic of relations in Abstract Algebra of I. N. Herstein and Discrete Mathematics by Rosen.

MScMathematics

V. Exercises: Partitions and Equivalence Relations

Leave a Reply Cancel reply

Mathematics Hothouse shares:

Like this:

Related

Leave a Reply Cancel reply