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

• Samuelb88
In summary, "Show the set of all functions from A to B is finite" means to prove that there is a finite number of functions that can map elements from set A to set B. To prove this, one can use a proof by contradiction method. Proving that the set of all functions from A to B is finite is important for understanding the relationship between the two sets and for efficient calculations and predictions. It is possible for the set to be infinite, but there are real-world examples, such as the set of all possible combinations of a lock, where it 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]$.

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 [itex]f:[n]\rightarrow [m]$.

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.

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} g(j) & \text{if j not equal to n+1} \\ i & \text{where i in [m], if i = n+1} \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!

Last edited:
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:
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.

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.

## 1. What is the meaning of "Show the set of all functions from A to B is finite"?

"Show the set of all functions from A to B is finite" means to prove that there is a finite number of functions that can map elements from set A to set B.

## 2. How can you prove that the set of all functions from A to B is finite?

To prove that the set of all functions from A to B is finite, you can use a proof by contradiction method. Assume that the set is infinite, and then use mathematical reasoning to show that this assumption leads to a contradiction.

## 3. What is the importance of proving that the set of all functions from A to B is finite?

Proving that the set of all functions from A to B is finite is important because it provides a deeper understanding of the relationship between set A and set B. It also allows for more efficient and accurate calculations and predictions in mathematical and scientific applications.

## 4. Can the set of all functions from A to B be infinite?

Yes, it is possible for the set of all functions from A to B to be infinite. For example, if set A has an infinite number of elements, and set B has a finite number of elements, then the set of all functions from A to B would also be infinite.

## 5. Are there any real-world examples of the set of all functions from A to B being finite?

Yes, one example is the set of all possible combinations of a lock with a limited number of digits. The set of all possible functions from A (the digits on the lock) to B (the number of digits in the combination) is finite, as there is a limited number of combinations that can be created.

• Calculus and Beyond Homework Help
Replies
1
Views
756
• Calculus and Beyond Homework Help
Replies
4
Views
661
• Calculus and Beyond Homework Help
Replies
11
Views
568
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
496
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
738
• Calculus and Beyond Homework Help
Replies
1
Views
767
• Calculus and Beyond Homework Help
Replies
15
Views
1K
• Calculus and Beyond Homework Help
Replies
34
Views
2K