Results 1 to 4 of 4

Math Help - Equivalence Relations and Functions

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Equivalence Relations and Functions

    Need help on the following problem:
    Let A={1,2,3,4,5,6}. In each case, give an example of a function f:A->A with the indicated properties, or explain why no such function exists.
    a) f is bijective, but not 1A.
    b) f is one-to-one, but not onto

    Now set A=N (natural numbers)
    a) f is bijective, but not 1A.
    b) f is one-to-one, but not onto
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kturf View Post
    Need help on the following problem:
    Let A={1,2,3,4,5,6}. In each case, give an example of a function f:A->A with the indicated properties, or explain why no such function exists.
    a) f is bijective, but not 1A.
    b) f is one-to-one, but not onto

    Now set A=N (natural numbers)
    a) f is bijective, but not 1A.
    b) f is one-to-one, but not onto
    What is 1A?

    For the first one b) it is impossible

    Theorem: If f:A\mapsto A is injective and A is finite then it is surjective.

    Proof: By definition \left|\text{Im }f\right|\le\left|\text{CoDom }f\right| where \text{Im} is the image and \text{CoDom} is the codomain. But for the case of injective functions \left|\text{Im }f\right|=\left|\text{Dom }f\right|, which implies then that \left|\text{Dom }f\right|\le\left|\text{CoDom }f\right|. In our case we have that \left|\text{Dom }f\right|=\left|A\right|. Now suppose that f was not surjective, then \left|A\right|<\left|\text{CoDom }f\right|=\left|A\right| which is a contradiction.


    For the second one b) what about f(n)=n+1?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    The notation should be 1_A, the identity mapping of A.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kturf View Post
    Need help on the following problem:
    Let A={1,2,3,4,5,6}. In each case, give an example of a function f:A->A with the indicated properties, or explain why no such function exists.
    a) f is bijective, but not 1A.
    b) f is one-to-one, but not onto

    Now set A=N (natural numbers)
    a) f is bijective, but not 1A.
    b) f is one-to-one, but not onto
    a) Uhh....yeah? You tell me why.

    a) Samesies

    Quote Originally Posted by Shanks View Post
    The notation should be 1_A, the identity mapping of A.
    Good eye! I usually see it as i_A or \iota_A
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. equivalence relations and functions
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 25th 2010, 01:31 AM
  3. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  4. equivalence relations
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: January 12th 2010, 07:17 PM
  5. Equivalence Relations and Functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 18th 2009, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum