# For any two finite sets $X$ and $Y$, prove that $\#(Y^X)=\#(Y)^{\#(X)}$ by induction

I came across the following exercise while self-studying Terrence Tao's book Analysis I:

Exercise 3.6.4 Let $X$ and $Y$ be finite sets. Then $Y^X$, the set of functions with domain $X$ and range $Y$, is finite and $\#(Y^X)=\#(Y)^{\#(X)}$.

Note: This question has been asked twice before (here and here) on this site. My attempt was a proof by induction, which was not present in either of these posts. So, I ask merely that any answers correct my inductive step, or any other errors, and not give alternate solutions. With that in mind, here is my go:

Let $X$ and $Y$ be finite sets with bijections $f:X\to\Bbb N_n$ and $g:Y\to\Bbb N_m$ (where $\Bbb N_n$ denotes the set of natural numbers less than $n$, where I am using the convention that the natural numbers start at zero). In this proof, we fix $m$ and induct on $n$. If it happens that $n=0$, then $\#(Y^X)=1$, as there is a unique function $\emptyset\to Y$ (uniqueness is a vacuous truth, in this case). Since $m^0=1$, the claim is trivial in this case, and we may assume that $n>0$. If it happens that $n=1$, then $Y^X$ is the set of all functions $\{*\}\to Y$, as $X$ is a singleton set. Notice that if the image of $\{*\}$ under any of these maps is greater than one, the image of $x$ cannot be unique, which contradicts our assumption that $Y^X$ consists of only functions. Therefore, the image of any one of these maps is a singleton, and it suffices to count only the elemtnts of $Y$, as $\{*\}$ remains fixed: $$\#(Y^X)=\#\left(\bigcup_{y\in Y}\{y\}\right)=\#(Y)^{\#\{*\}}.$$ Furthermore, suppose our claim holds for some $n\in\Bbb N$. Then, if $x'\notin X$ and $Z=X\cup\{x'\}$, \begin{align}Y^Z :&=\{f\mid \operatorname{dom}(f)=Z\land \operatorname{ran}(f)=Y\} \\ &=\{(x,y)\in f\mid x\in X\cup\{x'\}\land y\in Y\} \\ &= (?) \\ &=Y^X\times Y^{\{x'\}},\end{align} and hence, $$\#(Y^Z)=m^n\times m=m^{n+1}.$$ This closes induction. What am I missing in the inductive step? What should go in place of $(?)$ in the third line above? It seems only plausible that it works out to be $Y^X\times Y^{\{x'\}}$, otherwise I am not sure how to apply the inductive hypothesis. Also, one can arrive at a contradiction of the original claim, considering \begin{align}\#(Y^Z)&=\#\left(\{f\mid \operatorname{dom}(f)=X\land \operatorname{ran}(f)=Y\}\cup \{f\mid \operatorname{dom}(f)=\{x’\}\land \operatorname{ran}(f)=Y\}\right) \\ &= m^n+m\neq m^{n+1} \end{align}. Why is this incorrect? Thanks in advance.

Update: Combinatorially speaking, the carnality of $Y^Z$ should be $\#(Y^X)\times\#(Y)$, as one can pair $\{x'\}$ with each element of $Y$, which as we mentioned above, should yield the cardinality of $Y$. But, this is in contradiction with what I have written before, and I am still interested in why it is false.

• This is just a simple combinatorics.Say $X = \{a, b, c \}$ and $Y = \{d, e\}$. Then for $a$, there could be two possible images, and associated with each of those gives a different function. For $b$, there could be two possible images. For $c$ there could be two possible images. That is, $2*2*2 = 2^{3}$. Jun 26, 2018 at 1:03
• @Mr.SnowRemover Yeah, but what was the mistake in my inductive step? A combinatorial approach was already mentioned in the posts I linked. Jun 26, 2018 at 1:07
• Hi. The combinatorial argument is helpful in guessing how to prove by induction, I guess. But let me stick to your way. What does $\mathbb{N}_{n}$ mean? Jun 26, 2018 at 1:23
• It shouldn't make a difference, because your $\Bbb N_n$ is in bijection with my $\Bbb N_n$, so any bijection I construct can be composed with a map from my $\Bbb N_n$ to your $\Bbb N_n$ and vice versa (map $0\leftrightarrow 1$, $1\leftrightarrow 2, \ \dots$) Jun 26, 2018 at 1:34
• No, this is not necessarily true. The image of $X$ must be a singleton set, but the range could have an arbitrary number of elements. In this case, the function at hand is non-surjective, yet still a function. Jun 26, 2018 at 1:46

You want to conclude that

