1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook