?> Equivalence Relations | Equivalence Relation | Math@TutorCircle.com
Sales Toll Free No: 1-855-666-7446

Equivalence Relations

Top

Relation is a branch of mathematics which plays a very important role. Let P and Q are two Sets then a relation R defined from Set P to set Q, is a subset of P X Q. Relation can be denoted in the list form and in tabular form as well, for example a relation ‘R’ on set P = 1, 2, 3, 4, 5 defined by R = (P, Q): Q = P + 2 can also be expressed as:-
P R Q if and only if Q = P + 2,
Let ‘U’ and ‘V’ the two Sets. Then a relation ‘R’ from set ‘U’ to set ‘V’ is a subset of U x V. Thus ‘R’ is a relation from U to V ↔ R is subset U x V. If ‘R’ is a relation from a non void set ‘U’ to a non void set ‘V’ and if (u, v) ε R, then we write u R v, which is read as 'u’ related to ‘v’ by the relation ‘R'. If (u, v) ε R, then we write ‘u ! R v’ and we can say that ‘u’ is not related to ‘v’ by the relation ‘R’.
Let’s see the types of relation which are shown below:
-Void, Universal, And Identity Relation.
-Reflexive Relation.
-Symmetric Relation.
-Anti Symmetric Relation.
-Transitive Relation.
Let’s discuss about equivalence relation.
A relation R on a set P is said to be an equivalence Relations on set P if and only if the given relation should be reflexive, symmetric and transitive. If the relation follows all these three condition then the relation is equivalence relations.
1. Reflexive relation i.e. (P, P) ∊R got all P ∊R.
2. Symmetric relation i.e. (P, Q) ∊then (Q ∊R) for all a, b ∊R.
3. Transitive relation i.e. (P, Q) ∊R and (Q, R) ∊R then (P, R) ∊R for all P, Q, R ∊R.
This is all about equivalence relations.

Define Equivalence Relation

Back to Top
A relation 'R' on Set 'P' define equivalence relation on 'P' if it follows three conditions. Conditions are shown below:
Reflexive relation: - Reflexive relation is a relation in which every element is related to itself. For example: (p, p) Є R for all p Є P.
Symmetric relation: - Relation 'R' is a symmetric relation if (p, q) Є R = (q, p) Є R for all p,q ЄP.
Transitive relation: - Relation 'r' is a transitive relation if (p, q) Є R and (q, r) Є R => (p, r) Є R for all p, q, r Є P.
Let's understand equivalence relation with help of an example.
Example:- If there are two relations R1, R2 defined on set A = a, b, c then;
R1 = (a, a), (a, b), (a, c), (b, b), (b, c), (c, a), (c, b), (c, c),
R2 = (a, b), (b, a), (a, c), (c, a) find whether these relations are Equivalence Relations or not?

Solution:- To show equivalence relation we need to satisfy above three conditions.
(1) Reflexive: - (a, a), (b, b), (c, c) ∊ R1. So we can say that relation R1 is reflexive.
Symmetric: - Here we observe that (a, b) ∊ R1 but (b, a) ∉ R1. So relation R1 is not symmetric on relation ‘A’.
Transitive: - Here we observe that (b, c) ∊ R1 and (c, a) ∊ R1 but (b, a) ∉ R1. So relation ‘R1’ is not transitive on relation ‘A’.
(2) Reflexive: - (a, a), (b, b), (c, c) are not present in R2. So relation R2 is not reflexive.
Symmetric: - Interchanging pair is present so given relation is symmetric on set ‘A’.
Transitive: - Here we observe that (a, b) ∊ R2 and (b, a) ∊ R2 but (a, a) ∉ R2. So relation R2 is not transitive on set ‘A’. So we can say that given relations are not equivalence relations.

Partial Orders

Back to Top
Partial orders can be defined as orders which show a relation 'R', over a Set 'S', partial order relation is represented by ≤. Any relation 'R', is a partial ordering only if it will satisfy following three conditions.
1. Reflexivity: x ≤ y.
2. Antisymmetry: x ≤ y and y ≤ x which implies x = y.
3. Transitivity: x ≤ y and y ≤ z implies x≤ z.

We can call Partial order set as poset. So in this case (R ,S) is called poset, here R and S are objects, (R, S) is also called as chain, and size of this chain is called partial order. It is necessary that chain is a well ordered, in this case (R, S) is well ordered.

Types of elements are:-

Greatest element: Suppose there is a set 'S', an element g in S is greatest element if every element of set S is ≤ to g.
Least element: In set S suppose we have an element 'e', this element is least if e is smaller than elements of set S.
Maximal element and minimal elements: Element 'X' is maximal element if there is no element 'y' in 'S' where x ≥ y. Similarly, an element 'x' in S is a minimal element if there is no element X in where x < y. If a poset has greatest element, it must be unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements.
Example: (N, ≤) this chain is called well ordered and, (N, ≥) this chain is not well ordered.