$$Y^Z = Y^{X} \times Y^{\{x'\}}$$

This will not be an equality of sets strictly speaking, since the first set has subets of tuples in $Z \times Y$, and the second one has subsets of tuples with each coordinate again being a tuple, in $X \times Y$ and $\{x'\} \times Y$ respectively. So I don't think you can conclude your argument by a chain of equalities. You can however do the following bijection

$$\Gamma : Y^Z \longrightarrow Y^{X} \times Y^{\{x'\}} \\ f \longmapsto (f^*, f_*)$$

with $f^*: x \in X \mapsto f(x) \in Y$ and $f_*(x') = f(x')$, whose inverse is

$$\Gamma^{-1} : Y^{X} \times Y^{\{x'\}} \longrightarrow Y^Z \\ \Gamma^{-1}(f,g)(z) = \cases{g(x') \quad \text{ if } z = x' \\ f(z) \quad \text{otherwise} }$$

Which shows what you ultimately need, that is, that

$$|Y^Z| = |Y^{X} \times Y^{\{x'\}}|$$

I don't know if this is a satisfactory answer, but as far as I know, this is not an 'avoidable' step.

Also, I think you could improve your inductive step, since the induction is on the size of the set and nothing else, I think it would be better to pick some $x' \in Z$ and define $X := Z \setminus \{x'\}$. Because in your current construction, you are adding an element to a previously defined set, which in principle you don't have. You could take it one step further and only prove this for sets of the form $\{1, \dots, n\}$ and then prove as an auxiliary result that $A^B \simeq C^D$ if $A \simeq C, B\simeq D$.

• (+1) Alright, that clears things up. I was thinking about that the other day, that it might not necessarily be the sets $Y^Z$ and $Y^X\times Y^{\{x’\}$, but merely their cardinalities; I was to lazy to formalize it and I couldn’t take it very far. Anyway, good answer! Jun 28, 2018 at 1:29
• No problem! I've added some comments (mostly) regarding writing style, which are of course subjective, but I felt they could be of use anyway. Jun 28, 2018 at 1:34
• Just to check, by $A\simeq B$ you mean $A$ is in bijection with $B$? Jun 28, 2018 at 1:39
• Yes, sorry, probably should have specified it since that's used in various contexts. Jun 28, 2018 at 1:41
• @Crosby I had made a typo in the last part of my answer, it has now been fixed. What I meant was that $A^B \simeq C^D$ when $A \simeq C, B\simeq D$, not $A \simeq B$ and $C \simeq D$. The latter is obviously false (take $A = B = \{1\}$ and $C = D = \{1,2\}$). Jun 28, 2018 at 3:38

Skimming over the OP's question and comments, I come away with the distinct impression that the only way to make this interesting is to set up the induction to give us the right perspective.

Lemma 1: Let $X$ and $Y$ be two finite sets with $\#(Y) \gt 0$ and $\bar x \notin X$. Let $\hat X = X \cup \{\bar x\}$. The number of functions from $\hat X$ into $Y$ is given by

$\tag 1 \#(Y^X) \times \#(Y)$

Proof (hint):

Let $S = \{\bar x\} \times Y$. Define a bijective mapping from ($Y^X \times S)$ to $Y^{\hat X}$ via

$\quad (f, (\bar x, y)) \mapsto f \cup \{(\bar x, y)\} \text{ where } f \in Y^X \text{ and } y \in Y$ $\quad \blacksquare$

Lemma 2: Let $n \in \mathbb N$. Suppose for any two finite sets $X$ and $Y$ the following is true:

$\tag 2 \text{If } \#(X) + \#(Y) = n \text{ Then } \#(Y^X)=\#(Y)^{\#(X)}$

Then if $U$ and $V$ are any two finite sets satisfying $\#(U) + \#(V) = n + 1$, then it must be true that

$\tag 3 \#(V^U)=\#(V)^{\#(U)}$.

Proof Sketch

If $\#(U) \times \#(V) = 0$ we can easily show that equation $\text{(3)}$ holds true. So we assume that $\#(V) \gt 0$ and $U$ has at least one element $u$. Set $X = U \text{\\} \{u\}$ and $Y = V$ so that $\#(X) + \#(Y) = n$. Using the assumed truth of all the $\text{(2)}$ statements and lemma 1, we see that equation $\text{(3)}$ holds true once again. $\quad \blacksquare$

The OP can use lemma 2 in a proof by induction. They might feel more comfortable starting the inductive base case at $n = 1$ or $n = 2$. If they really love math they can really start at $n = 0$, but they would have to cry out that

$\quad \#(\emptyset^{\emptyset}) = 0^0 = 1$

That might require taking a few drinks first!

Looking over this answer and considering Cameron Buie's comments, it appears that I am using the method of infinite descent (induction by any other name).

• @cam I left setting up the induction to the OP. I proved lemma 2 (really the inductive step disguised) using lemma 1 and assuming that the premise of lemma 2 [an infinite number of statement with tag (2)] is true. I might be stepping out of the formal set theory bounds with my naive set theory. Does lemma 2 makes sense standing on its own and not part of the inductive hypothesis? Jun 28, 2018 at 0:54
• (+1) This is much clearer, now that you've put the tombstones in. It seemed that "The OP can use lemma 2..." had been part of the Lemma 2 proof sketch, before. Jun 28, 2018 at 23:52

I think that one path is prove the next propostion in order to prove the original proposition:

Proposition. Let $$X, Y$$ finite sets where $$\#(X)=n$$. Then $$Y^{X}$$ is finite and $$\#(Y^{X})=(\#(Y))^{n}$$

Proof. We use the principle of mathematical induction, where $$P(n)$$ is the statement given in the proposition.

First we prove $$P(0)$$. We assume $$X, Y$$ are finite sets, and $$\#(X) = 0$$. Then we have $$X = \emptyset$$. We know that exists an only function from the empty set to $$Y$$, hence exists an only function from $$X$$ to $$Y$$. We call this function $$f$$ and we can prove $$Y^{X} =\{f\}$$. Consider the function $$s:\{i \in \mathbb{N} : 1 \leq i \leq 1\} \to Y^{X}$$, where $$s(a) := f$$. We can prove $$s$$ is a bijection and therefore, $$Y^{X}$$ have cardinality $$1$$. We can conclude $$Y^{X}$$ is finite and $$\#(Y^{X}) = (\#(Y))^{0}$$. This proves $$P(0)$$.

Now we prove the inductive step. Let $$k \in \mathbb{N}$$ and suppose $$P(k)$$. We assume $$X, Y$$ are finite sets, where $$\#(X)=k{+\!+}$$. We know $$k{+\!+} \geq 1$$, and hence $$X \neq \emptyset$$. Let $$x$$ an object where $$x \in X$$, we can conclude $$X - \{x\}$$ have cardinality $$k$$. Hence $$X - \{x\}$$ is finite and $$\#(X - \{x\}) = k$$. From our inductive hypothesis, we can conclude $$Y^{X - \{x\}}$$ is finite and $$\#(Y^{X - \{x\}}) = (\#(Y))^{k}$$.

Consider the function $$g : Y^{X - \{x\}} \times Y^{\{x\}} \to Y^{(X - \{x\}) \cup \{x\}}$$, where $$g(a, b)$$ is the function defined as $$g(a, b): (X - \{x\}) \cup \{x\} \to Y$$, where $$\begin{cases} (g(a, b))(c) := a(c), & \text{if } c \in X - \{x\} \\ (g(a, b))(c) := b(c), & \text{if } c \in X \end{cases}$$ We can prove $$g$$ is a bijection and hence $$Y^{X - \{x\}} \times Y^{\{x\}}$$ have the same cardinality as $$Y^{(X - \{x\}) \cup \{x\}}$$.

In the case $$Y = \emptyset$$, we can conclude $$Y$$is finite and $$\#(Y) = 0$$. Let $$a$$ an arbitrary object and we assume $$a \in Y^{X}$$, then we have $$a : X \to Y$$, and considering $$x \in X$$, we have $$a(x) \in Y$$, which is false. Therefore $$a \notin Y^{X}$$ and we can conclude $$Y^{X} = \emptyset$$. Then we have $$Y^{X}$$ is finite and $$\#(Y^{X}) = 0$$. Furthermore, considering $$k{+\!+} \neq 0$$, we have $$0^{k{+\!+}} = 0$$, and hence $$\#(Y^{X})=0^{k{+\!+}}$$, so $$\#(Y^{X}) = (\#(Y))^{k{+\!+}}$$.

In the case where $$Y \neq \emptyset$$, consider the function $$g : Y \to Y^{\{x\}}$$, where $$g(y) : \{x\} \to Y$$, where $$(g(y))(a) := y$$. We can prove $$g$$ is a bijection, and hence, $$Y$$ have the same cardinality as $$Y^{\{x\}}$$.

We know $$Y$$ have not cardinality $$0$$, and considering that it is finite, we have $$Y$$ have cardinality $$p$$, where $$p \in \mathbb{N}$$. So $$\#(Y) = p$$, where $$p \neq 0$$. Furthermore, $$Y$$ have the same cardinality as $$\{ i \in \mathbb{N} : 1 \leq i \leq p \}$$, and in consequence $$Y^{\{x\}}$$ have the same cardinality as $$\{ i \in \mathbb{N} : 1 \leq i \leq p \}$$. We can conclude $$Y^{\{x\}}$$ is finite and $$\#(Y) = \#(Y^{\{x\}})$$.

Considering $$Y^{(X - \{x\})}$$ and $$Y^{\{x\}}$$ are finite sets, we have $$Y^{(X - \{x\})} \times Y^{\{x\}}$$ is finite, and $$\#(Y^{(X - \{x\})} \times Y^{\{x\}}) = \#(Y^{(X - \{x\})}) \times \#(Y^{\{x\}}) = (\#(Y))^{k} \times \#(Y) = (\#(Y))^{k{+\!+}}$$. Because $$Y^{(X - \{x\})} \times Y^{\{x\}}$$ have the same cardinality as $$Y^{(X - \{x\}) \cup \{x\}}$$, we can conclude $$Y^{(X - \{x\}) \cup \{x\}}$$ is finite and $$\#(Y^{(X - \{x\}) \cup \{x\}}) = (\#(Y))^{k{+\!+}}$$.

We know $$(X - \{x\}) \cup \{x\} = X$$, and hence $$Y^{(X - \{x\}) \cup \{x\}} = Y^{X}$$. Therefore $$Y^{X}$$ is finite and $$\#(Y^{X}) = (\#(Y))^{k{+\!+}}$$. This completes the induction.