“Mathematics is, in its way

the poetry of logical ideas”

RELATIONS
(1) Types of Relations
Universal Relation
1. Empty Relation
A relation in which no
2. A relation in which each 3. Identity Relation
4. Reflexive Relation:
A relation in which each (a, a)R, for every
element of A is related to element of A is related to
element is related to a A.
any other element of A, i.e., every element of A, i.e.,
R=ϕ  A×A. R=A×A.
{
itself only. I = ( a, a ) , a ∈ A }

Transitive Relation: 7. Equivalence Relation : 8. Inverse Relation

5. Symmetric Relation:
(a1, a2)R implies that
6. (a1, a2)R & (a2,a3)R implies
A relation R in a set A is said to
be an equivalence relation if
Inverse relation of R from A to B,
denoted by R–1, is a relation from B to
that (a1, a3)R, for all A is defined by
(a2,a1 )R, for all a1,a2A. R is reflexive,symmetric & R–1 = {(b, a) : (a, b) R}.
a1, a2, a3A.
transitive.

Antisymmetric: A relation is Irreflexive Partial order relation

Asymmetric Relation 10. antisymmetric if: 11. 12.
9. R is irreflexive iff R is a partial order, if R is
( x, y ) ∈ R ⇒ ( y, x ) ∉ R • For all x, y ∈ X[( x, y ) ∈ R & ( y, x ) ∈ R] ⇒ x = y ∀a ∈ A, ( ( a,a ) ∉ R ) Reflexive, Antisymmetric
• For all x, y ∈ X[( x, y ) ∈ R & x ≠ y] ⇒ ( y, x ) ∉ R and Transitive.

2. EXAMPLE: Relation Reflexive Symmetric Asymmetric Antisymmetric Irreflexive Transitive

R1
A = {1, 2, 3, 4}. Identify the properties of relations.
R2
R1 = {(1,1) , ( 2, 2 ) , ( 3,3) , ( 2,1) , ( 4,3) , ( 4,1) , ( 3, 2 )} R3
R 2 = A × A, R 3 = φ, R 4 = {(1,1) , ( 2, 2 ) , ( 3,3) , ( 4, 4 )} R4

R 5 = {(1,1) , ( 2, 2 ) , ( 3,3) , ( 4, 4 ) , (1, 2 ) , ( 2,1) , ( 4,3) , ( 3, 4 )}

R5

If A={1,2},a relation R={(1,2)} on A is a transitive relation.

NOTE using the similar argument a relation R = {(x, y) : x is wife of y} is transitive, where as R = {(x, y) : x is father of y} is not transitive.

3. PROPERTIES
2. 3. 6.
1. 4. 5. R is reflexive implies
R is asymmetric implies R is not symmetric
that R is irreflexive. By does not imply R is R is not symmetric R is not antisymmetric that R is not
definition, for all antisymmetric. Counter does not imply R is does not imply R is asymmetric. By
R is not reflexive does
a, b ∈ A, ( a, b ) ∈ R example: asymmetric. Counter symmetric. Counter definition, for all
not imply R is irreflexive. a ∈ A, ( a,a ) ∈ R
Counter example: and ( b,a ) ∉ R This implies example: example:
A = {1, 2,3} , R = This implies that, both
A = {1, 2,3} , R = {(1,1)} that for all ( a, b ) ∈ R,a ≠ b A = {1, 2,3} , R = A = {1, 2,3} , R =
{(1, 2 ) , ( 2,3) , ( 3, 2 )} (a, b) and (b, a) are in
Thus, for all a ∈ A, ( a,a ) ∉ R {(1, 2 ) , ( 2, 2 )} {(1, 2 ) , ( 2,3) , ( 3, 2 )} R when a = b. Thus, R is
Therefore, R is irreflexive.
not asymmetric.

(4) COUNTING OF RELATION

Number of relations Number of reflexive The number of The number of binary
Number of Identity Number of Symmetric
from set A to B = 2mn, relation set on a set antisymmetric binary relation on A which are
relation on a set with relation set on a set with
where with ‘n’ elements = n ( n+1) /2 relations possible on both symmetic and
‘n’ elements = 1 n ( n−1) ‘n’ elements = 2
| A |= m ,| B |= n 2 2
A is 2n ⋅ 3(n − n)/2 antisymmetric is 2n.

