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

[Samuelb88]

Homework Statement

If A and B are finite, show the set of all functions f: A \rightarrow B is finite.

Homework Equations

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

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

The Attempt at a Solution

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

I'm not quite sure how to proceed from here. Thus far I considered proceeding by cases, that is, when n=m, n<m, and m<n. If I proceed by cases, I get stuck at the case of n=m because I can't figure out how to show there are finitely many functions that map [n] \rightarrow [m].

 

[micromass]

Hi Samuelb88!

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

\emptyset\rightarrow [m]

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

[n+1]\rightarrow [m]

The fact that this works is because every function f:[n+1]\rightarrow [m][/tex] restricts to a function f:[n]\rightarrow [m].

 

[gb7nash]

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

Let A = {x₁,x₂, ... , x_n} and B = {y₁,y₂, ... , x_m}

Step 1: Pick f(x₁)

m ways

Step 2: Pick f(x₂)

m ways

.
.
.

Step n: Pick f(x_n)

m ways.

By the multiplication property...

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

If you're not allowed to use combinatorics, I would go with Micromass's method.

 

[Samuelb88]

Alright, proceeding by induction on n. As my base case I cite that for n=0, there are no such functions g: \emptyset \rightarrow [m] \Rightarrow thus there are finitely many.

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

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

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

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 g \Rightarrow there are finitely many h. Thus there are finitely many g: [n+1] \rightarrow [m]. Done!

 

[Dick]

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.

 

[TylerH]

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.

 

[HallsofIvy]

It should be easy to show that if A has n members and B has m, then there are exactly m^n[/b] functions from A to B.