Countable sets in the wild – The Proof Theory Blog

TL;DR: there are various definitions of the notion ‘countable set of reals’ and only one seems to lead to nice equivalences in Reverse Mathematics. In particular, injections and bijections to the naturals à la Cantor are not very suitable. A slightly more general notion leads to many equivalences involving regulated and bounded variation functions, as well as basic properties of the Riemann integral.

Long version: Cantor’s pioneering work in set theory established that ‘infinity’ comes in different sizes, a fact that genuinely surprised even Karl Weierstrass. In particular, Cantor’s first set theory paper establishes that the real numbers are not countable. The latter notion can be made precise via a number of different definitions, as follows.

A set $A\subset \mathbb{R}$ is denumerable if there is a sequence $(x_n)_{n \in \mathbb{N}}$ that includes all elements of $A$ .
A set $A\subset \mathbb{R}$ is countable if there is an injection to the naturals, i.e. there exists a mapping $Y: \mathbb{R}\rightarrow \mathbb{N}$ such that for al $x, y\in A$ , we have $Y(x)=Y(y)\rightarrow x=y$ .
A set $A\subset \mathbb{R}$ is strongly countable if there is a bijection to the naturals, i.e. there is an injection $Y$ to the naturals that is also surjective: $(\forall n\in \mathbb{N})(\exists x \in A)(Y(x)=n)$ .
A set $A\subset \mathbb{R}$ is height-countable if there is a height function, i.e. a mapping $H:\mathbb{R}\rightarrow \mathbb{N}$ such that for all $n\in \mathbb{N}$ , the set $A_n:=\{x\in A:H(x)\leq n\}$ is finite.

The first three notions are well-known while height functions can be found here and there in the literature when discussing e.g. the countability of the rationals. Clearly, height-countability amounts to

unions over $\mathbb{N}$ of finite sets

since we readily have $A=\cup_n A_n$ in item 4. above.

As it happens, one readily shows that the reals are not denumerable in a weak system using Cantor’s diagonal argument (see Simpson’s excellent SOSOA, II.4.7). There is even an efficient algorithm that, given a sequence of reals, produces a real not in that sequence (see Gray, 1994).

By contrast, the following principles are surprisingly hard to prove in terms of comprehension.

NIN there is no injection from $[0,1]$ to $\mathbb{N}$ .

NBI there is no bijection from $[0,1]$ to $\mathbb{N}$ .

Many third-order theorems imply NIN and NBI while -in terms of comprehension- full second-order arithmetic comes to the fore in any proof of NIN or NBI; this hardness remains if we restrict to ‘nice’ function classes (see here). All relevant results can be found here in a joint paper with Dag Normann. We stress that NIN and NBI are the weakest known third-order principles that exhibit the aforementioned hardness.

In light of the previous paragraph, the uncountability of $\mathbb{R}$ seems like a natural topic of study in Reverse Mathematics. Try as we might, we could not obtain any natural equivalences using injections or bijections to the naturals. By contrast, many equivalences may be found here for the following principle, over a conservative extension of ACA $_0$ :

NIN $_{alt}$ : the unit interval is not height countable.

In particular, NIN $_{alt}$ is equivalent to the following:

1) For regulated $f:[0,1]\rightarrow \mathbb{R}$ , there is a point $x\in [0,1]$ where $f$ is continuous (or quasi-continuous, or lower semi-continuous, or Darboux).
2) For regulated $f:[0,1]\rightarrow\mathbb{R}$ , the set of continuity points is dense in $[0,1]$ .
3) For regulated $f:[0,1]\rightarrow [0,1]$ with Riemann integral $\int_{0}^{1}f(x)dx=0$ , there is $x\in [0,1]$ with $f(x)=0$ (Bourbaki).
4) (Volterra) For regulated $f,g:[0,1]\rightarrow\mathbb{R}$ , there is $x\in [0,1]$ such that $f$ and $g$ are both continuous or both discontinuous at $x$ .
5) (Volterra) For regulated $f:[0,1]\rightarrow\mathbb{R}$ , there is either $q\in \Q\cap [0,1]$ where $f$ is discontinuous, or $x\in [0,1]\setminus \Q$ where $f$ is continuous.
6) For regulated $f:[0,1]\rightarrow\mathbb{R}$ , there is $y\in (0,1)$ where $F(x):=\lambda x.\int_{0}^{x}f(t)dt$ is differentiable with derivative equal to $f(y)$ .
7) For regulated $f:[0,1]\rightarrow\mathbb{R}$ , there are $a, b\in [0,1]$ such that ${ x\in [0,1]:f(a)\leq f(x)\leq f(b)}$ is infinite.
8) Blumberg’s theorem restricted to regulated functions.

Many more equivalences can be found in the associated paper, including equivalences for functions of bounded variation.

Finally, a fairly ‘weird’ fact is that the items 1-8 become provable (say in a conservative extension of ACA $_0$ ) if we add the additional condition ‘Baire 1’. There is no contradiction here as

all regulated functions are Baire 1 on the unit interval (*)

is of course provable in say ZF. Nonetheless, (*) is suprisingly hard to prove as (*) implies NIN (see here). We have no real explanation for this phenomenon.

Leave a Reply Cancel reply