# Let $A$ be finite. Suppose $B$ is countably infinite. Is the set $B^A$ uncountably infinite?

Let $$A$$ be a finite set. Suppose $$B$$ is countably infinite. Is the set $$B^A$$ uncountably infinite?

I am new to infinite cardinality arguments, but my initial thinking is yes. However, I am uncertain if the claim requires the Axiom of Choice... I am concerned that I am using the Axiom of Choice without realizing it, and I would like to not invoke the axiom if possible. The following is my pseudo-informal argument.

Because $$B$$ is countably infinite, there exists an injection (possibly bijection) from $$B$$ to $$\mathbb N$$. (i.e. $$B \preceq \mathbb N)$$. Let $$F$$ be one such function so that $$F:B \xrightarrow{1-1} \mathbb N$$.

Knowing that $$\mathbb N$$ is well-ordered, I can conclude that all subsets of $$\mathbb N$$ are well-ordered. Thus every member of $$\mathcal P(\mathbb N) \setminus \{\emptyset\}$$ has a minimal element. Further, by Cantor's Diagonal argument $$\mathcal P (\mathbb N)$$ is uncountably infinite, which implies that $$\mathcal P(\mathbb N) \setminus \{\emptyset\}$$ is uncountably infinite as well. I believe a similar argument can be made for $$\mathcal P(B)$$.

Let $$p_{_B}$$ be an arbitrary element of $$\mathcal P( B) \setminus \{\emptyset\}$$. I know that restricting $$F$$'s domain to $$p_{_B}$$ will produce a subset in $$\mathbb N$$. Call this subset $$\mathbb N_{p_B}$$. (i.e. $$F[p_{_B}]=\mathbb N_{p_B}$$)

Let $$n_{0}$$ be the minimal element of $$\mathbb N_{p_B}$$. Let $$b \in p_{_B}$$ be the element that is mapped to through $$F^{-1}$$...i.e. $$F^{-1}(n_0)=b$$. Because $$F$$ is injective, this is unambiguous.

Now, consider the construction of a function $$g_{p_B}$$. Let $$g_{p_B}$$ be the function that takes all elements of $$A$$ and maps them to the $$b \in p_{_B}$$ that corresponds to minimal element $$n_0$$ for a given $$\mathbb N_{p_B}$$. (This is where I am concerned...I think I am using a valid invocation of the Axiom of Replacement, but perhaps it is actually the Axiom of Choice)

Because there are an uncountably infinite number of $$p_{_B}$$'s in $$\mathcal P( B) \setminus \{\emptyset\}$$, there must necessarily be an uncountably infinite number of $$g_{p_B}$$'s that satisfy the above definition. The collection of all such functions is a subset of $$B^A$$. Therefore, if a subset of a given set is uncountably infinite, the set itself must be uncountably infinite.

Edit

Just to highlight an issue in my reasoning, here is one of my afterthoughts (confirmed by Arturo Magidin):

"Now that you mention it, it does seem like there is necessarily a chance that many of the $$g_{p_B}$$'s are redundant...i.e. there may be a $$p_{_B}\neq p'_{_B}$$ that can be represented by the same $$g$$ function. Perhaps that is an issue as well."

• You’ll need to worry about the possiblity that $A$ is empty or a singleton. Does your argument take that into account? Feb 28 at 0:46
• Ahhh. Good call on if $A = \emptyset$. Could you please explain what the issue is with $A$ being a singleton, though? Now that you mention it, it does seem like there is necessarily a chance that many of the $g_{p_B}$'s are redundant...i.e. there may be a $p_{_B} \neq p'_{_B}$ that can be represented by the same $g$ function. Perhaps that is an issue as well. Feb 28 at 0:50
• There is an obvious bijection between functions $\{\star\}\to B$ and $B$; so you can’t get more than $|B|$ functions if you are mapping from a singleton. Feb 28 at 0:52
• Using cardinal numbers, one can look at this the proof that $B^A$ is countable as proving $\aleph_0^n=\aleph_0$, which can be done using $\aleph_0\cdot\aleph_0=\aleph_0$ and induction on $n$. (Or, if you prefer this formulation, you prove first that $|B\times B|=B$ and then you get $|B\times B\times\dots\times B|=|B|$ by induction.) There are several posts where you can find the claim for product of two sets: Bijecting a countably infinite set $S$ and its cartesian product $S \times S$, ... Feb 28 at 9:46
• Feb 28 at 9:47

The answer is negative: if $$A$$ is finite and $$B$$ is countably infinite then $$B^A$$ is either finite or countably infinite, and hence is certainly not uncountably infinite. You can prove this by induction on the size $$|A|$$ of $$A$$. If $$|A| = 0$$, then $$A$$ is empty and $$B^A$$ comprises the single function $$\emptyset$$. If $$|A|= k + 1$$, pick $$a_0$$ in $$A$$ and observe that any function $$f_0 : A \setminus \{a_0\} \to B$$ has only countably many extensions to a function $$f : A \to B$$ (because we have only countably many choices for $$f(a_0)$$). By the inductive hypothesis there are only countably many such $$f_0$$, and then using the fact that $$X \times Y$$ is countable if both $$X$$ and $$Y$$ are, you have that there are at most countably many such $$f$$.
• Thank you! Just a quick question for you: In your final sentence when you talk of $X$ and $Y$, can I think of $X$ as being the countably infinite set that contains all of the $f_0$ variants and can I think of $Y$ as being the countably infinite set that contains all of the possible $f(a_0)$ assignments? Feb 28 at 21:32