UNIT-2

Set Theory, Relations and

Functions

Click to add text

Click to add text

Introduction to Set Theory

• Set theory was developped by German mathematician G.Cantor in 1895.

Definition of Set:

A Set is a well-defined collection of objects called elements which share some common property. Well-defined means we should be able to determine if a given element is contained in set by means of certain rules.

​

Examples: The following are the examples of sets

• The states in India.
• The self-financing engineering colleges in Andhra

Pradesh.

• The students who have joined the computer science

branch in a college

N : The set of all natural numbers (i.e., all positive integers)

Z : The set of all integers

Z⁺ : The set of all positive integers

Z* : The set of all nonzero integers

E : The set of all even integers

Q : The set of all rational numbers

Q* : The set of all nonzero rational numbers

Q⁺ : The set of all positive rational numbers

R : The set of all real numbers

R* : The set of all nonzero real numbers

R⁺ : The set of all positive real numbers

C : The set of all complex numbers

C* : The set of all nonzero complex numbers

Element or Member:

The objects which make up a set are called Elements or

Members of the set.

The symbol ∈ is used to denote that an element is a member of a set and ∉ is used to denote that an object is not a member of a set.

Example: Suppose S= { All even numbers}i.e., S={ 2,4,6,8,.......} where S is the set name.

The members or elements of the set are 2,4,6,8,.....

2 ∈ S, 8 ∈ S but 0 ∉ S

• Capital letters A,B,C,.......Z are generally used to denote the sets.
• Lowercase letters a,b,c,.....z are generally used to denote the elements of the set

Finite Set:

if the number of elements in a set are finite or countable, then we

say that the set is a Finite Set.

Example:

if we consider the set of all students in a college . Here students are the elements of the set and it is possible to count the number of students in a college, hence it is a finite set.

Infinite Set:

if the number of elements in a set are Infinite or non-countable, then we say that the set is a Infinite Set.

Example:

if we consider the set of all natural numbers . Here the number 1,2,3,..... are the elements of the set and it is impossible to count the number of elements in a natural number set, hence it is a infinite set.

Singleton Set:

A set having only one element is called Singleton Set

Example:

The set of all integers between 2 and 8 containing the squares of integers is the singleton set consisting of integer 4 only

Set Notations:

Generally a set is represented in two ways.

1. Roster Notation
2. Set builder notation

Roster Notation:

In Roster notation, all the elements are listed, possibly separated by commas and enclosed with in the braces.

Examples:

1. The set of vowels in English alphabet.

V={a,e,i,o,u}

2. The set of even positive integers less than or equal to 10.

E={2,4,6,8,10}

3. The set of positive integers less than 100.

P={1,2,3,4,..........99}

​

Set builder Notation:

In Set builder notation, we define the elements of the set by specifying the characteristic property which all the elements of the set possess .

Examples:

1. The set of vowels in English alphabet.

V={x/x is a vowel in the English alphabet }

2. The set of even positive integers less than or equal to 10.

P={x/x is a positive even integer less than 10 }

3. The set of positive integers less than 100.

B={x/x is a positive integer not exceeding 100 }

Cardinality:

The number of elements in a set is called the Cardinality or

Size of a set.

If A is a finite set , then Cardinality of set A is denoted by |A|

Examples on Cardinalities:

A = {Mercedes, BMW, Porsche}

B = {1, {2, 3}, {4, 5}, 6}

C = ∅

D = { x ∈ N | x≤ 7000 }

E = { x ∈ N | x> 7000 }

|A| = 3

|B| = 4

|C| = 0

|D| = 7001

E is infinite!

Example: Suppose set A={ 1,2,3,4,5}, then the cardinality of set A is 5 i.e., |A|=5

Superset:

Let X and Y be any two sets . If X ⊆ Y, then “X is contained in Y” or “Y contains X” or Y is a superset of X, written Y ⊇ X

Null Set:

A Set which does not contain any element is called an Empty set or Null Set. It is denoted by ∅ or { }

∅={ } means Null Set,it does not contain any element.

Universal Set:

A Set is called Universal set if it includes every set under consideration. A Universal Set is denoted by U.

Subset:

Let A and B be two sets, then A is said to be a subset of B if every element of set A is an element of set B.

if A is subset of B, then we can say that A is contained in B. A is subset of B is denoted by A⊆ B

Example: Let A={ 2,3,4,5,8,9} and B={2,3,4,5,8,9}

By observing the above two sets, every element of set A is an element of set B. Hence we can write it as A⊆ B

Proper Subset:

Let A and B be two sets, then A is said to be a proper subset of B, if A is a subset of B and there is atleast one element of B which is not in A. The symbol ⊂ stands for “ is a proper subset of “

A is a proper subset of B is denoted by A ⊂ B

Example: Let A={ 2,3,4,5,8,9} and B={2,3,4,5,8,9,10,11}

By observing the above two sets, every element of set A is an element of set B and B contains two elements: 10 and 11 which are not in A. Hence we can write it as A ⊂ B

NOTE:

1. Every set is a subset of itself i.e., A⊆ A
2. No set is a proper subset of itself i.e., A ⊂ A
3. The empty set is a subset of every set.

Equal Sets:

Two sets A and B are said to be equal if they have precisely the same elements. Then we write A=B.

if A⊆ B and B⊆ A then we write A=B.

Example: Let A={ 1,2,3,4} and B={x/x is a positive integer with x²<20}

​

By observing the above two sets, every element of set A is an element of set B i.e.,. A⊆ B and every element of set B is an element of set A, Hence we can write it as A=B.

​

NOTE:

1. Two sets A and B are equal if and only if A⊆ B and B⊆ A
2. For any three sets A ,B and C, if A⊆ B and B⊆ C, then A⊆ C
3. For any three sets A ,B and C, if A= B and B= C, then A= C

Power Set:

Given a set A, a collection of all subsets of A is called the Power set of A.

Power set of set A is denoted by P(A).

Suppose set A has n elements, then power set of A i.e., P(A) contains 2ⁿ elements.

Example:

1. Let us consider set A={1,2,3}

P(A)={∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}} contains 8 elements.

2. Let us consider set S={ a, b} P(S)={∅,{a},{b},{ a, b}} contains 4 elements
3. Let us consider set A = ∅

P(A) = {∅}

Note: |A| = 0, |P(A)| = 1

Operations on Sets

• We can perform certain basic operations on sets. Using these operations, we can construct new sets by combining the elements of given sets.
• The following operations performed on the sets are
1. Union
2. Intersection
3. Disjoint
4. Complement
5. Set Difference
6. Symmetric Difference

7. Cartesian Product

Union operation:

Consider two sets A and B. The union of two sets A and B is denoted by AUB is the set of all elements which are members of the set A or the set B or both.

AUB={ x/x ∈ A or x ∈ B }

​

B={ 2,3,4} and C={3,4,5} find out AUB, BUC

Symbolically

Example:

Let A={1,2,3}

and AUC.

AUB={1,2,3} U {2,3,4}= {1,2,3,4}

BUC={2,3,4} U { 3,4,5}= {2,3,4,5}

AUC={1,2,3} U{ 3,4,5}= {1,2,3,4,5}

Intersection operation:

Consider two sets A and B. The intersection of two sets A and B is denoted by A ∩ B is the set consisting of all elements which belongs to both A and B.

Symbolically A ∩ B={ x/x ∈ A and x ∈ B }

Example:

Let A={1,2,3}

B ∩ C and A ∩ C.

B={ 2,3,4} and C={3,4,5} find out A ∩ B,

A ∩ B={1,2,3} ∩ {2,3,4}= {2,3}

B ∩ C={2,3,4} ∩ { 3,4,5}= {3,4}

A ∩ C={1,2,3} ∩{ 3,4,5}= {3}

Disjoint Operation:

Two sets A and B are called disjoint if and only if A ∩ B= ∅

i.e., A and B sets have no element in common.

Example:

Let A={1,2,3} B={ 4,5,6} and C={7,8,9} find out A ∩ B,

B ∩ C and A ∩ C.

A ∩ B={1,2,3} ∩ {4,5,6}= ∅

B ∩ C={4,5,6} ∩ { 7,8,9}= ∅

A ∩ C={1,2,3} ∩ { 7,8,9}= ∅

• Hence we can say that A,B,C sets are called Disjoint sets because they have no common elements in between them.

Complement Operation:

if U is the universal set and A is any set, then the set of elements which belongs to U but which do not belong to A is called the complement of A and is denoted by A^c

Symbolically, A^c = { x/x ∈ U and x ∉ A }

Example:

Let U={1,2,3,4,5}, A={ 1,3,5 } and B={4,5} find out

and B^c

_Ac

_Ac _Bc

= U – A = {1,2,3,4,5} – {1,3,5 }= { 2,4 }

= U – B = {1,2,3,4,5} – {4,5 }= { 1,2,4 }

Difference:

if A and B are any two sets, then the set of elements that belongs to A but do not belongs to B is called the difference of A and B or relative complement of B with respect to A and it is denoted by A-B.

Symbolically, A – B = { x/x ∈ A and x ∉ B }

Example:

Let A={1,2,3,4,5} and B={ 1,3,5 } find out A-B.

A – B = {1,2,3,4,5} – {1,3,5 }= { 2,4 }

Symmetric difference:

Let A and B are any two sets, then the set of elements that

the Symmetric

belongs to A or B , but not to both is called

difference of A and B and is denoted by A ∆ B.

A ∆ B = (A-B) U (B-A)

Example:

Let A={1,2,3,4,5} and B={ 1,3,5 } find out A ∆ B. We know that

A ∆ B = (A-B) U (B-A)

A – B = {1,2,3,4,5} – {1,3,5 }= { 2,4 }

B – A = {1,3,5 } – {1,2,3,4,5} = ∅

A ∆ B = (A-B) U (B-A) = {2,4 } U ∅ = { 2,4 }

Cartesian Product

• Let A and B be two sets, then the set of all order pairs (a, b), where a∈ A and b ∈ B is called the Cartesian product or Cross product of A and B.
• The Cartesian product of two sets is defined as: A×B = {(a, b) | a∈ A and b ∈ B}
• The Cartesian product of two sets is defined as: B×A = {(b, a) | b∈ B and a ∈ A}

Example: Let A={1,0,-1} and B={2,3} find out A×B and B×A

A×B={ (1,2),(1,3),(0,2),(0,3),(-1,2),(-1,3)}

B×A={ (2,1),(2,0),(2,-1),(3,1),(3,0),(3,-1)}

