Analysis – Counting the rationals

It is easy to see that to show that $\mathbb Q$ is countable, it suffices to show the countability of $\mathbb Q^+$ , or even of $\mathbb Q\cap(0,1]$ .

There is a straightforward way of enumerating the latter: First list the fractions with denominator $1$ , then those with denominator $2$ (skipping those already listed), then those with denominator $3$ (again, skipping repetitions), etc. This list begins

$\displaystyle \frac11;\frac12;\frac13,\frac23;\frac14,\frac34;\frac15,\frac25,\frac35,\frac45;\dots$

Cantor’s first proof of the uncountability of the reals (the nested intervals argument) from 1874 proceeds as follows:

Given any (injective) sequence $a_1,a_2,\dots$ of reals, we want to exhibit a real that was not listed. There are two cases: Either there are $i\ne j$ with $a_i<a_j$ , and such that there is no $k$ with $a_k\in(a_i,a_j)$ , in which case we are obviously done, or (more interestingly), whenever $a_i<a_j$ , we can find an $a_k$ strictly in between (the range of the sequence is dense in itself). Assume we are in this situation.

Define two sequences $b_1,b_2,\dots$ and $c_1,c_2,\dots$ as follows:

First, $b_1=a_1$ and $c_1=a_2$ .
For definiteness, suppose that $a_1>a_2$ . The other case is treated similarly. Let $b_2$ be $a_i$ , where $i$ is least such that $a_i\in(c_1,b_1)$ . Then define $c_2$ as $a_j$ , where $j$ is least such that $a_j\in(c_1,b_2)$ .
In general, given $c_n<b_n$ , we define $b_{n+1}$ as $a_k$ , where $k$ is least such that $a_k\in(c_n,b_n)$ , and then define $c_{n+1}$ as $a_m$ , where $m$ is least such that $a_m\in(c_n,b_{n+1})$ . Note that these sequences are well defined, because of our density assumption.

The construction just described ensures that if $I_n=[c_n,b_n]$ , then:

For any $n$ , we have that $a_n\notin I_{n+1}$ , and
The intervals are nested and decreasing: $I_1\supsetneq I_2\supsetneq I_3\dots$

It follows (from the completeness of the reals) that $\bigcap_n I_n\ne\emptyset$ , and (from 1.) that any real in this intersection is not in the range of the sequence $a_1,a_2,\dots$

It turns out that if we carry out Cantor’s construction when the sequence of $a_i$ is the enumeration of the rationals in $(0,1]$ we began with, then $\bigcap_n I_n=\{1/\phi\}$ , where $\phi$ is the golden ratio.

This is proved in the nice note

Mike Krebs, and Thomas Wright. On Cantor’s first uncountability proof, Pick’s theorem, and the irrationality of the golden ratio, Amer. Math. Monthly, 117 (7), (2010), 633–637. MR2681523 (2011e:11127).

II.

There is a very nice enumeration of $\mathbb Q^+$ with combinatorial significance.

The rationals are used to label the nodes of the infinite complete binary tree, and the resulting enumeration simply follows the nodes of the tree, lexicographically.

We begin by putting $1/1$ at the root of the tree. Once a node has been labelled $m/n$ , its left successor is labelled $m/(m+n)$ , and its right successor is latex $(m+n)/n$ .

And that’s all! The list so produced begins

$\displaystyle \frac11;\frac12,\frac21;\frac13,\frac32,\frac23,\frac31;\dots$

The proof that this is indeed a bijective listing of $\mathbb Q^+$ is remarkably simple; one verifies in order the following claims:

The numerator and denominator of any of the assigned fractions are relative prime.
Every positive rational is assigned to some node.
Every positive rational is assigned to some node.

For this, one proceeds by induction. For example, if there is a fraction $m/n$ not in reduced form, and used as a label, pick such a fraction appearing in as small a level as possible, and note that the fraction cannot be $1/1$ . A contradiction is now attained by noting that $\mathrm{gcd}(m,n)=\mathrm{gcd}(m-n,n)=\mathrm{gcd}(m,n-m)$ .

Similarly, if $m/n$ appears in more than one node, then $m\ne n$ , and its immediate predecessor (either $(m-n)/n$ or $m/(n-m)$ , depending on whether $m>n$ or $m<n$ ) must also appear more than once.

Finally, if some fraction is not listed, we can choose its denominator $n$ least among the denominators of all skipped fractions, and then choose its numerator $m$ least among the numerators of all skipped fractions with denominator $n$ . A contradiction follows because $m\ne n$ , and if $m>n$ , then $(m-n)/n$ must also have been skipped, but $m-n<m$ , while if $m<n$ , then $m/(n-m)$ must have been skipped, but $n-m<n$ .

This enumeration is due to Neil Calkin and Herbert Wilf, who also showed that it has the following nice combinatorial properties:

There is a sequence $b(0),b(1),b(2),\dots$ of positive integers such that the $n$ -th fraction in the enumeration is just $\displaystyle \frac{b(n)}{b(n+1)}$ (in reduced form). In particular, the denominator of a fraction is the numerator of its successor in the enumeration. So $b(0)=1$ , $b(1)=1$ , $b(2)=2$ , $b(3)=1$ , $b(4)=3$ , $b(5)=2$ , $b(6)=3$ , etc.
In fact, $b(n)$ is precisely the number of ways of writing $n$ as a sum of powers of $2$ , where each power can be used at most twice. For example, $b(6)=3$ , because we can write $6$ as $2^2+2^1$ , as $2^2+2^0+2^0$ , or as $2^1+2^1+2^0+2^0$ .