The number of binary The number of binary The number of There are at least 2n
transitive relations
relation on A which are relation which are both asymmetric binary
(lower bound) and
both symmetric and reflexive and antisymmetric relation possible on at most
2 2
asymmetric is 1. on the set A is3(n − n)/2 the set A is 3(n − n)/2 2
n2 −n
2n − 2 2 + 1 (upper bound)
 5. OPERATION ON RELATIONS:
1. R1 − R 2 = {( a, b )∣( a, b ) ∈ R1 and ( a, b ) ∉ R 2 } 2.R 2 − R1 = {( a, b )∣( a, b ) ∈ R 2 and ( a, b ) ∉ R1} 3. R1 ∪ R 2 = {( a, b )∣( a, b ) ∈ R1 or ( a, b ) ∈ R 2 }

4. R1 ∩ R 2 = {( a, b )∣( a, b ) ∈ R1 and ( a, b ) ∈ R 2 }

PROPERTIES 6. COMPOSITON OF
1) If R1 and R2 are reflexive, and symmetric, then R1  R2
is reflexive, and symmetric. RELATIONS
2) If R1 is transitive and R 2 is transitive, then R1 ∪ R 2
need not be transitive. Let R1 ⊆ A × B and R 2 ⊆ B × C ,Composition of R 2 on
counter example: Let A = {1, 2} such that R1 = {(1, 2 )} and R1 , denoted as R1 R 2 or simply R1R 2 is
R 2 = {( 2,1)}.R1 ∪ R 2 = {(1, 2 ) , ( 2,1)} and (1,1) ∉ R1 ∪ R 2 implies that
R1 R 2 = {( a,c )∣a ∈ A,c ∈ C ∧ ∃b ∈ B such that
R1 ∪ R 2 is not transitive.

3) If R1 and R2 are equivalence relations, then R1  R2 is

( ( a, b ) ∈ R1 , ( b,c ) ∈ R 2 )}
an equivalence relation. NOTE
4) If R1 and R2 are equivalence relations on A, R1 (R2  R3)  R1 R2  R1 R3
• R1 − R 2 is not an equivalence relation (reflexivity fails).
R1 (R2  R3) = R1 R2  R1R3
• R1 − R 2 is not a partial order (since R1 − R 2 is not reflexive).
• R1 ⊕ R 2 = R1 ∪ R 2 − ( R1 ∩ R 2 ) is neither equivalence relation R1 ⊆ A × B, R2 ⊆ B × C , R3 ⊆ C × D. ( R1 R2 ) R3 = R1 ( R2 R3 )
nor partial order (reflexivity fails)
5) The union of two equivalence relation on a set is not ( R1oR 2 )−1 = R 2 −1oR1−1
necessarily an equivalence reation on the set.
6) The inverse of a equivalence relation R is an
equivalence relation.

7. EQUIVALENCE CLASS
Equivalence class of a ∈ A is defined as [a] = {x∣( x,a ) ∈ R} , that is all the elements related to a under
the relation R.
Example
E=Even integers, O=odd integers.
(i) All elements of E are related to each other and all elements of O are related to each other.
(ii) No element of E is related to any element of O and vice-versa.
(iii) E and O are disjoint andZ = E ∪ O
The subset E is called the equivalence class containing zero and is denoted by [0].

Properties: consider an equivalence relation R defiend on a set A.

1.  [a] = A 2. For every a,b∈A such that a ∈ [ b ] ,a ≠ b it follows that [ a ] = [ b ] 3. ∑ | [x] | =| R |

∀a∈A ∀x∈A

4. For any two equivalence class[ a ] and [ b ], either [ a ] = [ b ] or [ a ] ∩ [ b ] = φ 5. For all a, b ∈ A , if a ∈ [ b ] then b ∈ [ a ]

6. For all a, b,c ∈ A , if a ∈ [ b ] and b ∈ [ c ] , then a ∈ [ c ] 7. For all a ∈ A, [ a ] ≠ φ

Congruence modulo n given by a  b (mod n) if and only if n divides (a – b).

8. BINARY OPERATIONS
Let S be a non-empty set. A function f : S × S  S is called a binary opertion on set S.
Note
n2
Number of binary operations on a set containing n elements is n