BodhiAI

Nov. 11, 2019
Relations

Let A and B be any two sets. Then a relation R from A to B is a subset of A×B

Thus, if R is a relation from A to B then RA×B

Important

If R is a relation from a non-void set A to a non-void set B and if (a, b)R, then we write a R b which is read as a is related to b by the relation R. If (a, b) R, then we write a R b and we say that a is not related to b by the relation R.

Problem Solving Trick

Total Number of Relations

Let A and B be two non-empty finite sets consisting of m and n elements respectively. Then A×B consists of mn ordered pairs So, total number of subsets of A×B is 2mn. Since each subset of A×B defines a relation from A to B, so total number of relations from A to B is 2mn. Among these 2mn relations the void relation and the universal relation A×B are trivial relations from A to B

Domain And Range of A Relation

Let R be a relation from a set A to a set B.Then the set of all first components of the ordered pairs belonging to R is called the domain of R, while the set of all second components of the ordered pairs in R is called the range of R.

Thus, if R is a relation from a set A to set B i.e. a R b, then

Domain (R) = {a :(a, b) R}

and Range (R) = {b : (a, b) R}

Example: If R is a relation from set A = {2, 4, 5} to set B = {1, 2, 3, 4, 6, 8} dfined by x R y such that x divides y, then

a) 2R2, 2R4, 2R6, 2R8, 4R4, 4R8 are the possible relations from set A to set B

Also, R = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 4), (4, 8)} is the set of ordered pairs.

b) Domain (R) = {2, 2, 2, 2, 4, 4} = {2, 4}

Range (R) = {2, 4, 6, 8, 4, 8} = {2, 4, 6, 8}

Important

Domain of a relation from A to B is a subset of A and its range is a subset of B.

Type of Relations

A. Void Relation

If for any set A, A×AA ×A then this relation is called the universal relation on A.

Important

It is to note here that the void and the universal relations on a set A are respectively the smallest and the largest relations on A.

C. Identity Relation

The relation IA on A is called the identity relation, if every element of A is related to itself only.

Hence, mathematically, the relation

is called the identity relation on A

If A {1, 2, 3} be any set then IA = {(1, 1), (2, 2), (3, 3)} Also, the set of ordered pairs represented by {(1, 1), (3, 3)} is not an identity relation because of the absence of (2, 2)

D. Reflexive Relation

A relation R on a set A is said to be reflexive if every element of A is related to itself.

Thus, If R is reflexive then, (a, a) R for all aA

A relation R on a set A is not reflexive if there exists an element aA such that (a, a) R

Example: a) If A = {1, 2, 3} be a set.

Then R = {(1, 1), (2, 2), (3, 3), (1, 3), (2, 1)} is a reflexive relation on A.

But R' = {(1, 1), (3, 3), (2, 1), (3, 2)} is not a reflexive, because for 2A, (2, 2) R

b) Let L be the set of all lines in a plane. Then relation R on L defined by (l1, l2) R such that l1 is parallel to l2 is reflexive, since every line is parallel to itself.

Important

The universal relation on a non-void set A is reflexive

E. Symmetric Relation

A relation R on a set A is said to be a symmetric relation iff

(a, b) R (b, a) R for all a, bA

i.e. a R b b R a for all a, b A

Also, A relation R on a set A is not a symmetric relation if there are at least two elements a, bA such that (a, b) R but (b, a) R

Example: a) Let A = {1, 2, 3, 4} be any set and let R1 and R2 be relations on A, such that

R1 = {(1, 3), (1, 4), (3, 1), (2, 2), (4, 1)} and

and R2 = {(1, 1), (2, 2), (3, 3), (1, 3)}

Clearly, R1 is a symmetric relation on A However, R2 is not so, because (1, 3) R2 but (3, 1) R2

b) Let L be the set of all lines in a plane and let R be a relation defined on L by the rule (x, y) R, such that x is perpendicular to y.

Then R is a symmetric relation on L, because i.e. if automatically implies

Important

a) The identity and the Universal relations on a non-void set are symmetric relations.

b) A reflexive relation on a set A is not necessarily symmetric.

Example:The relation R = {(1, 1), (2, 2), (3, 3), (1, 3)} is a reflexive relation on set A = {(1, 2, 3)} but it is not symmetric

c) The relation R on a set A is symmetric iff R = R-1

F. Transitive Relation

Let A be any set.A relation R on A is said to be a transitive relation iff

(a, b) R and (b, c) R

(a, c) R for all a, b, c A

i.e. a R b and b R c

a R c for all a, b, c A

Example: a) On the set N of natural numbers, the relation R defined by xRy, such that x is less than y is transitive, because for any x, y, z N

x < y and y < z x < z

i.e. x R y and y R z x R z

b) Let L be the set of all straight lines in a plane.The the relation is parallel to on L is a transitive relation, because for any l1, l2, l3 L

l1||l2 and l2||l3 l1||l3

Important

The identify and the universal relations on a non-void set are transitive.

G. Antisymmetric Relation

Let A be any set. A relation R on set A is said to be an antisymmetric relation iff

(a, b) R and (b, a) R a = b for all a, bA

Important

a) it follows from this definition that if (a, b) R and (b, a) R, then also R is an antisymmetric relation.

b) The identity relation on a set A is an antisymmetric relation.

Inverse Relation

Let A, B be two sets and let R be a relation from a set A to a set B. Then the inverse of R, denoted by R-1, is a relation from B to A and is defined by

R-1 = {(b, a) : (a, b) R}

i.e. If (a, b) R then (b, a) R-1

Also, Dom (R) = Range (R-1)

and Range (R) = Dom (R-1)

Equivalence Relation

A relation R on a set A is said to be an equivalence relation on A iff

a) it is reflexive i.e. (a, a) R for all a aA

b) it is symmetric i.e. (a, b) R (b, a) R for all a, bA

c) It is transitive i.e. (a, b) R and (b, c) R (a, c) R for all a, b, c A.

Example: Let R be a relation on the set of all lines in a plane defined by (l1, l2) R, such that line l1 is parallel to line l2.

Let L be the given set of all lines in a plane.Then, we observe the following properties

Reflexive: For each line lL, we have

l||l (l, l) R for all l L R is reflexive

Symmetric: Let l1, l2 L such that (l1, l2) R. Then

(l1, l2) R l1||l2 l2||l1 (l2,l1) R

So, R is symmetric on L

Transitive Let l1, l2, l3 L such that (l1, l2) R and (l2, l3) R. Then

(l1, l2) R and (l2, l3) R l1||l2 and l2||l3 l1||l3

(l1, l3) R

So, R is transitive on L.

Hence, R is a reflexive, symmetric and transitive thus,R is an equivalence relation on L