Relations and Functions

The set theory helps us understand how a collection of like objects behave. Venn diagrams are useful when you have different sets of the same type. However, to work with sets of different kinds, you need to know the concept of relations and functions.

Suppose your are given two sets, A and B such that

A = {a,b,d,k, j,v} and
B = {Anu, Ben, Don, Kaushik, Sonia}

We can define another set R such that

R = {(x,y) : x is the first letter in the word y; x ∈ A and y ∈ B}
= {(a,Anu), (b,Ben), (d,Don), (k,Kaushik)}

Arrow Diagram representation of relation R

Every member of R is an ordered pair such that the first element x is from set A and second element y is from set B. However,not every element of A or B is included.

y is called the image of x.

The set R here, is an example of a relation.
Formally,

Relation R on A and B is a subset of A x B,

where A x B is the Cartesian product of sets A and B. 

Cartesian Product of Sets

The cartesian product A x B is the set of ordered pairs (a,b) such that a is an element of A and b is an element of B. In the given example, the Cartesian product A x B will be

A x B = {(a, Anu), (a, Ben), (a, Don), (a, Kaushik), (a, Sonia), (b, Anu), (b, Ben), (b, Don), (b, Kaushik),               (b, Sonia), (d, Anu), (d, Ben), (d, Don), (d, Kaushik), (d, Sonia), (k, Anu), (k, Ben), (k, Don), (k,                Kaushik), (k, Sonia), (j, Anu), (j, Ben), (j, Don), (j, Kaushik), (j, Sonia), (v, Anu), (v, Ben), (v,                    Don), (v, Kaushik), (v, Sonia)}
n(A x B) = n(A) x n(B)
= a x b = 6 x 5 = 30

R ⊆ A x B

We know that the number of subsets of a set containing n elements = 2^n
Since R ⊆ A x B,
hence the total number of relations that can be defined on A and B = 2^ab

Some useful properties involving Cartesian product:

A x (B∩C)  = (A x B) ∩ (A x C)
A x (B∪C)  = (A x B) ∪ (A x C)

Domain and Range

For any relation R defined on A and B, we can define the domain and range as:

Domain of R is the set of all first elements, {x} of the ordered pairs (x,y).

In the above example, domain of R = {a,b,d,k}

Range of R is the set of all second elements, {y} of the ordered pairs (x,y).

In the above example, range of R = {Anu, Ben, Don, Kaushik}

The set B, is called the codomain of R.
In the above example, codomain of R = {Anu, Ben, Don, Kaushik, Sonia}

Clearly,

Range ⊆ Codomain

That is it for today. 

Part 2: Venn Diagrams and operations on Sets

For introduction to set theory, see part 1 here

To continue our discussion, let’s study Venn diagrams. These are very helpful way to visualize set operations.
Let’s start with an example:

Let there be two sets A and B such that

A = {x:x is a perfect square and x ≤ 25} = {1, 4,9,16,25}
B = {y: y is an even number and y < 25} = {2,4,6,8,…,24}

We can depict this data in the form of a Venn Diagram as follows:

Sets are represented as circles and members are written inside of their set. Members which are common to both sets are written at the common area between the circles.
Note that the universal set U is denoted by the rectangle (here can be taken as the set of all numbers from 1 to 25).

Set operations: Union

Union of two given sets, A and B, is defined as the set which contains members of either A or B or both. It is denoted as A ∪ B.
Taking the above example,
A ∪ B = {1, 2, 4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 25}

Set operations: Intersection

Intersection of two given sets, A and B, is defined as the set which contains members which are common to both A and B. It is denoted as A ∩ B.
Taking the above example,
A ∩ B = {4, 9, 25}

Set operations: Difference

Difference of two given sets, A and B, is defined as the set which contains members which belong to A, but not to B. It is denoted as A–B.
Again, taking the above example,
A–B = {1, 9, 25}

Set operations: Complement

Complement of a given set A, is denoted by A′ and is defined as the set which contains members which belong to U, but not to A.
It can be easily verified that, A′= U–A.
Again, taking the above example,
A′= U–A = {2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24}

A very useful relation in set theory is

n(A∪B)  =   n(A) + n(B) – n(A∩B)
i.e., total no.of elements in A and B = no. of elements in A + no. of elements in B – no. of elements in both A and B

(because when we count no. of elements in A+no. of elements in B, we counted common elements twice, hence we subtract them once from total)

There are a couple of useful properties, known as the De Morgan’s laws:

That is it for set theory.

Part 1: The Set Theory (basics)

Sets

Our solar system has 8 planets: Mercury, Venus, Earth, Mars, Jupiter, Saturn, Neptune and Uranus. They all have one feature in common: they  are relatively big round objects that revolve around the Sun. We all have agreed upon this identification and no other object can be said to be a planet of our solar system (sorry Pluto).

Such a collection of well-defined objects is called a set. Note that the members (or elements) of a set have at least one common property that is not shared by anything that is not included in that set.

Sets are denoted by capital letters and the elements are listed inside curly braces as shown in the following examples:

The empty set

A set which contains no element. Denoted by Φ or {}.

e.g.
A = {x: x is a natural number such that 3<x<4}
since no such number exists, A is an empty set.

Finite and infinite sets

A set with countable elements is called a finite set.
A set with infinite number of elements is called an infinite set.

e.g.
The set of vowels, V = {a,e,i,o,u} is a finite set.
The set of natural numbers, N = {1,2,3…} is an infinite set.

Equality of sets

Two sets are said to be equal if and only if they have exactly the same elements.
e.g.
A = {1,2,3} and
B = {3,3,2,1}
are equal because the elements of both are the same.

Note that it doesn’t matter if the elements are repeated or written in a different sequence.

Hence,
A = {x : x is a letter in the word “ALLOY”} and
B = {y: y is a letter in the word “LOYAL”}

are equal and we can write
A = B = {A,L,O,Y} = {L,O,A,Y} etc.

Subset

Consider two sets A and B such that

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

We see that every element of B is also an element of A. But not every element of A is that of B (for example, 3 belongs to A but not B).

We say that B is a subset of A and A is the superset of B.
Note that every set is a subset of itself. Also, Φ is a subset of every set.

Power set

The collection of all subsets of a set A is called the power set of A. It is denoted by P(A).

e.g. if A = {a,s,d}
then P(A) = {{a},{s},{d},{a,s},{s,d},{a,d},{a,s,d},Φ}.

Universal set

Consider the set of real numbers, R. Every rational or irrational number belongs to the set R. Every integer belongs to R. Calculations in mathematics all deal with numbers that lie within the domain of real numbers (excluding complex analysis, we shall deal with that later). Hence, we get the ‘sense’ that the set of real numbers, R, is a superset of all the sets involving numbers. For our context, the set R is then called the ‘Universal set’.
Another example is the set of countries, if we want to know which of them are members of the UN, we can consider the set of all countries of the world as the universal set.

 

A universal set is one of the supersets of all the sets in a given context (denoted by U). It is usually specified according to the problem at hand.

That is it for today.

For details, see my notes on set theory: set theory-definitions.