Question

549 Determine which of the following are fiunctions with the given domains X and codomains Y. For those that are fiunctions, determine which are injective, surjective, or bijective. (e) X = Y = N and f I(m,)ENx NIm has exactly n distinct prime factors ) For exanple, (80, 3) Efbecause 80 24.5 has two distinct prime fâctors. (f) Y= {1,2,3,4} ,X=P(Y) , and f-((x,y E X x Y the smallest element of x is y) Forexampk.2,4), I)Ef

Answer 1

We are given 2 relations, and we need to find which of them are functions.

The condition for a relation to be a function is that one element in the domain cannot be related to more than one element in the codomain, i.e, we cannot have both the ordered pairs  , where $y_1 \neq y_2$ . If this property is satisfied, we say the function is well defined.

For a function f to be injective, we require that if f(x) = f(y), then x = y. Or, if we have both $(x, z) \textnormal{ and } ( y, z)$ in f, then x=y.

For a function f to be surjective, we require that every element in the codomain has a preimage.

Now, we look at the given relations:

(e) This relation is a surjective function.

Here the domain and range are both the set of all natural numbers. If m is a natural number, then it has a unique prime factorization. Hence, for m, the number of distinct prime factors is unique. If we call this number n, then n is unique. By the definition of this relation, m maps to n+1 and only to n+1. Therefore, this relation is a function.

We check for injectivity: Using the example in the question $(80, 3) \in f$ . But then $20 = 4 \times 5 = 2^2. 5$ . So, we also have $(20, 3) \in f$ . But $20 \neq 80$ , and by the above definition, f is not injective. Therefore f is not bijective either.

It remains to show that f is surjective.

Consider the natural number 1 in the codomain. If 1 has a pre image, then it is the natural number m with 1-1 = 0 prime factors. This is satisfied by the number 1 in the domain. As 1 is neither prime nor composite, it has 0 prime factors.

For any n in the codomain such that n > 1, we can take n-1 distinct prime numbers $p_1, p_2, \ldots, p_{n-1}$ and find their product $m = p_1 \cdot p_2\cdot \ldots \cdot p_{n-1}$ .   Then $\left ( m, n \right ) \in f$ . Since there are infinitely many primes, we can do this for all natural numbers, irrespective of how large they are. Hence f is surjective.

(f) This relation is also a surjective function.

In this case, the domain X is the power set of Y = {1,2,3,4} ( set of all subsets of Y) and the codomain is Y = {1,2,3,4}.

Again, f is well defined.

Any element of X has to be a finite set which is a subset of Y. We do not consider the case of the empty set: since it has no elements of Y, we cannot talk about its minimum element.

For any other element of X, there can only be one corresponding element of Y. Hence, f is a function.

This function f is not injective. If we let $x = \left \{ 1,2 \right \}, y =\left \{ 1,2,3 \right \}$ , then we have $(x, 1), (y, 1) \in f$ . So, f is also not bijective.

However, f is surjective. For each element in Y, we have at least 1 pre image. For eg

$\left ( \left \{ 1,2 \right \}, 1 \right ), \left ( \left \{ 2,3 \right \}, 2 \right ), \left ( \left \{ 3,4 \right \}, 3 \right ), \left ( \left \{ 4 \right \}, 4 \right )$ are all in f.