• NOTE:
1. if A and B are finite sets with| A |=m and | B |=n, then | A×B | =mn elements.
2. if A and B are finite sets, then | A×B | = | A | ×| B |

Venn Diagrams:

To represent the relationship between the sets can be depicted in diagrams called “Venn Diagrams”

Venn Diagrams

• Abstract visualization of a Universal set, U as a rectangle, with all subsets of U shown as circles.
• Shaded portion represents the corresponding set

Example:

• In Figure 1.1, Set X( shaded) is a subset of the Universal set U

Set Operations and Venn Diagrams

23

• Union of Sets

Example: If X = {1,2,3,4,5} and Y = {5,6,7,8,9}, then

XUY = {1,2,3,4,5,6,7,8,9}

Set Operations and Venn Diagrams

• Intersection of Sets:

Example: If X = {1,2,3,4,5} and Y = {5,6,7,8,9}, then X ∩ Y = {5}

Set Operations and Venn Diagrams

• Disjoint Sets

Example: If X = {1,2,3,4,} and Y = {6,7,8,9}, then X ∩ Y = ∅

Set Operations and Venn Diagrams

• Set Difference:

• Example:

If X = {a,b,c,d} and Y = {c,d,e,f},

then

X – Y = {a,b}

Y – X = {e,f}

Set Operations and Venn Diagrams

• Ā = { x | x ∉ A }

• Ā(A Complement) is shaded.

Complement:

Let U be the universal set. The complement of the set A, denoted by Ā, is the complement of A with respect to U. In other words, the containing those complement of the set A is U – A.

FUNCTION

• Let A and B be any two sets. A relation f from A to B

there is a

is called a function if for every a ∈ A unique element b ∈ B such that (a , b) ∈ f.

(OR)

a

b

• Let A and B be any two nonempty sets. A function from A into B is a relation that associates with each element of A exactly one element of B.

f

A

B

• A function f from A to B is also written as

f: A🡪 B which is read as “ a function of A into B”

• Set A is called domain of the function f.
• Set B is called the co-domain of function f.

• Functions are also called mappings or transformations

3

1

0

–1

2

3

.

f

A

B

​

Domain= {0,1,3}

Range or Co-Domain=

{-1,2}

Graphical Representation of Function

• Functions can be represented graphically in several ways:

•

•

A

B

a

b

f f

•

•

•

•

•

•

•

•

•

x

Plot

y

Graph

Like Venn diagrams

A B

Image and Preimage

X

Y

z

1

2

3

FIG-1

In Fig-1: Element x has image element 3 and element y has image element 1 and element z has image element 2.

Element 1 has element y and

In Fig-1: preimage element element z

2 has preimage and element 3 has

the preimage element x

Which of the following is a function?

It is not a function because a3 has no image

It is not a function because a1 has two images b1 and b3

It is a function

• Figure (iii) is an example of a function. Since the given function maps every element of A with that of B.
• In figure (ii), the given function maps one element of A with two elements of B (one to many).
• Figure (i) is a violation of the definition of the function. The given function does not map every element of A.

Examples on Function

Which relation mapping represents a function?

​

Fig-1 Fig-2

3

1

0

–1

2

3

2

–1

3

2

3

–2

0

Fig-1 is a function but Fig-2 is not a function

because -1 has two images 3 and -2

A B

A B

Examples on Function

x y z

1

2

3

a b c

x y z

a b c

x y z

FIG-1

FIG-2

FIG-3

It is a Function

It is not a Function Because element b has no

image

It is a Function

DOMAIN, CO-DOMAIN, IMAGE, PRE- IMAGE, RANGE

38

• If f: A→B, and f(a)=b (where a ∈ A & b ∈ B), then:
• A is the domain of f.
• B is the co-domain of f.
• b is the image of a under f.
• a is a pre-image of b under f.
• In general, b may have more than one pre- image.
• The range R⊆B of f is {b | ∃a f(a)=b }.

• Example: if the function f is defined by f(x)= x²+1 on the set {-2, -1, 0, 1, 2 }. Find the range of f.

Sol:

f(x)= x²+1

f(-2)=(-2)²+1=4+1=5

f(-1)=(-1)²+1=1+1=2 f(0)=(0)²+1=0+1=1 f(1)=(1)²+1=1+1=2 f(2)=(2)²+1=4+1=5

Range of function f is {1,2,5}

• Example: The following fig defines a function f which maps the set {a , b , c , d } to itself. Find the range of f

a b c d

a b c d

The range consists of all the

Image points. The elements a and c only appear as images. Hence range of f is

The set { a, c}

Types of Functions

• One to One(1-1) function (Injective)
• Onto function (Surjective)
• Bijective function (One to One and onto function)
• Many to one function
• Constant function
• Identity function

One-to-One(Injective) Function

42

• A function f: A→B is called one-to-one (1-1) or injective, or an injection, if distinct element of set A are mapped into distinct elements of set B.
• Example:

f

In the beside fig: a1, a2, a3 and a4 elements in set A have unique images b1, b3, b2, b4 in set B respectively, hence f is one-to- one

Examples on One-to-One function

43

• Graph representations of functions that are (or not) one-to-one:

•

•

•

•

•

•

•

•

•

One-to-one

•

•

•

•

•

•

•

•

•

Not one-to-one

•

•

•

•

•

•

•

•

•

Not even a

function!

Onto (Surjective) Functions

• A function f : A→B is called onto or surjective or surjection if and only if for every element b ∈ B there is an element a ∈ A such that f(a)=b.
• A function f : A→B is called onto or surjective or surjection, if the range Rf = B.

f

f

​

In the beside fig: b1, b2, b3 and b4 elements in set B have preimages a4, a3, a2, a1 in set A respectively, hence f is onto

Illustration of Onto

45

• Some functions that are or are not onto their codomains:

Onto

(but not 1-1)

•

•

•

•

•

Not Onto (or not 1-1)

• •

_• •

_• •

_• •

•

• _•

• •

_• •

_• •

Both 1-1 and onto

• •

_• •

_• •

_• •

1-1 but not onto

•

•

•

•

•

Bijection function

46

• A function f : A→B is called One-to-One Onto or bijective or bijection if and only if function f is both one-to-one and onto.

f

In the beside fig: a1, a2, a3 and a4 elements in set A have unique images b4, b3, b2, b1 in set B respectively, hence f is one-to-one

In the beside fig: b1, b2, b3 and b4 elements in set B have preimages

a3, a2, a1

a4,

in set A

hence f is

respectively, onto.

Hence

f is bijective

because f is one-to-one and onto

• A function f : A→B is bijective, then A and B have same number of elements.
• A function f : A→B is invertible if and only if f is one-to-one and onto
• Consider the below function f, f is not bijective because f is not one-to-o^f ne and f is not onto.

Identity Function

• A function f : A→A is called the identity function if the image of every element of set A is itself, in this case f(A)=A.

defined on a set A is usually

3

1

0

3

1

0

• Identity function denoted by I_A or 1_A
• Note that the identity function is both one-to-one and onto (bijective).

f

A

A

Constant Function

• A function f : A→B is called a constant function if all the elements of set A have the same image in B.
• From the below diagram, f(A)=4

3

1

0

4

f

A

B

In the beside fig: 3, 1, 0 elements in set A have the

image

hence

same

4 in set B

f is a

constant function

Many to One function

• A function f : A→B is called a Many-to-one function if one or more elements of set A is mapped to one element in set B.

3

1

0

4

5

f

A

B

​

In the beside fig:

3, and 1 elements in set A have the image 4 in set B hence f is a Many- to-one function

Composition of Functions

• The term "composition of functions" (or "composite function") refers to the combining together of two or more functions in a manner where the output from one function becomes the input for the next function.

​

• A composite function is created when one function is substituted

into another function.

​

• Let f: X → Y and g: Y → Z be two functions. The composition of f and g is a new function from X to Z is denoted by (gof):X→Z is given by

(gof)(x)=g(f(x)) for all x ∈ A

​

• gof is read as “g composed with f of x" or “ g of f of x ".

Fig:

x

f(x)

g(f(x))

gof

f

g

g

f

Composition of functions f and g

1. gof is read as “g composed with f of x“ or
2. fog is read as “f composed with g of x“ or

“g of f of x“

“f of g of x".

• gof is called the left composition of g with f or relative product of

functions f and g.

• When dealing with composition, always start with the function on the

