Skip to content

The Proof Theory Blog

⊢ ∃x (D(x) → ∀yD(y))

Menu
  • Home
  • About
  • Contribute
  • Resources
Menu

Countable sets in the wild

Posted on May 8, 2023May 9, 2023 by Sam Sanders

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.

  1. 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.
  2. 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.
  3. 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).
  4. 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

Your email address will not be published. Required fields are marked *

Meta

  • Register
  • Log in
  • Entries RSS
  • Privacy Policy

Search

© 2023 The Proof Theory Blog | Powered by Minimalist Blog WordPress Theme
The Proof Theory Blog uses cookies, but you can opt-out if you wish. For further information see our privacy policy. Cookie settingsAccept
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT