2

I want to find some simple surjective function from $\mathbb{N}$ to $\mathbb{Q}$.

Since $\mathbb{Q}$ is countable, it should be possible.

Can someone find such function?

Mykybo
  • 1,027
  • Every natural number can be written in base-$2$ and such string can be interpreted as a path in the Stern-Brocot tree. That provides a bijective map from $\mathbb{N}$ to $\mathbb{Q}\cap(0,1]$. – Jack D'Aurizio Oct 13 '16 at 15:45
  • 1
    Depending on what you mean by simple, the inverse of the Cantor pairing function provides a surjective map from $Bbb N$ to the positive rationals. You can patch up the negatives by taking even $k$ to the positive rational that comes from $k/2$ and odd $k$ to the negative of the rational that comes from $(k-1)/2$ – Ross Millikan Oct 13 '16 at 15:45
  • Anyway, the existence of a bijection between $\mathbb{N}$ and $\mathbb{Q}$ is usually proved through the Cantor-Bernstein theorem, i.e. by showing that there is an injective function from $\mathbb{N}$ to $\mathbb{Q}$ and an injective function from $\mathbb{Q}$ to $\mathbb{N}$. An explicit bijection is doomed to be quite involved, indeed. – Jack D'Aurizio Oct 13 '16 at 15:47
  • So if you only want surjective and not injective... couldn't you go $0,1/1, 2/1, 1/2, 3/1, 2/2, 1/3 \ldots$, it's the usual take the sets $A_n={1/n,2/n,3/n \ldots}$, one above the other and count along diagonals. Now to get the negatives numbers also, just add them in: $0,1/1, -1/1, 2/1, -2/1 , 1/2, -1/2, 3/1, -3/1, 2/2, -2/2, 1/3, -1/3 \ldots$? I added zero in at the front of the sequence because otherwise it wouldn't be there. – snulty Oct 13 '16 at 16:02
  • See this picture, and there's no point in skipping repeated numbers: http://faculty.uml.edu/klevasseur/courses/m419/proj/RationalCount/Images/RationalCount_gr_1.gif – snulty Oct 13 '16 at 16:08

3 Answers3

7

Consider $A=\{2^p3^q, p,q\geq 1 \}$, $B=\{5^r7^s, r,s \geq 1\}$, $A\bigcup B\subset N$, define $f(2^p3^q)={p\over q}, f(5^r7^s)=-{r\over s}$ and $f(n)=0$ if $n\in N-A\bigcup B$.

Tsemo Aristide
  • 87,475
1

Let $$f(n)=\frac{(n\bmod \lfloor\sqrt n\rfloor)- \lfloor\sqrt n/2\rfloor}{\lfloor\sqrt[4]n\rfloor} $$

Hagen von Eitzen
  • 374,180
0

First, put the set of all half-open intervals $[n, n+1)$, $n \in \Bbb{Z}$, into bijection with the naturals, numbering them $I_1, I_2,...$. The rational numbers in $[n, n+1)$ can be counted as follows: $n, n+1/2, n+1/3, n+ 2/3,...$: first partially order the rationals in that interval by their denominators written in lowest form, then order the sets of rationals with the same denominator by their numerators. This is a total order and you can just count them one after the other. Clearly this is a bijection. Now you can define $f(k,m)$ to be the $m$th rational listed in $I_k$.This a bijection between $\Bbb{Q}$ and $\Bbb{N}^2$, and the latter set is countable by a canonical bijection.

Vik78
  • 3,877