I want to check whether the following set and $\mathbb{N}$ are equinumerous: $$\{f \in \mathbb{Z}^{\mathbb{N}}: \forall n \in \mathbb{N} \ \ f(2n) + f(2n+1) = 0\}$$ I know the answer is they are not, however, I'm having trouble understanding why this is the case.

I get that $f$ are infinite sequences with terms from $\mathbb{Z}$. The sequences are of the form: $$\left\langle *, 1, -1, 5, -5, \dots \right\rangle$$ $$\left\langle *, 7, -7, -2, 2, \dots \right\rangle$$ $$\left\langle *, -3, 3, -15, 15, \dots \right\rangle$$ $$\left\langle *, -8, 8, 157, -157, \dots \right\rangle$$ $$\left\langle *, 0, 0, 0, 0, \dots \right\rangle$$ where $* \in \mathbb{Z}$.

Is there a relatively easy way to show this is not a countable set? My strong suspicion is that I'm supposed to use Cantor's diagonal argument but I can't put my finger on how to apply it.


We denote by $a_i^j$ the $i$th term of the $j$th function. We can write down tese functions as $$\left\langle a_0^0, a_1^0, a_2^0, a_3^0, a_4^0, a_5^0, \dots \right\rangle$$ $$\left\langle a_0^1, a_1^1, a_2^1, a_3^1, a_4^1, a_5^1, \dots \right\rangle$$ $$\left\langle a_0^2, a_1^2, a_2^2, a_3^2, a_4^2, a_5^2, \dots \right\rangle$$ $$\left\langle \dots, \dots, \dots, \dots, \dots, \dots \right\rangle$$

Now, we notice that for $$\left\langle a_0^0, a_1^0+1, a_2^0, a_3^0, a_4^0, a_5^0, \dots \right\rangle$$ $$\left\langle a_0^1, a_1^1, a_2^1, a_3^1+1, a_4^1, a_5^1, \dots \right\rangle$$ $$\left\langle a_0^2, a_1^2, a_2^2, a_3^2, a_4^2, a_5^2+1, \dots \right\rangle$$ $$\left\langle \dots, \dots, \dots, \dots, \dots, \dots \right\rangle$$ we can choose a sequence $$\left\langle *, a_1^2+1, *, a_3^2+1, *, a_5^2+1, \dots \right\rangle$$ where we choose $*$s such that the sequence satisfies our initial condition. This sequence is an element of $\mathbb{Z}^{\mathbb{N}}$. However, its second term differs from the second term of $f^1$, its fourth term differs from the fourth term of $f^2$ and so on, so this sequence is not one of $f$s. This means that $f$ is not surjective and the considered set is not countable.

  • 2
    $\begingroup$ The functions are fully determined by the odd positions in the sequence. Assume the set is countable and construct a function that differs from function $1$ at the $1$'sth position, differs from function $2$ at the $3$rd position ... $\endgroup$ – Winther Dec 7 '16 at 14:24
  • $\begingroup$ Thanks for that. I wrote down an answer based on your comments. $\endgroup$ – Zelazny Dec 7 '16 at 15:29

Your assertion that each sequence is fully defined by its two first terms is in error. You have overlooked sequences of (e.g) the following forms:

  <*, 1,-1, -1,1, 1,-1, -1,1 ... >

  <*, 1,-1, -1,1, -1,1, 1,-1 ... >

  <*, 1,-1, 2,-2, 3,-3, ... >

  <*, 1,-1, 4,-4, 1,-1, 5,-5, 9,-9, ... >

  <*, -7,7, -1,1, -8,8, -2,2, -8,8, ... >
  • $\begingroup$ Thanks for pointing this out. I've edited my original question. $\endgroup$ – Zelazny Dec 7 '16 at 14:18

This might help. Cantor's goal was to show that the power set $2^{\mathbb{N}}$ had a cardinality strictly greater than the natural numbers. So a big picture view of what is going on here is taking $\{0,1\} \subset \mathbb{Z}$ which implies that $\lvert 2^{\mathbb{N}}\rvert \leq \lvert\mathbb{Z}^{\mathbb{N}}\rvert$. Where $2^{\mathbb{N}}$ is the set of all functions $\sigma:\mathbb{N} \to \{0,1\}$ which is a subset of the set $\mathbb{Z}^{\mathbb{N}}$ of ALL (as the answer above mentioned) functions $\rho:\mathbb{N} \to \mathbb{Z}$. So the cardinality of the specific set you've constructed in your answer lies somewhere "between" $2^{\mathbb{N}}$ and $\mathbb{Z}^{\mathbb{N}}$ (i.e. they have the same cardinality)

If you can convince yourself that the power set of the naturals is uncountable (which seems to be more the part which you are stuck on), then you will see why this is true. Thinking about the power set as a space of functions might help you see the essence of what Cantor's argument is rather than weird strings of 1's and 0's.


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.