Home / UGC NET / Equivalence and Partial Orderings

Equivalence and Partial Orderings

  •  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 º n (mod d)is read “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

reflexive: x mod 3 = x mod 3
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
Consider the sets [x]= {y | yRx}, where x is an integer, and R is the relation above.

[0] = {0,3,6,9,12,….}
[1] = {1,4,7,10,13,….}
[2] = {2,5,8,11,14,…}
From the definition of [x] it follows that

[0] = [3] = [6] …
[1] = [4] =…
[2] = [5] = …
Thus the relation R produces three different sets [0], [1] and [2].

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:

Let R be a binary relation defined on a set A.
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:

      1. 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
      2. 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

      1. 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:

        1. Reflexivity xRx
        2. Symmetry: If xRy then yRx
        3. Transitivity: If xRy and yRz, then xRz
      2. Consider the set P of all persons and the relation R “having same age”.
        R is a relation of equivalence:

        1. Reflexivity: obviously, a person has same age as him/herself.
        2. Symmetry: If person a has same age as person b, then person b has
          same age as person a

 

        1. 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.
      1. Consider the set S of all students in a college and the relation R “having the same advisor”.
        R is a relation of equivalence:

        1. Reflexivity: obviously, a student has the same advisor.
        2. Symmetry: If student a has the same advisor as student b, then
          student b has the same advisor as student a

 

        1. 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.
      1. Consider the set of all people and the relation R having same first name.
        R is a relation of equivalence.
      2. 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 = {(Ai,Aj)| Ai. Í Aj}. 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:

 

 


Learning GoalsKnow the definitions of equivalence relations, partial orders and total orders.
Be able to apply the definitions in order to determine the type of a given relation.


Exam-like problems

    1. 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 }

    2. For each of the following relations determine whether it is partial order, total order, equivalence relation, or none of these
      1. Let N be the set of natural numbers.
        A binary relation R is defined on N in the following way:

R = {(x,y) | y = x or y = x+1} 

      1. Let N be the set of natural numbers, and let A = N x N.
        A binary relation R is defined on A as follows:

(x1, x2) R (y1, y2) if and only if x1 = y1i.e. R = {((x1, x2), (y1, y2)) | x1 = y1}

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

R = {(p,q) | p ® q is true} 

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

R = {(a,b)| a is perpendicular to b} 

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

R = {(a,b)| a is parallel to b} 

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

Check Also

Probability ugc net exam

Probability Formula Probability is based on observations of certain events. Probability of an event is …