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:-
Define Equivalence RelationBack to Top
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 OrdersBack to Top
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.