Results 1 to 2 of 2

Thread: Proof by induction: For finite sets A, B w/ cardinality n, m >= 1, show there are...

  1. #1
    New Member
    Join Date
    Oct 2017
    Posts
    8

    Question Proof by induction: For finite sets A, B w/ cardinality n, m >= 1, show there are...

    Let A and B be finite sets of cardinality n and m respectively, where n and m are positive natural numbers.

    Show, using induction on n, that there are mn functions from A to B.




    Would i be ok to use base step as n = 1? for a function A -> B for one in A

    A (x) mapping to B (a1,a2,a3.... am)

    The number of functions possible for n-1 is m^n

    I don't know how to go on with the induction step. Any ideas?
    Last edited by stapel; 12-01-2017 at 01:57 PM. Reason: Typing out the text in the graphic; creating useful subject line.

  2. #2
    New Member
    Join Date
    Nov 2017
    Location
    Brussels, Belgium
    Posts
    15
    Quote Originally Posted by sita View Post
    Let A and B be finite sets of cardinality n and m respectively, where n and m are positive natural numbers.

    Show, using induction on n, that there are mn functions from A to B.




    Would i be ok to use base step as n = 1? for a function A -> B for one in A

    A (x) mapping to B (a1,a2,a3.... am)

    The number of functions possible for n-1 is m^n

    I don't know how to go on with the induction step. Any ideas?
    Hi sita,

    A couple of remarks about you thoughts:
    • Yes, it is OK to take [tex]n = 1[/tex] as the base case. The base case should be the smallest possible case covered by the hypothesis. In this case, the hypothesis says that [tex]n > 0[/tex].
    • Concerning the induction step, if [tex]A[/tex] contains [tex]n-1[/tex] elements, the number of functions would be [tex]m^{n-1}[/tex] by the induction hypothesis, not [tex]m^n[/tex] as you wrote.


    This being said, the idea would be to assume that [tex]A[/tex] contains n elements, and to write [tex]A = A'\cup\{a_n\}[/tex], where [tex]A'[/tex] contains [tex]n-1[/tex] elements.

    To define a function [tex]f : A\to B[/tex], you must define [tex]f(x)[/tex] for all [tex]x\in A'[/tex], and for [tex]x = a_n[/tex] (i. e., you must define [tex]f(a_n)[/tex]).

    This means that a function [tex]f : A\to B[/tex] is defined by:

    • a function [tex]f': A'\to B[/tex], and the induction hypothesis tells you how many such functions exist.
    • for each such function, the image [tex]f(a_n)\in B[/tex], and there are [tex]m[/tex] possible choices for this.


    Can you put the pieces together ?
    Last edited by stapel; 12-01-2017 at 01:57 PM. Reason: Copying typed-out graphical content into reply.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •