1
$\begingroup$

I get that to prove a set is countable you have to find a bijection from that set to a countable set, but i usually get stuck trying to find that function. I'm trying to prove whether or not these sets: $\mathbb{Z}^{[0,1]}$ and $[0,1]^{\mathbb{Z}}$, are countable or uncountable.

Thanks!

$\endgroup$
1
$\begingroup$

First notice that we have a bijective function from $\mathbb{N}$ to $\mathbb{Z}$, So we can reduce our problems to $[0,1]^\mathbb{N}$ and $\mathbb{N}^{[0,1]}$. Further we have that $\mathcal{P}(\mathbb{N})$ is uncountable. Then look at the function $$ f:\mathcal{P}(\mathbb{N})\to[0,1]^{\mathbb{N}} $$ by sending $A\in\mathcal{P}(\mathbb{N})$ to the map in $[0,1]^{\mathbb{N}}$ which send $x\in\mathbb{N}$ to $1$ if $x\in A$ and zero otherwise. This gives an injective function, thus we conclude that $[0,1]^\mathbb{N}$ is uncountable.

Then for the other notice you can imbed $\mathbb{N}$ in $[0,1]$ by looking at $1/n$. then you can look at a subset of the set $\mathbb{Z}^{[0,1]}$ which is $\{0,1\}^\mathbb{N}$ and then you can say again with the above argument that it is uncountable.

$\endgroup$
1
  • $\begingroup$ Could you explain a little further?. We can change $\mathbb{N}$ by $\mathbb{Z}$ just because $\mathbb{N}\sim \mathbb{Z}$?. What further argument could be given in order to prove that $[0,1]^{\mathbb{N}}$ countable $\iff$ $[0,1]^{\mathbb{Z}}$ countable. I'm sorry if this is a very basic question. $\endgroup$ – Cure Apr 9 '14 at 2:04
3
$\begingroup$

I hope that by $[0,1]$ you mean the interval and that it is not a typo for $\{0,1\}$.

Finding an explicit bijection can be (very) hard. Instead, one can use the CSB theorem to show two sets have the same cardinality by showing that injections in both directions exist. Or, to show that a set is countable, one can express the set is a countable union of countable sets.

To show that a set $S$ is not counatable it suffices to find an injection $B\to S$ from an uncountable set $B$. This is possible your second set. Can you think of an injection $B\to [0,1]^\mathbb Z$ for a suitabley chosen $B$? Can you then solve for the first set?

$\endgroup$
2
  • $\begingroup$ Yes, by [0,1] I mean the interval. $\endgroup$ – Rachel Mar 30 '14 at 23:11
  • $\begingroup$ does this injection work: g $\in$ $[0,1]^{\mathbb{Z}}$ then f(g) = $a_n$ where $a_i = g(i)$ with i $\in$ $\mathbb{N}$? $\endgroup$ – Rachel Mar 30 '14 at 23:25
0
$\begingroup$

Your second set contains an isomorphic copy of $[0,1]$ as a subset (fix all but the first coordinate), and so can't be countable. You're first set is uncountable for the same reason; consider the subset where each coordinate is the same. What is this isomorphic to?

$\endgroup$

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.