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

Question

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.

Answer 1

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$.

Answer 2

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).

Answer 3

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.