Page 16 - DMTH403_ABSTRACT_ALGEBRA

Unit 1: Generating Sets

If we define g : A  B by g(1) = 1, g(2) = 1, g(3) = 4, then g is also a function. The domain of g Notes
remains the same, namely, A. But the range of g is {1, 4}.
Remark: We can also consider a function f : A  B to be the subset { (a, f(a)) | a  A } of A × B.
Now let us look at functions with special properties.
Definition: A function f : A  B is called One-one (or injective) if f associates different elements
of A with different elements of B, i.e., if a , a  A and al  a,, then f(a )  f(a ). In other words, f is
1
2
l
2
1-1 if f(a ) = f(a )  a = a .
2
1
2
1
In the examples given above, the function f is one-one. The function g is not one-one because 1
and 2 are distinct elements of A, but g(1) = g(2).
Now consider another example of sets and functions.
Let A = (1, 2, 3), B = { p, q, r }. Let f : A  B be defined by f(1) = q, f(2) = r, f(3) = p. Then f is a function.
Here the range of f = B = codomain of f. This is an example of an onto function, as you shall see.
Definition: A function f : A  B is called onto (or surjective) if the range of f is B, i.e., if, for each
b  B, there is an a  A such that f(a) = b. In other words, f is onto if f(A) = B.
For another important example of a surjective function, consider two non-empty sets A and B.
We define the function  : A × B  A :  ((a, b)) = a.  is called the projection of A × B onto A. You
l
1
1
can see that the range of  is the whole of A. Therefore,  is onto. Similarly,  : A × B  B :  ((a,
1
1
2

b)) = b, the projection of A × B onto B, is a surjective function.
If a function is both one-one and onto, it is called bijective, or a bijection.
Consider the following example that you will use again and again.
Example: Let A be any set. The function I : A  A : I (a) = a is called the identity function
A
A
on A. Show that I, is bijective.
Solution: For any a  A, I (a) = a. Thus, the range of I is the whole of A. That is, I is onto.
A
A
A
I is also 1-1 because if a , a  A such that a  a , then I (a )  I (a ).
A
A
2
2
1
A
1
2
1
Thus, I is bijective.
A
If f : A  B is a bijection, then we also say that the sets A and B are equivalent. Any set which is
equivalent to the set { 1, 2, 3 ,............, n}, for some n  N, is called a finite set. A set that is not finite
is called an infinite set.
Convention: The empty set  is assumed to be finite.
Let us now see what the inverse image of a function is.
Definition: Let A and B be two sets and f : A  B be a function, Then, for any subset S of B, the
inverse image of S under f is the set
f (S) = { a  A | f(a)  S }.
–1
For example, I (A) = { a  A | I (a)  A } = A.
1

A
A
f–1({ 1, 2, 3 }) = { n  N | f(n)  { 1 , 2 , 3 } }
= { n  N | n + 5  { 1,2,3 }}
= , the empty set.
We now give some nice theorems involving the inverse image of a function.

LOVELY PROFESSIONAL UNIVERSITY 9