Results 1 to 2 of 2

Math Help - Proof regarding functions

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    123

    Proof regarding functions

    Prove by induction that if set A has n elements and set B has m elements, then there are m^n many functions from A to B.

    I see how this is intuitive, but can't figure out how to write a formal proof.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by h2osprey View Post
    Prove by induction that if set A has n elements and set B has m elements, then there are m^n many functions from A to B.

    I see how this is intuitive, but can't figure out how to write a formal proof.
    fix m and do the induction over n. if n = 1, then A has only one element and it can be mapped to any of m elements of B. so there are m functions in this case.

    now suppose the claim is true for n and let A be a set with n + 1 elements. so A = A' \cup \{x \}, where A' is a set with n elements. a map from A to B can send x to

    any element of B. so there are m possibilities for the image of x. also by induction hypothesis there are m^n ways to map A' to B. thus there are m \cdot m^n=m^{n+1}

    ways to map A to B.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A functions proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 12th 2010, 02:10 AM
  2. Proof regarding 1-1 functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2009, 03:54 PM
  3. Proof using functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2009, 12:25 PM
  4. functions proof (is it right?)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 10th 2009, 01:56 PM
  5. Functions Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 1st 2009, 05:42 PM

Search Tags


/mathhelpforum @mathhelpforum