Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Show the set of all functions from A to B is finite

  1. Jul 2, 2011 #1
    1. The problem statement, all variables and given/known data
    If A and B are finite, show the set of all functions [itex]f: A \rightarrow B[/itex] is finite.


    2. Relevant equations
    Lemma. If A is finite such that [itex]|A|=n[/itex], then there is a bijective correspondence between A and [itex][n][/itex].

    *Notation. [itex][n] = \{ 1, ..., n \}[/itex]


    3. The attempt at a solution
    Let A, B be finite such that [itex]|A|=n[/itex] and [itex]|B|=m[/itex]. Then by my lemma, I can find bijective maps between both A and [itex][n][/itex], and B and [itex][m][/itex]. Thus in order to show that the set of all functions [itex]f: A \rightarrow B[/itex] is finite, it suffices to show that the set of all functions [itex]g: [n] \rightarrow [m][/itex] is finite.

    I'm not quite sure how to proceed from here. Thus far I considered proceeding by cases, that is, when [itex]n=m[/itex], [itex]n<m[/itex], and [itex]m<n[/itex]. If I proceed by cases, I get stuck at the case of [itex]n=m[/itex] because I can't figure out how to show there are finitely many functions that map [itex][n] \rightarrow [m][/itex].
     
  2. jcsd
  3. Jul 2, 2011 #2
    Hi Samuelb88! :smile:

    I think the easiest is to proceed by induction on n. So first show that there are finitely many functions

    [tex]\emptyset\rightarrow [m][/tex]

    and then show (using the induction hypothesis) that there are finitely many functions

    [tex][n+1]\rightarrow [m][/tex]

    The fact that this works is because every function [itex]f:[n+1]\rightarrow [m][/tex] restricts to a function [itex]f:[n]\rightarrow [m][/itex].
     
  4. Jul 2, 2011 #3

    gb7nash

    User Avatar
    Homework Helper

    Hm, perhaps I'm looking at this from a different angle, but I think the easiest way is the following:

    Let A = {x1,x2, ... , xn} and B = {y1,y2, ... , xm}

    Step 1: Pick f(x1)

    m ways

    Step 2: Pick f(x2)

    m ways

    .
    .
    .

    Step n: Pick f(xn)

    m ways.

    By the multiplication property...

    -------------

    If you're not allowed to use combinatorics, I would go with Micromass's method.
     
  5. Jul 2, 2011 #4
    Alright, proceeding by induction on [itex]n[/itex]. As my base case I cite that for [itex]n=0[/itex], there are no such functions [itex]g: \emptyset \rightarrow [m][/itex] [itex]\Rightarrow[/itex] thus there are finitely many.

    *This part I'm a little confused on since either there are [itex]m[/itex] functions (constant functions) such that [itex]g: \emptyset \rightarrow [m][/itex] or there are zero. I believe there zero since there are no elements in the domain of the function [itex]\Rightarrow[/itex] there cannot be any images in the codomain.

    As my inductive hypothesis, I suppose that there are finitely many functions [itex]g: [n] \rightarrow [m][/itex]. I want to show there are finitely many functions [itex]g: [n+1] \rightarrow [m][/itex]. By our inductive hypothesis, we know there are finitely many functions from [itex][n] \rightarrow [m][/itex]. Thus let [itex]j \in [n+1][/itex] and define [itex]h: [n+1] \rightarrow [m][/itex] as follows:

    [tex]h(j) = \begin{cases}
    g(j) & \text{if j not equal to n+1} \\
    i & \text{where i in [m], if i = n+1}
    \end{cases}[/tex]

    Edit: Just realized I didn't quite finish my proof here, although I finished it in my head. :)

    At any rate, since there are finitely many [itex]g[/itex] [itex]\Rightarrow[/itex] there are finitely many [itex]h[/itex]. Thus there are finitely many [itex]g: [n+1] \rightarrow [m][/itex]. Done!
     
    Last edited: Jul 2, 2011
  6. Jul 2, 2011 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't see why you need induction. As gb7nash pointed out, you can count the functions just by multiplying choices. Why complicate that? And I wouldn't even count that as 'using combinatorics'. It's just multiplying.
     
    Last edited: Jul 2, 2011
  7. Jul 3, 2011 #6
    You could use the definition of a function (or mapping), which is: A map from A to B is a subset of A x B, where x denotes the cross product. The definition implies that the set of all maps from A to B is the set of all subsets (ie the powerset) of A x B. Then you prove the powerset of A x B is finite.
     
  8. Jul 3, 2011 #7

    HallsofIvy

    User Avatar
    Science Advisor

    It should be easy to show that if A has n members and B has m, then there are exactly [itex]m^n[/b] functions from A to B.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook