0

The instruction for proving that the set of rational numbers, $\mathbb{Q}^{+}$, is countable, is as follows:

  1. First assume each $x\in \mathbb{Q}^{+}$ is in reduced form.
  2. Construct a one-to-one function $p: \omega \times \omega \rightarrow \omega$.
  3. Using $p$ to show that $\mathbb{Q}^{+}$ is countable.

Following this path, I constructed the following proof (step 2. is done earlier in another exercise, so I skip this step):

Assume 1. holds, we have that $(\forall x\in \mathbb{Q}^{+})(x\text{ in reduced form })\rightarrow (\exists!n\in \mathbb{N})(\exists!m\in \mathbb{N})(x=n/m)$ so the function $g: \mathbb{Q}^{+}\rightarrow \omega \times \omega$ defined by $g=\{\langle x, \langle n, m\rangle \rangle: (\exists x\in \mathbb{Q}^{+}) \wedge(x\text{ in reduced form}) \wedge (x=n/m)\}$ is one-to-one. So $p\circ g:\mathbb{Q}^{+}\rightarrow \omega$ is also one-to-one. So $\mathbb{Q}^{+}$ consists of all $x$ in reduced form is countable.

This proof explicitly assumes that $1/2$ and $2/4$ represent the same number $.5$ in $\mathbb{Q}^{+}$ and only one of them is counted not both.

However, I found another proof based on Cantor's construction of rational numbers which does count both $1/2$ and $2/4$ separately. So, I'm quite confused over whether $1/2$ and $2/4$ should be counted as two different elements of $\mathbb{Q}^{+}$ or not?

Asaf Karagila
  • 393,674
Tran Khanh
  • 546
  • 2
    If the set of rationals counting equivalent fractions separately is countable, then a smaller set will also be countable. – user317176 Oct 30 '23 at 07:36
  • @user317176 that's right! But I want to find out how the steps in the instruction could produce the proof not getting it from other proof. I'm suspecting that my proof is missing the part for counting all other elements $a/b\in \mathbb{Q}^{+}$ such that $a/b=n/m=x$. – Tran Khanh Oct 30 '23 at 07:55
  • Usually , duplicates are not considered in the proof that the rational numbers are countable. If we hit some number , we already have written down , we omit it and go to the next. – Peter Oct 30 '23 at 12:31
  • 1/2 and 2/4 are the same number. But even if we consider them in the counting procedure , the set keeps still countable. – Peter Oct 30 '23 at 12:32
  • @Peter it's true, and that's what I haven't figured out how to do using the above-mentioned instruction. – Tran Khanh Oct 30 '23 at 15:34
  • @Peter I realized that if $1/2$ and $2/4$ are counted separately then we can just drop the assumption that $x$ is in reduced form to get the result. But I'm still confusing why two different proofs co-exist while the counting methods are different. – Tran Khanh Oct 30 '23 at 16:29
  • Please don't add irrelevant tags back. – Asaf Karagila Oct 30 '23 at 20:19
  • Why is it confusing that there are different proofs using different counting methods? Many theorems have many proofs. New proofs of the Pythagorean theorem still come up from time to time. – Ethan Bolker Oct 30 '23 at 20:36
  • One counts $1/2$ and $2/4$ separately the other don't while the set of discourse, $\mathcal{Q}^{+}$, is the same. It's what confusing me. – Tran Khanh Oct 31 '23 at 02:13

0 Answers0