2
$\begingroup$

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
    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.2012-09-09

1 Answers 1

3

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.

  • 1
    @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.2012-09-09