Which of the following sets is bijection to set of Integers?

Question

Which of the following sets is bijecton to set of integers:

A. $(\mathbb{Z}^{101})$
B. $(\mathbb{Z} \times \mathbb{Q})$
C. $(\mathbb{Z} \times \mathbb{R})$
D. $(\mathbb{R}^2)$

This was one of the entrance test questions for a college I applied to. I know set of real numbers is not countable so options C and D are not possible. But I am confused between A and B.

I also know that set Z and Q individually are countable hence bijection to Integers. Bijection from Q to set of integers can be proved using diagonalization with which I am familiar.

I cannot think of any theories that can be useful in making this decision. Can you point to any such theories? Though the test is over, I am still curious to know correct answer and why.

Answer 1

If a set $A$ is countable, then $A^n$ is countable for each nonnegative integer $n$. However, the real numbers are not countable.

Answer 2

If $A,B$ are countable and if $\Bbb{N}\times\Bbb{N}$ is countable then $A\times B$ is also countable.

Proof: Since $A,B$ are countable there exist a bijection $f: A\to \Bbb{N},g: B\to\Bbb{N}$,so in fact there exists a bijection $t: A\times B\to \Bbb{N}\times \Bbb{N}$ which is $t(x,y)=(f(x),g(y))$.

To show that $\Bbb{N}\times\Bbb{N}$ you could use a Cantor pairing function,also you could use Cantor–Schröder–Bernstein which states that if you show that there exist a injection between $\Bbb{N}\times \Bbb{N}\to \Bbb{N}$ and between $\Bbb{N}\to\Bbb{N}\times \Bbb{N}$ then there exists a bijection between those two sets.

Example of a bijective function from $\Bbb{N}\times \Bbb{N}\to \Bbb{N}$ is $f(x,y)=2^{x-1}(2y-1)$.

Lets get back to the problem so $\Bbb{Z}\times\Bbb{Z}$ is countable,so is $(\Bbb{Z}\times\Bbb{Z})\times\Bbb{Z}$, inductively one can find that $\Bbb{Z}^n$ is countable for every $n$.