- Equivalence relations

**Definition:**

A relation **R** is an **equivalence relation **if and only if it is reflexive, symmetric and transitive.

**Examples:**

Let **m** and **n** be integers and let **d** be a positive integer. The notation

**m**is congruent to

**n**modulo

**d**“.

The meaning is: the integer division of d into m gives the same remainder

as the integer division of d into n.

Consider the relation R = {(x,y)| x mod 3 = y mod 3}

For example, 4 mod 3 = 1, 7 mod 3 = 1, hence hence (4,7) Î R.

The relation is

symmetric: if x mod 3 = y mod 3, then y mod 3 = x mod 3

transitive: if x mod 3 = y mod 3, and y mod 3 = z mod 3, then x mod 3 = z mod 3

[1] = {1,4,7,10,13,….}

[2] = {2,5,8,11,14,…}

[1] = [4] =…

[2] = [5] = …

Each number is exactly in one of these sets.

The set {[0], [1], [2]} is a **partition** of the set of non-negative integers.

**Theorem:** Each equivalence relation on a set induces a partition of that set,

and each partition of a set induces an equivalent relation on the set.

The sets in the partition are called **classes of equivalence**.

- Partial orders

**Definition:**

R is a partial order relation iff R is transitive and anti-symmetric.

**Weak partial order**

- : R is reflexive.

**Strict partial order**

- : R is not reflexive (irreflexive or neither reflexive nor irreflexive).

**Examples**:

- Let A be a set, and P(A) be the power set of A.

The relation ‘subset of’ on P (A) is a partial order relation - Let N be the set of positive integers, and R be a relation defined as follows:

(x, y) Î R iff y is a multiple of x, e.g. (3,12) Î R, while (3, 4) Ï R

R is a partial order relation. It is reflexive, anti-symmetric, and transitive

- Total orders

**Definition: **A partial order is a **total or linear** **order** iff for all **x** and **y** in the set

either **xRy** or **yRx** is true.

In a totally ordered set all elements are comparable.

**Example:** The relation “less than or equal to” is a total order relation.

- More examples

**Equivalence**

- Consider the set T of all triangles and relation R = {(x,y)| x and y have equal angles}

R is an equivalence relation. It has the three properties:- Reflexivity xRx
- Symmetry: If xRy then yRx
- Transitivity: If xRy and yRz, then xRz

- Consider the set P of all persons and the relation R “having same age”.

R is a relation of equivalence:- Reflexivity: obviously, a person has same age as him/herself.
- Symmetry: If person
**a**has same age as person**b**, then person**b**has

same age as person**a**

- Transitivity: If person
**a**has same age as person**b**, and person**b**has

same age as person**c**, then person**a**has same age as person**c**. - Consider the set S of all students in a college and the relation R “having the same advisor”.

R is a relation of equivalence:- Reflexivity: obviously, a student has the same advisor.
- Symmetry: If student
**a**has the same advisor as student**b**, then

student**b**has the same advisor as student**a**

- Transitivity: If student
**a**has the same advisor as student**b**,

and student**b**has the same advisor as student**c**, then student**a**has

the same advisor as student**c**. - Consider the set of all people and the relation R having same first name.

R is a relation of equivalence. - Consider the set of all English words and the relation

R = {(a,b)| a and b have same number of letters. R is a relation of equivalence.

Partial order

Consider the power set of a set A = {a, b, c} and the relation R defined on the power set of A.

R = {(A_{i},A_{j})| A_{i}. Í A_{j}}. R is a partial order. It is not a total order.

If we eliminate the links implied by the transitivity, we get a simpler diagram, called **Hasse diagram**:

Be able to apply the definitions in order to determine the type of a given relation.

- For each of the following relations determine whether it is partial order, total order, equivalence relation, or none of theseAll relations are on the set of humansR1 = {(x,y) | x is a child of y}
R2 = {(x,y) | x is a descendent of y}

R3 = {(x,y) | x is a spouse of y}

R4 = {(x,y) | x is a wife of y}

R5 = {(x,y) | x and y have same parents}

R6 = {(x,y) | x and y have same parent}

R7 = {(x,y) | x is younger than y }

- For each of the following relations determine whether it is partial order, total order, equivalence relation, or none of these
- Let N be the set of natural numbers.

A binary relation R is defined on N in the following way:

- Let N be the set of natural numbers.

- Let N be the set of natural numbers, and let A = N x N.

A binary relation R is defined on A as follows:

- Let A be the set of all English statements. A binary relation R is defined on A as follows:

- Let A be the set of all lines on the plane. A binary relation R is defined on A as follows:

- Let A be the set of all lines on the plane. A binary relation R is defined on A as follows:

For more example :- http://www.math.uah.edu/stat/foundations/Equivalence.html

Hope this helps !!

Feel free to contact. & share the notes to as many people as possible, never hesitate in sharing Knowledge ?

Good Luck Friends!!!

God is always with you.

With Best wishes and Best Regards,

Admin