Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Functions » Relations

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Relations

Module by: Sunil Kumar Singh. E-mail the author

We encounter different types of relationship in our daily life. Besides human relationship that we are so familiar with, there are numerous other relationships, including those which are purely abstraction of processes and ideas.

In essence, any two elements which are paired have potential to possess relationship between them. Now think of the Cartesian product that we have defined for two sets. It consists of ordered pairs of elements - one each from the two sets. The total numbers of ordered pairs in a Cartesian product is equal to the product of numbers of elements in each set. A particular relation, however, may not comprise all ordered pairs.

In this module, we shall limit our discussion to binary relations only. A binary relation is a relation as defined between two elements either from the same set of from two different sets.

Consider a “get together”. Divide the people in two groups comprising of males and females. A certain numbers of ordered pairs will qualify for a relation say “classmate of” – not all. Similarly, a relation such as “brother of” may include some of the ordered pairs of the Cartesian product of two set.

M = { A , B , C , D , E } M = { A , B , C , D , E }

F = { G , H , I , J , K } F = { G , H , I , J , K }

We can represent the relationship of “classmate of” as shown here :

Figure 1: Relation between elements of two sets
Relation
 Relation  (r1.gif)

From the figure, we can write the collection of relationship “classmate of” as a set of ordered pairs of two sets,

R classmate of = { A , G , A , K , D , G , D , I } R classmate of = { A , G , A , K , D , G , D , I }

In the nutshell, we can think of relation as a collection (set), which comprises of ordered pairs (instances of relation). Note that it is a specific relation. This is a relation between elements of two sets. Clearly, this relation set can not exceed the Cartesian product of two sets under consideration. Thus, a relation set is a subset of Cartesian product set.

Definition 1: Relation
A relation “R” from a non-empty set “A” to non-empty set “B” is a subset of Cartesian product “AXB”.

We need to note that a relation is defined in a particular order “from” to “to”. It is for this reason, we denoted relation pictorially by an arrow which is directed from the elements of "from" set “A” to "to" set “B”.

Consider few examples,

R = { x , y : x = y 2 , x A , y B } R = { x , y : x = y 2 , x A , y B }

R = { x , y : x = y + 1, x A , y B } R = { x , y : x = y + 1, x A , y B }

In certain circumstance, we are required to work with relation among the elements of the same set. For example, consider the male set defined earlier. Some of the male members may as well be classmates and hence related to each other. Such relation is relation on one set only and is called "relation on A" or "relation on B" etc. Few examples are :

R = { x , y : x = x + 1, x A } R = { x , y : x = x + 1, x A }

R = { x , y : y = x + 1 a n d x , y A } R = { x , y : y = x + 1 a n d x , y A }

Example

Problem 1 : Let A = { 1,2, . . , 10 } A = { 1,2, . . , 10 } . Write down the relation set in roaster form, which is defined as :

R = { x , y : y = 3 x a n d x , y A } R = { x , y : y = 3 x a n d x , y A }

Solution : We begin with the first element of “A” i.e. x =1. Since other element also belongs to set “A”, it is required that the value of “y” be one of the elements in the set "A".

F o r x = 1, y = 3 X 1 = 3 F o r x = 1, y = 3 X 1 = 3

F o r x = 2, y = 3 x = 3 X 2 = 6 F o r x = 2, y = 3 x = 3 X 2 = 6

F o r x = 3, y = 3 x = 3 X 3 = 9 F o r x = 3, y = 3 x = 3 X 3 = 9

Thus, “x” can assume values “1”,”2” and “3” for which “y” can assume values “3”,”6” and “9” respectively in accordance with the given relation. The relation, therefore, is set of ordered pairs :

R = { 1,3 , 2,6 , 3,9 } R = { 1,3 , 2,6 , 3,9 }

We can visualize the relation pictorially as shown in the figure.

Figure 2: Relation between elements of the same set
Relation on self
 Relation on self  (r2a.gif)

Domain of the relation

The domain represents the valid values of the first element of the ordered pairs in the relation. Clearly, the elements of domain of a relation belong to “from” set “A”. But, elements in the domain are only those which are valid for the relation. It means that domain does not consist of all elements of “from” set “A”. Thus, domain set is a subset of “from” set “A”.

Definition 2: Domain
The set of first elements of all ordered pairs in the relation “R” from set “A” to “B” is called the domain of relation “R”.

We can write the domain set of relation “R” from set “A” to set “B” in set builder form as :

Domain R = { x : x , y R } Domain R = { x : x , y R }

Consider the example given earlier. The relation set is :

R = { 1,3 , 2,6 , 3,9 } R = { 1,3 , 2,6 , 3,9 }

The domain according to definition is :

Domain R = { 1,2,3 } Domain R = { 1,2,3 }

Domain R A Domain R A

