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.


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


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

  • $\begingroup$ 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? $\endgroup$
    – S.Cramer
    Feb 28 at 21:32
  • 1
    $\begingroup$ That's exactly right. $\endgroup$
    – Rob Arthan
    Feb 28 at 22:26
  • $\begingroup$ Awesome. Cheers~~ $\endgroup$
    – S.Cramer
    Feb 28 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.