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
    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.2012-09-09
  • 0
    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?2012-09-09
  • 5
    How do you _define_ $\mathbb Q$ if fractions feel arbitrary to you?2012-09-09
  • 0
    @ThomasAndrews Well, one definition which I know of is to consider rationals as a set of objects satisfying all the axioms satisfied by the reals except the least upper bound axiom.2012-09-09
  • 2
    @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).2012-09-09
  • 0
    @RagibZaman I have no issues with the proof involving fractions. I am just curious as to whether there is a proof which does not involve choosing a representation.2012-09-09
  • 0
    @HenningMakholm Ok. That I didn't realize. So the only way to unqiuely characterize rationals is via fractions?2012-09-09
  • 0
    @Thiagarajan That doesn't describe the rationals, because it could describe, for example, $\mathbb Q[\sqrt{2}]$.2012-09-09
  • 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.

  • 0
    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.2012-09-09
  • 0
    @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.2012-09-09
  • 0
    @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.2012-09-09
  • 1
    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.2012-09-09
  • 0
    @HenningMakholm Ah!! Ok. I didn't think of that. The problem was that I have always thought (wrongly) that $\mathbb{Q}$ is simply the ordered field which you get if you take the reals and throw away the LUB axiom. That was the definition of $\mathbb{Q}$ that I had in mind when I asked the question. Thanks for setting me right.2012-09-09
  • 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