I have seen a few proofs which shows the countability of rationals (denoted $\mathbb{Q}$). But they always involve picking a representation for the rationals (like fractions,Calkin-Wilf trees) and then showing a bijection between $\mathbb{N}$ and that representation. Is there some sort of canonical bijection between $\mathbb{Q}$ and $\mathbb{N}$?

P.S By canonical bijection, I mean one which doesn't rely on a specific representation of $\mathbb{Q}$.

  • 1
    $\begingroup$ Fractions are very much inherent in the definition of the rationals, so if you don't like using those then anything else will probably only be worse. $\endgroup$ – Ragib Zaman Sep 9 '12 at 19:23
  • $\begingroup$ Yes, how do you define the rationals, I'd not as pairs of relatively prime integers, or as equivalnce classes or pairs of arbitrary integers? $\endgroup$ – Thomas Andrews Sep 9 '12 at 19:25
  • 5
    $\begingroup$ How do you define $\mathbb Q$ if fractions feel arbitrary to you? $\endgroup$ – Henning Makholm Sep 9 '12 at 19:26
  • 2
    $\begingroup$ @Thiagarajan: That description does not define the rationals uniquely -- it is also satisfied, for example, by the set of real numbers of the form $\frac{a+b\sqrt 2}{c}$ where $a$ and $b$ are integers and $c$ a nonzero integer. There are also uncountable sets that satisfy it (at least if we assume the Axiom of Choice). $\endgroup$ – Henning Makholm Sep 9 '12 at 19:33
  • 1
    $\begingroup$ What about the fact the the cardinality of any field of fractions is the same as the underlying integral domain? This as least only relates the integers and rationals by algebraic structure. $\endgroup$ – user452 Sep 9 '12 at 19:47

If you really want to define the rationals without using fractions, you could define them as the smallest subset of $\mathbb R$ that contains $1$ and is closed under the four basic arithmetic operations.

(Here we need to explicitly ignore the circular feeling that we need the rationals in order to be sure $\mathbb R$ exists in the first place. If we put our minds to it, we could probably find some way to side-step that -- for example by defining $\mathbb R$ as the completion of the ordered ring of terminating decimal fractions, and then proving separately that what we get is a complete ordered field).

Then we can construct $\mathbb Q$ as follows: Let $f$ be a function that maps finite subsets of $\mathbb R$ to other finite subsets of $\mathbb R$ as follows: $$ \begin{align} f(A) = A & \cup \{ a+b \mid a,b\in A \} \cup \{ a-b \mid a,b \in A \} \\& \cup \{ a\times b \mid a,b\in A \} \cup \{ a\div b \mid a,b \in A, b\ne 0 \} \end{align}$$ Then by our definition above we can show $$ \mathbb Q = f(\{1\}) \cup f(f(\{1\})) \cup \cdots = \bigcup_{n\ge 1} f^n(\{1\}) $$ Since a countable union of finite sets is countable, $\mathbb Q$ must be countable.

However, one might very well object that this is really just a thin disguise of choosing arithmetic expressions as "representations" of the rationals.

  • $\begingroup$ Thanks. I phrased the question poorly. But this was still useful in that the above discussion forced me to figure out what rationals really are. I learnt $\mathbb{Q}$ is homeomorphic to any countable and metrizable topological space with no isolated points. So to some extent it seems countabilty is built into the definition of rationals. $\endgroup$ – Thiagarajan Sep 9 '12 at 19:51
  • $\begingroup$ @Thia: it is not built into some definitions. If you define $\mathbb{Q}$ as the fraction field of $\mathbb{Z}$, then it is a theorem that $\mathbb{Q}$ is countable. $\endgroup$ – Qiaochu Yuan Sep 9 '12 at 19:54
  • $\begingroup$ @Thiagarajan: But this topological characterization of $\mathbb Q$ (it it's true) tells us nothing about arithmetic in $\mathbb Q$, and is therefore not a possible definition of $\mathbb Q$ for most mathematical purposes. $\endgroup$ – Henning Makholm Sep 9 '12 at 19:58
  • 1
    $\begingroup$ You could define $\mathbb{Q}$ in a similar way, but without using $\mathbb{R}$, as the unique field that embeds into any field of characteristic zero. Of course at some point you would have to prove that a field of characteristic zero exists, so you could construct $\mathbb{Q}$ with fractions in the usual way, and then use the uniqueness to show that the isomorphism type of $\mathbb{Q}$ is independent of the particulars of the construction. $\endgroup$ – Trevor Wilson Sep 9 '12 at 20:05
  • 1
    $\begingroup$ @Thiagarajan The theory of ordered fields, without the LUB axiom, is satsified by $\mathbb{R}$ and by $\mathbb{Q}$ and by many other structures, both countable and uncountable. The theory of ordered fields, with the negation of the LUB axiom added, is satisfied by $\mathbb{Q}$ but again also by many other structures, both countable and uncountable. $\endgroup$ – Trevor Wilson Sep 9 '12 at 20:14

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.