This is proved in the nice note

Neil J. Calkin, and Herbert S. Wilf. Recounting the rationals, Amer. Math. Monthly, 107 (4), (2000), 360–363. MR1763062 (2001d:11024).

Some natural questions:

What can we say about the real(s) that comes out when the procedure from Cantor’s proof from section I is applied to this enumeration?
Any infinite path through the binary tree defines a sequence of rationals. What reals appear as limit points of these sequences?

This entry was posted on Wednesday, September 18th, 2013 at 7:38 pm and is filed under 414/514: Analysis I. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to Analysis – Counting the rationals

314 – Foundations of Analysis – Syllabus | A kind of library says:

January 29, 2014 at 10:57 pm

[…] 30. Comparing infinities. Counting the rationals. This week, office hours end at 2:30. Office hours this week will be on Friday, […]

Reply

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Categories

Mathoverflow

Convergence of $\sum(n^3\sin^2n)^{-1}$ May 14, 2010

I saw a while ago in a book by Clifford Pickover, that whether the Flint Hills series $\displaystyle \sum_{n=1}^\infty\frac1{n^3\sin^2 n}$ converges is open. I would think that the question of its convergence is really about the density in $\mathbb N$ of the sequence of numerators of the standard convergent approximations to $\pi$ (which, in itself, seems li […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Well known theorems that have not been proved February 3, 2023

I am not sure whether this qualifies as "well-known". Anyway, in set theory, in the study of the partition calculus (transfinite generalizations of Ramsey's theorem), effort centered for a while in studying relations of the form $$ \omega^m\to(\omega^n,k)^2 $$ for $m,n,k$ positive integers. Here, exponentiation is in the ordinal sense. This re […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper? December 23, 2014

This is Theorem 39 in the paper (see Theorem 4.(i) for a user-friendly preview). But the fact that $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ is older (1946) and due to Erdős, see here: Paul Erdős. Some set-theoretical properties of graphs, Univ. Nac. Tucumán. Revista A. 3 (1942), 363-367 MR0009444 (5,151d). (Anyway, it is probably easier to read a more modern pre […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for The Erdős-Turán conjecture or the Erdős' conjecture? June 3, 2013

One of the best places to track these things down is The mathematical coloring book, by Alexander Soifer, Springer 2009. Chapter 35 is on "Monochromatic arithmetic progressions", and section 35.4, "Paul Erdős’s Favorite Conjecture", is on the problem you ask about. As far as I can tell, the question is sometimes called the Erdős-Turán con […]

Andrés E. Caicedo

Relative densities September 12, 2013

Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory. How can I count the relative density of those $p$ (of the form $3k+1$) such that the equation $2=3x^3$ has no solutions modulo $p$? Really, even pointers on how to say anything […]

Andrés E. Caicedo

Math.StackExchange

Does $|X|^m\cdot n^{|X|}\le (n+m)^{|X|}$ hold without choice? February 16, 2023

As we learned in this question, provably in $\mathsf{ZF}$, if $X$ is infinite then $|X|^n\le(n+1)^{|X|}$ for any natural number $n$, and this is optimal in the sense that, in general, $n+1$ cannot be replaced with $n$. A naïve inductive attempt to show the inequality suggests that perhaps we can actually prove that $|X|\cdot n^{|X|}\le(n+1)^{|X|}$, although […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Transfinite derivatives December 5, 2013

In Ralph P. Boas's A primer of real functions, page 118, this is discussed in the following way: The derivative of infinite order of $f$ is defined on an interval $I$ iff the sequence $(f^{(n)})$ converges uniformly on $I$ (it is enough to require uniform convergence on compact subsets of $I$). Call $L$ the limit of this sequence, so $L$ is continuous a […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for cardinals such that $\alpha < \alpha ^ \beta$ January 31, 2023

Recall that the beth ($\beth$) numbers are defined by transfinite recursion as $\beth_0=0$, $\beth_{\alpha+1}=2^{\beth_\alpha}$ and $\beth_\lambda=\sup_{\alpha

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Prove that Baire space $\omega^\omega$ is completely metrizable? November 30, 2013

The point here is that two functions are close iff they agree on an initial segment, that is, $d(f,g)\le 1/(n+1)$ iff $f(0)=g(0),f(1)=g(1),\dots,f(n-1)=g(n-1)$. Now, if $(f_n)_n$ is a Cauchy sequence, then, for each $n$, there is $N_n$ such that for all $m,k>N_n$ we have $d(f_m,f_k)\le1/(n+1)$. That is, all functions $f_m$ with $m>N_n$ agree on their f […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Is it possible for a function to be smooth everywhere, analytic nowhere, yet Taylor series at any point converges in a nonzero radius? January 7, 2014

No, this is not possible. Dave L. Renfro wrote an excellent historical Essay on nowhere analytic $C^\infty$ functions in two parts (with numerous references). See here: 1 (dated May 9, 2002 6:18 PM), and 2 (dated May 19, 2002 8:29 PM). As indicated in part 1, in Zygmunt Zahorski. Sur l'ensemble des points singuliers d'une fonction d'une variab […]

Andrés E. Caicedo

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library