I don't fully understand the proof I have been given for ℤ^n being countable. I'm getting lost at the bit "Let µk : Z^k × Z → Z×Z" onwards. Could anyone maybe try explaining it in a different way please?
Thanks in advance!
[Math] Proof that ℤ^n ( for all n∈ℕ) is countable
elementary-set-theory
Related Solutions
In general, if $m$ is any cardinal number we have $2^m > m$. I think this is a Theorem by Cantor.
The proof is very simple:
If $f: A \to {\mathcal P}(A)$ is any function then the set $B= \{x\in A \mid x \notin f(x) \}$ cannot be in the image of $f$ (the argument is exactly the liar paradox)...
This means that no function from $A$ to ${\mathcal P}(A)$ can be surjective.
Added You can also prove that $2^{\aleph_0} > \aleph_0$ by showing that $2^{\aleph_0}$ is the cardinality of $[0,1)$.
To do this, all you have to do is to write all numbers in $[0,1)$ in binary, and then $f: [0,1) \to P(N)$ can be defined as $f(x)=$ the set of positions of $1's$ in the binary representation of $x$. This function is injective (and almost surjective), thus $P(N)$ has at least as many elements as $[0,1)$.
Cantor diagonalization argument shows that $[0,1)$ is uncountable, thus $P(N)$ is also uncountable...
First of all, let me assure you there is no general "explicit" bijection. The reason is that the axiom of choice is needed to choose enumerations for each countable set (separately). In its absence, it is consistent that a countable union of countable sets can be uncountable (in fact, it could be equal to the real numbers!).
But suppose that we are given enumerated sets, namely $S_n$ and $f_n$ which is an injection from $S_n$ to $\Bbb N$. In this case we can explicitly define an bijection from $\bigcup S_n$ into $\Bbb N$.
But why? That would be working quite hard to make all the indices fall into place. Instead we want to use the following theorems:
- The product of two countable sets is countable. Therefore $\Bbb{N\times N}$ is countable.
- An infinite subset of a countable set is countable.
So it suffices to show that there is an injection into a countable set, and we're done.
We might want to say, map $s_{n,m}$ to the ordered pair $(n,f_n(s_{n,m}))$, which will be an injection from $\bigcup S_n$ into $\Bbb{N\times N}$. But what if the $S_n$'s are not pairwise disjoint? Then you might have an element mapped into two places at once.
To overcome this difficulty we can do one of two things:
Make then $S_n$'s disjoint, by considering, perhaps $S_n\times\{x_n\}$, where $x_n$ is a set which will guarantee that these are disjoint. We can prove that such $x_n$'s exist. Or perhaps by redefining $S_n'=S_n\setminus\bigcup_{k<n}S_k$, which will remove the duplicates and perhaps empty out a few of the sets. Either option works.
Just do the second option implicitly, by mapping $s_{n,m}$ to $(n,f_n(s_{n,m}))$ if $n$ is the smallest number such that $s_{n,m}\in S_n$.
In either case, this makes the above injection into $\Bbb{N\times N}$ well-defined. So now either that $\bigcup S_n$ is finite or has a bijection with an infinite subset of a countable set, so it is countable.
Best Answer
Suppose we know there is some bijection $$f:\mathbb{Z}^k\to\mathbb{Z}$$ Now, we can define a bijection $$g:\mathbb{Z}^{k+1}\to\mathbb{Z}\times \mathbb{Z}$$ as follows: for every $(a_1,a_2,\ldots,a_{k+1})\in\mathbb{Z}^{k+1}$, we say that: $$g(a_1,a_2,\ldots,a_{k+1})=(f(a_1,a_2,\ldots ,a_k),a_{k+1})$$ We already have a bijection $$h:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$$ So now, $h\circ g$ is a bijection from $\mathbb{Z}^{k+1}$ to $\mathbb{Z}$. So if $\mathbb{Z}^k$ is countable, then $\mathbb{Z}^{k+1}$ is as well.