0
$\begingroup$

Prove that set $ \mathbb{Z}×\mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.

It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $\mathbb{Z} \times \mathbb{Q}$ to $\mathbb{N}$?

This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?

$\endgroup$
  • 1
    $\begingroup$ "It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection? $\endgroup$ – Arthur Nov 22 '18 at 8:07
  • 1
    $\begingroup$ @Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $\mathbb Z\times \mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious. $\endgroup$ – 5xum Nov 22 '18 at 8:34
  • $\begingroup$ " Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers." $\endgroup$ – Hagen von Eitzen Nov 22 '18 at 8:35
  • 1
    $\begingroup$ Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.) $\endgroup$ – Asaf Karagila Nov 22 '18 at 12:40
  • 1
    $\begingroup$ (Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".) $\endgroup$ – Asaf Karagila Nov 22 '18 at 12:43
0
$\begingroup$

Take the map $\left(m,\dfrac pq\right)\rightarrow (m,p,q) \quad p,q,m\in\mathbb{Z}\:$ i.e. mapping $\mathbb{Z}\times\mathbb{Q} \rightarrow \mathbb{Z}\times\mathbb{Z}\times\mathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.

$\endgroup$
0
$\begingroup$

Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ thinking about that.

Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.

$\endgroup$

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.