We're working in $\sf{ZF}$ set theory, we assume $n$ is a finite cardinal, and the set $X$ is not finite. My question is: what's the smallest cardinal $k$ for which $\sf{ZF}$ proves $|X^n| \leq |k^X|$? We know that such $k$ must exist and be finite, since $|X^n|\leq |2^X|^n=|(2^n)^X|$ proves $k\leq 2^n$. The case $n=0$ is trivial, $k_0=1$. The case $n=1$ isn't much harder, $k_1=2$. The analogous question for $\sf{ZFC}$ is also trivial, $k_n=2$ for all $n>0$, but without Choice the problem seems rather difficult even for $n=2$.
I was able to prove the upper bound $k_n\leq n+1$ for all $n$, and I suspect this is optimal. In particular, I suspect that for each $n$, it's consistent that there exists infinite $X$ for which $|X^n|\not\leq |n^X|$. More strongly, I suspect it's consistent that there exists $X$ for which all $n$ have $|X^n|\not\leq |n^X|$. Unfortunately I'm not very familiar with forcing techniques, so I don't know how to prove this. It might be possible to establish a nice lower bound by considering the case where $X$ is an amorphous set, but I couldn't figure out how to do it. I would accept any answer that at least finds $k_3$.
To prove that $k_n\leq n+1$, I'll start by proving $|X^n|\leq n^n|(n+1)^X|$. Consider a function $f:n\to X$. We use $f$ to define the functions $p:X\to (n+1)$ and $g:n\to n$ like so.
$$p(x):=\begin{cases}n &: x\notin f[n] \\ \min\{j<n : x=f(j)\} &: x\in f[n]\end{cases}$$
$$g(j):=p(f(j))$$
Notice that the map $f\mapsto (g,p)$ sends $X^n\to n^n\times (n+1)^X$. This map is moreover an injection, since we have $p^{-1}[g(j)]=\{f(j)\}$ for all $j<n$. The intuition behind this strategy is that the function $p$ injects the image of $f$ into $n$, and then we use this numbering to compress $f$ into a function $g:n\to n$. Since $p$ can be used to decompress $g$ back into $f$, we have an injection. From these arguments, it follows that $|X^n|\leq n^n|(n+1)^X| \leq |(n+2)^X|$ and therefore $k_n\leq n+2$.
For $n>0$, the above strategy can be further improved to give $k_n\leq n+1$. To do this, let $M=(n+1)\times(n+2)$, and find an injection $\iota:M\to X$, which is possible since $X$ is infinite. For each $j<n+1$, define the sets $B_j=\{\iota(j,i) : i<n\}$ and $I_j=\{\iota(j,i) : n\leq i<n+2\}$, so that the collection of all $I_j$ and $B_j$ are pairwise disjoint, and each $|B_j|=n$ and $|I_j|=2$. Using the same map $f\mapsto (g,p)$ as before, we notice that there necessarily exists $j<n+1$ for which we have the image $p[B_j\cup I_j]=\{n\}$. Relying on that fact, we define the map $(g,p)\mapsto q\in (n+1)^X$ as follows.
$$J:=\min\{j<n+1 : p[B_j\cup I_j]=\{n\}\}$$
$$q(x):=\begin{cases} p(x) &: x\notin (I_J\cup B_J) \\ 0 &: x\in I_J \\ g(i) &: x\in B_J\land x=\iota(J,i) \end{cases}$$
To recover $(g,p)$ from $q$, first we recover $J<n+1$ as the unique number satisfying $q[I_J]=\{0\}$. Now we easily recover $g$ via $g(i)=q(\iota(J,i))$, and for $p$ we have $p(x)=q(x)$ when $x\notin (I_J\cup B_J)$ and $p(x)=n$ otherwise. The recoverability of $(g,p)$ from $q$ proves this is an injection. The intuition behind this strategy is that $p$ leaves a lot of empty space on which $p(x)=n$ is constant, and we can fit enough information in that space to encode $g$. We partition a subset of $X$ into some blocks $B_j$ and indicators $I_j$, and based on the structure of $p$, we're guaranteed that some block/indicator pair will be vacant. We choose one of these vacant block/indicator pairs, encode $g$ inside the block $B_j$, and enable the indicator $I_j$ so we know where to look to decode $g$. By composing our injections, we can send $f\mapsto q$ to prove $|X^n|\leq |(n+1)^X|$ and thus $k_n\leq n+1$ for all $n>1$. A similar strategy should prove $m|X^n|\leq |(n+1)^X|$ for all finite $m$, which is an interesting albeit unrelated result.
Best Answer
We prove $k_n=n+1$ by considering the case where $X$ is a strictly amorphous set, which is known to be consistent with $\sf{ZF}$. Since $X$ is amorphous, any partition of $X$ will contain at most one infinite part. Moreover since $X$ is strictly amorphous, any partition of $X$ into finite sets will be composed almost entirely of singletons. We'll rely on the four results established in this answer, listed below, plus another lemma and theorem we prove below.
Lemma 1: Given wellorderable $\alpha$ and $f:X \to \alpha$, the image $f[X]$ is finite.
Theorem 1: For $n\in\omega$ and $F:X^n\to [X]^{<\omega}$, the set $\bigcup\{F(p)\setminus p[n] : p\in X^n\}$ is finite.
Theorem 2: For $F:[X]^{<\omega}\to [X]^{<\omega}$, the set $\bigcup\{F(S)\setminus S : S\in [X]^{<\omega}\}$ is finite.
Lemma 2: Given wellorderable $\alpha$ and $f:X \to \alpha$, there's unique $s \in \alpha$ having $f^{-1}(s)$ be infinite.
proof: The image of $f$ is finite, so the preimages of $f$ form a finite partition of $X$. Since $X$ is amorphous, exactly one of these partitions will be infinite.$\Box$
Definition: Given well orderable $\alpha$ and $f:X \to \alpha$, define $L(f):=s$ as in the above lemma.
Definition: Given well orderable $\alpha$ and $f:X \to \alpha$, define $D(f):=\{x : f(x)\neq L(f)\}$, which is finite.
Theorem 3: Given $k\in\omega$ and $F:k^X \to [X]^{<\omega}$, the set $\bigcup\{F(p)\setminus D(p) : p\in k^X\}$ is finite.
proof: For each $S\in[X]^{<\omega}$, define $G(S):=\bigcup\{F(p) : D(p)=S, p\in k^X\}$. The set of $p$ quantified over by $G(S)$ has a natural injection into $k\times k^S$, which is finite, thus $G(S)$ is a finite union of finite sets. Since $G:[X]^{<\omega}\to [X]^{<\omega}$, it follows that the set $\bigcup\{G(S)\setminus S : S\in[X]^{<\omega}\}$ is finite, and this is a superset of $\bigcup\{F(p)\setminus D(p) : p\in k^X\}$, proving our claim.$\Box$
For our strategy, we take any $n>1$ and assume $|X^n|\leq |k^X|$. This implies there's an injection $Q:X^n\to k^X$, and we exploit the properties of strict amorphousness to prove $n+1\leq k$. To do this, we'll prove that there exists an injective $f\in X^n$ such that the map $x\mapsto Q(f)(x)$ is injective over $x\in f[n]$, and moreover that $Q(f)(x)\neq L(Q(f))$ on the same domain. Once we find such $f$, the injective condition implies that $|Q(f)[f[n]]|=|f[n]|=n$, and since there exists $x\in X$ for which $Q(f)(x)=L(Q(f))$, where necessarily $x\notin f[n]$, it follows that $|Q(f)[X]|\geq n+1$. Since $Q(f)[X]\subseteq k$, it will follow that $n+1\leq k$.
To begin, consider the map $f\mapsto D(Q(f))$, which sends $X^n\to [X]^{<\omega}$. By theorem 1, it follows that the set $B:=\bigcup\{D(Q(f))\setminus f[n] : f\in X^n\}$ is a finite subset of $X$. This lets us decompose $Q$ in a unique way, simply by describing its behavior on $f[n]$, on $B$, and in the remaining cases where it equals $L(Q(f))$. For simplicity, for each $j<k$ let $\sigma_j:k\to k$ be the permutation which is identity except for swapping $j$ with $0$. Using this language, we form an injection $Q[X^n]\to (k\times k^B)\times k^X$, defined so that $Q(f)\mapsto (g_f, p_f)$, where $g_f,p_f$ are defined as follows. $$\begin{align} g_f&:=(L(Q(f)),Q_f\restriction_B) \\ p_f(x)&:=\begin{cases} \sigma_{L(Q(f))}(Q(f)(x)) &: x\in f[n] \\ 0 &: x\notin f[n]\end{cases} \end{align}$$
It's not too hard to prove that if $(g_f,p_f) = (g_h, p_h)$ then necessarily $Q(f)=Q(h)$ and consequently $f=h$, so the map $f\mapsto (g_f,p_f)$ is injective. For simplicity we'll label $N=k\times k^B$, which is a finite set, hence $g_f$ takes on only finitely many values. Now we prove our first goal, which is that for most $f$, we have $p_f$ nonzero on the image of $f$. To prove this, we consider the functions $F:N\times k^X \to [X]^{<\omega}$ and then $F_0:k^X\to [X]^{<\omega}$ defined as follows. $$\begin{align} F(g,p)&:=\begin{cases} P^{-1}(g,p)[n] &: (g,p)\in P[X^n] \\ \emptyset &: (g,p)\notin P[X^n] \end{cases} \\ F'(p)&:=\bigcup_{g\in N} F(g,p) \end{align}$$ $$X_0:=\{x\in X : \exists(f\in X^n), x\in f[n]\land p_f(x)=0\}$$
The function $F$ works since $P$ is injective, so whenever $(g,p)$ is in the image $P[X^n]$, then $P^{-1}(g,p)\in X^n$ and then $F(g,p)$ is the finite image of that $n$-tuple. The function $F'$ just unions $F(g,p)$ over the finitely many $g\in N$, so $F'(p)$ is also finite. Every $x\in X_0$ admits $f\in X^n$ with both $x\in f[n]$ and $p_f(x)=0$, thus $x\in (F(g_f,p_f)\setminus D(p_f))\subseteq (F'(p_f)\setminus D(p_f))$. It follows that $X_0\subseteq\bigcup\{F'(p)\setminus D(p) : p\in k^X\}$, but because $F':k^X\to [X]^{<\omega}$, the set is finite by theorem 3, thus $X_0$ is finite. It follows that, where $X\setminus X_0$ is a cofinite subset of $X$, all $f\in (X\setminus X_0)^n$ and all $x\in f[n]$ have $p_f(x)\neq 0$. Now we work toward our second goal, that for most $f$, we have $p_f$ injective on the image of $f$. To begin, we'll restrict the domain $X$ so that, for each $t<n$, the evaluations $p_f(f(t))$ are constant across all injective $f$. To do this, we recursively define the functions $F_{(t,j)}:X^{n-j}\to k$ across all $j\leq n$, and the functions $E_{(t,j)}:X^{n-j}\to[X]^{<\omega}$ for $0<j<n$, and finally the set $X_1$, as follows. $$\begin{align} F_{(t,0)}(f)&:=p_f(f(t)) \\ F_{(t,j+1)}(x_0,\cdots,x_{n-j-2})&:=L(x_{n-j-1}\mapsto F_{(t,j)}(x_0,\cdots,x_{n-j-1})) \\ \ell_t&:=F_{(t,n)}(\emptyset) \\ E_{(t,j+1)}(x_0,\cdots,x_{n-j-2})&:=D(x_{n-j-1}\mapsto F_{(t,j)}(x_0,\cdots,x_{n-j-1})) \\ X_1&:=\bigcup_{t<k}\bigcup_{j=1}^{j<n}\bigcup\{E_{(t,j)}(f)\setminus f[n-j] : f\in X^{n-j}\} \end{align}$$
By theorem 1, it follows quickly that the set $X_1$ is a union of finitely many finite sets, so it's finite. By continuing the recursion up to $j=n$, we get $F_{(t,n)}:X^0\to k$, and the only function $f\in X^0$ is the empty function, hence we get $\ell_t\in k$ as a constant independent of $f$. Taking any injective $f:n\to (X\setminus X_1)$, each integer $j\in(0,n)$ has $f(n-j-1)\notin E_{(t,j+1)}(f\restriction_{n-j})$ and consequently $F(f\restriction_{n-j})=F(f\restriction_{n-j-1})$, and by finite induction it follows that $p_t(f(t))=F_{(t,0)}(f)=F_{(t,n)}(\emptyset)=\ell_t$. Since $\ell_t$ is independent of $f$, we see that indeed $p_t(f(t))$ is constant across all injective $f\in (X\setminus X_1)^n$.
To complete our proof, we show that the map $n\to k$ defined by $t\mapsto \ell_t$ is injective and nonzero. To do this, let $Y=X\setminus(X_0\cup X_1)$, which is an infinite subset of $X$. Taking any $f\in Y^n$, we'll have $p_t(f(t))\neq 0$ by construction of $X_0$, but we'll also have $p_t(f(t))=\ell_t$ by construction of $X_1$, thus $\ell_t\neq 0$ as desired. To prove injectivity, take any $i<j<n$ and by contradiction suppose $\ell_i=\ell_j$. Select any injective $f'\in X^{n\setminus\{i,j\}}$, and for each $g\in N$ we define the relation $C_g$ as follows. $$C_g:=\{(\{f(i),f(j)\},f(i)) : f\in Y^n\text{ is injective, }g_f=g, f'\subseteq f\}$$
This relation $C_g$ actually defines a choice function for some collection of unordered pairs in $Y$. To see that $C_g$ is a function, suppose we have two satisfying $f_1,f_2$ each of which had $(\{f_u(i),f_u(j)\} f_u(i))\in C_g$, but such that $f_1(i)\neq f_2(i)$. Because $g_{f_1}=g=g_{f_2}$, the injectivity of our map $f\mapsto (g_f,p_f)$ implies that $p_{f_1}\neq p_{f_2}$. It's easily shown that $f_1(i)=f_2(j)$ and $f_1(j)=f_2(i)$, and consequently $f_1[n]=f_2[n]$, thus $p_{f_1}(x)=p_{f_2}(x)=0$ whenever $x\in X\setminus f_u[n]$. For $x=f_1(i)=f_2(j)$ we get $p_{f_1}(x)=\ell_i=\ell_j=p_{f_2}(x)$, and this similarly happens when $x=f_1(j)$. The only remaining $x$ are in the image of $f'$, but there must be $t\neq i,j$ for which $x=f'(t)=f_1(t)=f_2(t)$, and thus $p_{f_1}(x)=\ell_t=p_{f_2}(t)$. This proves $p_{f_1}(x)=p_{f_2}(x)$ for all $x\in X$, thus $p_{f_1}=p_{f_2}$, contradicting our assumption that $f_1\neq f_2$. With this contradiction, it's established that $C_g$ is a function defined on some domain.
It's clear by definition that whenever $(x,y)\in C_g$ then $y\in x$, thus $C_g$ is a choice function. We can merge these functions across all the $g\in N$ to get a choice function defined for every unordered pair in $Y$. Indeed, notice that if $x,y\in Y$ has both $x,y\notin f'[n\setminus\{i,j\}]$ and $x\neq y$, then the extended function $f=f'\cup\{(i,x),(j,y)\}$ obeys our conditions, and thus $C_{g_f}(\{x,y\})=x$. It follows that for nearly every pair $\{x,y\}$, there exists $g\in N$ for which $\{x,y\}\in\operatorname{dom}(C_g)$. Recalling that $g\in N$ and $N$ is a finite set, we can define some well order on $N$ and merge all the $C_g$ according to that ordering. The cases where no such $g$ exists can be handled manually, so we define the following choice function for all unordered pairs in $Y$. $$C(\{x,y\}):=\begin{cases} C_g(\{x,y\}) &: g=\min\{g'\in N : \{x,y\}\in\operatorname{dom}(C_g)\} \\ f(t) &: t=\min\{t'<n : f'(t)\in\{x,y\}\} \\ x &: x=y\land (\{x,y\}\cap f'[n\setminus\{i,j\}])=\emptyset \end{cases}$$
This is impossible however, as it contradicts the fact that $Y\subseteq X$ is an infinite subset of a strictly amorphous set, and thus is also strictly amorphous. To see why $C$ is impossible, define $H(x):=\{y\in Y : C(\{x,y\})=x\}$ and notice that, for all $x\neq y$, either $x\in H(y)$ or $y\in H(x)$, but not both. Letting $Y_0=\{x\in Y : |H(x)|\in \omega\}$, the map $x\mapsto H(x)$ sends $Y_0\to [Y]^{<\omega}$ and thus the union $\bigcup\{H(x)\setminus\{x\} : x\in Y_0\}$ is a finite set. If $Y_0$ were infinite, we could find distinct $x,y\in Y_0$ for which $y\notin H(x)$ and $x\notin H(y)$, but as established this is impossible. Since $Y_0$ is finite, it follows that the complement $Y_\infty:=\{x\in Y : |H(x)|\notin\omega\}$ is infinite. Now the map $x\mapsto (Y\setminus H(x))$ sends $Y_\infty\to [Y_\infty]^{<\omega}$, and again by theorem 1 the union $\bigcup\{(Y\setminus H(x)) : x\in Y_\infty\}$ is finite, so the intersection $\bigcap\{H(x) : x\in Y_\infty\}$ is cofinite. We can thus find distinct $x,y$ within $Y_\infty$ for which both $x\in H(y)$ and $y\in H(x)$, but this is again impossible.
We finally conclude that the map $n\to k$ defined by $t\mapsto \ell_t$ is both injective and nonzero, therefore $k-1=|k\setminus\{0\}|\geq n$ which proves $n\leq k+1$. Combining this with the upper bound $k_n\leq n+1$ proven in the question statement, we conclude that $k_n=n+1$. In summary: given standard finite cardinals $n,k$, we have that $\sf{ZF}$ proves $|X^n|\leq |k^X|$ for all infinite $X$ if and only if $n<k$. Moreover, it is consistent with $\sf{ZF}$ that there exists infinite $X$ such that all $n\in\omega$ have $|X^n|\not\leq |n^X|$. In particular, this happens whenever $X$ is strictly amorphous.