Injective, surjective, inclusion and exclusion question

**breitling** · February 14th 2011, 03:17 AM

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,
write down the inverse function. (Justify your answers.)
(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.

**FernandoRevilla** · February 14th 2011, 03:53 AM

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

**imind** · February 14th 2011, 01:31 PM

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

**FernandoRevilla** · February 14th 2011, 09:25 PM

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

**breitling** · February 15th 2011, 02:30 AM

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)

**breitling** · May 12th 2011, 04:10 AM

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?

**emakarov** · May 12th 2011, 07:58 AM

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.

**emakarov** · May 12th 2011, 01:22 PM

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.

Thread: Injective, surjective, inclusion and exclusion question

LinkBack

Thread Tools

Display

Injective, surjective, inclusion and exclusion question

Similar Math Help Forum Discussions

Inclusion and exclusion question

inclusion & exclusion question help

inclusion-exclusion question

inclusion-exclusion principle question

inclusion/exclusion question

Search Tags