# Thread: Injective, surjective, inclusion and exclusion question

1. ## Injective, surjective, inclusion and exclusion question

Hi i have the following question from an old exam paper im stuck on, its a three part question and goes as follows:

(b) Which of the following functions are surjective, injective or bijective? If it is bijective,
(i)
f : Z12 Z12 : f([a]12) = [a]12 · [5]12;
(ii)
f : Z12 Z12 : f([a]12) = [a]12 · [3]12.
[ 10 marks ]

(c) Let
A be the set of 3-digit decimal integers {000, 001, 002, . . . , 999}. Use the Inclusion-
Exclusion Principle to find how many elements of
A are not divisible by 2, nor by 3, nor by
5. (It may be useful to denote by
A2 the set of 3-digit decimal integers that are divisible by

2.)

The first question i have tried to find examples of this in text books but with no luck, i realsie that a one-one function is injective and is described as a function for which different inputs give different outputs, i am fine in the case of f: N->N where f(x)=x^2 but the format in which the question is shown above i havent got a clue

For the inclusion and exclusion i am aware it will be something to do with the AuBuC equation mate letting a= not divisible by 2, b= not divisible by 2 etc then to find the relevant A and B etc to plug into the equation?

Any help would be most appreciated, thanks in advance.

2. Originally Posted by breitling
f : z12 z12 : f([a]12) = [a]12 · [5]12;

We have

$f([x])=f([x'])\Rightarrow [5][x]=[5][x']$

As $[5][5]=[1]$ , multiplying both sides by $[5]$ we deduce $[x]=[x']$ and $f$ is injective. On the other hand, $f([x])=5[x]=[y]$ implies $[x]=5[y]$, so $f$ is also surjective and $f^{-1}=f$ .

f : z12 z12 : f([a]12) = [a]12 · [3]12.

Now, is different because there is no $[a]\in\mathbb{Z}_{12}$ such that $[a][3]=[1]$ . Try yourself.

Fernando Revilla

3. Originally Posted by FernandoRevilla
We have

$f([x])=f([x'])\Rightarrow [5][x]=[5][x']$

As $[5][5]=[1]$ , multiplying both sides by $[5]$ we deduce $[x]=[x']$ and $f$ is injective. On the other hand, $f([x])=5[x]=[y]$ implies $[x]=5[y]$, so $f$ is also surjective and $f^{-1}=f$ .

Now, is different because there is no $[a]\in\mathbb{Z}_{12}$ such that $[a][3]=[1]$ . Try yourself.

I had a side question that follows this topic ... is what you wrote due to multiplicative inverses and zero divisors?

Thanks

4. Originally Posted by imind
I had a side question that follows this topic ... is what you wrote due to multiplicative inverses and zero divisors?
Right.

Fernando Revilla

5. Originally Posted by FernandoRevilla
We have

$f([x])=f([x'])\Rightarrow [5][x]=[5][x']$

As $[5][5]=[1]$ , multiplying both sides by $[5]$ we deduce $[x]=[x']$ and $f$ is injective. On the other hand, $f([x])=5[x]=[y]$ implies $[x]=5[y]$, so $f$ is also surjective and $f^{-1}=f$ .

Now, is different because there is no $[a]\in\mathbb{Z}_{12}$ such that $[a][3]=[1]$ . Try yourself.

Fernando Revilla
Oh i understand yes, many thanks so the inverse is [5]... we havent gone over anything along these lines so a bit like a duck out of wahter, for part two would you use [4] since you cant find the [a] that gives [1] instead do [4] that gives [0] again i aplogise as i havent seen a question like this before.

For the second question i went back over it again and found the p(divible by 2), p(divisible by 3), p(divisible by 5) to obtain the inclusion exclusion forumula:
p(aubuc)= 1/2+1/3+1/5-1/6-1/10-1/15+1/30=11/15
Then 1-p(aubuc) to get p(not divisble by 2 or 3 or 5)

6. Originally Posted by FernandoRevilla
We have

$f([x])=f([x'])\Rightarrow [5][x]=[5][x']$

As $[5][5]=[1]$ , multiplying both sides by $[5]$ we deduce $[x]=[x']$ and $f$ is injective. On the other hand, $f([x])=5[x]=[y]$ implies $[x]=5[y]$, so $f$ is also surjective and $f^{-1}=f$ .

Now, is different because there is no $[a]\in\mathbb{Z}_{12}$ such that $[a][3]=[1]$ . Try yourself.

Fernando Revilla
I have managed the injective part of the second question, since f(a)=f(b)--> a=b then f([a]12) = [a]12 · [3]12 is not injective since we can let a=0 and a=4 so every element in the domain doesn't give a distinct image? However im struggling to show where it is surjective or not, i have to show for all values in the range there exist a value in the codomain?

7. However im struggling to show where it is surjective or not, i have to show for all values in the range there exist a value in the codomain?
A function from a finite set to itself (or to another set with the same number of elements) is an injection iff it is a surjection. You an multiply each number 0, ..., 11 by 3 and see which numbers are not produced.

8. Originally Posted by breitling
For the second question i went back over it again and found the p(divible by 2), p(divisible by 3), p(divisible by 5) to obtain the inclusion exclusion forumula:
p(aubuc)= 1/2+1/3+1/5-1/6-1/10-1/15+1/30=11/15
Then 1-p(aubuc) to get p(not divisble by 2 or 3 or 5)
The original problem asks not about the fraction of elements, but about the exact number of elements. One has to be careful: for example, the number of elements divisible by 3 is 334. In general, I believe, the number of elements divisible by n is $\lceil1000/n\rceil$. My answer to question 2 is 266.