Co-domain

In a relation “R” from set “A” to “B”, the set “B” is called co-domain.

Range of the relation

The range represents the valid values of the second element of the ordered pairs in the relation.

Definition 3: Range
The set of second elements of all ordered pairs in the relation “R” from set “A” to “B” is called the range of relation “R”.

We can write the range set of relation “R” from set “A” to set “B” in set builder form as :

Range R = { y : x , y R } Range R = { y : x , y R }

Consider the example given earlier. The relation set is :

R = { 1,3 , 2,6 , 3,9 } R = { 1,3 , 2,6 , 3,9 }

The range according to definition is :

Range R = { 3,6,9 } Range R = { 3,6,9 }

Clearly, the elements of range of a relation belong to “to” set “B”. But, elements in the range are only those which are valid for the relation. It means that range does not consist of all elements of “to” set “B”. Thus, range set is a subset of “to” set “B”.

Range R B Range R B

Example

Problem 2 : Let A = { 1,2,3,4,5 } A = { 1,2,3,4,5 } and B = { 1,4,5 } B = { 1,4,5 } . Let a relation from “A” to “B” is :

R = { x , y : x < y , x , y A X B } R = { x , y : x < y , x , y A X B }

Find R, Domain (R) and Range(R).

Solution : Let us find “y” for each value of “x”.

For x = 1, y = 4,5 For x = 1, y = 4,5

F o r x = 2, y = 4,5 F o r x = 2, y = 4,5

F o r x = 3, y = 4,5 F o r x = 3, y = 4,5

F o r x = 4, y = 5 F o r x = 4, y = 5

F o r x = 5, There is no value of “y” in set “B” F o r x = 5, There is no value of “y” in set “B”

Hence,

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

Domain R = { 1,2,3,4 } Domain R = { 1,2,3,4 }

Range R = { 4,5 } Range R = { 4,5 }

Numbers of relations

Between two sets, the Cartesian product set consists of all possible instances of relation as ordered pair. Here, we need to find the total possible relations that can be generated from these ordered pairs. We have seen that total numbers of ordered pairs in the Cartesian product of sets “A” and “B” is “pq”, where “p” and “q” are the numbers of elements in two sets respectively.

Now, relation is nothing but a subset of the Cartesian product. It means that total numbers of relation is equal to total numbers of possible subsets of the Cartesian product. Recall that the set formed from all possible subsets is called power set. The numbers of subsets in the power set is given by

n = 2 p q n = 2 p q

Clearly, this number “n” denotes all possible relations (subsets) that can be generated from two finite sets. We should, however, be careful in interpreting this number as it also contains the mandatory empty set, which is not a meaningful set from the point of view of relation.

Inverse relation

Inverse relation of a given relation “R” from set “A” to set “B” is set of ordered pairs in which first and second elements exchanges their positions. The inverse set is defined in reference to a given relation. The inverse relation of a given relation “R” from “A” to “B” is denoted as “ R - 1 R - 1 ”. Clearly,

R - 1 = { y , x : x , y R } R - 1 = { y , x : x , y R }

where,

R = { x , y : x , y A X B } R = { x , y : x , y A X B }

We should be careful to understand that “-1” is not a power, but a part of symbol to represent inverse relation with respect to a given relation. It is also clear that :

I f x , y R y , x R - 1 . I f x , y R y , x R - 1 .

As the elements in the ordered pair of the relation exchanges positions, domain and range sets are exchanged across the sets.

Domain R - 1 = Range R Domain R - 1 = Range R

Range R - 1 = Domain R Range R - 1 = Domain R

Example

Problem 3 : Let A = { 1,2, . . , 10 } A = { 1,2, . . , 10 } . A relation on “A” is defined as

R = { x , y : y = 3 x , w h e r e x , y A } R = { x , y : y = 3 x , w h e r e x , y A }

Find R - 1 R - 1 , Domain ( R - 1 R - 1 ) and Range ( R - 1 R - 1 ).

Solution : In the earlier example, we determined the relation “R” as :

R = { 1,3 , 2,6 , 3,9 } R = { 1,3 , 2,6 , 3,9 }

According to the definition of inverse set, the elements of the ordered pair in the relation set are exchanged :

R - 1 = { 3,1 , 6,2 , 9,3 } R - 1 = { 3,1 , 6,2 , 9,3 }

Clearly, inverse relation can be represented in set builder form as :

R - 1 = { y , x : y = x / 3, w h e r e x , y A } R - 1 = { y , x : y = x / 3, w h e r e x , y A }

Now, the domain and range of R - 1 R - 1 are :

D o m a i n R - 1 = { 3,6,2 } D o m a i n R - 1 = { 3,6,2 }

Range R - 1 = 1,2,3 Range R - 1 = 1,2,3

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks