Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Some days ago I've seen Cantor's diagonal argument, and it presented a table similar to the following one:

$$\begin{matrix} {\frac{1}{1}}&{\frac{1}{2}}&{\frac{1}{3}}&{\frac{1}{4}}&{\cdots}\\ {\frac{2}{1}}&{\frac{2}{2}}&{\frac{2}{3}}&{\frac{2}{4}}&{\cdots}\\ {\frac{3}{1}}&{\frac{3}{2}}&{\frac{3}{3}}&{\frac{3}{4}}&{\cdots}\\ {\vdots}&{\vdots}&{\vdots}&{\vdots}&{\ddots} \end{matrix}$$

If we follow some diagonals, we're going to meet repeated numbers such as $1/1,\; 2/2,\; \cdots$ so what are the conditions to find only non repeated numbers? I had a feeling that the set for such a task is the following one:

$$\{0,1\}\cup \{a/b: \, a,b\in\mathbb{Z}, \;b\neq 0, \; b \in primes, \; a\neq b \}\tag{1.0}$$

The first idea I had was only for the positive rationals:

$$\{0,1\}\cup \{a/b: \, a,b\in\mathbb{N}, \;b\neq 0, \; b \in primes, \; a\neq b \}\tag{1.1}$$

But I'm really not sure of what I'm doing nor have I the mental tools to prove that, I just had a feeling. I was quite certain (with some magical mystery in my head) that $(1.1)$ was right, but I extended it also to negative rationals in $(1.0)$ and I'm a little less certain that it would work for this specific case.

I just dropped some tags which I believe that are related somehow, but I'm not sure of what tags would be adequate, if you know it, please edit.

share|improve this question
4  
$b\in Prime$ is too strong, you won't be able to enumerate $\frac{1}{6}$ –  Gina Jan 5 at 7:32
1  
+1 for my FB friend. –  B. S. Jan 5 at 7:44
1  
See math.stackexchange.com/questions/7643/… and the questions linked there. –  Martin Sleziak Jan 5 at 12:31
4  
As a note, this is not Cantor's diagonal argument, which refers to his proof that the real numbers are uncountable. –  Mike Miller Jan 5 at 13:08
1  
@Mike, actually some people speak of Cantor's first and second diagonal argument, and the first is is this one which shows $\lvert\mathbb N\times\mathbb N\rvert=\lvert\mathbb N\rvert$. Still I agree that the diagonal argument should refer to the second. –  Carsten Schultz Jan 5 at 13:29
show 1 more comment

4 Answers 4

up vote 15 down vote accepted

This should ideally be a comment but I can't comment yet.

The Wilf-Calkin tree also enumerates positive rationals.

Wikipedia: Calkin-Wilf tree

share|improve this answer
1  
Don't mind. Your answer is welcome. –  Vladimir Putin Jan 5 at 8:16
add comment

There's an easy method: just take the reduced fractions.

Another easy method is to note the diagonal argument has already given you an ordering on all of the positive fractions. So to take each positive rational exactly once, all you have to do is take only those fractions that don't have an equal value appearing earlier in the sequence.

There are more elegant schemes too: for example, Farey sequences can give you rationals from 0 to 1, and the the related Stern-Brocot tree for all positive rationals.

share|improve this answer
add comment

Remember that each rational number admit an unique reduced form with positive denominator. So all you need to do is to enumerate all of them. $\frac{a}{b}$ is in reduced form with positive denominator if $\gcd(a,b)=1$ and $b>0$.

So there are plenty of way to go about this really. One way, is to fill up the table with each row corresponde to a $b\in\mathbb{Z}^{+}$ with $b$ increasing. The 0th row contains just $0$. After that for each row, from left to right will will have one block for each value of $a$ where $\gcd(a,b)=1$ and $0<a\leq b$; each block will contain $\frac{a}{b},-\frac{a}{b},\frac{b}{a},-\frac{b}{a}$. Then each row is finite, and you can enumerate them row by row rather than diagonally.

Just to elaborate, the 6th row, we have $b=6$ and thus the row look like this:

$\frac{1}{6},-\frac{1}{6},\frac{6}{1},-\frac{6}{1},\frac{5}{6},-\frac{5}{6},\frac{6}{5},-\frac{6}{5}$

share|improve this answer
    
Is $0<a<\leq b$ supposed to be $0<a\leq b$? (Probably a typo.) –  Martin Sleziak Jan 5 at 12:34
    
Thanks, I fixed it. –  Gina Jan 5 at 13:20
add comment

Aside from the bijections given by the Cantor Pairing Function, the Stern-Brocot tree or the Calkin-Wilf tree mentioned elsewhere, I'd like to present a nice bijection between the natural numbers $\mathbb{N}$ and the rationals $\mathbb{Q}$ which makes use of the fact that both the natural numbers and the positive rationals have a unique prime factorization.

Let $\rho$ be a bijection between the natural numbers and the non-negative integers $\mathbb{N}_0:=\mathbb{N}\cup\{0\}$, e.g. $$\rho:n\mapsto n-1.$$

Let $\sigma$ be a bijection between $\mathbb{N}_0$ and $\mathbb{Z}$ which fixes $0$, e.g. $$\sigma:n\mapsto\left\{\begin{matrix}{n/2}&{n\text{ even}}\\{-(n+1)/2}&{n\text{ odd}}\end{matrix}\right.$$

Next, let $\mathbb{P}=\{p_1, p_2, p_3, \ldots\}$ be the set of prime numbers.

Let $n$ be a positive integer. Since in $\mathbb{N}$, factorization into prime factors is unique, there exist uniquely determined exponents $e_1, e_2, e_3, \ldots$ such that $$n=\prod_{i=1}^\infty p_i^{e_i}.$$

(Note that infinitely many $e_i$ are zero, so the right-hand side is a well-defined expression.)

Now, define $$\tau^*(n):=\prod_{i=1}^\infty p_i^{\sigma(e_i)}.$$

Then, it is easy to see that

  • $\tau^*(n)$ is well-defined (i.e. the product on the right-hand side converges),
  • $\tau^*(n)$ is a positive rational,
  • the construction yields different values $\tau^*(m)$, $\tau^*(n)$ for different arguments $m$, $n$.

Therefore, $\tau^*$ yields a bijection between $\mathbb{N}$ and the positive rationals $\mathbb{Q}^+$ that can be extended to a bijection $\tau$ between $\mathbb{Z}$ and all of $\mathbb{Q}$: $$\tau:z\mapsto\left\{\begin{matrix}{\tau^*(z)}&{z>0}\\{0}&{z=0}\\{-\tau^*(-z)}&{z<0}\end{matrix}\right.$$

Finally, composition of $\rho$, $\sigma$ and $\tau$ gives a bijection $\tau\circ\sigma\circ\rho:\mathbb{N}\to\mathbb{Q}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.