$\mathbb{N} \times \mathbb{N}$ is countable? Until this morning I was pretty sure that the answer was yes. It should have the same cardinality of $\mathbb{Q}$, which is countable. Besides the cartesian product of countable set should be countable (http://en.wikipedia.org/wiki/Countable_set). 
Yet this morning a professor of mine told me that it is not and gave me this proof: 
It is clear that $\mathbb{N} \times \{0,1\} \subset \mathbb{N} \times \mathbb{N}$. Now, an element of $\mathbb{N} \times \{0,1\}$ can be seen as a succession $\{x_n\}_{n \in \mathbb{N}}$ where $x_n$ can be $0$ or $1$.
I.e. if we consider $\{x_n\}_{n \in \mathbb{N}}$ the binary representation of the decimal part of a real number, then $\mathbb{N} \times \{0,1\}$ should be the set of all real numbers between $0$ and $1$, i.e. $[0,1]$, which is uncountable. So also $\mathbb{N} \times \mathbb{N}$.
I feel a bit confused as I don't see any error in my professor's proof, yet I don't see how can this be coherent with the countability of the cartesian product of countable sets. 
 A: An element of $\Bbb{N} \times \{0,1\}$ is a tuple $(n, \varepsilon)$ with $\varepsilon \in \{0,1\}$.
A succsession $(x_n)_n$ (also called sequence) is an element of $\{0,1\}^{\Bbb{N}}$, the set of all maps $\Bbb{N} \to \{0,1\}$.
So the argument shows that $\{0,1\}^\Bbb{N}$ is uncountable, and so is
$$
\Bbb{N}^\Bbb{N} \supset \{0,1\}^\Bbb{N},
$$
the set of all maps $\Bbb{N} \to \Bbb{N}$.
But this does not imply that the set $\Bbb{N} \times \{0,1\}$ is uncountable. You can also write
$$
\Bbb{N} \times \{0,1\} = \bigcup_n \{(n,0), (n,1)\},
$$
so that it is clear that $\Bbb{N} \times \{0,1\}$ is countable as a countable union of finite (hence countable) sets.
So either your professor or you were confused, or you did not completely understand what your professor wanted to say.
All in all: $\Bbb{N} \times \Bbb{N}$ is countable.
A: Define $\phi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by $\phi(n,m)=2^n3^m.$ you can convince yourself that $\phi$ is injective. so $\phi$ restrcited to its range is bijective. Thus card$(\mathbb{N}\times\mathbb{N})=$card$(\mathbb{N})$
A: Besides the obvious mistake in interpretation of multiplication and exponentiation, as pointed out by PhoemueX, here is some other points to note:

*

*If we consider a binary sequence as a decimal representation, we will definitely not get the entire interval $[0,1]$. For example $0.5$ will never ever ever be equal to a number whose decimal expansion consists only of the digits $0,1$. (At least not if set theory is consistent...)


*If we consider the binary sequence as a binary representation of a real number in $[0,1]$ then we get some numbers twice, for example $0.0\overline 1$ and $0.1\overline 0$ are both exactly $\frac12$ (remember that these numbers are binary, not decimal!).
So while we get that the result is the entire interval, it's not a bijection, so we don't quite have that $\Bbb N\times\{0,1\}$ or even $\{0,1\}^\Bbb N$ is "the set of all numbers in $[0,1]$", since this seems to imply that each number has a unique representation as a binary string.
In any case, the crux of the mistake is the confusion (perhaps due to a communication error when asking the question) between the Cartesian product and set exponentiation.
