0
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What are you trying to show with this example? $\endgroup$ – TonyK Apr 7 '14 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$ – balaya Apr 7 '14 at 19:00
  • $\begingroup$ Yes, OK! Why don't you edit your answer to make that clear? I was baffled. $\endgroup$ – TonyK Apr 7 '14 at 19:04
  • $\begingroup$ I don't see how the new function is necessarily different from every $f_i$. $\endgroup$ – Cure Apr 10 '14 at 19:43
0
$\begingroup$

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

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

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.