, Discussion of assignment 03 semester 1.
Suppose U = {1, 2, 3, 4, 5, a, b, c} is a universal set with the subset A = {a, b, c, 1, 2, 3, 4}.
Answer questions 1 and 2 by using the given sets U and A.
Question 1
Which one of the following relations on A is NOT functional?
1. {(1, 3), (b, 3), (1, 4), (b, 2), (c, 2)}
2. {(a, c), (b, c), (c, b), (1, 3), (2, 3), (3, a)}
3. {(a, a), (c, c), (2, 2), (3, 3), (4, 4)}
4. {(a, c), (b, c), (1, 3), (3, 3)}
Answer: Alternative 1
Discussion
First we look at the definition of functionality:
Suppose R B × C is a binary relation from a set B to a set C. We may call R functional if the
elements of B that appear as first co-ordinates of ordered pairs in R do not appear in more than
one ordered pair of R.
We consider the relations provided in the different alternatives:
2
, 1. Let L = {(1, 3), (b, 3), (1, 4), (b, 2), (c, 2)} (say). L is not functional since the
elements 1 and b appear more than once as first co-ordinates in ordered pairs of L.
2. Let M = {(a, c), (b, c), (c, b), (1, 3), (2, 3), (3, a)} (say).
M is a relation on A = {a, b, c, 1, 2, 3, 4}: {a, b, c, 1, 2, 3} = dom(M) A and
ran(M) = {a, b, c, 3} A. Each first co-ordinate appears only once as first co-ordinate thus M is
functional.
3. Let N = {(a, a), (c, c), (2, 2), (3, 3), (4, 4)} (say).
N is a relation on A = {a, b, c, 1, 2, 3, 4}: {a, c, 2, 3, 4} = dom(N) A and
ran(N) = {a, c, 2, 3, 4} A. Each first co-ordinate appears only once as first co-ordinate thus N
is functional.
4. Let S = {(a, c), (b, c), (1, 3), (3, 3)} (say).
S is a relation on A = {a, b, c, 1, 2, 3, 4}: {a, b, 1, 3} = dom(S) A and
ran(S) = {c, 3} A. Each first co-ordinate appears only once as first co-ordinate thus S is
functional.
From the arguments provided we can deduce that alternative 1 should be selected.
Refer to study guide, p 98.
Question 2
Which one of the following alternatives represents a surjective function from U to A?
1. {(1, 4), (2, b), (3, 3), (4, 3), (5, a), (a, c), (b, 1), (c, b)}
2. {(a, 1), (b, 2), (c, a), (1, 4), (2, b), (3, 3), (4, c)}
3. {(1, a), (2, c), (3, b), (4, 1), (a, c), (b, 2), (c, 3)}
4. {(1, a), (2, b), (3, 4), (4, 3), (5, c), (a, a), (b, 1), (c, 2)}
Answer: Alternative 4
Discussion
We look at the definitions of a function and of surjectivity:
Suppose R B × C is a binary relation from a set B to a set C. We may call R a function from B
to C if every element of B appears exactly once as the first co-ordinate of an ordered pair in R
(i.e. f is functional), and the domain of R is exactly the set B, ie dom(R) = B. A function R from
B to C is surjective iff ran(R) = C.
We have U = {1, 2, 3, 4, 5, a, b, c} and A = {a, b, c, 1, 2, 3, 4}.
We consider the relations provided in the different alternatives:
3