right g(f(x).

Example-1: Given f (x) = 5x + 1 and g (x) = 3x - 2. find out (fog)(x) and (gof)(x).

Sol: (fog)(x)=f(g(x))

=f(3x-2)

=5(3x-2)+1

=15x-10+1

=15x-9

(gof)(x)=g(f(x))

=g(5x+1)

=3(5x+1)-2

=15x+3-2

=15x+1

Example-2: Given f (x) = 3x² + 4x + 7 and g (x) = x + 1.

Sol: i. (gof)(x)=g(f(x)) =g(3x² + 4x + 7)

= (3x² + 4x + 7)+1= 3x² + 4x +8

ii. (fog)(x)=f(g(x)) =f(x + 1)

= 3(x+1)² + 4(x+1) + 7

= 3(x² +2x+1)+ 4x +4+7

= 3x² +6x+3+ 4x +4+7

= 3x² +10x+14

Example-3: Given f (x) = x² - 1 and g (x) = 3x + 2. Find out (fog)(2),(gof)(4),(gog)(-1),(fof)(3)

Sol: (fog)(2)=f(g(2))=f(3(2)+2)=f(8)=(8)²-1=63

(gof)(4)=g(f(4))=g((4)²-1)=g(15)=3(15)+2=47

(gog)(-1)=(g(g(-1))=g(3(-1)+2)=g(-1)=3(-1)+2=-1

(fof)(3)=f(f(3))= f(((3)²-1)=f(8)= )=(8)²-1=63

Example-4: Consider f, g and h, all functions on the integers, by

f (n) =n², g (n) = n + 1 and h (n) = n - 1.

Determine (i) hofog (ii) gofoh (iii) fogoh.

​

Sol: (i) (hofog)(n) =h(f(g(n)))

=h(f(n+1))

=h((n+1)²)

= ((n+1)²)-1

=n²+2n+1-1

=n² +2n

(ii) (gofoh)(n)=g(f(h(n)))

=g(f(n-1))

=g((n-1)²)

= ((n-1)²)+1=n² -2n+1+1=n² -2n+2

iii. (fogoh)(n) = f(g(h(n)))

= f(g(n-1))

= f(n-1+1)

= f(n)

= n²

Example-5: Let X={1,2,3} ,Y={p, q} and Z={a, b} also let f: X → Y be defined by f={(1,p),(2,q),(3,q)} and g: Y → Z be defined by g={(p, b),( q, b)}. Find gof.

Sol: gof(1)=g(f(1))=g(p)=b

gof(3)=g(f(3))=g(q)=b

gof(2)=g(f(2))=g(q)=b gof={(1,b),(2,b),(3,b)}

Example-6: Let X={1,2,3} and f,g,h and s be functions from X to X given by

f={(1,2),(2,3),(3,1)}

h={(1,1),(2,2),(3,1)}

g={(1,2),(2,1),(3,3)}

s={(1,1),(2,2),(3,3)}

Find fog,gof,fohog, sog, gos, sos and fos.

Sol:

fog={(1,3),(2,2),(3,1)}

gof={ (1,1),(2,3),(3,2)}

fohog= fo (hog)= fo{(1,2),(2,1),(3,1)}={(1,3),(2,2),(3,2)}

sog={(1,2),(2,1),(3,3)}

gos={(1,2),(2,1),(3,3)}

sos={(1,1),(2,2),(3,3)}

fos={(1,2),(2,3),(3,1)}

Note: Composition of functions is Associative.

if f: A → B , g: B → C and h: C → D are the functions, then ho(gof)=(hog)of

since f: A → B , g: B → C, then gof: A → C since gof: A → C, h: C → D, then ho(gof): A → D

now hog: B → D, f: A → B , then (hog)of ): A → D

therefore ho(gof)=(hog)of

Inverse of a function

• Let f and g are two functions. if f: A → B and g: B → A, then the function g is called the inverse of the function f if and only if gof=IA and fog=IB, where IA is the identity function on A and IB is the identity function on B.
• g is called an inverse of f and we write it as g=f^-1
• Example-1: Let A={1,2,3,4} ,f and g are two functions defined from A to A is given by f={(1,4),(2,1),(3,2),(4,3)} and g={(1,2),(2,3),(3,4),(4,1)}. Prove that f and g are inverse of each other.

Sol: we check that

(gof)(1)=g(f(1))=g(4)=1= IA

(gof)(2)=g(f(2))=g(1)=2= IA

(gof)(3)=g(f(3))=g(2)=3= IA

(gof)(4)=g(f(4))=g(3)=4= IA

(fog)(1)=f(g(1))=f(2)=1= IA

(fog)(2)=f(g(2))=f(3)=2= IA

(fog)(3)=f(g(3))=f(4)=3= IA

(fog)(4)=f(g(4))=f(1)=4= IA

Thus, for all x ∈ A, we have (gof)(x)= IA(x) and (fog)(x)= IA(x).

Therefore, g is an inverse of f and it also follows that f is an inverse of g.

Example-2: Consider the function f: R → R

defined by defined by

f(x)=2x+5. Let a function g: R → R be

g(x)=1/2*(x-5). Prove that g is an inverse of f.

Sol: we check that, for any element x ∈ R,

(g o f)(x)=g(f(x))=g(2x+5)=1/2* (2x+5-5)=1/2*2x=x= IR(x) (f o g)(x)=f(g(x))=f(1/2*(x-5)=2(1/2* (x-5)+5=x= IR(x)

Thus, for all x ∈ R, we have (gof)(x)= IR(x) and (fog)(x)= IR(x).

Therefore, g is an inverse of f and it also follows that f is

an inverse of g.

• Procedure for finding the inverse of a function:
1. Replace f(x) with y
2. Switch x’s and y’s
3. Solve for y
4. Replace y with f^-1(x)

Example-1: find out the inverse of f(x)=x³-2 Sol: 1. Replace f(x) with y

y= x³-2

2. Switch x’s and y’s x= y³-2
3. Solve for y y³=x+2 y=3√x+2
4. Replace y with f^-1(x) f^-1(x)=3√x+2

The inverse of f(x)=x³-2 is f^-1(x)=3√x+2 Example-2: find out the inverse of f(x)=5x-3/2x+1 Sol: 1. Replace f(x) with y

y= 5x-3/2x+1

2. Switch x’s and y’s x=5y-3/2y+1
3. Solve for y

x(2y+1)=5y-3

2xy+x=5y-3

subtract 5y on both sides 2xy-5y+x=5y-5y-3

y(2x-5)=-3-x

y=-3-x/(2x-5)

4. Replace y with f^-1(x)

f^-1(x)= =-3-x/(2x-5)

The inverse of f(x)=5x-3/2x+1 is f^-1(x)= =(-3-x)/(2x-5)

Relations

• If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs, An ordered pair is commonly known as a point, has two components which are the x and y coordinates with their first element taken from set A and their second element taken from set B. The ordering of the two components is important
• This is an example of an ordered pair.

Cartesian Product:

Let A and B be two sets, then the set of all order pairs (a, b), where a∈ A and b ∈ B is called the Cartesian product or Cross product of A and B.

• The Cartesian product of two sets is defined as: A×B = {(a, b) | a∈ A and b ∈ B}
• The Cartesian product of two sets is defined as: B×A = {(b, a) | b∈ B and a ∈ A}

Example: Let A={1,0,-1} and B={2,3} find out A×B and B×A

A×B={ (1,2),(1,3),(0,2),(0,3),(-1,2),(-1,3)}

B×A={ (2,1),(2,0),(2,-1),(3,1),(3,0),(3,-1)}

Therefore A×B not equals to B×A, if the sets A and B are different. Symbolically A×B ≠ B×A

Relation or Binary Relation:

Let A and B be sets. A binary relation (or) relation R from set A to set B is a subset of A×B.

• In other words, for a binary relation R we have R ⊆ A×B. We use the notation

a R b to denote that (a, b)∈R

and

a R b to denote that (a, b)∉R.

​

• When (a, b) belongs to R, a is related to b by relation R. Symbolically it is denoted by (a, b)∈R
• When (a, b) does not belongs to R, a is not related to b by relation R. Symbolically it is denoted by (a, b) ∉ R

Example:

Let P be a set of people, C be a set of cars, and D be the relation describing which person drives which car(s).

P = {Carl, Suzanne, Peter, Carla}, C = {Mercedes, BMW, tricycle}

D = {(Carl, Mercedes), (Suzanne, Mercedes), (Suzanne, BMW), (Peter, tricycle)}

This means that Carl drives a Mercedes, Suzanne drives a Mercedes, Suzanne drives a BMW, Peter drives a tricycle, and Carla does not drive any of these vehicles.

• A relation D is simply a collection of ordered pairs that are subset of P×C
• Relations are used to store information in computer databases.

Problem-1: if A is a finite set with m elements and B is a finite set with n elements . Find the number of relations from set A to set B

Sol: The set of all relations from set A to set B is precisely the set of all subsets of A×B. Therefore, the number of relations from A to B is equal to the number of subsets of A×B.

Since |A|=m and |B|=n, we have |A×B|=mn.

Therefore A×B has 2^mn number of subsets.

This implies that there are 2^mn relations from set A to Set B.

For example, |A|=3 and , |B|=2

then there exist 2^3×2 =2⁶=64 relations from A to B.

Problem-2: Let A and B be finite sets with |B|=3. if there are 4096 relations from A to B. What is |A|?

Sol:

Suppose if |A|=m and |B|=n, then there are 2^mn relations from set A to Set B.

Therefore n=3 and 2^mn =4096 2^mn =4096

2^3m =4096

₂3m _{= 2}12

bases are equal on both sides , hence powers are also equal.

3m=12

m=4, hence |A|=4

Problem-3: Let A={1,2,3} and B={2,4,5} determine the following.

1. |A×B|
2. Number of relations from A to B.
3. Number of binary relations on A.

Sol: We have |A|=m=3 and |B|=n=3

i. |A×B| = m*n=3*3=9

2. Number of relations from A to B= 2^mn

= 2^3×3 =2⁹=512

3. Number of binary relations on A=2^mn

₌₂m×m

= 2^3×3 =2⁹=512

Properties of Relations

• A relation has mainly 6 properties.
1. Reflexive property
2. Irreflexive property
3. Symmetric property
4. Antisymmetric property
5. Asymmetric property
6. Transitive property

Properties of Relations

Reflexive Property:

A relation R on a set A is said to be reflexive if (a, a)∈R for every element a∈A.

Example: Let us consider the set A={1, 2, 3, 4}. A relation R defined on set A as R={(1,1),(2,2),(3,3),(4,4),(1,3),(2,4)}

is relation R is reflexive or not?

Sol: relation R satisfy the reflexive property if (a, a)∈R for every element a ∈ A.

(1,1),(2,2),(3,3),(4,4) ∈ R

Irreflexive Property:

A relation R on a set A is called irreflexive if (a, a)∉R for every element a ∈ A.

Example: from the above example, relation R does not satisfy irreflexive property,

if (a, a)∈R for every element a ∈ A. (1,1),(2,2),(3,3),(4,4) ∈ R

Symmetric Property:

A relation R on a set A is called symmetric if whenever (a, b)∈R then (b, a)∈R for all a, b ∈ A.

Example: Let us consider the set A={1, 2, 3, 4}. A relation R defined on set A as:

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

is relation R is symmetric or not?

Sol:

if (1,2) ∈R then (2,1) ∈R

if (4,2) ∈R then (2,4) ∈R

Hence relation R satisfy the Symmetric property

Antisymmetric Property:

A relation R on a set A is called antisymmetric if whenever (a, b)∈R and (b, a)∈R, then a=b

OR

A relation R on a set A is called antisymmetric if whenever (a, b)∈R and (b, a) ∉ R, then a ≠ b

Example: Let us consider the set A={1, 2, 3, 4}. A relation R defined on set A as:

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

is relation R is Antisymmetric or not?

Sol: if whenever (1,2) ∈ R and (2,1) ∈ R, then 1 ≠ 2 if whenever (4,2) ∈ R and (2,4) ∈ R, then 4 ≠ 2

Hence relation R does not satisfy the Antisymmetric property

Asymmetric Property:

A relation R on a set A is called asymmetric if (a, b)∈R implies that (b, a)∉R for all a, b ∈ A.

Example: Let us consider the set A={1, 2, 3, 4}. A relation R defined on set A as:

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

is relation R is Asymmetric or not?

Sol: if (a, b)∈R implies that (b, a)∉R for all a, b ∈ A. if (1,2) ∈R then (2,1) ∈R

if (4,2) ∈R then (2,4) ∈R

Hence relation R does not satisfy the Asymmetric property

Transitive Property:

A relation R on a set A is called transitive if whenever (a, b)∈R and (b, c)∈R, then (a, c)∈R for all a, b, c ∈ A.

Example: Let us consider the set A={1, 2, 3, 4}. A relation R defined on set A as:

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

is relation R is transitive or not?

Sol: if whenever (a, b)∈R and (b, c)∈R, then (a, c)∈R for a, b, c ∈ A.

if (1,2),(2,1) ∈ R then (1,1) ∉ R,

if (4,2),(2,4) ∈ R then (4,4) ∉ R,

if (1,2),(2,4) ∈ R then (1,4) ∉ R,

Hence relation R does not satisfy the transitive property

Example-2: Let A={1,2,3,4} and R={(1,1),(1,2),(2,1), (2,2),

(3,4),(4,3),(3,3),(4,4)}.Identify which properties are satisfied by the relation R

1. Reflexive: (a, a) ∈ R for all a ∈ A (1,1),(2,2),(3,3),(4,4) ∈ R

Hence relation R satisfies the reflexive property

2. Symmetric: if (a, b) ∈ R then (b, a) ∈ R for all a, b ∈ A if (1,2) ∈ R then (2,1) ∈ R

if (3,4) ∈ R then (4,3) ∈ R

Hence relation R satisfies the Symmetric property

3. Transitive: if (a, b) ∈ R ,(b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ A

if (1,2),(2,1) ∈ R then (1,1) ∈ R,

if (2,1),(1,2) ∈ R then (2,2)∈ R,

if (4,3),(3,4) ∈ R then (4,4)∈ R.

Hence relation R satisfies the transitive property

d. Asymmetric: if (a, b) ∈ R then (b, a) ∉ R for all a, b ∈ A if (1,2) ∈ R then (2,1) ∈ R

if (3,4) ∈ R then (4,3) ∈ R

Hence relation R does not satisfy the Asymmetric property

e. Antisymmetric:

if whenever (a, b)∈R and (b, a)∈R, then a = b and if whenever (a, b)∈R and (b, a) ∉ R, then a ≠ b

if whenever (1,2) ∈ R and (2,1) ∈ R, then 1 ≠ 2

if whenever (3,4) ∈ R and (4,3) ∈ R, then 3 ≠ 4 Hence relation R does not satisfy the Antisymmetric property

• Example-3: Let A={1,2,3,4} and R={(1,1),(1,2),(2,2),(2,4),(1,3),(3,3),(3,4),(1,4),(4,4)}.Identify which properties are satisfied by the relation R
1. Reflexive: (a, a) ∈ R for all a ∈ A (1,1),(2,2),(3,3),(4,4) ∈ R

Hence Relation R satisfies the reflexive property

• Symmetric: if (a, b) ∈ R then (b, a) ∈ R for all a, b ∈ A

if (1,2) ∈ R then (2,1) ∉ R if (2,4) ∈ R then (4,2) ∉ R if (1,3) ∈ R then (3,1) ∉ R if (3,4) ∈ R then (4,3) ∉ R if (1,4) ∈ R then (4,1) ∉ R

Hence Relation R does not satisfies symmetric property

• Transitive: if (a, b) ∈ R ,(b, c) ∈ R then (a, c) ∈ R for all a, b, c

∈ A

if (1,2),(2,2) ∈ R then (1,2) ∈ R,

if (1,2),(2,4) ∈ R then (1,4)∈ R,

if (1,3),(3,3) ∈ R then (1,3)∈ R.

if (1,3),(3,4) ∈ R then (1,4)∈ R.

if (3,4),(4,4) ∈ R then (3,4)∈ R.

if (1,4),(4,4) ∈ R then (1,4)∈ R.

Hence Relation R satisfies the transitive property

d. Asymmetric: if (a, b) ∈ R then (b, a) ∉ R for all a, b ∈ A

if (1,2) ∈ R then (2,1) ∉ R if (2,4) ∈ R then (4,2) ∉ R if (1,3) ∈ R then (3,1) ∉ R if (1,4) ∈ R then (4,1) ∉ R if (3,4) ∈ R then (4,3) ∉ R

Hence Relation R satisfies the asymmetric property

e. Antisymmetric:

if a = b whenever (a, b)∈R and (b, a)∈R and if a ≠ b whenever (a, b)∈R and (b, a) ∉ R

if whenever (1,2) ∈ R and (2,1) ∉ R, then 1 ≠ 2

if whenever (3,4) ∈ R and (4,3) ∉ R, then 3 ≠ 4

if whenever (2,4) ∈ R and (4,2) ∉ R, then 2 ≠ 4

if whenever (1,3) ∈ R and (3,1) ∉ R, then 1 ≠ 3

if whenever (1,4) ∈ R and (4,1) ∉ R, then 1 ≠ 4 Hence Relation R satisfies the Antisymmetric property

EQUIVALENCE RELATION

• A Relation R on a set X is called an Equivalence relation on X if and only if it satisfies the following properties.
1. Reflexive property
2. Symmetric Property
3. Transitive property
• Reflexive property

for any element ‘a’, (a, a) ∈ R for all a ∈ A

2. Symmetric property

for any two elements a and b,

if (a, b)∈R then (b, a)∈R for all a, b ∈ A

3. Transitive property

for any three elements ‘a’, ‘b’ and ‘c’, if (a, b) ∈ R ,(b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ A

​

Example: The following are the examples of Equivalence relation.

• Equality of numbers on a set of real numbers.
• Equality of subsets of a universal set

Example-1:

Let A={1,2,3,4}and R={(1,1),(1,2),(2,1),(2,2),(3,4),

(4,3), (3,3), (4,4)} be a relation on A. Verify that R is an Equivalence Relation.

Sol: To prove that R is a Equivalence relation on set A, it satisfies the following properties.

1. Reflexive property
2. Symmetric Property
3. Transitive property

a. Reflexive: for any element ‘a’,

(a, a) ∈ R for all a ∈ A (1,1),(2,2),(3,3),(4,4) ∈ R

Hence Relation R satisfies the reflexive property

b. Symmetric: for any two elements ‘a’ and ‘b’, if (a, b) ∈ R then (b, a) ∈ R for all a, b ∈ A

if (1,2) ∈ R then (2,1) ∈ R if (3,4) ∈ R then (4,3) ∈ R

Hence Relation R satisfies the Symmetric property

c. Transitive: for any three elements ‘a’, ‘b’ and ‘c’

if (a, b) ∈ R ,(b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ A if (1,2),(2,1) ∈ R then (1,1) ∈ R,

if (2,1),(1,2) ∈ R then (2,2) ∈ R,

if (3,4),(4,4) ∈ R then (4,4)∈ R.

Hence Relation R satisfies the transitive property Therefore relation R is an Equivalence Relation

Example-2:

Let A={1,2,3,4,5,6,7,8,9,10,11,12} on this set define a relation R by ( x, y) ∈ R if and only if x-y is a multiple of 5. Verify that R is an Equivalence Relation.

Sol: To prove that R is a Equivalence relation on set A, it satisfies the

following properties.

1. Reflexive property
2. Symmetric Property
3. Transitive property

1. Reflexive: for any element ‘a’, a ∈ A, we have a-a is multiple of 5. Therefore , ( a, a) ∈ R.

For example : for any element a=5,5 ∈ A then (5,5) ∈ R i.e., 5-5 is a multiple of 5 i.e., 0 is a multiple of 5(5*0=0)

Hence Relation R satisfies the reflexive property

b. Symmetric: for any two elements ‘a’ and ‘b’ where a, b ∈ A. let us consider a=10,b=5 ∈ A.

if ( a, b) ∈ R then a-b is a multiple of 5

if (10,5) ∈ R then 10-5 is a multiple of 5 if ( b, a) ∈ R then b-a is a multiple of 5

if (5,10) ∈ R then 5-10 is a multiple of 5 Hence Relation R satisfies the symmetric property

c. Transitive:

for any three elements ‘a’, ‘b’ and ‘c’ where a, b and c ∈ A let us consider a=20,b=10 and c=5 ∈ A.

if (a , b) ∈ R and (b , c) ∈ R then (a , c) ∈ R

(a-c) is a multiple of 5 =(a-b) is a multiple of 5 +(b-c) is a multiple of 5

Hence Relation R satisfies the transitive property Therefore relation R is an Equivalence Relation

PARTIALLY ORDERED SET OR POSET

• A Relation R on a set A is said to be a partial ordering relation or partial order relation if and only if it satisfies the Reflexive, Antisymmetric and Transitive properties.
• Partial ordering is represented by the symbol “≤”, this symbol does not necessarily mean that “less than or equal to”.
• If ≤ is a partial ordering on P, then the order pair ( P, ≤ ) is called a Partially Ordered Set or a poset

• Let (P, ≤ ) be a poset. if for every x, y ∈P we have either x ≤ y ∨ y ≤ x, then ≤ is called simple ordering or linear ordering on P and (P, ≤ ) is called a totally ordered or simply ordered set or a chain.
• Let (P, ≤ ) be a poset, then ( P, ≥ ) is also a poset. ( P, ≥ ) Is called the dual of (P, ≤ )

PARTIAL ORDER RELATION

• A Relation R on a set A is said to be a partial ordering relation or partial order relation if and only if it satisfies the following properties.
1. Reflexive property

for any element ‘a’, (a, a) ∈ R for all a ∈ A

• Antisymmetric property

for any two elements a and b,

if a = b whenever (a, b)∈R and (b, a)∈R and if a ≠ b whenever (a, b)∈R and (b, a) ∉ R,

where a, b ∈ A

3. Transitive property

for any three elements ‘a’, ‘b’ and ‘c’

if (a, b) ∈ R ,(b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ A

​

Example: The following are the examples of partial ordering relation.

1. ≥ (greater than or equal to) is a partial ordering relation on the set of integers.
2. ⊆ (inclusion relation) is a partial ordering relation on the power set of set s.
3. Divisibility relation | is a partial ordering on the set of positive integers.

Example-1: Show that “greater than or equal” relation ( ≥) is a partial ordering on the set of integers.

Sol: To prove that ( ≥) is a partial ordering on the set of integers. it satisfies the following properties.

1. Reflexive property
2. Antisymmetric Property
3. Transitive property

1. Reflexive property:

for every integer a, a ≥ a, for all a ∈ Z

Hence ≥ satisfies the Reflexive property.

2. Antisymmetric Property

for any two integers a and b

if a ≥ b and b ≥ a then a=b , for all a, b ∈ Z if a ≥ b and b ≥ a then a=b , for all a, b ∈ Z

Hence ≥ satisfies the Antisymmetric property

3. Transitive property

for any three integers a, b and c

if a ≥ b and b ≥ c then a ≥ c , for all a, b ,c∈ Z Hence ≥ satisfies the Transitive property.

therefore it follows that ≥ is a partial ordering on the set of integers and (Z, ≥) is a Poset.

Example-2: Show that “Inclusion” relation

(⊆) is a partial ordering on the power set of a set.

Sol: To prove that (⊆) is a partial ordering on the power set of a set. it satisfies the following properties.

1. Reflexive property
2. Antisymmetric Property
3. Transitive property

1. Reflexive property:

for every set A,

A ⊆ A whenever A is a subset of S Hence ⊆ satisfies the Reflexive property.

2. Antisymmetric Property

for any two sets A and B

if A ⊆ B and B ⊆ A then A = B, for all A, B ∈ S Hence ⊆ satisfies the Antisymmetric property

3. Transitive property

for any three sets A, B and C

if A ⊆ B and B ⊆ C then A ⊆ C, for all A, B,C ∈ S Hence ⊆ satisfies the Transitive property.

​

Therefore it follows that ⊆ is a partial ordering on the power set of a set and (P(S), ⊆) is a Poset.

HASSE DIAGRAM

• A partial ordering relation ≤ on a set P can be represented by means of a diagram known as Hasse diagram of (P, ≤).
• Steps for drawing Hasse diagram:
1. In Hasse diagram, each element is represented by a small circle.
2. The circle for x ∈ P is drawn below the circle for y ∈ P if x < y and a line is drawn between x and y if y covers x
3. if x < y but y does not cover x , then x and y are not connected directly by a single line. However they are connected through one or more element of P

4. it is possible to obtain the set of order pairs in ≤ from such a

diagram.

5. From a totally ordered set (P, ≤ ), the Hasse diagram consists of circles one below the other. Thus a poset is called a chain.

​

Example-1: Let P={ 1,2,3,4 } and ≤ be the relation “less than or

equal to”. Draw the Hasse diagram.

Sol: Let R={( x, y)| x, y ∈ P and x less than or equal to y}

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

3

2

1

1 ≤ 2

2 ≤ 3

3 ≤ 4

1

1

2

1 ≤ 2

1

2

3

1 ≤ 2

2 ≤ 3

4

Example-2: Let P={ 1,2,3,4 } and if R is a relation on the set A defined by x R y if x divides y. Draw the Hasse diagram.

Sol: from the definition of R, we have

R={( x, y)| x, y ∈ P and x divides y}

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

1

1

2

1 divides 2

1

3

2

1 divides 2

1 divides 3

1

2

3

4

1 divides 2

1 divides 3

2 divides 4

Example-3: Let P={ 2,3,6,12,24,36 } and ≤ be the relation such that x ≤ y if x divides y, then the Hasse diagram is

2

3

6

12

24

36

2

3

6

2

3

6

2

3

12

3

6

24

12

2 divides

6

2

2 divides 6

3divides 6

3divides 6

6 divides 12

12 divides 24

6 divides 12

3divides 6

12 divides 24

6 divides 12

2 divides 6

3divides 6

12 divides

36

Therefore R satisfies the Antisymmetric property

Transitive: for all a, b, c ∈ P, if a divides b and b divides c, then a divides c i.e., if ( a, b) ∈ R and ( b, c) ∈ R then ( a, c) ∈ R

R={(1,1),(1,2),(1,3),(1,4),(1,6),(1,12),(2,2),(2,4),(2,6),(2,12),(3,3), (3,6),(3,12),(4,4),(4,12),(6,6),(6,12),(12,12)}

Therefore R satisfies the Transitive property.

​

Relation R satisfies Reflexive, Antisymmetric and Transitive properties on set P. Hence relation R is partial order relation on set P

R={(1,1),(1,2),(1,3),(1,4),(1,6),(1,12),(2,2),(2,4),(2,6),(2,12),(3,3), (3,6),(3,12),(4,4),(4,12),(6,6),(6,12),(12,12)}

Hasse Diagram is:

1

1

2

1 divides 2

1

2

3

1 divides 2

1 divides 3

1

2

3

4

1 divides 2

1 divides 3

2 divides 4

6

4

1

3

1 divides 3

2

1 divides 2

3 divides 6

2 divides 4

2 divides 6

12

6

4

1

2

1 divides 2

3

1 divides 3

3 divides 6

2 divides 6

2 divides 4

4 divides 12

6 divides 12

Example-4: Let P={ 1,2,3,4,6,12 } and if R is a relation on the set A defined by x R y if x divides y. Prove that R is a partial order on P. Draw the Hasse diagram for this relation.

​

Sol: from the definition of R, we note that R={( x, y)| x, y ∈ P and x divides y}

​

R={(1,1),(1,2),(1,3),(1,4),(1,6),(1,12),(2,2),(2,4),(2,6),(2,12),(3,3),

(3,6),(3,12),(4,4),(4,12),(6,6),(6,12),(12,12)}

Reflexive: Evidently, ( a, a) ∈ R for all a ∈ P

(1,1),(2,2),(3,),(4,4),(6,6),(12,12) ∈ R

Therefore relation R is Reflexive.

Antisymmetric: for all a, b ∈ P, if a divides b and b divides a, then a=b. for all a, b ∈ P, if a divides b and b does not divides a, then a ≠ b Hence R is Antisymmetric

Example-5: Let P={ 1,2,3,4,6,8,12} and ≤ be the partial ordering relation on set P such that x ≤ y if x divides y. Draw the Hasse diagram.

Sol: from the definition of R, we note that R={( x, y)| x, y ∈ P and x divides y}

R={(1,1),(1,2),(1,3),(1,4),(1,6),(1,8),(1,12),(2,2),(2,4),(2,6),(2,8),

(2,12),(3,3),(3,6),(3,12),(4,4),(4,8),(4,12),(6,6),

(6,12),(8,8),(12,12)}

• Hasse Diagram for relation R is:

1

8

12

6

4

3

2

1 divides 3

1 divides 2

3 divides 6

2 divides 4

6 divides 12

4 divides 8

4 divides

12

Example-6: Draw the Hasse diagram representing the positive divisors of 36.

Sol: The set of all positive divisors of 36 is: D₃₆={1,2,3,4,6,9,12,18,36}

The relation R of divisibility(a R b if and only if a divides b) is a partial order on the set D₃₆. The relation R(divisibility) contains the following order pairs.

R={(1,1),(1,2),(1,3),(1,40,(1,6),(1,9),(1,12),(1,18),(1,36),(2,2)

(2,4),(2,6),(2,12),(2,18),(2,36),(3,3),(3,6),(3,9),(3,12),(3,18),(3,

36),((4,4),4,12),(4,36),(6,6),(6,12),(6,36),,(9,9),(9,18),(9,36),(1

2,12),(12,36),(18,18),(18,36),(36,36)}

​

Relation R(divisibility) satisfies reflexive, Antisymmetric, Transitive properties by observing the above order pairs. Hence, relation R is Partial order relation on D₃₆

Hasse Diagram:

1

2

3

4

6

9

12

18

36

1 divides 2

1 divides 3

2 divides 4

3 divides 9

4 divides 12

9 divides 18

18 divides 36

12 divides 36

3 divides 6

2 divides 6

6 divides 12

6 divides 18

Example-7: Consider the partial order of divisibility on the se

A. Draw the Hasse diagram for the poset and determine whether the poset is totally order or not.

i. A={ 1,2,3,5,6,10,15,30}

Sol: Hasse diagram for (i)

ii. A={ 2,4,8,16,32}

Hasse diagram for (ii)

30

32

16

​

​

8

​

4

​

2

• By examining the above Hasse diagrams, we find that the given relation is totally ordered in case (ii), but is not totally ordered in case (i)

Example-8: Let S={1,2,3} and P(S), the power set of S. On P(S), define the relation R by X R Y if and only if X⊆Y. Show that this relation is a partial order on P(S). Draw its Hasse diagram.

Sol: For any set S, the set P(S) contains all subsets of S.

We have already proved that the subset relation ⊆ is reflexive, antisymmetric and transitive on P(S) for any set S. This relation is a partial order on S.

For the given set S={1,2,3} also, ⊆ is a partial order. For the given set S={1,2,3}, the subsets of S are

{∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}

• HASSE DIAGRAM :

∅

{1}

{1,2,3}

{2,3}

{1,3}

{1,2}

{3}

{2}

Example-9: Consider the partial order of divisibility relation on set A. Draw the Hasse diagram for the following

i. A={ 1,2,3,4,6,8,12,16,24,48}

Sol: Hasse diagram for (i)

ii. A={ 1,3,5,9,15,45}

Hasse diagram for (ii)

1

1

5

3

9

15

45

4

6

8

12

16

24

2

3

48

TERMINOLOGY RELATED TO POSETS

Maximal member :

Let (P, ≤) is a poset, an element a∈P is called a maximal member of P, if there is no element b ∈P such that a<b(a strictly precedes b).

Minimal member :

Let (P, ≤) is a poset, An element a∈P is called a minimal member of P, if there is no element b ∈P such that b<a(a strictly precedes b).

Greatest member :

Let (P, ≤) is a poset, if there exist an element a∈P such that b

≤ a for all b ∈P, then a is called the greatest member of the poset.

Least member:

Let (P, ≤) is a poset, if there exist an element a∈P such that

a ≤ b for all b ∈P, then a is called the greatest member of the poset.

Example:

d

e

a

b

d

a b

c

d

a

d

c

a

b

c

c

b

FIG-1

FIG-2

FIG-3

FIG-4

*Let Us Consider The Hasse Diagrams Of Four Posets, Given In The

Above Fig.

• For FIG-1, a and b are minimal elements and d and e are the maximal

elements

• For FIG-2, a and b are minimal elements and d is the greatest element or maximal elements. There is no least element.
• For FIG-3, a is the least element or minimal element and c and d are the

maximal elements. There is no greatest element.

• For FIG-4, a is the least element and d is the greatest element.

• A minimal member need not be unique. All those members which appear at the lowest level of a Hasse diagram of a poset are minimal members.
• In the below Hasse diagram, it contains one maximal member and two minimal members .

OPERATIONS ON RELATIONS

• The following operations can be performed on relations.
1. Intersection
2. Union
3. Difference
4. Complement
5. Composition
6. Converse

1. Intersection:

Let A and B be two sets. Let R and S be the two relations from set A to set B. The intersection of two relations from set A to Set B is represented by R ∩ S is defined as

R ∩ S={(a , b) ∈ A x B / (a, b) ∈ R and (a, b) ∈ S }

R ∩ S is the intersection of relations R and S

a (R ∩ S) b ⬄ a R b ∧ a S b

2. Union:

Let A and B be two sets. Let R and S be the two relations from set A to set B. The union of two relations from set A to Set B is represented by R U S is defined as

R U S={(a , b) ∈ A x B / (a, b) ∈ R or (a, b) ∈ S }

R U S is the union of relations R and S

a (R U S) b ⬄ a R b ∨ a S b

3. Difference:

Let A and B be two sets. Let R and S be the two relations from set A to set B. The difference of two relations from set A to Set B is represented by R - S is defined as

R - S={(a , b) ∈ A x B / (a, b) ∈ R and (a, b) ∈ S }

R - S is the difference of relations R and S

a (R - S) b ⬄ a R b ∧ a S b

4. Complement:

Let A and B be two sets. Let R be a relation from set A to set B. The complement of a relation R from set A to Set B is represented by R^c is defined as

R^c ={(a , b) ∈ A x B / (a, b) ∈ R} R^c is complement of a relation R a (R^c) b ⬄ a R b

5. Composition:

Let A,B and C be three sets Let R be a relation from set A to set B and S be a relation from set B to set C. The composite or R and S is the relation consisting of order pairs (a,c) where a ∈ A and c ∈ C and for which there exist an element b ∈ B such that (a,b) ∈ R and (b,c) ∈ S.

The composition of R and S denoted by R o S

6. Converse:

Given a relation R from set X to Set Y, a relation ~R

from Y to X is called the converse of R.

​

The order pairs of ~R are obtained by interchanging the members in of the order pairs of R.

for x ∈ X and y ∈ Y, then x R y ⬄ y ~R x

~R={(b, a) | (a, b) ∈ R

Example:

Let R= {(1,2),(1,3),(1,4)} then find out ~R.

Sol: R= {(1,2),(1,3),(1,4)}

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

Example

Example-1: Let A={1,2,3} and B={ 1,2,3,4}. The relations R={(1,1),(2,2),(3,3)}and S={(1,1),(1,2),(1,3),(1,4)} can be

combined. Find out R U S, R ∩ S, R-S, S-R, R^c ,R o S and s^c

Sol:

i. R U S={(1,1),(2,2),(3,3)} U {(1,1),(1,2),(1,3),(1,4)}

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

​

ii. R ∩ S={(1,1),(2,2),(3,3)} ∩{(1,1),(1,2),(1,3),(1,4)}

={(1,1)}

iii. R-S = {(1,1),(2,2),(3,3)} - {(1,1),(1,2),(1,3),(1,4)}

={(2,2),(3,3)}

iv. S-R = {(1,1),(1,2),(1,3),(1,4)} –{(1,1),(2,2),(3,3)}

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

= A x B –R

v. R^c = U-R

={ (1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4)}-

{(1,1),(2,2),(3,3)}

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

vi. s^c = U-S

= A x B –S

={ (1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4)}-

{(1,1),(1,2),(1,3),(1,4)}

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

vii. R o S={(1,1),(2,2),(3,3)} o {(1,1),(1,2),(1,3),(1,4)}

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

viii. S o R= {(1,1),(1,2),(1,3),(1,4)} o {(1,1),(2,2),(3,3)}

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

Example-2: Let the relations R={(1,1),(1,3),(3,2),(3,4),(4,2)}and

S={(2,1),(3,3),(3,4),(4,1)}. Find out R o S, S o R, R o R, S o S, (R o S) o R, R o

(S o R), R³ ,R² ,R⁴ , R^6.

Sol:

i. R o S= {(1,1),(1,3),(3,2),(3,4),(4,2)}o {(2,1),(3,3),(3,4),(4,1)}

={ (1,3),(1,4),(3,1),(4,1)}

ii. S o R={(2,1),(3,3),(3,4),(4,1)}o {(1,1),(1,3),(3,2),(3,4),(4,2)}

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

iii. R o R= {(1,1),(1,3),(3,2),(3,4),(4,2)} o {(1,1),(1,3),(3,2),(3,4),

(4,2)}

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

iv. S o S={(2,1),(3,3),(3,4),(4,1)}o {(2,1),(3,3),(3,4),(4,1)}

={ (3,3),(3,4),(3,1)}

v. (R o S) o R= { (1,3),(1,4),(3,1),(4,1)}o {(1,1),(1,3),(3,2),(3,4),

(4,2)}

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

vi. R o (S o R)= {(1,1),(1,3),(3,2),(3,4),(4,2)}o { (2,1),(2,3), (3,2),(3,4),(4,1),(4,3)}

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

vii.

R³= Ro R o R= (Ro R) o R = Ro (R o R)

= {(1,1),(1,3),(3,2),(3,4),(4,2)}o { (1,1),(1,2),(1,3),(1,4),(3,2)}

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

viii. R²= R o R= {(1,1),(1,3),(3,2),(3,4),(4,2)} o {(1,1),(1,3),(3,2),

(3,4), (4,2)}

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

ix. R⁴= R³ o R= { (1,1),(1,3),(1,2),(1,4)} o {(1,1),(1,2),(1,3),

(1,4), (3,2)}

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

x. R⁶= R³ o R³ = { (1,1),(1,3),(1,2),(1,4)} o { (1,1),(1,3),(1,2),(1,4)}

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

PARTITION SET

• Let A be a non-empty set. Suppose there exist non-empty subsets A1,A2,A3,...,Ak of A such that the following three conditions hold:
1. Ai ≠ ∅, for each i
2. A is the union of A1,A2,A3,..., Ak; that is A1𝖴A2𝖴.... 𝖴

AK=A

• Any two of the subsets A1,A2,A3,..., Ak are disjoint; that is Ai ∩ A j= ∅ for i ≠ j.

Then the set P={A1,A2,A3,..., Ak} is called a partition of A and A1,A2,A3,..., Ak are called the blocks or cells of the partition.

Example-1: Let A={ a, b, c, d, e, f, g, h, i, j} and the subsets of A are A1={a, b, c, d, e} A2={f, g, h} A3={ i, j} A4={ a, b, c, d} A5={c}. Find out the partitions.

Sol: Let A={ a, b, c, d, e, f, g, h, i, j} Subsets of A are A1={a, b, c, d, e}

A2={f, g, h}

A3={ i, j}

A4={ a, b, c, d}

A5={c}.

i. π1={A1,A2,A3} is a partition because

A1 ∩ A2={a, b, c, d, e} ∩ {f, g, h} = ∅

A1 ∩ A3= {a, b, c, d, e} ∩ {i, j} = ∅

A2 ∩ A3= {f, g, h} ∩ {i, j} = ∅

and A1 𝖴 A2 𝖴 A3= {a, b, c, d, e} 𝖴 {f, g, h} 𝖴 {i, j} =

{a, b, c, d, e, f, g, h, i, j} = A therefore π1={A1,A2,A3} is a partition

2. π2={A1,A4,A5} is not a partition because

A1 ∩ A4 ={a, b, c, d, e} ∩ {a, b, c, d} ={a, b, c, d} ≠ ∅

A4 ∩ A5={{a, b, c, d} ∩ {c} = { c } ≠ ∅

A1 ∩ A5 ={a, b, c, d, e} ∩ {c} ={c} ≠ ∅

Therefore π2={A1,A4,A5} is not a partition

3. π3={A2,A4,A5} is not a partition because

A4 ∩ A5={a, b, c, d} ∩ {c} = { c } ≠ ∅

A2 ∩ A5 ={f, g, h} ∩ {c}= ∅

A2 ∩ A4 ={f, g, h} ∩ {a, b, c, d} = ∅

and A2 𝖴 A4 𝖴 A5= {f, g, h} 𝖴{a, b, c, d} 𝖴 { c}

= {a, b, c, d, f, g, h} ≠ A

Therefore π3={A2,A4,A5} is not a partition Therefore partition of set A is π1={A1,A2,A3} only.

Example-2: List out all the partitions of A={1,2,3}. Sol: Let us take the subsets of set A are

A1={1} A4={1,2}

A2={2} A5={2,3}

A3={3} A6={1,3}

1. Now consider the partition π1={A1,A2,A3}

A1 ∩ A2={1} ∩ {2} = ∅ A1 ∩ A3= {1} ∩ {3} = ∅ A2 ∩ A3= ={2} ∩ {3} = ∅

and A1 𝖴 A2 𝖴 A3= {1} 𝖴 {2} 𝖴 {3}

={1,2,3} = A

Therefore π1={A1,A2,A3} is a partition

2. Now consider the partition π2={A1,A5}

A1 ∩ A5 ={1} ∩ {2,3} = ∅

and A1 𝖴 A5 = {1} 𝖴 {2,3}={1,2,3} = A

Therefore π2={A1,A5} is a partition

3. Now consider the partition π3={A2,A6}

A2 ∩ A6 ={2} ∩ {1,3} = ∅

and A2 𝖴 A6 = {1} 𝖴 {2,3}={1,2,3} = A

Therefore π3={A2,A6} is a partition

4. Now consider the partition π4={A3,A4}

A3 ∩ A4 ={3} ∩ {1,2} = ∅

and A3 𝖴 A4 = {3} 𝖴 {1,2}={1,2,3} = A

Therefore π4={A3,A4} is a partition.

​

Therefore the partitions of set A= {1,2,3} are

π1={A1,A2,A3} π2={A1,A5} π3={A2,A6}

π4={A3,A4}

Example-3: Let A={1,2,3,4,5,6,7,8,9,10} and subsets of set A

are A1={1,2,3,4}

A4={4,8,10}

A2={5,6,7}

A5={8,9,10}

A3={4,5,7,9}

A6={1,2,3,6,8,10}

Which of the following are the partition of A?

a. {A1,A2,A3} b. {A1,A3,A5} c. {A3,A6}

d. {A2,A3,A4}

Sol: a. Consider first partition π1={A1,A2,A3}

A1 ∩ A2={1,2,3,4} ∩ {5,6,7} = ∅

A1 ∩ A3= {1,2,3,4} ∩ {4,5,7,9} = {4} ≠ ∅

A2 ∩ A3 ={5,6,7} ∩ {4,5,7,9} = {5,7} ≠ ∅

and A1 𝖴 A2 𝖴 A3 ={1,2,3,4} 𝖴 {5,6,7} 𝖴 {4,5,7,9}

={1,2,3,4,5,6,7,9} ≠ A

Therefore π1={A1,A2,A3} is not a partition

b. Consider first partition π2={A1,A3,A5}

A1 ∩ A3= {1,2,3,4} ∩ {4,5,7,9} = {4) ≠ ∅

A3 ∩ A5= ={4,5,7,9} ∩ {8,9,10} = {9} ≠ ∅

A1 ∩ A5= {1,2,3,4} ∩ {8,9,10} = ∅

and A1 𝖴 A3 𝖴 A5= {1,2,3,4} 𝖴 {4,5,7,9} 𝖴 {8,9,10}

={1,2,3,4,5,7,8,9,10} ≠ A

Therefore π2={A1,A2,A3} is not a partition

iii. Now consider the partition π3={A3,A6}

A3 ∩ A6 ={4,5,7,9} ∩ {1,2,3,6,8,10} = ∅

and A3 𝖴 A6 ={4,5,7,9} 𝖴 {1,2,3,6,8,10}

={1,2,3,4,5,6,7,8,9,10}= A

Therefore π3={A3,A6} is a partition

d. Consider first partition π4={A2,A3,A4}

A2 ∩ A3 ={5,6,7} ∩ {4,5,7,9} = {5,7} ≠ ∅

A3 ∩ A4= {4,5,7,9} ∩ {4,8,10} = {4) ≠ ∅

A2 ∩ A4 ={5,6,7} ∩ {4,8,10} = ∅

and A2 𝖴 A3 𝖴 A4 ={5,6,7} 𝖴 {4,5,7,9} 𝖴 {4,8,10}

={4,5,6,7,8,9,10} ≠ A

Therefore π4={A2,A3,A4} is not a partition

​

Therefore π3={A3,A6} is a partition only, but the remaining π1, π2, π4 are not partitions.

Theorem:

Let P be a partition of the set A. Define a relation R on A as aRb where a and b are members of the same block, then R is an equivalence relation on A.

Example-1: Let A={1,2,3,4} and P={{1,2,3},{4}} be a partition of

A. Find the equivalence relation determined by P.

Sol: A={1,2,3,4} and P={{1,2,3},{4}}

P contains two blocks:{1,2,3} and {4}

Each element in each block is related to itself and related to

every other element in the same block.

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

Example-2: Let X={a, b, c, d, e} and let C={{a, b},{c},{ d, e}}. Show that the partition C defines an equivalence relation on X.

Sol: X={a, b, c, d, e} and C={{a, b},{c},{ d, e}} C contains three blocks :{a, b},{c},{ d, e}

Each element in each block is related to itself and related to

every other element in the same block.

R={{a, a),(a, b),(b, a),(b, b),(c, c),(d, d),(d, e),(e, d),( e, e)}

Properties of Equivalence class:

1. Let R be an equivalence relation on set A and a ∈ A, then a ∈ [a]
2. Let R be an equivalence relation on set A and let a, b ∈ A, then aRb if and only if [a]=[b].
3. Let R be an equivalence relation on set A and let a, b ∈ A, then the following condition hold.

if [a] ∩ [b] ≠ ∅, then [a] = [b]

Example-1: Let A={1,2,3,4}. The equivalence relation R={(1,1), (1,2),(2,1),(2,2),(3,4),(4,3),(3,3),(4,4)} defined on this set A,

determine the partition induced.

Sol: By examining the given relation R, we find that the equivalence

classes of the elements of A with respect to R are

Equivalence class of 1 is [1]={1,2}

Equivalence class of 2 is [2]={1,2}

Equivalence class of 3 is [3]={3,4}

Equivalence class of 4 is [4]={3,4}

Out of the above 4 equivalence classes, only [1] and [3] are distinct. These two distinct equivalence classes constitute the partition.

P={[1],[3]}={{1,2},{3,4}}

This is the partition of the given set A induced by the given relation R.

Verification:

A=[1] 𝖴 [3] ={1,2} 𝖴 {3,4}={1,2,3,4}

Example-2: Let A={1,2,3,4,5}. The equivalence relation R={(1,1),

(2,2),(2,3),(3,2),(3,3),(4,4),(4,5),(5,4),(5,5)} defined on this set A,

Find the partition of A induced by R.

Sol: By examining the given relation R, we find that the equivalence classes of the elements of A with respect to R are

Equivalence class of 1 is [1]={1}

Equivalence class of 2 is [2]={2,3}

Equivalence class of 3 is [3]={2,3}

Equivalence class of 4 is [4]={4,5}

Equivalence class of 5 is [5]={4,5}

Out of the above 5 equivalence classes, only [1],[2] and [4] are distinct.

These three distinct equivalence classes constitute the partition of A

induced by R.

P={[1],[2],[4]}={{1},{2,3},{4,5}}

This is the partition of the given set A induced by the given relation R. Verification:

A=[1] 𝖴 [2] 𝖴 [4]={1} 𝖴 {2,3} 𝖴 {4,5}={1,2,3,4,5}

​

NOTE: i. The partition P will be denoted by A

R

ii. The elements of

A are called quotient sets of A

R

with respect to R

Example-3: Let A={1,2,3,4} and let R={(1,1), (1,2),(2,1),(2,2), (3,4),

(4,3),(3,3),(4,4)} be an equivalence relation on A. Determine A

R

Sol: By examining the given relation R, we find that the equivalence classes of the elements of A with respect to R are

Equivalence class of 1 is [1]={1,2}

Equivalence class of 2 is [2]={1,2}

Equivalence class of 3 is [3]={3,4}

Equivalence class of 4 is [4]={3,4}

Out of the above 4 equivalence classes, only [1] and [3] are distinct.

These two distinct equivalence classes constitute the partition.

P={[1],[3]}={{1,2},{3,4}}

Hence A = {[1],[3]}

R

Example-4: Let A={1,2,3,4,5,6} and let R={(1,1), (1,5),(2,2),(2,3), (2,6),

(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3),(6,6)} be an equivalence

R

relation on A. Find the partition of A induced by

i.e., Find the equivalence class of R.

Sol: By examining the given relation R, we find that the equivalence

classes of the elements of A with respect to R are

Equivalence class of 1 is [1]={1,5}

Equivalence class of 2 is [2]={2,3,6}

Equivalence class of 3 is [3]={2,3,6}

Equivalence class of 4 is [4]={4}

Equivalence class of 5 is [5]={1,5}

Equivalence class of 6 is [6]={2,3,6}

Out of the above 6 equivalence classes, only [1], [2],[4] are distinct. These three distinct equivalence classes constitute the partition.

P={[1],[2],[4]}={{1,5},{2,3,6},{4}}

Hence partition of A induced by R i.e.,

​

Hence A = {{1,5},{2,3,6},{4}} R

Example-5: List all partitions of A={1,2,3}. Show that any partition of the set induces an Equivalence relation.

Sol: First write the subsets of A

P1={1}, P2={2},P3={3},P4={1,2}, P5={2,3], P6={1,3}

The partition sets of P are

i. Now consider the partition π1={P1,P2,P3}={{1},{2},{3}}

Each element in each block is related to itself and related to every

other element in the same block.

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

π1 induces an Equivalence Relation

2. Now consider the partition π2={P1,P5}={{1},{2,3}}

Each element in each block is related to itself and related to every other element in the same block.

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

π2 induces an Equivalence Relation

3. Now consider the partition π3={P2,P6}={{2},{1,3}}

Each element in each block is related to itself and

related to every other element in the same block.

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

π3 induces an Equivalence Relation

4. Now consider the partition π4={P3,P4}={{3},{1,2}}

Each element in each block is related to itself and

related to every other element in the same block.

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

π4 induces an Equivalence Relation

Covering of a Set

Let S be a given set and A1,A2,A3,...,Ak are the subsets of S and the union of the subsets A1𝖴A2𝖴.... 𝖴 AK=S then the set A is called a Covering of S and the sets A1,A2,A3,...,Ak are said to cover S.

The subsets A1,A2,A3,...,Ak of S are mutually disjoint , then A is called a partition of S and the subsets A1,A2,A3,...,Ak are called the blocks of the partition.

Example-1: List out all the partitions of S={a, b, c} and consider the following collections of subsets of S

A={{a, b},{b, c}} B={{a},{a, c}} C={{a},{ b, c}}

D={{a ,b, c}} E={{a},{b},{c}} F={{a},{a, b},{a, c}}

Sol: The sets A and F are coverings of S

Considering set A, The union of its subsets form a set S

{a, b} 𝖴{b, c}={a, b, c}=S.

Hence set A covers S

Considering set F, The union of its subsets form a set S

{a} 𝖴 {a, b} 𝖴{a, c}={a, b, c}=S.

Hence set F covers S.

The sets C,D and E are partitions

Considering set C, it contains two subsets {a} and {b,c} that are mutually exclusive because {a} ∩ {b, c} = ∅, Therefore set C is a partition. The union of the two subsets form a set S because {a} 𝖴{b, c}={a, b, c}=S. Therefore set C cover S

Considering set D, it contains only one set, it forms a set S and it is mutually exclusive itself. Therefore set D is a partition and set D cover S.

Considering set E, it contains three subsets {a} {b} and {c} that are mutually exclusive because {a} ∩ {b} ∩ { c} = ∅, Therefore set E is a partition and union of the two subsets form a set S because {a}

𝖴 {b} 𝖴 {c}={a, b, c}=S. Therefore set E cover S.

The set B is neither a partition nor a covering of S.

Considering set B, it contains two subsets {a}, {a,c} that are not mutually exclusive because {a} ∩ {a, c} ≠ ∅ , hence it is not a partition and union of the two subsets does not form a set S because {a} 𝖴 {a, c} } ≠ S . Therefore set B does not covers S.

Representation of Relations

Two methods are used for representing the relations.

1. Representing the relations using Relation Matrix
2. Representing the relations using Directed Graphs.

Representing the relations using Relation Matrix:

Let A={ a1,a2,.......,am} and B={b1,b2,......,bn } are finite sets containing m and n elements respectively and R is a relation from A to B, then we can represent the relation R by an m x n matrix called Relation Matrix. This relation matrix is denoted by MR=[mij], where

mij= 1

if (ai, bj) ∈ R

0 if (ai, bj) ∉ R

Where

the matrix representing a relation MR=[mij]= 1 when ai is related to bj

the matrix representing a relation MR=[mij]= 0 when ai is not related to bj

Example-1: Let A={a1,a2,a3} and B={b1,b2,b3,b4} are finite sets, then the relation R from set A to set B is given by R={(a1,b1),

(a1,b4),(a2,b2),(a2,b3),(a3,b1),(a3,b3)}. Write down the relation matrix.

Sol: A={a1,a2,a3} and B={b1,b2,b3,b4} are two finite sets.

R={(a1,b1), (a1,b4),(a2,b2),(a2,b3),(a3,b1),(a3,b3)}

The relation Matrix MR is represented by using the following rule.

R has a value 1 when ai is related to bj

R has a value 0 when ai is not related to bj

b1 b2 b3 b4

Example-2: Let A={a1,a2,a3} and B={b1,b2,b3,b4,b5} are finite sets.

Find out the order pairs in the relation R represented by the

matrix. b1 b2 b3 b4 b5

a1

0 1 0 0 0

1 0 1 1 0

1 0 1 0 1

MR= a2

a3

Sol: Relation R consists of those order pairs (ai, bj) with mij=1, it follows that

R={(a1,b2),(a2,b1),(a2,b3),(a2,b4),(a3,b1),(a3,b3),(a3,b5)}

A relation matrix MR of a relation R on a set has the following properties.

1. R is reflexive if all the elements on the main diagonal of MR are equal to 1.
2. R is symmetric if and only if mji=1 whenever mij=1. This also means mji=0 whenever mij=0.

R is symmetric if and only if MR=(MR)^T

3. R is an antisymmetric if mji=1 with i ≠ j, then mji=0. In

otherwords, either mij=0 or mji=0 when i ≠ j

Example-3: Suppose that the relation R on a set is represented by the matrix. Is R is reflexive, Symmetric and Antisymmetric.

​

1 1 0

MR= 1 1 1

0 1 1

Sol: Since all the diagonal elements of this matrix are equal to 1.

Hence R is reflexive.

Since MR is Symmetric it follows that R is symmetric.

Since MR is not Antisymmetric it follows that R is not

Antisymmetric.

Directed Graphs:

A relation can be represented pictorially by drawing its digraph

as follows.

1. A small circle is drawn for each element of A and marked with

the corresponding element. This circles are called vertices.

2. An arrow is drawn from vertex ai to the vertex aj if and only if aiRaj. This is called an edge(directed). Note that an element of the form (a,a) in a relation corresponds to a directed edge from a to a.Such an edge is called a loop.
3. This pictorial representation of R is called a directed graph or

digraph of R.

Example-4: Let A={1,2,3,4} and R be a relation defined on set A

as R={(1,1),(1,3),(2,1),(2,3),(2,4),(3,1),(3,2),(4,1),(4,3)}.Draw

the diagraph of relation R.

Sol: Each and every element in set A can be represented by a small circle.

1 2

​

​

4 3

Digraph of Relation R

​

Every first element in the order pair is related with the other element In the same order pair, at that time, these two elements are connected By using the directed edge from first element of order pair to second element of order pair. In order pair, both elements are same, then they are connected by using self loop.

In the above graph, at vertex 1, self loop is there.

Example-5: What are the order pairs in the relation R defined on set A={1,2,3,4} represented by the directed graph shown below.

Sol: The order pairs from the above digraph of a relation R are

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

Each of these pairs corresponds to an edge of the directed

graph with (2,2) and (3,3) corresponding to loops.

2

1

4

3

The directed graph representing a relation can be used to

determine whether the relation has various properties.

1. A relation is reflexive if and only if there is a loop at every vertex of the directed graph, so that every order pair of the form (x, x) occurs in the relation.
2. A relation is symmetric if and only if for every edge between distinct vertices in its digraph, there is an edge in the opposite direction , so that (y, x) in the relation whenever (x, y) is in the relation.
3. A relation is antisymmetric if and only if there are never

two edges in opposite directions between distinct vertices.

4. A relation is transitive if and only if whenever there is an edge from a vertex x to a vertex y and an edge from a vertex y to a vertex z, there is an edge from x to z.

Example-6: Determine whether the relations for the directed graphs shown below are reflexive, symmetric, antisymmetric and transitive.

1

2

3

1

2

3

4

Digraph R

Digraph S

1. Considering the digraph R, the order pairs obtained from the

diagraph are

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

there are self loops at every vertex of the directed graph of R, hence it is reflexive.

R is not symmetric because (1,2) ∈ R but (2,1) ∉ R

(1,3)∈R but (3,1)∉ R

R is not antisymmetric because

if (2,3) ∈R and (3,2) ∈R then 2≠3

R is transitive

if (1,3) ∈R and (3,2) ∈R then (1,2) ∈R

if (2,3) ∈R and (3,2) ∈R then (2,2) ∈R

2. Considering the digraph S, the order pairs obtained from the

diagraph are

S={(1,2),(2,1),(1,3),(1,4),(3,1),(4,1),(4,4),(2,2)}

1. there are no self loops at every vertex of the directed graph of

S, hence R is not reflexive.

2. R is symmetric because every edge between distinct vertices is accompanied by an edge in the opposite direction.
3. R is not antisymmetric because every edge between distinct vertices is accompanied by an edge in the opposite direction
4. R is not transitive because (1,2) ∈ R and (2,1) ∈ R but (1,1) ∉

R

Compatibility Relations

A relation R on a set A is said to be a Compatibility relation if it is Reflexive and Symmetric.

Clearly, all equivalence relations are compatibility relations. A compatibility relation is denoted by ≈

Example-1: Let X={ ball, bed, dog, let, egg} and let the relation R be given by R={( x, y) | x, y ∈ X ∧ x R y if x and y contain some common letter }

Sol: R is a compatibility relation on set X and x , y are two elements of X. Let x and y are called compatible if x R y. Denoting ball by x1, bed by x2, dog by x3, let by x4 and egg by x5.

now the graph of the compatibility relation as follows.

1. Each element in set X is related or compatible to itself, hence draw self loop at each and every vertex in set X
2. If x and y are related or compatible, draw the edge between them.

graph of the above compatibility relation as follows:

x1

x2

x5

x3

x1

x2

x3

x5

x4

Denoting ball by x1, bed by x2, dog by x3, let by x4 , egg by x5.

x4

Since ≈ is a

Compatibility relation, it necessary to

the loops at

is not draw each

element and it is not

necessary to draw both xRy and yRx, then we can simplify

of

the graph Compatibility relation as

The elements in each of the sets {x1,x2,x4} and

{x2,x3,x5} are related to each other, these two sets define a cover of X. The set {x2,x4,x5} also has elements compatible to each other.

A compatibility relation does define a covering of the set X

The relation matrix for the given relation is

Maximal Compatibility block: Let X be a set and ≈ a compatibility relation on X. A subset A ⊆ X is called a maximal compatibility block if any element of A is compatible to every other elements of A and no element of X-A is compatible to all elements of A.

The subsets {x1,x2,x4}, {x2,x3,x5} and {x2,x4,x5} are maximal compatibility blocks. These sets are not mutually disjoint, and therefore they only define a covering of X.

Procedure to find the maximal compatibility blocks corresponding to a compatibility relation:

1. First draw a simplified graph of the compatibility relation.
2. From this graph, pick the largest complete polygons. By a largest complete polygon, we mean a polygon in which any vertex is connected to every other vertex.
3. Similarly, any two elements which are compatible to one another but to no other elements also forms a maximal compatibility block.
4. The final sets of compatibility classes including those which are isolated elements constitute the maximum compatibility classes.

Example-2: Let the compatibility relation on a set {1,2,3,4,5,6} is represented by a graph. Find out the maximum compatibility blocks of the relation.

3

1

5

2

4

​

Sol:

The maximum compatibility blocks are: {1,3,4}, {2,3},{4,5},{2,5} Since 1,3 and 4 elements are compatible to each other,

2 and 3 elements are compatible to each other 4 and 5 elements are compatible to each other 2 and 5 elements are compatible to each other

Example-3: Let the compatibility relation on a set {1,2,3,4,5,6} is represented by a graph. Find out the maximum compatibility blocks of the relation..

3

5

6

1

2

4

​

Sol:

The maximum compatibility blocks are: {1,2,3}, {1,3,6},{3,5,6},{4} Since 1,2 and 3 elements are compatible to each other,

1,3 and 6 elements are compatible to each other 3,5 and 6 elements are compatible to each other element 4 is compatible to itself.

Example-4: Let the compatibility relation on a set {1,2,3,4,5,6} is represented by a graph. Find out the maximum compatibility blocks of the relation.

1

4

3

2

5

6

Sol:

The maximum compatibility blocks are: {1,2,3,4}, {3,6},{2,5},{5,6} Since 1,2 ,3 and 4 elements are compatible to each other,

3 and 6 elements are compatible to each other 2 and 5 elements are compatible to each other 5 and 6 elements are compatible to each other

Example-5: Let the compatibility relation on a set {1,2,3,4,5,6} be given by a matrix. Draw the graph and find out the maximum compatibility blocks of the relation.

​

2 1

3 1 1

4 0 0 0

5 0 0 1 1

6 1 0 1 0 1

1 2 3 4 5

Sol:

1

3

2

4

6

5

The maximum compatibility blocks are: {1,2,3}, {1,3,6}, {3,5,6},

{3,4,5}

Since 1,2 and 3 elements are compatible to each other, 1,3 and 6 elements are compatible to each other 3,5 and 6 elements are compatible to each other 3,4 and 5 elements are compatible to each other,

TRANSITIVE CLOSURE

The transitive closure of a relation R is the smallest transitive

relation containing R. We denote the Transitive relation of R by R⁺.

Let X be any finite set containing n elements and R be a relation in X. The relation R⁺ = R 𝖴 R² 𝖴 R³ 𝖴....... 𝖴 Rⁿ in X is called the Transitive closure of R in X.

Example-1: Let X={1,2,3,4} and R={(1,2),(2,3),(3,4)} be a relation on

X. Find R⁺

Sol: Given relation R={(1,2),(2,3),(3,4)}

Transitive closure of a relation R is defined by

R⁺ = R 𝖴 R² 𝖴 R³ 𝖴....... 𝖴 Rⁿ

1 2

4

3

R³ ={(1,4)}

R⁴ = ∅

[ by applying transitive closure of R and R²]

[ we have to stop the procedure when Rⁿ = ∅ ]

R⁺= R 𝖴 R² 𝖴 R³ 𝖴 R⁴

={(1,2),(2,3),(3,4)}𝖴{(1,3),(2,4)} 𝖴 {(1,4)} 𝖴 { ∅}

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

Therefore Transitive closure of R is R⁺={(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)}

4 3

​

if (1,2)∈ R and (2,3) ∈ R then (1,3) ∈ R

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

2

1

1

2

4 3

​

(2,3)∈ R and (3,4) ∈ R then (2,4) ∈ R

1

2

4

3

Example-2: Let X={1,2,3,4} and R={(1,1),(1,4),(2,3), (3,1),(3,4)} be a

relation on X. Find R⁺

Sol: Given relation R={(1,1),(1,4),(2,3), (3,1),(3,4)}