Quick bijection between $\mathbb{Q}\cap (a,\ b)$ and $\mathbb{Q}$ [duplicate]

This question already has an answer here:

I need a really quick way of showing there's a bijection from $\mathbb{Q}\cap(a,\ b)$ to $\mathbb{Q}$ for any real numbers $a < b$. I attempted a few ways but I'm drawing a blank right now .Nothing I've worked on is fruitful (it either goes nowhere or is much too complicated) so I'm omitting it from the question. Any simple ideas? Mainly I'm looking for something that can be rigorously justified and explained in a matter of no more than three to four lines.

Clarification: I don't need to construct a bijection, I just need to show that there is one.

Clarification 2: The context I'm working in doesn't have a definition of "countable", so I can't just say both sets are countable unfortunately.

Clarification 3: We know that there exists a bijection from $\mathbb{Q}$ to $\mathbb{N}$. Our construction was essentially that you can list all elements of $\mathbb{Q}$ in a grid and spiral outwards from the origin, ignoring duplicates, and assigning the next natural to the next unique rational in the spiral path.

marked as duplicate by Asaf Karagila♦ elementary-set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 15 '16 at 22:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• An explicit bijection or a proof that a bijection exists? – Alexis Olson Oct 15 '16 at 21:20
• @AlexisOlson A proof that a bijection exists. – user3002473 Oct 15 '16 at 21:20
• They both are countable sets. – Jack D'Aurizio Oct 15 '16 at 21:22
• If you can't directly just say that they are both countable, use this fact indirectly: give a bijection between each with the natural numbers. – Morgan Rodgers Oct 15 '16 at 21:25
• Do you know how to construct a bijection between $\mathbb{Q}$ and $\mathbb{N}$ and, if yes, how? That would frame your question better in terms of what you can use vs. what not. – dxiv Oct 15 '16 at 21:38

5 Answers

Let's map $[0,+\infty)\cap \mathbb Q$ bijectively onto $[0,1)\cap \mathbb Q$ with $$f(x) = 1-\frac{1}{x+1}$$ and map $(-\infty,0) \cap \mathbb Q$ bijectively onto $(-1,0)\cap \mathbb Q$ with $-f(-x)$.

This has the advantage that it is the restriction of a homeomorphism $(-\infty,+\infty)\to (-1,1)$ to the rationals.

Fron this we can do any $(a,b)$ with rational endpoints.

• Just a (minor) nitpick about the last line, but the question doesn't assume that $a,b \in \mathbb{Q}$. – dxiv Oct 15 '16 at 22:18

The intersection $\mathbb Q \cap (a,b)$ is countable.

Hint based on Clarification 3:

We know that there exists a bijection from $\mathbb{Q}$ to $\mathbb{N}$. Our construction was essentially that you can list all elements of $\mathbb{Q}$ in a grid and spiral outwards from the origin, ignoring duplicates, and assigning the next natural to the next unique rational in the spiral path.

$\mathbb{Q} \cap (a,b)$ is clearly a subset of $\mathbb{Q}$, and it is clearly infinite. Take then the previously defined "grid" and remove from it any rationals that fall outside $(a,b)$. By the same "spiral" argument, you can define a bijection between the numbers left unremoved i.e. $\mathbb{Q} \cap (a,b)$ and $\mathbb{N}$. Once you have the bijections $f:\mathbb{Q} \to \mathbb{N}$ and $g:\mathbb{Q} \cap (a,b) \to \mathbb{N}$, you have the bijection $g \circ f^{-1} :\mathbb{Q} \cap (a,b) \to \mathbb{Q}$.

1) since $\Bbb Q$ is dense in $\Bbb R$, $\mathbb{Q}\cap (a,\ b)$ is an infinite sized set

2) $\mathbb{Q}\cap (a,\ b) \subset \Bbb Q$

3) then by (1) the same bijection you constructed from $\Bbb Q \to \Bbb N$ also maps all elements of $\mathbb{Q}\cap (a,\ b)$ onto $\Bbb N$. And since (1) shows there are an infinite number of elements then such a bijection exists.

We can describe $Q:=\mathbb{Q}\cap(a,b)$ as $$Q=\{\frac{r}{s}:r\in\mathbb{Z}, s\in\mathbb{Z}^+,gcd(|r|,s)=1,as<r<sb\},$$ where the condition $gcd(|r|,s)=1$ ensures that we are counting each rational in $Q$ only once. This implies that $Q$ can be written as the disjoint union $$Q=\bigcup_{s\in\mathbb{Z}^+}Q_s,$$ where $Q_s:=\{\frac{r}{s}\in Q:r\in\mathbb{Z}\}$. Clearly every $Q_s$ is finite (and nonempty if $s(b-a)>1$) so you might write the elements (if any) of $Q_1$ in a row, the elements (if any) of $Q_2$ in a second row, and so on. This arrangement allows you to Cantor-diagonalize in the same fashion that the diagonal argument for $\mathbb{Q}$, concluding that the cardinal of $Q$ is the same as that of $\mathbb{N}$, and so that that of $\mathbb{Q}$ (which by definition means that there exists a bijection between $Q$ and $\mathbb{Q}$).