# Are the following sets countable?

I'm trying to determine if the following sets are countable: (a) $\mathbb{Z}^{[0,1]}, (b) [0,1]^{\mathbb{Z}}, (c) \mathbb{Z}^{\mathbb{Z}}$, (d) the set given by functions $f:\mathbb{Z}\to\mathbb{R}$ such that $f(n)\neq0$ only for finitely $n$ (otherwise zero), (e) the set given by functions $f:\mathbb{Z}\to\mathbb{Z}$ such that $f(n)\neq0$ only for finitely $n$ (otherwise zero).

Here $Y^X$ denotes the set of all function from $X$ to $Y$. I've seen similar question that involves $\{0,1\}$ instead of $[0,1]$, I'm not sure how to proceed if I have the last case (I'm considering the possibility that the question is wrong, wouldn't imply that question 1 and 2 are uncountable just because $[0,1]$ is uncountable?).

Is there a theorem that states "If $f:X\to Y$ and $X$ or $Y$ is uncountable then $Y^{X}$ is uncountable"?

For (a) I'm tempted to say uncountable but I haven't found a way to write a proof that looks good.

Still, I believe I could prove that $Z^{[0,1]}$ is uncountable also by proving that $\mathbb{Z_+}^{\{0,1\}}$ is uncountable because $\mathbb{Z_+}^{\{0,1\}} \subset \mathbb{Z}^{[0,1]}$. To do this I repeat Cantor's argument: if $\mathbb{Z_+}^{\{0,1\}}$ is countable then we can have a list $\{f_1,f_2\}$ with every function, but defining $f(n)= 0$ (if $f_n(n)=1)$ and $f(n)=1$ (if $f(n(n)=0)$ we have a that $f$ is not in the list; I believe this would probe (b).

For (c), since $Z^{[0,1]} \subset Z^{\mathbb{Z}}$ can I conclude $Z^{\mathbb{Z}}$ uncountable?.

Can I conclude (d) uncountable because $\mathbb{R}$ uncountable?. Another argument may be the following: If countable we have a list $\{f_1,f_2,f_3,\dots\}$ of functions, now define $f(n) = a_1.a_2a_3a_3\dots$ where $a_n= 0$ if nth term of the decimal expression of $f_n(n)$ is not $0$ and $1$ otherwise; would this construct a function that is not in the former set and finish the proof?.

For (e) maybe I can split $\mathbb{Z}$ considering $\mathbb{Z}=\mathbb{Z_{-}}\cup{\{0\}}\cup\mathbb{Z_+}$ and prove that each one is countable. I'm not sure yet what to do, should I consider all the cases, this is, $f:Z_+\to Z_+, f:Z_+\to Z_{-}$, etc?.

Is there a theorem that states "If $f:X\to Y$ and $X$ or $Y$ is uncountable then $Y^X$ is uncountable"?

I don't see what role $f$ plays here, but yes, it is true that if $|X| \ge 2$ and $Y$ is non-empty, then $|X^Y| \ge |X|$ and $|X^Y| \ge |Y|$.

To see that $|X^Y| \ge |X|$, we have the functions $\{f_{\alpha}:Y \to X\}_{\alpha \in X}$ defined by $f_\alpha(y) = \alpha$ for all $y \in Y$. Each $f_\alpha$ is a distinct element of $X^Y$ (because $Y$ is non-empty), and the cardinality of $\{f_\alpha\}$ is the same as the cardinality of $X$.

To see that $|X^Y| \ge |Y|$, choose any distinct $x_0,x_1 \in X$ (we can do this because $|X| \ge 2$), and define the functions $\{f_{\beta}:Y \to X\}_{\beta \in Y}$ by:

$f_\beta(\beta) = x_0$
$f_\beta(y) = x_1$ if $y \ne \beta$

Each $f_\beta$ is a distinct element of $X^Y$, and the cardinality of $\{f_\beta\}$ is the same as the cardinality of $Y$.

To prove the stronger result that $|X^Y|$ is strictly greater than $|Y|$, you can use Cantor's diagonal argument.

For (a), suppose towards contradiction the set is countable, and write it out as $f_1, f_2, f_3, \ldots : [0,1] \to \mathbb{Z}$. Define $f:[0,1]\to \mathbb{Z}$ by $f(1/n) = f_n(1/n)+1$ and $f(x)=0$ if $x\neq 1/n$ for some $n$.

• What are you trying to show with this example? – TonyK Apr 7 '14 at 18:56
• That if we list $\{f_1,f_2,f_3,\dots\}$ assuming $f$ countable the function aboves give a function that is not included in the list, then (a) is uncountable. – balaya Apr 7 '14 at 19:00
• Yes, OK! Why don't you edit your answer to make that clear? I was baffled. – TonyK Apr 7 '14 at 19:04
• I don't see how the new function is necessarily different from every $f_i$. – Cure Apr 10 '14 at 19:43

d: Uncountable: $\{(f: \mathrm{Z} \rightarrow \mathrm{R}, 0 \mapsto x, z \mapsto 0 \text{ for$z \neq 0$}) | x \in \mathrm{R} \} \cong \mathrm{R}$.

• Could you explain a little further? – Cure Apr 7 '14 at 20:16
• @Dante: TonyKs answer is very nice, no real need to improve this one. – Keba Apr 7 '14 at 22:15
• Thank you Keba! But my answer only applies to cases (a) and (b). – TonyK Apr 7 '14 at 23:40
• Also, if I change $\mathbb{Z}$ by $\mathbb{R}$ in balaya's answer, doesn't that prove (d) uncountable?. – Cure Apr 7 '14 at 23:49