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$

3 Answers 3

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
    Commented Mar 30, 2014 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
    Commented Mar 30, 2014 at 23:25
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
    Commented Apr 9, 2014 at 2:04
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .