Results 1 to 8 of 8

Math Help - Injective, surjective, inclusion and exclusion question

  1. #1
    Junior Member
    Joined
    Jan 2011
    Posts
    58

    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,
    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.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    Quote Originally Posted by breitling View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    16
    Quote Originally Posted by FernandoRevilla View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    Quote Originally Posted by imind View Post
    I had a side question that follows this topic ... is what you wrote due to multiplicative inverses and zero divisors?
    Right.


    Fernando Revilla
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2011
    Posts
    58
    Quote Originally Posted by FernandoRevilla View Post
    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)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jan 2011
    Posts
    58
    Quote Originally Posted by FernandoRevilla View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Quote Originally Posted by breitling View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion and exclusion question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 19th 2011, 05:00 AM
  2. inclusion & exclusion question help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 17th 2010, 08:49 AM
  3. inclusion-exclusion question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 17th 2010, 12:44 AM
  4. inclusion-exclusion principle question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 8th 2010, 07:39 AM
  5. inclusion/exclusion question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 3rd 2009, 08:31 PM

Search Tags


/mathhelpforum @mathhelpforum