1 Introduction and preliminaries
1.1 Aim and motivation
The aim of the program Reverse Mathematics (RM; see Section 1.2.1 for an introduction) is to find the minimal axioms needed to prove a given theorem of ordinary mathematics. Generally, the minimal axioms are equivalent to the theorem at hand, assuming a weak logical system called the base theory. The Big Five phenomenon is a central topic in RM, as follows.
$[...]$
we would still claim that the great majority of the theorems from classical mathematics are equivalent to one of the big five. This phenomenon is still quite striking. Though we have some sense of why this phenomenon occurs, we really do not have a clear explanation for it, let alone a strictly logical or mathematical reason for it. The way I view it, gaining a greater understanding of this phenomenon is currently one of the driving questions behind reverse mathematics. (see [Reference Montalbán57, p. 432])
A natural example is the equivalence between the Weierstrass approximation theorem and weak König’s lemma from [Reference Simpson83, IV.2.5]. In [Reference Normann and Sanders68], Dag Normann and the author greatly extend the Big Five phenomenon by establishing numerous equivalences involving the second-order Big Five systems on one hand, and well-known third-order theorems from analysis about possibly discontinuous functions on the other hand, working in Kohlenbach’s higher-order RM (see Section 1.2.1). Moreover, following [Reference Normann and Sanders68, Section 2.8], slight variations/generalisations of these third-order theorems cannot be proved from the Big Five and much stronger systems. Nonetheless, an important message of [Reference Normann and Sanders68] is just how similar second- and higher-order RM can be, as the latter reinforces the existing Big Five with many further examples.
In this paper, we develop the RM-study of approximation theorems, often involving Bernstein polynomials
$B_{n}$
, defined as follows:
$$ \begin{align} B_n(f,x):=\sum_{k=0}^{n} f\big({k}/{n}\big)p_{n,k}(x), \text{ where } p_{n, k}(x):= \binom{n}{k} x^k (1-x)^{n-k}. \end{align} $$
Weierstrass [Reference Weierstrass92] and Borel [Reference Borel9, p. 80] already study polynomial approximations while Bernstein [Reference Bernstein6] provides the first explicit polynomials, namely
$B_{n}$
as above, and showed that for continuous
$f:[0,1]\rightarrow {\mathbb R}$
, we have for all
$x\in [0,1]$
that
$$ \begin{align} f(x)=\lim_{n\rightarrow \infty}B_{n}(f, x), \end{align} $$
where the convergence is uniform. Approximation results for discontinuous functions are in [Reference Chlodovsky18, Reference Herzog and Hill33, Reference Kantorovitch43, Reference Picard71] andFootnote
1
take the form (1.2) for points of continuity and the form (1.3) if the left and right limits
$f(x-)$
and
$f(x+)$
exist at
$x\in (0,1)$
:
$$ \begin{align}\textstyle \frac{f(x+)+f(x-)}{2}=\lim_{n\rightarrow \infty}B_{n}(f, x). \end{align} $$
We stress that for general
$f:[0,1]\rightarrow {\mathbb R}$
, (1.2) may hold at x where f is discontinuous, i.e., (1.2) is much weaker than continuity at x. For instance, Dirichlet’s function
$\mathbb {1}_{\mathbb Q}$
satisfies (1.2) for all rationals and is discontinuous everywhere.
In this paper, we develop the RM-study of approximation theorems based on (1.2) and (1.3) for regulated, semi-continuous, cliquish, and Riemann integrable functions. Scheeffer and Darboux study regulated functions in [Reference Darboux20, Reference Scheeffer80] without naming this class, while Baire introduced semi-continuity in [Reference Baire4]. Hankel studies cliquish functions using an equivalent definition in [Reference Hankel30]. Thus, there is plenty of historical motivation for our RM-study.
In particular, we show that many approximation theorems for discontinuous functions are equivalent to weak König’s lemma in Theorem 2.3. We also show that slight variations fall far outside of the Big Five, but do yield equivalences for four new ‘Big’ systems, namely the uncountability of
${\mathbb R}$
[Reference Sanders78], the enumeration principle for countable sets [Reference Normann and Sanders64], the Baire category theorem [Reference Sanders79], and the pigeon-hole principle for measure [Reference Sanders79]. These new Big systems boast equivalences involving principles based on pointwise continuity and it is perhaps surprising that the same holds for the weaker condition (1.2). Moreover, the equivalences for these new Big systems are robust as follows:
A system is robust if it is equivalent to small perturbations of itself. ([Reference Montalbán57, p. 432]; emphasis in original)
In particular, our equivalences generally go through for many variations of the function classes involved, with examples in Theorems 3.3 and 3.8. There is an apparent tension here with the earlier observation that slight variations in the theorems can greatly affect the logical strength required to prove them. We attempt to explain this phenomenon in Remark 3.11.
Finally, in Section 1.2.1, we provide an introduction to RM; we introduce essential higher-order concepts in Sections 1.2.2–1.2.4. We establish the equivalences for weak König’s lemma in Section 2 and the equivalences for the ‘new’ big systems in Section 3.2–3.4.
1.2 Preliminaries and definitions
We briefly introduce RM in Section 1.2.1. We introduce some essential axioms (Section 1.2.2) and definitions (Section 1.2.3) needed in the below. We discuss the definition of countable set in higher-order RM in Section 1.2.4.
1.2.1 Reverse Mathematics.
RM is a program in the foundations of mathematics initiated around 1975 by Friedman [Reference Friedman27, Reference Friedman28] and developed extensively by Simpson and others [Reference Dzhafarov and Mummert22, Reference Simpson82, Reference Simpson83]. The aim of RM is to identify the minimal axioms needed to prove theorems of ordinary, i.e., non-set theoretical, mathematics.
First of all, we refer to [Reference Stillwell84] for a basic introduction to RM and to [Reference Dzhafarov and Mummert22, Reference Simpson82, Reference Simpson83] for an overview of RM. We expect basic familiarity with RM, in particular Kohlenbach’s higher-order RM [Reference Kohlenbach46] essential to this paper, including the base theory
${\textsf {RCA}}_{0}^{\omega }$
, also introduced in Section 4.2. An extensive introduction can be found in, e.g., [Reference Normann and Sanders61, Reference Normann and Sanders62, Reference Normann and Sanders65] and elsewhere.
Secondly, as to notations, we have chosen to include a brief introduction as a technical appendix, namely Section 4. All undefined notions may be found in the latter, while we do point out here that we shall sometimes use common notations from type theory. For instance, the natural numbers are type
$0$
objects, denoted
$n^{0}$
or
$n\in {\mathbb N}$
. Similarly, elements of Baire space are type
$1$
objects, denoted
$f\in {\mathbb N}^{{\mathbb N}}$
or
$f^{1}$
. Mappings from Baire space
${\mathbb N}^{{\mathbb N}}$
to
${\mathbb N}$
are denoted
$Y:{\mathbb N}^{{\mathbb N}}\rightarrow {\mathbb N}$
or
$Y^{2}$
.
Thirdly, the main topic of this paper is the RM-study of real analysis, for which the following notations suffice. Both in
${\textsf {RCA}}_{0}$
and
${\textsf {RCA}}_{0}^{\omega }$
, real numbers are given by Cauchy sequences (see Definition 4.4 and [Reference Simpson83, II.4.4]) and equality between reals ‘
$=_{{\mathbb R}}$
’ has the same meaning in second- and higher-order RM. Functions on
${\mathbb R}$
are defined as mappings
$\Phi $
from
${\mathbb N}^{{\mathbb N}}$
to
${\mathbb N}^{{\mathbb N}}$
that respect real equality, i.e.,
$x=_{{\mathbb R}}y\rightarrow \Phi (x)=_{{\mathbb R}}\Phi (y)$
for any
$x, y\in {\mathbb R}$
, which is also called function extensionality.
Fourth, experience bears out that the following fragment of the Axiom of Choice is often convenient when (first) proving equivalences. This principle can often be omitted by developing a more sophisticated alternative proof (see, e.g., [Reference Normann and Sanders63]).
Principle 1.1 (
${\textsf {QF-AC}}^{0,1}$
).
For any
$Y^{2}$
, we have
$:$
$$ \begin{align} (\forall n\in {\mathbb N})(\exists f\in {\mathbb N}^{{\mathbb N}})(Y(f, n)=0 )\rightarrow (\exists (f_{n})_{n\in {\mathbb N}})(\forall n\in {\mathbb N})(Y(f_{n}, n)=0 ). \end{align} $$
As discussed in [Reference Kohlenbach46, Remark 3.13], this principle is not provable in
${\textsf {ZF}}$
while
${\textsf {RCA}}_{0}^{\omega }+{\textsf {QF-AC}}^{0,1}$
suffices to prove the local equivalence between (epsilon–delta) continuity and sequential continuity, which is also not provable in
${\textsf {ZF}}$
.
Finally, the main difference between Friedman–Simpson and Kohlenbach’s framework for RM is whether the language is restricted to second-order objects or if one allows third-order objects. An important message of [Reference Normann and Sanders68] and this paper is that the second-order Big Five are equivalent to third-order theorems concerning possibly discontinuous functions, as is also clear from Theorems 2.3 and 2.4.
1.2.2 Some comprehension functionals.
In second-order RM, the logical hardness of a theorem is measured via what fragment of the comprehension axiom (broadly construed) is needed for a proof. For this reason, we introduce some axioms and functionals related to higher-order comprehension in this section. We are mostly dealing with conventional comprehension here, i.e., only parameters over
${\mathbb N}$
and
${\mathbb N}^{{\mathbb N}}$
are allowed in formula classes like
$\Pi _{k}^{1}$
and
$\Sigma _{k}^{1}$
.
First of all, the functional
$\varphi $
in
$(\exists ^{2})$
is also Kleene’s quantifier
$\exists ^{2}$
and is clearly discontinuous at
$f=11\dots $
in Cantor space:
$$\begin{align} (\exists \varphi^{2}\leq_{2}1)(\forall f^{1})\big[(\exists n^{0})(f(n)=0) \leftrightarrow \varphi(f)=0 \big]. \end{align}$$
In fact,
$(\exists ^{2})$
is equivalent to the existence of
$F:{\mathbb R}\rightarrow {\mathbb R}$
such that
$F(x)=1$
if
$x>_{{\mathbb R}}0$
, and
$0$
otherwise (see [Reference Kohlenbach46, Proposition 3.12]). Related to
$(\exists ^{2})$
, the functional
$\mu ^{2}$
in
$(\mu ^{2})$
is called Feferman’s
$\mu $
(see [Reference Avigad and Feferman3]) and may be found—with the same symbol—in Hilbert–Bernays’ Grundlagen [Reference Hilbert and Bernays34, Supplement IV]:
$$\begin{align} (\exists \mu^{2})(\forall f^{1})\big[ (\exists n)(f(n)=0) \rightarrow [f(\mu(f))=0&\wedge (\forall i<\mu(f))(f(i)\ne 0) ]\\ & \wedge [ (\forall n)(f(n)\ne0)\rightarrow \mu(f)=0] \big]. \notag \end{align}$$
We have
$(\exists ^{2})\leftrightarrow (\mu ^{2})$
over
${\textsf {RCA}}_{0}^{\omega }$
(see [Reference Kohlenbach46, Section 3]) and
${\textsf {ACA}}_{0}^{\omega }\equiv {\textsf {RCA}}_{0}^{\omega }+(\exists ^{2})$
proves the same sentences as
${\textsf {ACA}}_{0}$
by [Reference Hunter35, Theorem 2.5].
Secondly, the functional
${\textsf {S}}^{2}$
in
$({\textsf {S}}^{2})$
is called the Suslin functional [Reference Kohlenbach46]:
$$\begin{align} (\exists{\textsf{S}}^{2}\leq_{2}1)(\forall f^{1})\big[ (\exists g^{1})(\forall n^{0})(f(\overline{g}n)=0)\leftrightarrow {\textsf{S}}(f)=0 \big]. \end{align}$$
The system
$\Pi _{1}^{1} {\text{-}{\textsf {CA}}}_{0}^{\omega }\equiv {\textsf {RCA}}_{0}^{\omega }+({\textsf {S}}^{2})$
proves the same
$\Pi _{3}^{1}$
-sentences as
$\Pi _{1}^{1} {\text{-}{\textsf {CA}}}_{0}$
by [Reference Sakamoto and Yamazaki75, Theorem 2.2]. By definition, the Suslin functional
${\textsf {S}}^{2}$
can decide whether a
$\Sigma _{1}^{1}$
-formula as in the left-hand side of
$({\textsf {S}}^{2})$
is true or false. We similarly define the functional
${\textsf {S}}_{k}^{2}$
which decides the truth or falsity of
$\Sigma _{k}^{1}$
-formulas from
$\textsf { L}_{2}$
; we also define the system
$\Pi _{k}^{1}{\text{-}\textsf {CA}}_{0}^{\omega }$
as
${\textsf {RCA}}_{0}^{\omega }+({\textsf {S}}_{k}^{2})$
, where
$({\textsf {S}}_{k}^{2})$
expresses that
${\textsf {S}}_{k}^{2}$
exists. We note that the operators
$\nu _{n}$
from [Reference Buchholz, Feferman, Pohlers and Sieg17, p. 129] are essentially
${\textsf {S}}_{n}^{2}$
strengthened to return a witness (if existent) to the
$\Sigma _{n}^{1}$
-formula at hand.
Thirdly, full second-order arithmetic
${\textsf {Z}}_{2}$
is readily derived from
$\cup _{k}\Pi _{k}^{1}{\text{-}\textsf {CA}}_{0}^{\omega }$
, or from
$$\begin{align} (\exists E^{3}\leq_{3}1)(\forall Y^{2})\big[ (\exists f^{1})(Y(f)=0)\leftrightarrow E(Y)=0 \big], \end{align} $$
and we therefore define
${\textsf {Z}}_{2}^{\Omega }\equiv {\textsf {RCA}}_{0}^{\omega }+(\exists ^{3})$
and
${\textsf {Z}}_{2}^\omega \equiv \cup _{k}\Pi _{k}^{1}{\text{-}\textsf {CA}}_{0}^{\omega }$
, which are conservative over
${\textsf {Z}}_{2}$
by [Reference Hunter35, Corollary 2.6]. Despite this close connection,
${\textsf {Z}}_{2}^{\omega }$
and
${\textsf {Z}}_{2}^{\Omega }$
can behave quite differently, as discussed in, e.g., [Reference Normann and Sanders61, Section 2.2] and Section 3.1. The functional from
$(\exists ^{3})$
is also called ‘
$\exists ^{3}$
’, and we use the same convention for other functionals.
Finally, Kleene’s quantifier
$\exists ^{2}$
plays a crucial role throughout higher-order RM. We recall that
$(\exists ^{2})$
is equivalent to the existence of a discontinuous function on
${\mathbb R}$
(or
${\mathbb N}^{{\mathbb N}}$
) by [Reference Kohlenbach46, Proposition 3.12], using so-called Grilliot’s trick. Thus,
$\neg (\exists ^{2})$
is equivalent to Brouwer’s theorem, i.e., all functions on the reals (and Baire space) are continuous. We will often make use of the latter fact without explicitly pointing this out.
1.2.3 Some definitions.
We introduce some required definitions, stemming from mainstream mathematics. We note that subsets of
${\mathbb R}$
are given by their characteristic functions as in Definition 1.2, well-known from measure and probability theory. We shall generally work over
${\textsf {ACA}}_{0}^{\omega }$
as some definitions make little sense over
${\textsf {RCA}}_{0}^{\omega }$
.
First of all, we make use the usual definition of (open) set, where
$B(x, r)$
is the open ball with radius
$r>0$
centred at
$x\in {\mathbb R}$
. We note that our notion of ‘measure zero’ does not depend on (the existence of) the Lebesgue measure.
Definition 1.2 (Sets).
-
• A subset
$A\subset {\mathbb R}$
is given by its characteristic function
$F_{A}:{\mathbb R}\rightarrow \{0,1\}$
, i.e., we write
$x\in A$
for
$ F_{A}(x)=1$
, for any
$x\in {\mathbb R}$
. -
• A subset
$O\subset {\mathbb R}$
is open in case
$x\in O$
implies that there is
$k\in {\mathbb N}$
such that
$B(x, \frac {1}{2^{k}})\subset O$
. -
• A subset
$O\subset {\mathbb R}$
is RM-open in case there are sequences of reals
$(a_{n})_{n\in {\mathbb N}}, (b_{n})_{n\in {\mathbb N}}$
such that
$O=\cup _{n\in {\mathbb N}}(a_{n}, b_{n})$
. -
• A subset
$C\subset {\mathbb R}$
is closed if the complement
${\mathbb R}\setminus C$
is open. -
• A subset
$C\subset {\mathbb R}$
is RM-closed if the complement
${\mathbb R}\setminus C$
is RM-open. -
• A set
$A\subset {\mathbb R}$
is enumerable if there is a sequence of reals that includes all elements of A. -
• A set
$A\subset {\mathbb R}$
is countable if there is
$Y: {\mathbb R}\rightarrow {\mathbb N}$
that is injective on A, i.e.,
$$\begin{align*}(\forall x, y\in A)( Y(x)=_{0}Y(y)\rightarrow x=_{{\mathbb R}}y). \end{align*}$$
-
• A set
$A\subset {\mathbb R}$
is measure zero if for any
$\varepsilon>0$
there is a sequence of open intervals
$(I_{n})_{n\in {\mathbb N}}$
such that
$\cup _{n\in {\mathbb N}}I_{n}$
covers A and
$\varepsilon>\sum _{n=0}^{\infty }|I_{n}|$
. -
• A set
$A\subset {\mathbb R}$
is dense in
$B\subset {\mathbb R}$
if for
$k\in {\mathbb N},b\in B$
, there is
$a\in A$
with
$|a-b|<\frac {1}{2^{k}}$
. -
• A set
$A\subset {\mathbb R}$
is nowhere dense in
$B\subset {\mathbb R}$
if A is not dense in any open sub-interval of B.
As discussed in Section 1.2.4, the study of regulated functions already gives rise to open sets that do not come with additional representation beyond the second item in Definition 1.2. We will often assume
$(\exists ^{2})$
from Section 1.2.2 to guarantee that basic objects like the unit interval are sets in the sense of Definition 1.2.
Secondly, we study the following notions, many of which are well-known and hark back to the days of Baire, Darboux, Dini, Jordan, Hankel, and Volterra [Reference Baire4, Reference Baire5, Reference Darboux20, Reference Dini21, Reference Hankel30, Reference Hankel31, Reference Jordan41, Reference Volterra90]. We use ‘sup’ and other operators in the ‘virtual’ or ‘comparative’ way of second-order RM (see, e.g., [Reference Simpson83, X.1] or [Reference Brown15]). In this way, a formula of the form ‘
$\sup A>a$
’ or ‘
$x\in \overline {S}$
’ makes sense as shorthandFootnote
2
for a formula in the language of all finite types, even when
$\sup A$
or the closure
$\overline {S}$
need not exist in
${\textsf {RCA}}_{0}^{\omega }$
.
Definition 1.3. For
$f:[0,1]\rightarrow {\mathbb R}$
, we have the following definitions
$:$
-
• f is upper semi-continuous at
$x_{0}\in [0,1]$
if
$f(x_{0})\geq _{{\mathbb R}}\lim \sup _{x\rightarrow x_{0}} f(x)$
. -
• f is lower semi-continuous at
$x_{0}\in [0,1]$
if
$f(x_{0})\leq _{{\mathbb R}}\lim \inf _{x\rightarrow x_{0}} f(x)$
. -
• f has bounded variation on
$[0,1]$
if there is
$k_{0}\in {\mathbb N}$
such that
$k_{0}\geq \sum _{i=0}^{n} |f(x_{i})-f(x_{i+1})|$
for any partition
$x_{0}=0 <x_{1}< \dots < x_{n-1}<x_{n}=1 $
. -
• f is regulated if for every
$x_{0}$
in the domain, the ‘left’ and ‘right’ limit
$f(x_{0}-) =\lim _{x\rightarrow x_{0}-}f(x)$
and
$f(x_{0}+)=\lim _{x\rightarrow x_{0}+}f(x)$
exist. -
• f is cadlag if it is regulated and
$f(x)=f(x+)$
for
$x\in [0,1)$
. -
• f is a
$U_{0}$
-function ([Reference Appell, Banaś and Merentes1, Reference Goffman, Moran and Waterman29, Reference Johnson and Tonne40, Reference Lorentz54]) if it is regulated and for all
$x\in (0,1):$
(1.5)
$$ \begin{align} \min(f(x+), f(x-))\leq f(x)\leq \max(f(x+), f(x-)). \end{align} $$
-
• f is Baire
$1$
if it is the pointwise limit of a sequence of continuous functions. -
• f is Baire 1
$^{*}$
ifFootnote
3
there is a sequence of closed sets
$(C_{n})_{n\in {\mathbb N}}$
such
$[0,1]=\cup _{n\in {\mathbb N}}C_{n}$
and
$f_{\upharpoonright C_{m}}$
is continuous for all
$m\in {\mathbb N}$
. -
• f is quasi-continuous at
$x_{0}\in [0, 1]$
if for
$ \epsilon> 0$
and any open neighbourhood U of
$x_{0}$
, there is non-empty open
${ G\subset U}$
with
$(\forall x\in G) (|f(x_{0})-f(x)|<\varepsilon )$
. -
• f is cliquish at
$x_{0}\in [0, 1]$
if for
$ \epsilon> 0$
and any open neighbourhood U of
$x_{0}$
, there is a non-empty open
${ G\subset U}$
with
$(\forall x, y\in G) (|f(x)-f(y)|<\varepsilon )$
. -
• f is pointwise discontinuous if for any
$x\in [0,1], k\in {\mathbb N}$
there is
$y\in B(x, \frac {1}{2^{k}})$
such that f is continuous at y. -
• f is locally bounded if for any
$x\in [0,1]$
, there is
$N\in {\mathbb N}$
such that
$(\forall y\in B(x, \frac {1}{2^{N}})\cap [0,1])(|f(y)|\leq N)$
.
As to notations, a common abbreviation is ‘usco’, ‘lsco’, and ‘
$BV$
’ for the first three items. Cliquishness and pointwise discontinuity on the reals are equivalent, the non-trivial part of which was already observed by Dini [Reference Dini21, Section 63]. Moreover, if a function has a certain weak continuity property at all reals in
$[0,1]$
(or its intended domain), we say that the function has that property. The fundamental theorem about
$BV$
-functions was proved already by Jordan in [Reference Jordan41, p. 229].
Theorem 1.4 (Jordan decomposition theorem).
A
$BV$
-function
$f : [0, 1] \rightarrow {\mathbb R}$
is the difference of two non-decreasing functions
$g, h:[0,1]\rightarrow {\mathbb R}$
.
Theorem 1.4 has been studied in RM via second-order codes [Reference Nies, Triplett and Yokoyama60]. For a
$BV$
-function
$f:[0, 1]\rightarrow {\mathbb R}$
, the total variation is defined as
$$ \begin{align}\textstyle V_{0}^{1}(f):=\sup_{0\leq x_{0}< \dots< x_{n}\leq 1}\sum_{i=0}^{n} |f(x_{i})-f(x_{i+1})|. \end{align} $$
Thirdly, the following sets are often crucial in proofs relating to discontinuous functions, as can be observed in, e.g., [Reference Appell, Banaś and Merentes1, Theorem 0.36].
Definition 1.5. The sets
$C_{f}$
and
$D_{f}$
(if they exist) respectively gather the points where
$f:{\mathbb R}\rightarrow {\mathbb R}$
is continuous and discontinuous.
One problem with the sets
$C_{f}, D_{f}$
is that the definition of continuity involves quantifiers over
${\mathbb R}$
. In general, deciding whether a given
${\mathbb R}\rightarrow {\mathbb R}$
-function is continuous at a given real, is as hard as
$\exists ^{3}$
from Section 1.2.2. For these reasons, the sets
$C_{f}, D_{f}$
only exist in strong systems. A solution is discussed in just below.
In this section, we introduce oscillation functions and provide some motivation for their use. We have previously studied usco, Baire 1, Riemann integrable, and cliquish functions using oscillation functions (see [Reference Sanders77, Reference Sanders79]). As will become clear, such functions are generally necessary for our RM-study.
Fourth, the study of regulated functions in [Reference Normann and Sanders64, Reference Normann and Sanders66, Reference Normann and Sanders67, Reference Sanders78] is really only possible thanks to the associated left- and right limits (see Definition 1.3) and the fact that the latter are computable in
$\exists ^{2}$
. Indeed, for regulated
$f:{\mathbb R}\rightarrow {\mathbb R}$
, the formula
$$\begin{align} f \textit{is continuous at a given real }x\in {\mathbb R} \end{align} $$
involves quantifiers over
${\mathbb R}$
but is equivalent to the arithmetical formula
$f(x+)=f(x)=f(x-)$
. In this light, we can define the set
$D_{f}$
—using only
$\exists ^{2}$
—and proceed with the usual (textbook) proofs. An analogous approach, namely the study of usco, Baire 1, Riemann integrable, and cliquish functions, was used in [Reference Sanders77, Reference Sanders79]. To this end, we used oscillation functions as in Definition 1.6. We note that Riemann, Ascoli, and Hankel already considered the notion of oscillation in the study of Riemann integration [Reference Ascoli2, Reference Hankel30, Reference Riemann, Baker, Christenson and Orde72], i.e., there is ample historical precedent.
Definition 1.6 (Oscillation functions).
For any
$f:{\mathbb R}\rightarrow {\mathbb R}$
, the associated oscillation functions are defined as follows
$: {\textsf {osc}}_{f}([a,b]):= \sup _{{x\in [a,b]}}f(x)-\inf _{{x\in [a,b]}}f(x)$
and
${\textsf {osc}}_{f}(x):=\lim _{k \rightarrow \infty }{\textsf {osc}}_{f}(B(x, \frac {1}{2^{k}}) ).$
We stress that
${\textsf {osc}}_{f}:{\mathbb R}\rightarrow {\mathbb R}$
is only
Footnote
4
a third-order object, as clearly indicated by its type. Now, our main interest in Definition 1.6 is that (
C
) is equivalent to the arithmetical formula
${\textsf {osc}}_{f}(x)=0$
, assuming the latter function is given. Hence, in the presence of
${\textsf {osc}}_{f}:{\mathbb R}\rightarrow {\mathbb R}$
and
$\exists ^{2}$
, we can define
$D_{f}$
and proceed with the usual (textbook) proofs, which is the approach we often took in [Reference Sanders77, Reference Sanders79]. Indeed, one can generally avoid the use of oscillation functions for usco functions.
1.2.4 On countable sets.
In this section, we discuss the correct definition of countable set for higher-order RM, where we hasten to add that ‘correct’ is only meant to express ‘yields many equivalences over weak systems like the base theory’.
First of all, the correct choice of definition for mathematical notions is crucial to the development of RM, as can be gleaned from the following quote.
Under the old definition [of real number in [Reference Simpson81]], it would be consistent with
${\textsf {RCA}}_{0}$
that there exists a sequence of real numbers
$(x_{n})_{n\in {\mathbb N}}$
such that
$(x_{n}+\pi )_{n\in {\mathbb N}}$
is not a sequence of real numbers. We thank Ian Richards for pointing out this defect of the old definition. Our new definition [of real number in [Reference Brown and Simpson16]], given above, is adopted in order to remove this defect. All of the arguments and results of [Reference Simpson81] remain correct under the new definition. [Reference Brown and Simpson16, p. 129]
In short, the early definition of ‘real number’ from [Reference Simpson81] was not suitable for the development of RM, highlighting the importance of the right choice of definition. Similar considerations exist for the definition of continuous function in constructive mathematics (see [Reference Bridges14, Reference Waaldijk91]), i.e., this situation is not unique to RM.
Secondly, we focus on identifying the correct definition for ‘countable set’. Now, going back to Hankel [Reference Hankel30], the sets
$C_{f}$
and
$D_{f}$
of (dis)continuity points of
$f:[0,1]\rightarrow {\mathbb R}$
play a central role in real analysis as is clear from, e.g., the Vitali–Lebesgue theorem which expresses Riemann integrability in terms of
$C_{f}$
. For regulated
$f:[0,1]\rightarrow {\mathbb R}$
, the set of discontinuity points satisfies
$D_{f}=\cup _{k\in {\mathbb N}} D_{k}$
for
$$ \begin{align}\textstyle D_{k}:=\{ x\in [0,1]: |f(x)-f(x+)|>\frac{1}{2^{k}}\vee |f(x)-f(x-)|>\frac{1}{2^{k}} \}, \end{align} $$
where
$D_{k}$
is finite via a standard compactness argument. In this way,
$D_{f}$
is countable but we are unable to construct an injection (let alone a bijection) from the former to
${\mathbb N}$
in, e.g.,
${\textsf {Z}}_{2}^{\omega }$
. Hence, we readily encounter countable sets ‘in the wild’, namely
$D_{f}$
for regulated f, for which the set-theoretic definition based on injections and bijections can apparently not be established in weak logical systems. Similarly, while
$D_{k}$
is closed,
${\textsf {Z}}_{2}^{\omega }$
does not prove the existence of an RM-code for
$D_{k}$
. In this way, theorems about countable (or RM-closed) sets in the sense of Definition 1.2
cannot be applied to
$D_{f}$
or
$D_{k}$
in fairly strong systems like
${\textsf {Z}}_{2}^{\omega }$
and the development of the RM of real analysis therefore seemingly falters.
The previous negative surprise notwithstanding, (1.7) also provides the solution to our problem: we namely have
$D_{f}=\cup _{k\in {\mathbb N}} D_{k}$
, i.e., the set
$D_{f}$
is
$$ \begin{align*} \textit{the union over }{\mathbb N} \textit{ of finite sets}. \end{align*} $$
Moreover, this property of
$D_{f}$
can be established in a (rather) weak logical system. Thus, we arrive at Definition 1.7 which yields many equivalences involving the statement the unit interval is not height-countable (see Section 3.2 and [Reference Sanders78]) on one hand, and basic properties of regulated functions on the other hand.
Definition 1.7. A set
$A\subset {\mathbb R}$
is height-countable if there is a height function
$H:{\mathbb R}\rightarrow {\mathbb N}$
for A, i.e., for all
$n\in {\mathbb N}$
,
$A_{n}:= \{ x\in A: H(x)<n\}$
is finite.
Height functions can be found in the modern literature [Reference Huxley37, Reference Kolmogorov and Fomin47, Reference Moll56, Reference Royden73, Reference Vatssa89], but also go back to Borel and Drach circa 1895 (see [Reference Borel10–Reference Borel and Drach12]) Definition 1.7 amounts to ‘union over
${\mathbb N}$
of finite sets’, as is readily shown in
${\textsf {ACA}}_{0}^{\omega }$
.
Finally, the observations regarding countable sets also apply mutatis mutandis to finite sets. Indeed, finite as each
$D_{n}$
from (1.7) may be, we are unable to construct an injection to a finite subset of
${\mathbb N}$
, even assuming
${\textsf {Z}}_{2}^{\omega }$
. By contrast, one readilyFootnote
5
shows that
$D_{n}$
from (1.7) is finite as in Definition 1.8.
Definition 1.8 (Finite set).
Any
$X\subset {\mathbb R}$
is finite if there is
$N\in {\mathbb N}$
such that for any finite sequence
$(x_{0}, \dots , x_{N})$
of distinct reals, there is
$i\leq N$
such that
$x_{i}\not \in X$
.
The number N from Definition 1.8 is called a size bound for the finite set
$X\subset {\mathbb R}$
. Analogous to countable sets, the RM-study of regulated functions should be based on Definition 1.8 and not on the set-theoretic definition based on injections/bijections to finite subsets of
${\mathbb N}$
or similar constructs.
In conclusion, Definitions 1.7 and 1.8 provide the correct definition of countable set in that they give rise to many RM-equivalences involving basic properties of regulated functions, as established in [Reference Sanders78]. By contrast, the set-theoretic definition involving injections and bijections, does not seem to seem suitable for the development of (higher-order) RM.
2 Equivalences involving weak König’s lemma
We establish equivalences between
${\textsf {WKL}}_{0}$
and approximation theorems for Bernstein polynomials for (dis)continuous functions. We sketch similar results for the other Big Five systems
${\textsf {ACA}}_{0}$
and
${\textsf {ATR}}_{0}$
. The RM-study of Bernstein polynomial approximation of course hinges on the following set, definable in
${\textsf {ACA}}_{0}^{\omega }$
as the defining formula is arithmetical:
$$ \begin{align} B_{f}:=\{ x\in [0,1]: f(x)=\lim_{n\rightarrow \infty} B_{n}(f, x)\}. \end{align} $$
Similarly, the left and right limits of regulated functions can be found using
$(\exists ^{2})$
(see [Reference Normann and Sanders64, Section 3]), which is another reason why we shall often incorporate the latter in our base theory.
First of all, we establish the equivalence between
${\textsf {WKL}}_{0}$
and the Weierstrass approximation theorem via Bernstein polynomials ([Reference Bernstein6]), as the proof is instructive for that of Theorem 2.2 and essential to that of Theorems 2.3 and 2.4.
Theorem 2.1 (
${\textsf {RCA}}_{0}^{\omega }$
).
The following are equivalent
$:$
-
•
${\textsf {WKL}}_{0}$
. -
• For continuous
$f:[0,1]\rightarrow {\mathbb R}$
and
$x\in (0,1)$
, we have (2.2)where the convergence is uniform.
$$ \begin{align} f(x)=\lim_{n\rightarrow \infty }B_{n}(f, x), \end{align} $$
Proof. First of all, it is well-known that
${\textsf {RCA}}_{0}$
can prove basic facts about basic objects like polynomials, as established in, e.g., [Reference Simpson83, II.6]. Similarly, the following can be proved in
${\textsf {RCA}}_{0}$
, for
$p_{n,k}(x):= \binom {n}{k} x^k (1-x)^{n-k}$
and any
$x\in [0,1], m\leq n$
:
$$ \begin{align}\textstyle p_{m, n}(x)\geq 0 \text{ and } \sum_{k\leq n}\left(x-{k \over n}\right)^{2}p_{n,k}(x)={x(1-x) \over n} \text{ and }{ \sum _{k\leq n} p_{n, k}(x)=1} \end{align} $$
using, e.g., binomial expansion and similar basic properties of polynomials.
Secondly, by [Reference Simpson83, IV.2.5],
${\textsf {WKL}}_{0}$
is equivalent to the Weierstrass approximation theorem for codes of continuous functions. Every code for a continuous function on
$[0,1]$
denotes a third-order (continuous) function by [Reference Normann and Sanders68, Theorem 2.2], which can be established directly by applying
${\textsf {QF-AC}}^{1, 0}$
from
${\textsf {RCA}}_{0}^{\omega }$
to the formula expressing the totality of the code on
$[0,1]$
. Hence, the upward implication follows.
Thirdly, for the remaining implication,
${\textsf {WKL}}_{0}$
implies that continuous functions are uniformly continuous on
$[0,1]$
, both for codes (see [Reference Simpson83, IV.2.3]) and for third-order functions (see [Reference Normann and Sanders68, Theorem 2.3]). Hence, fix continuous
$f:[0,1]\rightarrow {\mathbb R}$
and
$k_{0}\in {\mathbb N}$
and let
$N_{0}\in {\mathbb N}$
be such that
$(\forall x, y\in [0,1])( |x-y|<\frac {1}{2^{N_{0}}}\rightarrow |f(x)-f(y)|<\frac {1}{2^{k_{0}+1}})$
. Clearly, f is bounded on
$[0,1]$
, say by
$M_{0}\in {\mathbb N}$
. Now fix
$x_{0}\in (0,1)$
, choose
$n\geq 2^{2M_{0}+2N_{0}+k_{0}+1}$
, and consider
$$ \begin{align} |f(x_{0})- B_{n}(f, x_{0})| &\textstyle=|f(x_{0})-\sum_{k=0}^{n} f\big(\frac{k}{n}\big) p_{n,k}(x_{0}) |\notag\\ &\textstyle=|\sum_{k=0}^{n}\big( f(x_{0})-f\big(\frac{k}{n}\big)\big) p_{n,k}(x_{0}) |\notag\\ &\textstyle\leq \sum_{k=0}^n \big| f\big(\frac{k}{n}\big) -f(x_{0}) \big| p_{n,k}(x_{0})\notag\\ &\textstyle=\sum_{i=0,1} \sum_{k\in A_{i}} \big| f\big(\frac{k}{n}\big) -f(x_{0}) \big| p_{n,k}(x_{0}), \end{align} $$
where
$A_{0}:=\{k\leq n: |x_{0}-\frac {k}{n}|\leq \frac {1}{2^{N_{0}}} \}$
and
$A_{1}:=\{0, 1, \dots n\}\setminus A_{0} $
, and where the second equality follows by the final formula in (2.3). The sets
$A_{i}$
(
$i=0,1$
) exist in
${\textsf {RCA}}_{0}$
by bounded comprehension (see [Reference Simpson83, X.4.4]). Now consider
$$\begin{align*}\textstyle \sum_{k\in A_{0}} \big| f\big(\frac{k}{n}\big) -f(x_{0}) \big| p_{n,k}(x_{0})\leq \frac{1}{2^{k_{0}+1}}\sum_{k\in A_{0} }p_{n,k}(x_{0})\leq \frac{1}{2^{k_{0}+1}}\sum_{k\leq n}p_{n,k}(x_{0})= \frac{1}{2^{k_{0}+1}}, \end{align*}$$
where the final equality follows by (2.3). For the other sum in (2.4), we have
$$\begin{align*}\textstyle \sum_{k\in A_{1}} \big| f\big(\frac{k}{n}\big) -f(x_{0}) \big| p_{n,k}(x_{0})\leq 2M_{0} \sum_{k\in A_{1}} \frac{(x_{0}-\frac{k}{n})^{2}}{1/2^{2N_{0}}} p_{n,k}(x_{0}) \leq 2M_{0} \sum_{k\leq n} \frac{(x_{0}-\frac{k}{n})^{2}}{1/2^{2N_{0}}} p_{n,k}(x_{0}), \end{align*}$$
where
$k\in A_{1}$
implies
$\frac {(x_{0}-\frac {k}{n})^{2}}{1/2^{2N_{0}}}\geq 1$
by definition and where
$p_{n,k}(x_{0})\geq 0$
is also used. Now apply the second formula from (2.3) to the final formula in the previous centred equation to obtain
$$\begin{align*}\textstyle \sum_{k\in A_{1}} \big| f\big(\frac{k}{n}\big) -f(x_{0}) \big| p_{n,k}(x_{0})\leq 2M_{0}2^{2N_{0}} \frac{x_{0}(1-x_{0})}{n} \leq \frac{1}{2^{k_{0}+1}}. \end{align*}$$
Thus, we have obtained
$|f(x_{0})- B_{n}(f, x_{0})|\leq \frac {1}{2^{k_{0}}}$
and uniform convergence.
Next, we wish to generalise the previous theorem to discontinuous functions, for which the following theorem from the literature (see, e.g., [Reference Herzog and Hill33, Theorem 5.1] or [Reference Chlodovsky18, Section 4, p. 68]) is essential, namely to Theorems 2.3 and 2.4.
Theorem 2.2 (
${\textsf {ACA}}_{0}^{\omega }$
).
For any
$f:[0,1]\rightarrow [0,1]$
and
$x\in (0,1)$
such that
$f(x+)$
and
$f(x-)$
existFootnote
6
, we have
$$ \begin{align}\textstyle \frac{f(x+)+f(x-)}{2}=\lim_{n\rightarrow \infty }B_{n}(f, x). \end{align} $$
Proof. First of all, the proof of the theorem is similar to that of Theorem 2.1, but more complicated as
$f(x_{0})$
in (2.4) is replaced by
$\frac {f(x_{0}+)+f(x_{0}-)}{2}$
in (2.6). In particular, (2.6) involves more sums than (2.1), but the only ‘new’ part is to show that (2.11) becomes arbitrarily small. An elementary proof of this fact is tedious but straightforward. For this reason, we have provided a sketch with ample references.
Secondly, fix
$k_{0}\in {\mathbb N}$
and
$x_{0}\in {\mathbb R}$
such that the left and right limits
$f(x_{0}-)$
and
$f(x_{0}+)$
exist. By definition, there is
$N_{0}\in {\mathbb N}$
such that for any
$y, z\in [0,1]$
:
$$\begin{align*}\textstyle x_{0}-\frac{1}{2^{N_{0}}}<z <x_{0}<y <x_{0}+\frac{1}{2^{N_{0}}}\rightarrow \big[\textstyle |f(x_{0}+)&-f(y)|< d\tfrac{1}{2^{k_{0}+1}} \wedge |f(x_{0}-)-f(z)|< d\tfrac{1}{2^{k_{0}+1}}\big]. \end{align*}$$
Note that increasing
$N_{0}$
does not change the previous property. Now use
$(\exists ^{2})$
to define
$A_{0}:=\{ k\leq n : x_{0}\leq k/n <x_{0}+\frac {1}{2^{N_{0}}}\}$
,
$A_{1}:=\{ k\leq n : x_{0}-\frac {1}{2^{N_{0}}}\leq k/n <x_{0}\}$
, and
$A_{2}:= \{k\leq n:|x_{0}-k/n|\geq \frac {1}{2^{N_{0}}} \} $
and consider:
$$ \begin{align}\textstyle B_{n}(f, x_{0})-\frac{f(x_{0}+)+f(x_{0}-)}{2} &\textstyle=\sum_{k=0}^n \big(f\big(\frac{k}{n}\big) -\frac{f(x_{0}+)+f(x_{0}-)}{2} \big )p_{n,k}(x_{0})\notag\\ &\textstyle=\sum_{i=0}^{2}\sum_{k\in A_{i}} \big(f\big(\frac{k}{n}\big) -\frac{f(x_{0}+)+f(x_{0}-)}{2} \big)p_{n,k}(x_{0}), \end{align} $$
where the first equality follows by the final formula in (2.3) for
$x=x_{0}$
.
Thirdly, we note that
$k\in A_{2}$
implies
$\frac {(x_{0}-\frac {k}{n})^{2}}{1/2^{2N_{0}}}\geq 1$
by definition, yielding
$$ \begin{align}\textstyle \sum_{k\in A_{2}}p_{n,k}(x_{0})\leq \sum_{k\in A_{2}} \frac{(x_{0}-\frac{k}{n})^{2}}{1/2^{2N_{0}}} p_{n,k}(x_{0})\leq \sum_{k\leq n} \frac{(x_{0}-\frac{k}{n})^{2}}{1/2^{2N_{0}}} p_{n,k}(x_{0}), \end{align} $$
where the second inequality holds since
$p_{n, k}(x_{0})\geq 0$
by (2.3). Now apply the second formula in (2.3) to (2.7) to obtain
$\sum _{k\in A_{2}}p_{n,k}(x_{0})\leq 2^{2N_{0}} \frac {x_{0}(1-x_{0})}{n} $
. Since f is assumed to be bounded on
$[0,1]$
, we have for
$n\geq 2^{2N_{0}+k_{0}+1}$
:
$$ \begin{align}\textstyle |\sum_{k\in A_{2}} \big(f\big({k}/{n}\big) -\frac{f(x_{0}+)+f(x_{0}-)}{2} \big)p_{n,k}(x)|<\frac{1}{2^{k_{0}+1}}. \end{align} $$
Fourth, we consider another sum from (2.6), namely the following:
$$ \begin{align}\textstyle &\textstyle\sum_{k\in A_{0}} \big(f\big(\frac{k}{n}\big) -\frac{f(x_{0}+)+f(x_{0}-)}{2} \big)p_{n,k}(x_{0})\notag\\ &=\textstyle\sum_{k \in A_0} (f(\frac{k}{n})-f(x_0+))p_{n,k}(x_0)+\frac{f(x_0+)-f(x_0-)}{2}(\sum_{k \in A_0}p_{n,k}(x_0)\big). \end{align} $$
By the choice of
$N_{0}$
, the first sum in (2.9) satisfies
$$ \begin{align} \textstyle |\sum_{k \in A_0} (f(\frac{k}{n})-f(x_0+))p_{n,k}(x_0)|&\leq \textstyle \sum_{k \in A_0} |f(\frac{k}{n})-f(x_0+)|p_{n,k}(x_0)\notag\\ &\textstyle\leq \frac{1}{2^{k_{0}+1}}\sum_{k\in A_{0}}p_{k, n}(x_{0})\leq \frac{1}{2^{k_{0}+1}}, \end{align} $$
where the final step in (2.10) follows from the final formula in (2.3). The same, namely a version of (2.9) and (2.10), holds mutatis mutandis for
$A_{1}$
. Thus, consider (2.11) which consists of the second sum of (2.9) and the analogous sum for
$A_{1}$
:
$$ \begin{align}\textstyle \frac{f(x_0+)-f(x_0-)}{2}(\sum_{k \in A_0}p_{n,k}(x_0) - \sum_{k\in A_{1}}p_{n,k}(x_0) ). \end{align} $$
Now,
$p_{n,k}(x)$
is well-known as the binomial distribution and the former’s properties are usually established in probability theory via conceptual results like the central limit theorem. In particular, for large enough
$N_{0}$
and associated n, the sums
$\sum _{k \in A_{i}}p_{n,k}(x_0)$
for
$i=0,1$
from (2.11) can be shown to be arbitrarily close to
$\frac 12$
. In light of (2.11), a proof (in
${\textsf {ACA}}_{0}^{\omega }$
) of this limiting behaviour of
$\sum _{k \in A_{i}}p_{n,k}(x_0)$
(for
$i=0,1$
) establishes (2.5) and the theorem.
Finally, an elementary proof of the limit behaviour of
$\sum _{k \in A_{i}}p_{n,k}(x_0)$
(
$i=0, 1$
) proceeds along the following lines, based on the de Moivre–Laplace theorem which is apparently a predecessor to the central limit theorem.
-
• First of all, Stirling’s formula provides approximations to the factorial
$n!$
. There are many elementary proofs of this formula (see, e.g., [Reference Borwein and Corless13, Reference Chung and AitSahlia19, Reference Feller24, Reference Impens38]). -
• Secondly, the de Moivre–Laplace theorem states approximations to the sum
$\sum _{k=k_{1}}^{k_{2}}p_{n,k}(x)$
in terms of the Gaussian integral
$\int e^{\frac {-t^{2}}{2}}dt $
([Reference Papoulis and Unnikrishna70]). There are elementary proofs of this approximation using (only) Stirling’s formula, namely [Reference Feller25, Chapter VII, Section 3, p. 182] or [Reference Chung and AitSahlia19, Theorem 6, p. 228]. -
• Thirdly, applying the previous for
$\sum _{k \in A_{i}}p_{n,k}(x_0)$
(
$i=0, 1$
), one observes that the only non-explicit term in the latter is
$\int _{0}^{+\infty } e^{\frac {-t^{2}}{2}}dt =\frac {\sqrt {2\pi }}{2}$
; the former sum is therefore arbitrarily close to
$\frac {1}{2}$
for
$N_{0}$
and n large enough.
It is a tedious but straightforward verification that the above proofs can be formalised in
${\textsf {ACA}}_{0}^{\omega }$
(and likely
${\textsf {RCA}}_{0}$
). Alternatively, one establishes basic properties of the
$\Gamma $
-function (see [Reference Borwein and Corless13]) and derives the de Moivre–Laplace theorem [Reference Papoulis and Unnikrishna70].
The final part of the previous proof involving
$\sum _{k \in A_{i}}p_{n,k}(x_0)$
, amounts to the special case of the theorem for (a version of) of the Heaviside function as follows:
$$\begin{align*}H(x):= \begin{cases} 1, & x\geq 0, \\ 0, & \text{otherwise.} \end{cases} \end{align*}$$
Building on the previous theorem, we can now develop the RM-study of approximation theorem for discontinuous functions.
Theorem 2.3 (
${\textsf {RCA}}_{0}^{\omega }$
).
The following are equivalent, where
$I\equiv [0,1]$
.
-
(a)
${\textsf {WKL}}_{0}$
. -
(b) For any function
$f:[0,1]\rightarrow {\mathbb R}$
, f is continuous on
$(0,1)$
if and only if the equation (2.2) holds uniformly on
$(0,1)$
. -
(c) For any cadlag
$f:I\rightarrow {\mathbb R}$
and
$x\in (0,1)$
, we have (2.12)with uniform convergence if
$$ \begin{align}\textstyle \frac{f(x+)+f(x-)}{2}=\lim_{n\rightarrow \infty }B_{n}(f, x), \end{align} $$
$C_{f}=I$
.
-
(d) For any
$U_{0}$
-function
$f:I\rightarrow {\mathbb R}$
and any
$x\in (0,1)$
, (2.12) holds, with uniform convergence if
$C_{f}=I$
.
If we additionally assume
${\textsf {QF-AC}}^{0,1}$
, the following are equivalent to
${\textsf {WKL}}_{0}$
.
-
(e) For any regulated
$f:I\rightarrow {\mathbb R}$
and
$x\in (0,1)$
, (2.12) holds, with uniform convergence if
$C_{f}=I$
. -
(f) For any locally bounded
$f:I\rightarrow {\mathbb R}$
and any
$x\in (0,1)$
such that
$f(x+)$
and
$f(x-)$
exist, (2.12) holds, with uniform convergence if
$C_{f}=I$
. -
(g) The previous item restricted to any function class containing
$C([0,1])$
.
Proof. First of all, to derive item (b) from
${\textsf {WKL}}_{0}$
, let
$f:[0,1]\rightarrow {\mathbb R}$
be such that (2.12) holds uniformly. Now fix
$k_{0}\in {\mathbb N}$
and let
$N_{0}\in {\mathbb N}$
be such that for
$n\geq N_{0}$
and
$x\in (0,1)$
,
$|B_{n}(f, x)-f(x)|<\frac {1}{2^{k_{0}}}$
. Then
$B_{N_{0}}(f, x)$
is uniformly continuous, say with modulus h ([Reference Simpson83, IV.2.9]). Fix
$x, y\in (0,1)$
with
$|x-y|<\frac {1}{2^{h(k_{0})}}$
and consider
$$\begin{align*}\textstyle |f(x)-f(y)|&\leq |f(x)-B_{N_{0}}(f, x)|+ |B_{N_{0}}(f, x)-B_{N_{0}}(f, y)|\\ &\quad +|B_{N_{0}}(f, y)-f(y)|\leq \frac{3}{2^{k_{0}}}. \end{align*}$$
To show that item (a) follows from items (b)–(g), note that each of the latter implies the second item from Theorem 2.1, i.e.,
${\textsf {WKL}}_{0}$
follows.
Secondly, to show that item (a) implies items (b)–(g), we invoke the law of excluded middle as in
$(\exists ^{2})\vee \neg (\exists ^{2})$
. In case
$\neg (\exists ^{2})$
, all functions on the reals are continuous by [Reference Kohlenbach46, Proposition 3.12]. In this case,
${\textsf {WKL}}_{0}$
implies the other items from the theorem by Theorem 2.1. In case
$(\exists ^{2})$
holds, items (b)–(g) follow by Theorem 2.2, assuming we can provide an upper bound to the functions at hand. To this end, if
$f:[0,1]\rightarrow {\mathbb R}$
is unbounded, apply
${\textsf {QF-AC}}^{0,1}$
to the formula
$$ \begin{align} (\forall n\in {\mathbb N})(\exists x\in [0,1])(|f(x)|>n), \end{align} $$
yielding a sequence
$(x_{n})_{n\in {\mathbb N}}$
such that
$|f(x_{n})|>n$
for all
$n\in {\mathbb N}$
; the latter sequence has a convergent sub-sequence, say with limit
$y\in [0,1]$
, by sequential compactness [Reference Simpson83, III.2]. Clearly, f is not locally bounded at y and hence also not regulated. We note that for unbounded cadlag or
$U_{0}$
-functions, (2.13) reduces to
$(\forall n\in {\mathbb N})(\exists q\in [0,1]\cap {\mathbb Q})(|f(q)|>n)$
, i.e., we can use
${\textsf {QF-AC}}^{0,0}$
(included in
${\textsf {RCA}}_{0}^{\omega }$
).
The ‘excluded middle trick’ from the previous proof should be used sparingly as some of our mathematical notions do not make muchFootnote
7
sense in
${\textsf {RCA}}_{0}^{\omega }$
. Using suitable modulus functions (for the definition of
$f(x+)$
and
$f(x-)$
), one could express uniform convergence of (2.12) for regulated functions; this does not seem to yield very elegant results, however.
Next, we briefly treat equivalences involving
${\textsf {ACA}}_{0}^{\omega }$
(and
${\textsf {ATR}}_{0}$
) and approximation theorems via Bernstein polynomials. Note that the functions
$g, h$
in the second item of Theorem 2.4 can be discontinuous and recall the set from (2.1). For the final item, there are many function classes between
$BV$
and regulated, like the functions of bounded Waterman variation (see [Reference Appell, Banaś and Merentes1]).
Theorem 2.4 (
${\textsf {RCA}}_{0}^{\omega }$
).
The following are equivalent to
${\textsf {ACA}}_{0}:$
-
(a) (Jordan) For continuous
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there are continuous and non-decreasing
$g, h:[0,1]\rightarrow {\mathbb R}$
such that
$f=g-h$
. -
(b) For continuous
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there are non-decreasing
$g, h:[0,1]\rightarrow {\mathbb R}$
such that
$f=g-h$
and
$B_{g}=B_{h}=[0,1]$
. -
(c) For continuous
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there are non-decreasing
$g, h:[0,1]\rightarrow {\mathbb R}$
such that
$f=g-h$
and
$B_{g}$
and
$B_{h}$
are dense in
$[0,1]$
. -
(d) For continuous
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there are non-decreasing
$g, h:[0,1]\rightarrow {\mathbb R}$
such that
$f=g-h$
and
$B_{g}$
and
$B_{h}$
have measure
$1$
. -
(e) For continuous
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there are non-decreasing
$g, h:[0,1]\rightarrow {\mathbb R}$
such that
$f=g-h$
and
$B_{g}$
and
$B_{h}$
are non-enumerable.
Proof. The equivalence between
${\textsf {ACA}}_{0}$
and item (a) is proved in [Reference Nies, Triplett and Yokoyama60] for RM-codes. Now, RM-codes for continuous functions denote third-order functions by [Reference Normann and Sanders68, Theorem 2.2], working in
${\textsf {RCA}}_{0}^{\omega }$
. Moreover, a continuous and non-decreasing function on
$[0,1]$
is determined by the function values on
$[0,1]\cap {\mathbb Q}$
, i.e., one readily obtains an RM-code for such functions in
${\textsf {RCA}}_{0}^{\omega }$
. In this way, item (a) is equivalent to
${\textsf {ACA}}_{0}$
as well. Item (b) follows from item (a) by Theorem 2.2. To show that item (b) implies item (a), invoke the law of excluded middle as in
$(\exists ^{2})\vee \neg (\exists ^{2})$
. In case
$(\exists ^{2})$
holds,
${\textsf {ACA}}_{0}$
and item (a) is immediate. In case
$\neg (\exists ^{2})$
holds, all functions on
${\mathbb R}$
are continuous [Reference Kohlenbach46, Proposition 3.12] and item (a) trivially follows from item (b). The other items are treated in (exactly) the same way.
We could also generalise Theorem 2.4 using pseudo-monotonicity [Reference Appell, Banaś and Merentes1, Definition 1.14], originally introduced by Josephy [Reference Josephy42] as the largest class such that composition with
$BV$
maps to
$BV$
. The RM of
${\textsf {ATR}}_{0}$
as in [Reference Normann and Sanders68, Theorem 2.25] includes the Jordan decomposition theorem restricted to
$BV$
-functions with an arithmetical graph. One readily shows that
${\textsf {ATR}}_{0}$
is equivalent to the third-to-fifth items in Theorem 2.4 with ‘continuous’ removed and restricted to ‘arithmetical
$f:[0,1]\rightarrow {\mathbb R}$
’.
Next, we establish an equivalence for
$(\exists ^{2})$
involving Bernstein polynomials. We note that ‘splittings’ as in Theorem 2.5 are rare in second-order RM, but not in higher-order RM, as studied in detail in [Reference Sanders76]. One can prove that
${\textsf {WKL}}_{0}$
in the theorem cannot be replaced by weak weak König’s lemma (see, e.g., [Reference Simpson83, X.1]).
Theorem 2.5 (
${\textsf {RCA}}_{0}^{\omega }$
).
The following are equivalent to
$(\exists ^{2}):$
-
(a) There is
$f:[0,1]\rightarrow [0,1]$
and
$x\in (0,1)$
such that
$f(x)\ne \lim _{n\rightarrow \infty }B_{n}(f, x)$
. -
(b)
${\textsf {WKL}}_{0}$
(or
${\textsf {ACA}}_{0}$
) plus
$:$
there is
$f:[0,1]\rightarrow {\mathbb R}$
and
$x\in (0,1)$
such that
$f(x)\ne \lim _{n\rightarrow \infty }B_{n}(f, x)$
. -
(c)
${\textsf {WKL}}_{0}$
(or
${\textsf {ACA}}_{0}$
) plus
$:$
there is
$f:[0,1]\rightarrow {\mathbb R}$
that is not bounded (or
$:$
not Riemann integrable, or
$:$
not uniformly continuous).
We cannot remove
${\textsf {WKL}}_{0}$
from the second or third item.
Proof. That
$(\exists ^{2})$
implies items (a) and (b) follows by applying Theorem 2.2 to the (suitably modified) Heaviside function. Item (c) follows from
$(\exists ^{2})$
by considering, e.g., Dirichlet’s function
$\mathbb {1}_{\mathbb Q}$
for the Riemann integrable case. Now let
$f:[0,1]\rightarrow [0,1]$
be as in item (a) and use Theorem 2.2 to conclude that f is discontinuous; then
$(\exists ^{2})$
follows by [Reference Kohlenbach46, Proposition 3.12].
Next, assume item (b) and suppose
$f:[0,1]\rightarrow {\mathbb R}$
as in the latter is continuous on
$[0,1]$
. Then
${\textsf {WKL}}_{0}$
implies that f is bounded [Reference Normann and Sanders68, Theorem 2.8]; now use Theorem 2.2 to obtain a contradiction, i.e., f must be discontinuous and
$(\exists ^{2})$
follows as before. That item (c) implies
$(\exists ^{2})$
follows in the same way. Finally, observe that by Theorem 2.1,
${\textsf {RCA}}_{0}^{\omega }+\neg {\textsf {WKL}}_{0}$
proves: there is
$f:[0,1]\rightarrow {\mathbb R}$
and
$x\in (0,1)$
such that
$f(x)\ne \lim _{n\rightarrow \infty }B_{n}(f, x)$
. Since
$\neg {\textsf {WKL}}_{0}\rightarrow \neg (\exists ^{2})$
, the final sentence follows and we are done.
Finally, the previous results are not unique: [Reference Bojanić and Chêng8, Theorem 2] expresses that for
$f:[-1, 1]\rightarrow {\mathbb R}$
of bounded variation and
$x_{0}\in (-1, 1)$
, the lim sup and lim inf of the Hermite–Fejér polynomial
$H_{n}(f, x)$
is some (explicit) term involving
$f(x_{0}+)$
and
$f(x_{0}-)$
; this term reduces to
$f(x)$
in case f is continuous at x. The proof of this convergence result is moreover lengthy but straightforward, i.e., readily formalised in
${\textsf {ACA}}_{0}^{\omega }$
. Perhaps surprisingly, the general case essentially reduces to the particular case of the Heaviside function, like in Theorem 2.2. A more complicated, but conceptually similar, approximation result may be found in [Reference Kumar, Kumar and Devaraj51]. Moreover, the Bohman–Korovkin theorem [Reference Lorentz, Golitschek and Makovoz55] suggests near-endless variations of Theorem 2.3.
3 Equivalences involving new Big systems
3.1 Introduction
In the below sections, we establish equivalences between the new Big systems from [Reference Normann and Sanders64, Reference Sanders78, Reference Sanders79] and properties of Bernstein polynomials for (dis)continuous functions, as sketched in Section 1.1.
-
• The uncountability of
${\mathbb R}$
is equivalent to the statement that for regulated functions, the Bernstein polynomials converge to the function value for at least one real (Section 3.2). -
• The enumeration principle
${\textsf {enum}}$
for countable sets is equivalent to the statement that for regulated functions, the Bernstein polynomials converge to the function value for all reals outside of a given sequence (Section 3.3). -
• The pigeon-hole principle for measure is equivalent to the statement that for Riemann integrable functions, the Bernstein polynomials converge to the function value almost everywhere (Section 3.4).
-
• The Baire category theorem is equivalent to the statement that for semi-continuous functions, the Bernstein polynomials converge to the function value for at least one real (Section 3.5).
The second item provides interesting insights into the coding practice of RM: while the Banach space
$C([0,1])$
can be given a code in
${\textsf {RCA}}_{0}^{\omega }+{\textsf {WKL}}$
, the relatively powerful principle
${\textsf {enum}}$
is required to code the Banach space of regulated functions by item (c) of Theorem 3.8.
Now, by the results in [Reference Normann and Sanders64, Reference Normann and Sanders65], the relatively strong system
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
cannot prove the uncountability of
${\mathbb R}$
formulated as follows
$$ \begin{align*} \textsf{NIN}_{[0,1]}:\text{ there is no injection from }[0,1]\text{ to }{\mathbb N}, \end{align*} $$
where
${\textsf {Z}}_{2}^{\omega }$
proves the same second-order sentences as second-order arithmetic
${\textsf {Z}}_{2}$
(see [Reference Hunter35] and Section 1.2.2); the system
${\textsf {Z}}_{2}^{\Omega }$
does prove
${\textsf {NIN}}_{[0,1]}$
, as many of the usual proofs of the uncountability of
${\mathbb R}$
show. The above-itemised principles, i.e., the Baire category theorem, the enumeration principle, and the pigeon-hole principle for measure, which are studied in Sections 3.3 and 3.4, all imply
${\textsf {NIN}}_{[0,1]}$
. In this way, certain approximation theorems are classified in the Big Five by Theorems 2.3 and 2.4, while slight variations or generalisations go far beyond the Big Five in light of Theorems 3.3, 3.8, 3.17, and 3.15, but are still equivalent to known principles, in accordance with the general theme of RM.
Finally, at least two of the above systems yield conservative extensions of
${\textsf {ACA}}_{0}$
, where
${\textsf {PHP}}_{[0,1]}$
expresses that for a sequence of closed sets of measure zero, the union also has measure zero (see Section 3.4).
Theorem 3.1.
-
• The system
${\textsf {ACA}}_{0}^{\omega }+{\textsf {NIN}}_{[0,1]}$
is
$\Pi _{2}^{1}$
-conservative over
${\textsf {ACA}}_{0}$
. -
• The system
${\textsf {ACA}}_{0}^{\omega }+{\textsf {PHP}}_{[0,1]}$
is
$\Pi _{2}^{1}$
-conservative over
${\textsf {ACA}}_{0}$
.
Proof. Kreuzer shows in [Reference Kreuzer50] that
${\textsf {ACA}}_{0}^{\omega }+(\pmb {\lambda })$
is
$\Pi _{2}^{1}$
-conservative over
${\textsf {ACA}}_{0}$
, where
$(\pmb {\lambda })$
expresses the existence of the Lebesgue measure
${\pmb {\lambda }}^{3}$
as a fourth-order functional on
$2^{{\mathbb N}}$
and
$[0,1]$
. To derive
${\textsf {NIN}}_{[0,1]}$
in the former system, let
$Y:[0,1]\rightarrow {\mathbb N}$
be an injection and derive a contradiction from the sub-additivity of
$\pmb {\lambda }$
as follows:
$$\begin{align*}\textstyle \pmb{\lambda}([0,1])=\pmb{\lambda}(\cup_{n\in {\mathbb N}} E_{n} )\leq \sum_{n\in {\mathbb N}}\pmb{\lambda}(E_{n})=0, \end{align*}$$
where
$E_{n}:=\{ x\in [0,1]:Y(x)=n\}$
is at most a singleton, i.e.,
$\pmb {\lambda }(E_{n})=0$
. The system
${\textsf {ACA}}_{0}^{\omega }+(\pmb {\lambda })$
trivially proves
${\textsf {PHP}}_{[0,1]}$
.
3.2 The uncountability of the reals
In this section, we establish equivalences between approximation theorems involving Bernstein polynomials and the uncountability of the reals. Our results also improve the base theory used in [Reference Sanders78].
First of all, we will study the uncountability of the reals embodied by the following principle, motivated by the observations in Section 1.2.4. As discussed in Section 3.1,
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
does notFootnote
8
prove
${\textsf {NIN}}_{{\textsf {alt}}}$
, and the same for the equivalent approximation theorems in Theorem 3.3.
Principle 3.2 (
${\textsf {NIN}}_{{\textsf {alt}}}$
).
The unit interval is not height-countable.
This principle was first introduced in [Reference Sanders78] where many equivalences are established, mainly for basic properties of regulated functions and related classes.
Secondly, we have the following theorem involving equivalences for
${\textsf {NIN}}_{{\textsf {alt}}}$
. Item (d) is defined using
$B_{f}$
from (2.1) and constitutes a variation of Volterra’s early theorem from [Reference Volterra90] that there is no
$f:{\mathbb R}\rightarrow {\mathbb R}$
satisfying
$C_{f}={\mathbb Q}$
. In light of the first equivalence, the restriction in item (c) is non-trivial.
Theorem 3.3 (
${\textsf {ACA}}_{0}^{\omega }+{\textsf {QF-AC}}^{0,1}$
).
The following are equivalent.
-
(a) The uncountability of
${\mathbb R}$
as in
${\textsf {NIN}}_{{\textsf {alt}}}$
. -
(b) For regulated
$f:[0,1]\rightarrow {\mathbb R}$
, there is
$x\in (0,1)\setminus {\mathbb Q}$
where f is continuous. -
(c) For regulated and pointwise discontinuous
$f:[0,1]\rightarrow {\mathbb R}$
, there is
$x\in (0,1)\setminus {\mathbb Q}$
where f is continuous. -
(d) (Volterra) There is no regulated
$f:[0,1]\rightarrow {\mathbb R}$
, such that
$B_{f}= {\mathbb Q}.$
-
(e) For regulated
$f:[0,1]\rightarrow {\mathbb R}$
, there is
$x\in (0,1)$
where f is continuous. -
(f) For regulated
$f:[0,1]\hspace{-1pt}\rightarrow\hspace{-1pt} {\mathbb R}$
, there is
$x\hspace{-1pt}\in\hspace{-1pt} (0,1)$
where
$f(x)\hspace{-1pt}=\hspace{-1pt}\lim _{n\rightarrow \infty } B_{n}(f, x)$
. -
(g) For regulated
$f:[0,1]\rightarrow {\mathbb R}$
, the set
$B_{f}$
is not (height-)countable.
Proof. First of all, (a)
$\rightarrow $
(b) is proved by contraposition as follows: let
$f:[0,1]\rightarrow {\mathbb R}$
be regulated and discontinuous on
$[0,1]\setminus {\mathbb Q}$
. In particular,
$[0,1]\setminus {\mathbb Q}=D_{f}= \cup _{k\in {\mathbb N}}D_{k}$
where
$D_{k}$
is as in (1.7). To show that
$D_{k}$
is finite, suppose it is not, i.e., for any
$N\in {\mathbb N}$
, there are
$x_{0}, \dots x_{N}\in D_{k}$
. Use
$(\exists ^{2})$
and
${\textsf {QF-AC}}^{0,1}$
to obtain a sequence
$(x_{n})_{n\in {\mathbb N}}$
in
$D_{k}$
. Since sequential compactness follows from
${\textsf {ACA}}_{0}$
[Reference Simpson83, III.2.2], the latter sequence has a convergent sub-sequence, say with limit
$y\in [0,1]$
. Then either on the left or on the right of y, one finds infinitely many elements of the sequence. Then either
$f(y+)$
or
$f(y-)$
does not exist, a contradiction, and
$D_{k}$
is finite.
To establish
$\neg {\textsf {NIN}}_{{\textsf {alt}}}$
, let
$(q_{m})_{m\in {\mathbb N}}$
be an enumeration of
${\mathbb Q}$
without repetitions and define a height function
$H:[0,1]\rightarrow {\mathbb N}$
for
$[0,1]$
as follows:
$H(x)=n$
in case
$x\in D_{n}$
and n is the least such number,
$H(x)=m$
in case
$x=q_{m}$
otherwise. By contraposition and using
${\textsf {QF-AC}}^{0,1}$
, one proves that the union of two finite sets is finite, implying that
$D_{k}\cup \{q_{0}, \dots , q_{k}\}$
is finite. A direct proof in
${\textsf {ACA}}_{0}^{\omega }$
is also possible as the second set has an (obvious) enumeration. Hence,
$[0,1]$
is height countable, as required for
$\neg {\textsf {NIN}}_{{\textsf {alt}}}$
.
Secondly, (b)
$\rightarrow $
(d) is immediate by Theorem 2.2 and the fact that
$f(x+)=f(x-)=f(x)$
in case
$x\in C_{f}$
. Now assume item (d) and suppose
${\textsf {NIN}}_{{\textsf {alt}}}$
is false, i.e.,
$H:[0,1]\rightarrow {\mathbb N}$
is a height function for
$[0,1]$
. Define
$g:[0,1]\rightarrow [0,1]$
using
$(\exists ^{2})$
:
$$\begin{align*}g(x):= \begin{cases} \frac{1}{2^{H(x)}} & x\not \in {\mathbb Q}, \\ 0 & x \in {\mathbb Q}. \end{cases} \end{align*}$$
To show that
$g(x+)=g(x-)=0$
for any
$x\in (0,1)$
, consider
$$ \begin{align}\textstyle (\forall k\in {\mathbb N} )(\exists N\in {\mathbb N})(\forall y \in (x-\frac{1}{2^{N}}, x))(|g(y)|<\frac{1}{2^{k}}). \end{align} $$
Suppose (3.1) is false, i.e., there is
$k_{0}\in {\mathbb N}$
such that
$(\forall N\in {\mathbb N})(\exists y \in (x-\frac {1}{2^{N}}, x))(|f(y)|\geq \frac {1}{2^{k}})$
. Modulo the coding of real numbers, apply
${\textsf {QF-AC}}^{0,1}$
to obtain a sequence of reals
$(y_{n})_{n\in {\mathbb N}}$
such that
$$ \begin{align}\textstyle (\forall N\in {\mathbb N})( y_{N} \in (x-\frac{1}{2^{N}}, x)\wedge |g(y_{N})|\geq \frac{1}{2^{k_{0}}}). \end{align} $$
Using
$\mu ^{2}$
, we can guarantee that each
$y_{n}$
is unique using the (limited) primitive recursionFootnote
9
available in
${\textsf {RCA}}_{0}^{\omega }$
. Now, by definition, the set
$C:=\{x\in [0,1]: H(x)\leq {k_{0}}\}$
is finite, say with upper bound
$K_{0}\in {\mathbb N}$
. Apply (3.2) for
$N=K_{0}+2$
and note that
$y_{0}, \dots , y_{K_{0}+2}$
are in C by the definition of g, a contradiction. Hence, (3.1) is correct, implying that g is regulated. Now apply item (d) to obtain
$x_{0}\in (0, 1)\setminus {\mathbb Q}$
such that
$g(x_{0})=\lim _{n\rightarrow \infty }B_{n}(g, x_{0})$
. However,
$g(x_{0})>0$
and
$B_{n}(g, x_{0})=0$
, a contradiction, and
${\textsf {NIN}}_{{\textsf {alt}}}$
must hold. The equivalence involving item (c) is immediate as g is continuous at every rational point in
$[0,1]$
, i.e., pointwise discontinuous.
Thirdly, we immediately have (b)
$\rightarrow $
(e)
$\rightarrow $
(f) by Theorem 2.2, and to show that item (f) implies
${\textsf {NIN}}_{{\textsf {alt}}}$
, we again proceed by contraposition. To this end, let
$H:{\mathbb R}\rightarrow {\mathbb N}$
be a height function for
$[0,1]$
and define
$h(x):= \frac {1}{2^{H(x)+1}}$
. We now prove prove
$\lim _{n\rightarrow \infty }B_{n}(h, x)=0$
for all
$x\in [0,1]$
. As Bernstein polynomials only invoke rational function values,
$B_{n}(h, x)=B_{n}(\tilde {h}, x)$
for all
$x\in [0,1]$
and
$n\in {\mathbb N}$
, where
$$ \begin{align} \tilde{h}(x):= \begin{cases} 0 & \text{ if }x\not \in {\mathbb Q},\\ \frac{1}{2^{H(x)+1}} & \text{ otherwise, } \end{cases} \end{align} $$
which is essentially a version of Thomae’s function [Reference Normann and Sanders68, Reference Thomae86]. Similar to g above, one verifies that
$\tilde {h}$
is continuous on
$[0,1]\setminus {\mathbb Q}$
using the fact that H is a height function. By Theorem 2.2, we have
$0=\tilde {h}(x)=\lim _{n\rightarrow \infty }B_{n}(\tilde {h}, x)$
for
$x\in (0,1)\setminus {\mathbb Q}$
. By the uniform continuity of the polynomials
$p_{k, n}(x)$
on
$[0,1]$
, we also have
$\lim _{n\rightarrow \infty }B_{n}(\tilde {h}, q)=0$
for
$q\in [0,1]\cap {\mathbb Q}$
. As a result, we obtain
$\lim _{n\rightarrow \infty }B_{n}(h, x)=0$
for all
$x\in [0,1]$
, which implies the negations of items (e) and (f), as
$h(x)>0$
for all
$x\in [0,1]$
. Clearly, item (g) implies item (f) while the former readily follows from
${\textsf {NIN}}_{{\textsf {alt}}}$
. Indeed, if item (g) is false for some regulated
$f:[0,1]\rightarrow {\mathbb R}$
, then
$C_{f}\subset B_{f}=\cup _{n\in {\mathbb N}}E_{n}$
by Theorem 2.2 for a sequence of finite sets
$(E_{n})_{n\in {\mathbb N}}$
. Since
$D_{f}=\cup _{n\in {\mathbb N}}D_{n}$
,
$[0,1]$
is height-countable as
$D_{n}\cup E_{n}$
is finite by the first paragraph of the proof.
We note that the base theory in the previous theorem is much weaker than in [Reference Sanders78]. Indeed, in the latter, the base theory also contained various axioms governing finite sets, all provable from the induction axiom. It seems that the latter can always be replaced by proofs by contradiction involving
${\textsf {QF-AC}}^{0,1}$
.
It is interesting that we can study items (b) and (d) without using (basic) real analysis, while items (e) and (f) seem to (really) require the study of the Bernstein approximation of (3.3). Theorem 3.3 goes through for ‘regulated’ replaced by ‘bounded variation’ if we assume, e.g., a small fragment of the classical function hierarchy, namely that a regulated function has bounded Waterman variation [Reference Appell, Banaś and Merentes1].
Next, we show that we can weaken the conclusion of item (e) in Theorem 3.3 to the weak continuity notions from Definition 3.4; these are a considerable improvement over, e.g., quasi-continuity in [Reference Sanders78] and go back over a hundred years, namely to Young [Reference Young93] and Blumberg [Reference Blumberg7].
Definition 3.4 (Weak continuity).
For
$f:[0,1]\rightarrow {\mathbb R}$
, we have that
$:$
-
• f is almost continuous (Husain, see [Reference Blumberg7, Reference Husain36]) at
$x\in [0,1]$
if for any open
$G\subset {\mathbb R}$
containing
$f(x)$
, the set
$\overline {f^{-1}(G)}$
is a neighbourhood of x. -
• f has the Young condition at
$x\in [0,1]$
if there are sequences
$(x_{n})_{n\in {\mathbb N}}, (y_{n})_{n\in {\mathbb N}}$
on the left and right of x with the latter as limit and
$\lim _{n\rightarrow \infty }f(x_{n})=f(x)=\lim _{n\rightarrow \infty }f(y_{n})$
.
With these definitions in place, we now have the following corollary to Theorem 3.3, which establishes a nice degree of robustness for the RM of
${\textsf {NIN}}_{{\textsf {alt}}}$
.
Corollary 3.5. Theorem 3.3 holds if we replace ‘continuity’ in item (e) by ‘almost continuity’ or ‘the Young condition’.
Proof. Assuming
${\textsf {NIN}}_{{\textsf {alt}}}$
, the function
$h:[0,1]\rightarrow {\mathbb R}$
from the proof of Theorem 3.3 does not satisfy either weak continuity notion anywhere. Indeed, the sequences from the Young condition are immediately seen to violate the fact that H from the proof of Theorem 3.3 is a height-function for
$[0,1]$
. Similarly, take any
$x_{0}\in [0,1]$
and note that for
$k_{0}\in {\mathbb N}$
such that
$\frac {1}{2^{k_{0}}}< h(x_{0})$
, the set
$f^{-1}(B(x_{0}, \frac {1}{2^{k_{0}}}))$
is finite, as H is a height-function for
$[0,1]$
.
3.3 The enumeration principle
In this section, we establish equivalences between approximation theorems involving Bernstein polynomials and the enumeration principle for height-countable sets as in Principle 3.6. Our results significantly improve the base theory used in [Reference Normann and Sanders64] and provide the ‘definitive’ RM of Jordan’s decomposition theorem [Reference Jordan41], especially in light of the new connection to Helly’s selection theorem as in Principle 3.7.
First of all, we will study Principle 3.6, motivated by Section 1.2.4.
Principle 3.6 (
${\textsf {enum}}$
).
A height-countable set in
$[0,1]$
can be enumerated.
We stress that textbooks (see, e.g., [Reference Appell, Banaś and Merentes1, p. 28] and [Reference Rudin74, p. 97]) generally only prove that certain sets are (height) countable, i.e., no enumeration is provided, while the latter is readily assumed in other places, i.e.,
${\textsf {enum}}$
is implicit in the mathematical mainstream. By the results in [Reference Normann and Sanders64],
${\textsf {ACA}}_{0}^{\omega }+{\textsf {enum}}$
proves
${\textsf {ATR}}_{0}$
and
$\Pi _{1}^{1} {\text{-}{\textsf {CA}}}_{0}^{\omega }+{\textsf {enum}}$
proves
$\Pi _{2}^{1}{\text{-}\textsf {CA}}_{0}$
, i.e.,
${\textsf {enum}}$
is rather ‘explosive’, in contrast to
${\textsf {NIN}}_{[0,1]}$
by Theorem 3.1.
A variation of
${\textsf {enum}}$
for countable sets, called
${\textsf {cocode}}_{0}$
, is studied in [Reference Normann and Sanders64] where many equivalences are established; the base theories used in [Reference Normann and Sanders64] are however not always elegant. Now, most proofs in [Reference Normann and Sanders64] go through mutatis mutandis for ‘countable’ replaced by ‘height-countable’; the latter’s central role was not known during the writing of [Reference Normann and Sanders64]. We provide some examples in Theorem 3.8, including new results for Bernstein approximation. We also need the following principle which is a contraposed version of Helly’s selection theorem [Reference Helly32, Reference Natanson58]; the RM of the latter for codes of
$BV$
-functions is studied in, e.g., [Reference Kreuzer49].
Principle 3.7 (Helly).
Let
$(f_{n})_{n\in {\mathbb N}}$
be a sequence of
$[0,1]\rightarrow [0,1]$
-functions in
$BV$
with pointwise limit
$f:[0,1]\rightarrow [0,1]$
which is not in
$BV$
. Then there is unbounded
$g\in {\mathbb N}^{{\mathbb N}}$
such that
$g(n)\leq V_{0}^{1}(f_{n})\leq g(n)+1$
for all
$n\in {\mathbb N}$
.
Intuitively, Helly is a rather weak statement that significantly simplifies the RM-study of
${\textsf {enum}}$
and
${\textsf {NIN}}_{{\textsf {alt}}}$
.
Next, we establish Theorem 3.8 where we note that the base theory is weaker than in [Reference Normann and Sanders64]. Indeed, in the latter, the base theory also contains various axioms governing countable sets, mostly provable from the induction axiom.
Theorem 3.8 (
${\textsf {ACA}}_{0}^{\omega }+{\textsf {QF-AC}}^{0,1}$
).
The following are equivalent.
-
(a) The enumeration principle
${\textsf {enum}}$
. -
(b) For regulated
$f:[0,1]\rightarrow {\mathbb R}$
, there is a sequence
$(x_{n})_{n\in {\mathbb N}}$
enumerating
$D_{f}$
. -
(c) For regulated
$f:[0,1]\rightarrow {\mathbb R}$
and
$p, q\in [0,1]\cap {\mathbb Q}$
,
$\sup _{x\in [p,q]}f(x)$
existsFootnote
10
. -
(d) For regulated and pointwise discontinuous
$f:[0,1]\rightarrow {\mathbb R}$
, there is a sequence
$(x_{n})_{n\in {\mathbb N}}$
enumerating
$D_{f}$
. -
(e) For regulated
$f:[0,1]\rightarrow {\mathbb R}$
, there is
$(x_{n})_{n\in {\mathbb N}}$
enumerating
$[0,1]\setminus B_{f}$
. -
(f) (Jordan) For
$f:{\mathbb R}\rightarrow {\mathbb R}$
which is in
$BV([0, a])$
for all
$a>0$
, there are monotone
$g, h:{\mathbb R}\rightarrow {\mathbb R}$
such that
$f(x)=g(x)-h(x)$
for
$x\geq 0$
. -
(g) The combination of
$:$
-
(f.1) Helly’s selection theorem as in Principle 3.7.
-
(f.2) (Jordan) For
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there are non-decreasing
$g, h:{\mathbb R}\rightarrow {\mathbb R}$
such that
$f(x)=g(x)-h(x)$
for
$x\in [0,1]$
.
-
Proof. The implication (a)
$\rightarrow $
(b) follows by noting that
$D_{k}$
as in (1.7) is finite, as established in the proof of Theorem 3.3, and applying
${\textsf {enum}}$
. The implication (b)
$\rightarrow $
(e) follows from Theorem 2.2. The implication (b)
$\rightarrow $
(c) is immediate as we can replace the supremum over
$p, q$
in
$\sup _{x\in [p,q]}f(x)$
by a supremum over
$[p, q]\cap ({\mathbb Q}\cup D_{f})$
.
For the implication (e)
$\rightarrow $
(a), let A be height-countable, i.e., there is
$H:{\mathbb R}\rightarrow {\mathbb N}$
such that
$A_{n}:=\{x\in [0,1]: H(x)<n\}$
is finite. Note that we can use
$\mu ^{2}$
to enumerate
$A\cap {\mathbb Q}$
, i.e., we may assume the latter is empty. Now define
$g:[0,1]$
as
$$ \begin{align} g(x):= \begin{cases} \frac{1}{2^{n+1}} & \text{ if }x\in A\text{ and }n\text{ is the least natural such that }H(x)<n,\\ 0 & \text{ if }x\not \in A. \end{cases} \end{align} $$
The function g satisfies
$g(x+)=g(x-)=0$
for
$x\in (0,1)$
, which is proved in exactly the same way as in the proof of Theorem 3.3. Let
$(x_{n})_{n\in {\mathbb N}}$
be the sequence provided by item (e) and note that by Theorem 2.2,
$(\forall n\in {\mathbb N})(x\ne x_{n} )$
implies
$g(x)=\frac {g(x+)+g(x-)}{2}=0$
for any
$x\in (0,1)$
. Hence,
$(x_{n})_{n\in {\mathbb N}}$
includes all elements of A, and
$(\exists ^{2})$
can remove all elements not in A, as required for
${\textsf {enum}}$
. Item (b) trivially implies item (d), while g from (3.4) is continuous on the rationals and therefore pointwise discontinuous, i.e., item (d) also implies item (a). To show that item (c) implies
${\textsf {enum}}$
, apply the former to g as in (3.4). In particular, one enumerates
$D_{g}$
using the usual interval-halving technique.
For the implication (a)
$\rightarrow $
(f), let f be as in the former and define
$D_{n,k}$
as
$$\begin{align*}\textstyle D_{n,k}:=\{ x\in [0,n]: |f(x)-f(x+)|>\frac{1}{2^{k}}\vee |f(x)-f(x-)|>\frac{1}{2^{k}} \}, \end{align*}$$
where we note that
$BV$
-functions are regulated (using
${\textsf {QF-AC}}^{0,1}$
) by [Reference Normann and Sanders65, Theorem 3.33]. As for
$D_{k}$
in (1.7), this set is finite and
$D_{f}=\cup _{n, k\in {\mathbb N}}D_{n,k}$
can be enumerated thanks to
${\textsf {enum}}$
. Now consider the variation function defined as
$$ \begin{align}\textstyle V_{0}^{y}(f):=\sup_{0\leq x_{0}< \dots< x_{n}\leq y}\sum_{i=0}^{n} |f(x_{i})-f(x_{i+1})|, \end{align} $$
where the supremum is over all partitions of
$[0, y]$
. Since we have an enumeration of
$D_{f}$
, (3.5) can be defined using
$\exists ^{2}$
by restricting the supremum to
${\mathbb Q}$
and this enumeration. By definition,
$g(x):=\lambda x.V_{0}^{y}(f)$
is non-decreasing and the same for
$h(x):=g(x)-f(x)$
. For the reverse implication, let A be height-countable, i.e., there is
$H:{\mathbb R}\rightarrow {\mathbb N}$
such that
$A_{n}:=\{x\in [0,1]: H(x)<n\}$
is finite. Then let
$f:{\mathbb R}\rightarrow {\mathbb R}$
be the indicator function of
$A_{n}$
on
$[0, n]$
, which is
$BV$
on
$[0, n]$
by [Reference Normann and Sanders65, Theorem 3.33]. Now apply item (f) and note that
$(\exists ^{2})$
can enumerate
$D_{g}$
for monotone g by [Reference Normann and Sanders65, Theorem 3.33], i.e.,
${\textsf {enum}}$
now follows.
To establish item (g) using
${\textsf {enum}}$
, sub-item (f.2) is a special case of item (f). For sub-item (f.1), consider Helly’s selection theorem, usually formulated as follows.
$$ \begin{align*} &\textit{Let }(f_{n})_{n\in {\mathbb N}} \textit{ be a sequence of }BV\textit{-functions such that }f_{n} \textit{ and }V_{0}^{1}(f_{n}) \textit{ are uniformly}\\ &\quad\textit{bounded. Then there is a sub-sequence }(f_{n_{k}})_{k\in {\mathbb N}} \textit{ with pointwise limit} f\in BV. \end{align*} $$
To establish the centred statement, Helly’s original proof from [Reference Helly32, p. 287] or [Reference Natanson58, p. 222] goes through in
${\textsf {ACA}}_{0}^{\omega }+{\textsf {enum}}$
as follows: for a sequence
$(f_{n})_{n\in {\mathbb N}}$
in
$BV$
as above, one uses
${\textsf {enum}}$
to obtain sequences of monotone functions
$(g_{n})_{n\in {\mathbb N}}$
and
$(h_{n})_{n\in {\mathbb N}}$
such that
$f_{n}=g_{n}-h_{n}$
. Then
$(g_{n})_{n\in {\mathbb N}}$
and
$(h_{n})_{n\in {\mathbb N}}$
have convergent sub-sequences with limits g and h that are monotone, which is (even) provable in
${\textsf {ACA}}_{0}^{\omega }$
. Essentially by definition,
$f=g-h$
is then the limit of the associated sub-sequence of
$(f_{n})_{n\in {\mathbb N}}$
. To obtain sub-item (f.1), use the contraposition of the centred statement, i.e., if the limit function f is not in
$BV$
, then
$(\forall N\in {\mathbb N})(\exists n)(V_{0}^{1}(f_{n})\geq N )$
. As in the previous paragraph,
$V_{0}^{1}(f_{n})$
can be defined using
$\exists ^{2}$
, given
${\textsf {enum}}$
. The function
$g\in {\mathbb N}^{{\mathbb N}}$
from the conclusion of sub-item (f.1) is therefore readily obtained (using
${\textsf {QF-AC}}^{0,0}$
and
$\exists ^{2}$
).
For the remaining implication (g)
$\rightarrow $
(a), let A be height-countable, i.e., there is
$H:{\mathbb R}\rightarrow {\mathbb N}$
such that
$A_{n}:=\{x\in [0,1]: H(x)<n\}$
is finite. As above, we may assume
$A\cap {\mathbb Q}=\emptyset $
as
$\exists ^{2}$
can enumerate the rationals in A. Define
$f_{n}(x):=\mathbb {1}_{A_{n}}(x)$
, which is
$BV$
by [Reference Normann and Sanders65, Theorem 3.33] and note
$\lim _{n\rightarrow \infty }f_{n}=f$
where
$f:=\mathbb {1}_{A}$
. If
$f\in BV$
, apply sub-item (f.2) and recall that
$(\exists ^{2})$
can enumerate
$D_{g}$
for monotone g by [Reference Normann and Sanders65, Theorem 3.33], i.e.,
${\textsf {enum}}$
now follows. If
$f\not \in BV$
, let
$g_{0}\in {\mathbb N}^{{\mathbb N}}$
be the function provided by sub-item (f.1) and note that
$V_{0}^{1}(f_{n})\leq g_{0}(n)+1$
implies that
$A_{n}$
is finite and has size bound
$g_{0}(n)+2$
. Now let
$\tilde {g}:[0,1]\rightarrow {\mathbb R}$
be (3.4) with ‘
$\frac {1}{2^{n}}$
’ replaced by ‘
$\frac {1}{2^{n}(g_{0}(n)+2)}$
’. Clearly, for any partition of
$[0,1]$
, we have
$\sum _{i=0}^{n} |\tilde {g}(x_{i})-\tilde {g}(x_{i+1})|\leq \sum _{i=0}^{n}\frac {1}{2^{i}}\leq 2$
, i.e.,
$\tilde {g}$
is in
$BV$
. Applying sub-item (f.2) to
$\tilde {g}$
,
${\textsf {enum}}$
follows as before, and we are done.
Regarding item (e) in Theorem 3.8, basic examples show that
$C_{f}\ne B_{f}$
, while the first equivalence in Theorem 3.3 shows that the restriction in item (d) is non-trivial. Item (c) expresses that the Banach space of regulated functions requires
${\textsf {enum}}$
, in contrast to, e.g., the Banach space of continuous functions ([Reference Simpson83, IV.2.13]). Moreover, the use of monotone functions in Theorem 3.8 can be replaced by weaker conditions, as follows.
Corollary 3.9. One can replace ‘monotone’ in items (f) or (g) by
$:$
-
•
$U_{0}$
-function, or
$:$
-
• regulated
$f:[0,1]\rightarrow {\mathbb R}$
such that for all
$x\in (0,1)$
, we have (3.6)
$$ \begin{align}\textstyle |f(x)-\lim_{n\rightarrow \infty} B_{n}(f, x)|\leq |\frac{f(x+)-f(x-)}{2}|. \end{align} $$
Proof. By [Reference Normann and Sanders68, Theorem 2.16],
$(\exists ^{2})$
suffices to enumerate the discontinuity points for functions satisfying the items in the corollary.
Next, Helly’s theorem as in Principle 3.7 is useful in the RM of the uncountability of
${\mathbb R}$
, as follows.
Theorem 3.10 (
${\textsf {ACA}}_{0}^{\omega }+\textsf {Helly}$
).
The following are equivalent.
-
(a) The uncountability of
${\mathbb R}$
as in
${\textsf {NIN}}_{{\textsf {alt}}}$
. -
(b) (Volterra) There is no
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, such that
$B_{f}= {\mathbb Q}$
. -
(c) For
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there is
$x\in (0,1)$
where f is continuous. -
(d) For
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there is
$x\in (0,1)$
where
$f(x)=\lim _{n\rightarrow \infty } B_{n}(f, x)$
. -
(e) For
$f:[0,1]\rightarrow {\mathbb R}$
in
$BV$
, there is
$x\in (0,1)$
such that (1.5) or (3.6).
Proof. That
${\textsf {NIN}}_{{\textsf {alt}}}$
implies the items (b)–(e) follows as in the proof of Theorem 3.3, namely by considering
$D_{k}$
from (1.7). For
$f\in BV$
with variation bounded by
$1$
, this set has at most
$2^{n}$
elements, as each element of
$D_{n}$
contributes at least
$\frac {1}{2^{n}}$
to the total variation, by definition. Hence,
$D_{k}$
is finite without the use of
${\textsf {QF-AC}}^{0,1}$
. Now,
${\textsf {NIN}}_{{\textsf {alt}}}$
implies that
$D_{f}=\cup _{k\in {\mathbb N}}D_{k}$
is not all of
$[0,1]$
, i.e.,
$C_{f}\ne \emptyset $
and the other items follow. To derive
${\textsf {NIN}}_{{\textsf {alt}}}$
from items (b)–(e), let
$H:[0,1]\rightarrow {\mathbb N}$
be a height-function for
$[0,1]$
and consider the finite sets
$A_{n}=\{x\in [0,1]:H(x)<n \}$
and
$B_{n}=A_{n}\setminus {\mathbb Q}$
. As above,
$\mathbb {1}_{B_{n}}$
is in
$BV$
but
$\lim _{n\rightarrow \infty }\mathbb {1}_{B_{n}}=\mathbb {1}_{{\mathbb R}\setminus {\mathbb Q}}$
is not in
$BV$
. Let
$g_{0}\in {\mathbb N}^{{\mathbb N}}$
be the function provided by Helly’s selection theorem and let
$g_{1}\in {\mathbb N}^{{\mathbb N}}$
be such that
$|A_{n}\cap {\mathbb Q}|\leq g_{1}(n)$
for all
$n\in {\mathbb N}$
, which is readily defined using
$\exists ^{2}$
. By definition,
$|A_{n}|\leq g_{0}(n)+g_{1}(n)+1$
for all
$n\in {\mathbb N}$
and define
$$\begin{align*}\textstyle g(x):=\frac{1}{2^{H(x)+1}}\frac{1}{(g_{0}(H(x)) +g_{1}(H(x)+1) +1 )}. \end{align*}$$
The latter is in
$BV$
(total variation at most
$1$
) and is totally discontinuous, i.e., item (c) is false, as required. The other implications follow in the same way.
We believe that Helly’s selection theorem as in Principle 3.7 is weak and in particular does not imply
${\textsf {NIN}}_{[0,1]}$
.
Finally, we attempt to explain why seemingly related mathematical notions behave so differently in higher-order RM.
Remark 3.11 (Second-order-ish functions).
As discussed in detail in [Reference Normann and Sanders68], quasi-continuous and cliquish
$[0,1]\rightarrow [0,1]$
functions are intimately related from the pov of real analysis. Nonetheless,
${\textsf {RCA}}_{0}^{\omega }+{\textsf {WKL}}_{0}$
proves that the former have a supremum while
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
cannot prove the existence of a supremum for the latter. A similar observation can be made for many pairs of function classes, including cadlag and regulated functions.
The crucial observation here is that for quasi-continuous and cadlag functions, the function value
$f(x)$
for any
$x\in [0,1]$
is determined if we know
$f(q)$
for any
$q\in [0,1]\cap {\mathbb Q}$
, provably in
${\textsf {ACA}}_{0}^{\omega }$
. We refer to such function classes as second-order-ish as their definition comes with an obvious second-order approximation device. By contrast, cliquish and regulated functions are not determined in this way, i.e., they apparently lack the latter device.
With the gift of hindsight, properties of second-order-ish function classes can be established in
${\textsf {RCA}}_{0}^{\omega }$
extended with the Big Five systems, which is one of the main observations of [Reference Normann and Sanders68]. By contrast, basic properties of non-second-order-ish functions can often not be proved in
${\textsf {Z}}_{2}^{\omega }$
or even
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
. Thus, our equivalences seems to be robust as long as we stay within the second-order-ish function classes, or dually: within the non-second-order-ish ones.
3.4 Pigeon hole principle for measure spaces
We introduce Tao’s pigeonhole principle for measure spaces from [Reference Tao85] and obtain equivalences involving the approximation theorem for Riemann integrable functions via Bernstein polynomials. The latter is studied in [Reference Chlodovsky18] where it is claimed this result goes back to Picard [Reference Picard71].
First of all, the pigeonhole principle as in
${\textsf {PHP}}_{[0,1]}$
is studied in [Reference Sanders79], with a number of equivalences for basic properties of Riemann integrable functions.
Principle 3.12 (
${\textsf {PHP}}_{[0,1]}$
).
If
$ (X_n)_{n \in {\mathbb N}}$
is an increasing sequence of measure zero and closed sets of reals in
$[0,1]$
, then
$ \bigcup _{n \in {\mathbb N} } X_n$
has measure zero.
By the main result of [Reference Trohimčuk88], not all nowhere dense measure zero sets are the countable union of measure zero closed sets, i.e.,
${\textsf {PHP}}_{[0,1]}$
does not generate ‘all’ measure zero sets.
Secondly, fragments of the induction axiom are sometimes used in an essential way in second-order RM (see, e.g., [Reference Neeman59]). An important role of induction is to provide ‘finite comprehension’ (see [Reference Simpson83, X.4.4]). As in [Reference Sanders79], we need the following fragment of finite comprehension, provable from the induction axiom.
Principle 3.13 (
${\textsf {IND}}_{{\mathbb R}}$
).
For
$F:({\mathbb R}\times {\mathbb N})\rightarrow {\mathbb N}, k\in {\mathbb N}$
, there is
$X\subset {\mathbb N}$
such that
$$\begin{align*}(\forall n\leq k)\big[ (\exists x\in {\mathbb R})(F(x, n)=0)\leftrightarrow n\in X\big]. \end{align*}$$
In particular, the following rather important result seems to require
${\textsf {IND}}_{{\mathbb R}}$
.
Theorem 3.14 (
${\textsf {ACA}}_{0}^{\omega }+{\textsf {IND}}_{{\mathbb R}}$
).
For Riemann integrable
$f:[0,1]\rightarrow {\mathbb R}$
with oscillation function
${\textsf {osc}}_{f}:[0,1]\rightarrow {\mathbb R}$
, the set
$D_{k}:=\{x\in [0,1]:{\textsf {osc}}_{f}(x)\geq \frac {1}{2^{k}}\}$
is measure zero for any fixed
$k\in {\mathbb N}$
.
Proof. The theorem follows from [Reference Sanders79, Corollary 3.4]. A sketch of the proof of the latter is as follows: let
$f:[0,1]\rightarrow {\mathbb R}$
be Riemann integrable with oscillation function
${\textsf {osc}}_{f}:[0,1]\rightarrow {\mathbb R}$
, such that
$D_{k_{0}}:=\{x\in [0,1]:{\textsf {osc}}_{f}(x)\geq \frac {1}{2^{k_{0}}}\}$
has measure
$\varepsilon>0$
for some fixed
$k_{0}\in {\mathbb N}$
. For a partition P given as
$0=x_{0}, t_{0},x_{1}, t_{1}, x_{1}, \dots , x_{k-1}, t_{k}, x_{k}=1 $
with small enough mesh, one obtains two partitions
$P', P"$
: as follows: in case
$[x_{i}, x_{i+1}]\cap D_{k_{0}}\ne \emptyset $
, replace
$t_{i}$
by respectively
$t_{i}'$
and
$t_{i}"$
such that
$|f(t_{i}')-f(t_{i}")|\geq \frac {1}{2^{k_{0}}}$
; these reals exist by definition of
$D_{k_{0}}$
. By definition,
$S(f, P')$
and
$S(f, P")$
are at least
$\varepsilon /2^{k_{0}+1}$
apart, i.e., f is not Riemann integrable, a contradiction. The definition of
$P', P"$
can be formalised using
${\textsf {IND}}_{{\mathbb R}}$
.
Thirdly, we establish Theorem 3.15 where we recall the set
$B_{f}$
from (2.1).
Theorem 3.15 (
${\textsf {ACA}}_{0}^{\omega }+{\textsf {IND}}_{{\mathbb R}}+{\textsf {QF-AC}}^{0,1}$
).
The following are equivalent.
-
(a) The pigeonhole principle for measure spaces as in
${\textsf {PHP}}_{[0,1]}$
. -
(b) (Vitali–Lebesgue) For Riemann integrable
$f:[0,1]\rightarrow {\mathbb R}$
with an oscillation function, the set
$ C_{f}$
has measure
$1$
. -
(c) For Riemann integrable
$f:[0,1]\rightarrow {\mathbb R}$
with an oscillation function, the set
$ B_{f}$
has measure
$1$
. -
(d) For Riemann integrable
$f:[0,1]\rightarrow {\mathbb R}$
with an oscillation function, the set of all
$x\in (0,1)$
such that (1.5) (or (3.6)) has measure
$1$
. -
(e) For Riemann integrable and pointwise discontinuous
$f:[0,1]\rightarrow {\mathbb R}$
with an oscillation function, the set
$ B_{f}$
has measure
$1$
. -
(f) For Riemann integrable lsco
$f:[0,1]\rightarrow {\mathbb R}$
, the set
$ B_{f}$
has measure
$1$
.
We can replace ‘usco’ by ‘cliquish with an oscillation function’ in the above.
Proof. First of all, assume
${\textsf {PHP}}_{[0,1]}$
and let
$f:[0,1]\rightarrow {\mathbb R}$
be as in item (b) of the theorem. By Theorem 3.14, each
$D_{k}:=\{x\in [0,1]:{\textsf {osc}}_{f}(x)\geq \frac {1}{2^{k}}\}$
has measure zero. By [Reference Sanders79, Theorem 1.17],
${\textsf {osc}}_{f}$
is usco and hence
$D_{k}$
is closed; both facts essentially follow by definition as well. Then
${\textsf {PHP}}_{[0,1]}$
implies that
$D_{f}=\cup _{k}D_{k}$
has measure zero, yielding item (b). By Theorem 2.2,
$B_{f}$
has measure one, i.e., item (c) follows, and the same for items (d) and (e).
For item (f), we proceed in essentially the same way:
$D_{f}$
exists in
${\textsf {ACA}}_{0}^{\omega }+{\textsf {QF-AC}}^{0,1}$
by [Reference Sanders79, Theorem 2.4], and we just need to define some kind of ‘replacement’ set for
$D_{k}$
. To this end, let
$f:[0,1]\rightarrow {\mathbb R}$
be lsco and consider:
$$ \begin{align}\textstyle f(x)\leq q \wedge (\forall N\in {\mathbb N})(\exists z\in B(x, \frac{1}{2^{N}})~\cap~{\mathbb Q})( f(z)>q+\frac{1}{2^{l}} ). \end{align} $$
Using
$(\exists ^{2})$
, let
$E_{q, l}$
be the set of all
$x\in [0,1]$
satisfying (3.7). Since f is lsco, (3.7) is-essentially by definition-equivalent to
$$ \begin{align*} \textit{the formula }(3.7) \textit{ with } `\cap~{\mathbb Q}\text{'} \textit{ omitted}. \end{align*} $$
Intuitively, the set
$E_{q,l}$
provides a ‘replacement’ set for
$D_{k}$
. Indeed, since f is lsco, the set
$E_{q,l}$
is closed. Moreover, we also have
$D_{f}=\cup _{l\in {\mathbb N}, q\in {\mathbb Q}}E_{q,l}$
, by the epsilon–delta definition of (local) continuity. That
$E_{q, l}$
has measure zero is proved in the same way as for
$D_{k}$
in Theorem 3.14. Again,
${\textsf {PHP}}_{[0,1]}$
implies that
$D_{f}$
has measure zero and Theorem 2.2 implies that
$B_{f}$
has measure one, as required for item (f).
To derive
${\textsf {PHP}}_{[0,1]}$
from item (f) (or the items (b)–(e)), let
$(X_{n})_{n\in {\mathbb N}}$
be an increasing sequence of closed and measure zero sets. Since
${\mathbb Q}$
has an enumeration, if
$\cup _{n\in {\mathbb N}}X_{n}\setminus {\mathbb Q}$
has measure zero, so does
$\cup _{n\in {\mathbb N}}X_{n}$
, say in
${\textsf {ACA}}_{0}^{\omega }$
. Hence, we may assume that
${\mathbb Q}\cap \cup _{n\in {\mathbb N}}X_{n}=\emptyset $
. Now consider the following function, which is usco, cliquish, and its own oscillation function by [Reference Sanders79, Theorems 1.16–1.18]:
$$ \begin{align} h(x):= \begin{cases} 0 & x\not \in \cup_{m\in {\mathbb N}}X_{m}, \\ \frac{1}{2^{n+1}} & x\in X_{n} \text{ and }n\text{ is the least such number,} \end{cases} \end{align} $$
and which satisfies
$B_{n}(h, x)=0$
for all
$x\in [0,1]$
. Now, h is Riemann integrable with integral equal to zero on
$[0,1]$
, which can be proved using the obviousFootnote
11
epsilon–delta proof. Moreover, since
${\mathbb Q}\cap \cup _{n\in {\mathbb N}}X_{n}=\emptyset $
, h is continuous at any rational and therefore pointwise discontinuous, i.e., the equivalence for item (e) readily follows. By item (f),
$B_{f}$
has measure
$1$
, implying that for almost all
$x\in (0,1)$
, we have
$h(x)=\lim _{n\rightarrow \infty } B_{n}(h,x )=0$
, i.e.,
$\cup _{n\in {\mathbb N}}X_{n}$
has measure zero, and
${\textsf {PHP}}_{[0,1]}$
follows. Note that item (d) also guarantees that
$h(x)=0$
almost everywhere, i.e.,
$\cup _{n\in {\mathbb N}}X_{n}$
has measure zero. For the final sentence of the theorem, recall that the function
$h:[0,1]\rightarrow {\mathbb R}$
from (3.8) is cliquish.
In light of Theorem 3.14, Riemann integrable functions can almost be proved to be continuous ae. However,
${\textsf {PHP}}_{[0,1]}$
is needed to establish that
$D_{f}=\cup _{k\in {\mathbb N}}D_{k}$
has measure zero. The restriction in item (e) is non-trivial as is it consistent with
${\textsf {Z}}_{2}^{\omega }$
that there are Riemann integrable functions that are totally discontinuous.
As to generalisations of the previous theorem, there are a surprisingly large number of rather diverse equivalent definitions of ‘Baire 1’ on the reals [Reference Baire5, Reference Koumoullis48, Reference Lee, Tang and Zhao53], including B-class-1-measurability and fragmentedness by [Reference Koumoullis48, Theorem 2.3] and [Reference Kuratowski52, Section 34, paragraph VII]. One readily shows that h from (3.8) satisfies these definitions, say in
${\textsf {ACA}}_{0}^{\omega }$
, i.e., the previous theorem can be formulated for these notions. By contrast, the restriction of item (b) or (e) in Theorem 3.15 to (the standard definition of) Baire 1 functions, can be proved in
${\textsf {ACA}}_{0}^{\omega }$
by [Reference Sanders79, Theorem 3.7]. In general, the function h from (3.8) is rather well-behaved and therefore included in many (lesser known than Baire 1) function classes.
3.5 Baire category theorem
We introduce the Baire category theorem and obtain equivalences involving the approximation theorem for usco and cliquish functions via Bernstein polynomials. The RM of
${\textsf {BCT}}_{[0,1]}$
as in Principle 3.16 and
${\textsf {PHP}}_{[0,1]}$
is often similar (see [Reference Sanders79]), which is why we treat the former in less detail.
First of all, we shall study the Baire category theorem formulated as follows. We have established a substantial number of equivalences in [Reference Sanders79] between this principle and basic properties of usco functions and related classes.
Principle 3.16 (
${\textsf {BCT}}_{[0,1]}$
).
If
$ (O_n)_{n \in {\mathbb N}}$
is a decreasing sequence of dense open sets of reals in
$[0,1]$
, then
$ \bigcap _{n \in {\mathbb N} } O_n$
is non-empty.
We assume that
$O_{n+1}\subseteq O_{n}$
for all
$n\in {\mathbb N}$
to avoid the use of induction to prove that a finite intersection of open and dense sets is again open and dense.
Secondly, we have the following theorem where we recall the set
$B_{f}$
from (2.1).
Theorem 3.17 (
${\textsf {ACA}}_{0}^{\omega }$
).
The following are equivalent.
-
(a) The Baire category theorem as in
${\textsf {BCT}}_{[0,1]}$
. -
(b) For usco
$f:[0,1]\rightarrow {\mathbb R}$
, the set
$ C_{f}$
is non-empty. -
(c) For cliquish
$f:[0,1]\rightarrow {\mathbb R}$
with an oscillation function, we have
$ C_{f}\ne \emptyset $
. -
(d) For usco
$f:[0,1]\rightarrow {\mathbb R}$
, the set
$ B_{f}$
is non-empty. -
(e) For cliquish
$f:[0,1]\rightarrow {\mathbb R}$
with an oscillation function,
$ B_{f}$
is non-empty.
Proof. For the implications (d)
$\rightarrow $
(a) and (e)
$\rightarrow (a)$
, let
$ (O_n)_{n \in {\mathbb N}}$
be a decreasing sequence of dense open sets of reals in
$[0,1]$
. In case there is
$q\in {\mathbb Q} $
with
$q\in \cap _{n\in {\mathbb N}}O_{n}$
,
${\textsf {BCT}}_{[0,1]}$
follows. For the case where
$\emptyset ={\mathbb Q}\cap \left (\cap _{n\in {\mathbb N}}O_{n}\right )$
, we proceed as follows. For
$X_{n}:= [0,1]\setminus O_{n}$
, consider h as in (3.8), which is usco, cliquish, and its own oscillation function by [Reference Sanders79, Theorems 1.16–1.18]. Hence, the set
$B_{h}$
from (2.1) is non-empty given item (d) or (e). We now show that
$\lim _{n\rightarrow \infty }B_{n}(h, x)=0$
for all
$x\in [0,1]$
, finishing the proof. To this end, recall that
${\mathbb Q}\subset \cup _{n\in {\mathbb N}}X_{n}$
and define
$Q_{n}:= X_{n}\cap {\mathbb Q} $
where
${\mathbb Q}=\cup _{n\in {\mathbb N}}Q_{n}$
. Now consider
$\tilde {h}:[0,1]\rightarrow {\mathbb R}$
as follows:
$$ \begin{align} \tilde{h}(x):= \begin{cases} 0 & x\not \in {\mathbb Q}, \\ \frac{1}{2^{n+1}} & x\in Q_{n} \text{ and }n\text{ is the least such number,} \end{cases} \end{align} $$
which is really a modification of Thomae’s function (see [Reference Normann and Sanders68, Reference Thomae86]). Then
$\tilde {h}$
is continuous on
$[0,1]\setminus {\mathbb Q}$
since each
$X_{n}$
is nowhere dense and closed. By Theorem 2.2, we have
$0=\tilde {h}(x)=\lim _{n\rightarrow \infty }B_{n}(\tilde {h}, x)$
for
$x\in (0,1)\setminus {\mathbb Q}$
. By the uniform continuity of the polynomials
$p_{k, n}(x)$
on
$[0,1]$
, we also have
$\lim _{n\rightarrow \infty }B_{n}(\tilde {h}, q)=0$
for
$q\in [0,1]\cap {\mathbb Q}$
. Since Bernstein polynomials only invoke rational function values, we have
$B_{n}(h, x)=B_{n}(\tilde {h}, x)$
for any
$x\in [0,1]$
and
$n\in {\mathbb N}$
. Hence, we conclude
$\lim _{n\rightarrow \infty }B_{n}({h}, x)=0$
for
$x\in [0,1]$
, as required.
Finally, the implications (a)
$\rightarrow $
(b)
$\rightarrow $
(d) and (a)
$\rightarrow $
(c)
$\rightarrow $
(e) follow from [Reference Sanders79, Theorem 2.3 and 2.16] and Theorem 2.2. For the first implication, one now defines a variation of
$E_{q, l}$
based on (3.7) to replace
$D_{k}$
, while the third one follows by the textbook proof.
As also stated in [Reference Sanders79], much to our own surprise, the ‘counterexample’ function from (3.8) has nice properties that are provable in weak systems, including the behaviour of the associated Bernstein polynomials.
Finally, we discuss certain restrictions of the above theorems.
Remark 3.18 (Restrictions, trivial, and otherwise).
It should not be a surprise that suitable restrictions of principles that imply
${\textsf {NIN}}_{[0,1]}$
, are again provable from the (second-order) Big Five. We discuss three examples pertaining to the above where two are perhaps surprising.
First of all, item (b) in Theorem 3.8 is equivalent to
${\textsf {ATR}}_{0}$
if we restrict to functions with an arithmetical or
$\Sigma _{1}^{1}$
-graph by [Reference Normann and Sanders68, Section 2.6]. The results in the latter pertain to bounded variation functions but are readily adapted to regulated functions, which also only have countably many points of discontinuity. Thus, the same restriction of item (e) in Theorem 3.8 is equivalent to
${\textsf {ATR}}_{0}$
in the same way. Similar results hold for the restriction to quasi-continuous functions.
Secondly, item (b) in Theorem 3.8 is provableFootnote
12
from
${\textsf {ATR}}_{0}$
(and extra induction) when restricted to Baire 1 functions by [Reference Normann and Sanders68, Section 2.6]. By Theorem 2.2, the same holds for the restriction to Baire 1 functions of (e) in Theorem 3.8. However, this restriction does not seem to be a ‘real’ one as many a textbook tells us that
$$ \begin{align} \textit{regulated functions are Baire 1 on the reals}. \end{align} $$
Of course, (3.10) is true but
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
cannot prove it by [Reference Normann and Sanders68, Theorem 2.35]. In general, the usual picture of the classical hierarchy of function classes looks very different in weak logical systems and even in
${\textsf {Z}}_{2}^{\omega }$
. Indeed, by Theorem 3.3, it is consistent with
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
that there are regulated functions that are discontinuous everywhere.
Thirdly, similar to the previous paragraph, item (b) of Theorem 3.17 restricted to Baire 1 functions is provable in
${\textsf {ACA}}_{0}^{\omega }$
by [Reference Sanders79, Theorem 2.9]. Again, this restriction does not seem ‘real’ as it is well-known that
$$ \begin{align} \textit{usco functions are Baire 1 on the reals}, \end{align} $$
but
${\textsf {Z}}_{2}^{\omega }+{\textsf {QF-AC}}^{0,1}$
cannot prove (3.11) by [Reference Sanders79, Corollary 2.8]. Unfortunately, the second-order coding of usco and lsco functions from [Reference Fernández-Duque, Shafer and Yokoyama26] is such that the Baire 1 representation of usco and lsco is ‘baked into’ the coding, in light of [Reference Fernández-Duque, Shafer and Yokoyama26, Section 6]. It would therefore be more correct to refer to the representations from [Reference Fernández-Duque, Shafer and Yokoyama26] as codes for usco functions that are also Baire 1. What is worse, (3.11) implies
${\textsf {enum}}$
is therefore not an ‘innocent’ background assumption in RM, as
${\textsf {ACA}}_{0}^{\omega }+{\textsf {enum}}$
proves
${\textsf {ATR}}_{0}$
and
$\Pi _{1}^{1} {\text{-}{\textsf {CA}}}_{0}^{\omega }+{\textsf {enum}}$
proves
$\Pi _{2}^{1}{\text{-}\textsf {CA}}_{0}$
(see Section 3.3).
4 Appendix. Technical Appendix: introducing Reverse Mathematics
We discuss the language of Reverse Mathematics (Section 4.1) and introduce—in full detail—Kohlenbach’s base theory of higher-order Reverse Mathematics (Section 4.2). Some common notations may be found in Section 4.3.
4.1 Introduction
We sketch some aspects of Kohlenbach’s higher-order RM [Reference Kohlenbach46] essential to this paper, including the base theory
${\textsf {RCA}}_{0}^{\omega }$
(Definition 4.1).
First of all, in contrast to ‘classical’ RM based on second-order arithmetic
${\textsf {Z}}_{2}$
, higher-order RM uses
$\textsf {L}_{\omega }$
, the richer language of higher-order arithmetic. Indeed, while the former is restricted to natural numbers and sets of natural numbers, higher-order arithmetic can accommodate sets of sets of natural numbers, sets of sets of sets of natural numbers, et cetera. To formalise this idea, we introduce the collection of all finite types
$\mathbf {T}$
, defined by the two clauses:
$$ \begin{align*} \text{(i) }0\in \mathbf{T}\text{ and (ii) If }\sigma, \tau\in \mathbf{T}\text{ then }( \sigma \rightarrow \tau) \in \mathbf{T}, \end{align*} $$
where
$0$
is the type of natural numbers, and
$\sigma \rightarrow \tau $
is the type of mappings from objects of type
$\sigma $
to objects of type
$\tau $
. In this way,
$1\equiv 0\rightarrow 0$
is the type of functions from numbers to numbers, and
$n+1\equiv n\rightarrow 0$
. Viewing sets as given by characteristic functions, we note that
${\textsf Z}_{2}$
only includes objects of type
$0$
and
$1$
.
Secondly, the language
$\textsf {L}_{\omega }$
includes variables
$x^{\rho }, y^{\rho }, z^{\rho },\dots $
of any finite type
$\rho \in \mathbf {T}$
. Types may be omitted when they can be inferred from context. The constants of
$\textsf {L}_{\omega }$
include the type
$0$
objects
$0, 1$
and
$ <_{0}, +_{0}, \times _{0},=_{0}$
which are intended to have their usual meaning as operations on
${\mathbb N}$
. Equality at higher types is defined in terms of ‘
$=_{0}$
’ as follows: for any objects
$x^{\tau }, y^{\tau }$
, we have
$$ \begin{align} [x=_{\tau}y] \equiv (\forall z_{1}^{\tau_{1}}\dots z_{k}^{\tau_{k}})[xz_{1}\dots z_{k}=_{0}yz_{1}\dots z_{k}], \end{align} $$
if the type
$\tau $
is composed as
$\tau \equiv (\tau _{1}\rightarrow \dots \rightarrow \tau _{k}\rightarrow 0)$
. Furthermore,
$\textsf {L}_{\omega }$
also includes the recursor constant
$\mathbf {R}_{\sigma }$
for any
$\sigma \in \mathbf {T}$
, which allows for iteration on type
$\sigma $
-objects as in the special case (4.2). Formulas and terms are defined as usual. One obtains the sub-language
$\textsf {L}_{n+2}$
by restricting the above type formation rule to produce only type
$n+1$
objects (and related types of similar complexity).
4.2 The base theory of higher-order Reverse Mathematics
We introduce Kohlenbach’s base theory
${\textsf {RCA}}_{0}^{\omega }$
, first introduced in [Reference Kohlenbach46, Section 2].
Definition 4.1. The base theory
${\textsf {RCA}}_{0}^{\omega }$
consists of the following axioms.
-
(a) Basic axioms expressing that
$0, 1, <_{0}, +_{0}, \times _{0}$
form an ordered semi-ring with equality
$=_{0}$
. -
(b) Basic axioms defining the well-known
$\Pi $
and
$\Sigma $
combinators
$($
aka K and S in [Reference Avigad and Feferman3]
$)$
, which allow for the definition of
$\lambda $
-abstraction. -
(c) The defining axiom of the recursor constant
$\mathbf {R}_{0}:$
for
$m^{0}$
and
$f^{1}:$
(4.2)
$$ \begin{align} \mathbf{R}_{0}(f, m, 0):= m \text{ and } \mathbf{R}_{0}(f, m, n+1):= f(n, \mathbf{R}_{0}(f, m, n)). \end{align} $$
-
(d) The axiom of extensionality
$:$
for all
$\rho , \tau \in \mathbf {T}$
, we have (Eρ, τ)
$$\begin{align} (\forall x^{\rho},y^{\rho}, \varphi^{\rho\rightarrow \tau}) \big[x=_{\rho} y \rightarrow \varphi(x)=_{\tau}\varphi(y) \big]. \end{align} $$
-
(e) The induction axiom for quantifier-free formulas of
$\textsf {L}_{\omega }$
. -
(f)
${\textsf {QF-AC}}^{1,0}$
: the quantifier-free Axiom of Choice as in Definition 4.2.
Note that variables (of any finite type) are allowed in quantifier-free formulas of the language
$\textsf {L}_{\omega }$
: only quantifiers are banned. Recursion as in (4.2) is called primitive recursion; the class of functionals obtained from
$\mathbf {R}_{\rho }$
for all
$\rho \in \mathbf {T}$
is called Gödel’s system T of all (higher-order) primitive recursive functionals.
Definition 4.2. The axiom
${\textsf {QF-AC}}$
consists of the following for all
$\sigma , \tau \in \textbf {T}$
:
$$\begin{align} (\forall x^{\sigma})(\exists y^{\tau})A(x, y)\rightarrow (\exists Y^{\sigma\rightarrow \tau})(\forall x^{\sigma})A(x, Y(x)), \end{align} $$
for any quantifier-free formula A in the language of
$\textsf {L}_{\omega }$
.
As discussed in [Reference Kohlenbach46, Section 2],
${\textsf {RCA}}_{0}^{\omega }$
and
${\textsf {RCA}}_{0}$
prove the same sentences ‘up to language’ as the latter is set-based and the former function-based. This conservation results is obtained via the so-called
${\textsf {ECF}}$
-interpretation, which we now discuss.
Remark 4.3 (The
${\textsf {ECF}}$
-interpretation).
The (rather) technical definition of
${\textsf {ECF}}$
may be found in [Reference Troelstra87, p. 138, Section 2.6]. Intuitively, the
${\textsf {ECF}}$
-interpretation
$[A]_{{\textsf {ECF}}}$
of a formula
$A\in \textsf {L}_{\omega }$
is just A with all variables of type two and higher replaced by type one variables ranging over so-called ‘associates’ or ‘RM-codes’ (see [Reference Kohlenbach45, Section 4]); the latter are (countable) representations of continuous functionals. The
${\textsf {ECF}}$
-interpretation connects
${\textsf {RCA}}_{0}^{\omega }$
and
${\textsf {RCA}}_{0}$
(see [Reference Kohlenbach46, Proposition 3.1]) in that if
${\textsf {RCA}}_{0}^{\omega }$
proves A, then
${\textsf {RCA}}_{0}$
proves
$[A]_{{\textsf {ECF}}}$
, again ‘up to language’, as
${\textsf {RCA}}_{0}$
is formulated using sets, and
$[A]_{{\textsf {ECF}}}$
is formulated using types, i.e., using type zero and one objects.
In light of the widespread use of codes in RM and the common practise of identifying codes with the objects being coded, it is no exaggeration to refer to
${\textsf {ECF}}$
as the canonical embedding of higher-order into second-order arithmetic.
4.3 Notations and the like
We introduce the usual notations for common mathematical notions, like real numbers, as also introduced in [Reference Kohlenbach46].
Definition 4.4 (Real numbers and related notions in
${\textsf {RCA}}_{0}^{\omega }$
).
-
(a) Natural numbers correspond to type zero objects, and we use ‘
$n^{0}$
’ and ‘
$n\in {\mathbb N}$
’ interchangeably. Rational numbers are defined as signed quotients of natural numbers, and ‘
$q\in {\mathbb Q}$
’ and ‘
$<_{{\mathbb Q}}$
’ have their usual meaning. -
(b) Real numbers are coded by fast-converging Cauchy sequences
$q_{(\cdot )}:{\mathbb N}\rightarrow {\mathbb Q}$
, i.e., such that
$(\forall n^{0}, i^{0})(|q_{n}-q_{n+i}|<_{{\mathbb Q}} \frac {1}{2^{n}})$
. We use Kohlenbach’s ‘hat function’ from [Reference Kohlenbach46, p. 289] to guarantee that every
$q^{1}$
defines a real number. -
(c) We write ‘
$x\in {\mathbb R}$
’ to express that
$x^{1}:=(q^{1}_{(\cdot )})$
represents a real as in the previous item and write
$[x](k):=q_{k}$
for the kth approximation of x. -
(d) Two reals
$x, y$
represented by
$q_{(\cdot )}$
and
$r_{(\cdot )}$
are equal, denoted
$x=_{{\mathbb R}}y$
, if
$(\forall n^{0})(|q_{n}-r_{n}|\leq {2^{-n+1}})$
. Inequality ‘
$<_{{\mathbb R}}$
’ is defined similarly. We sometimes omit the subscript ‘
${\mathbb R}$
’ if it is clear from context. -
(e) Functions
$F:{\mathbb R}\rightarrow {\mathbb R}$
are represented by
$\Phi ^{1\rightarrow 1}$
mapping equal reals to equal reals, i.e., extensionality as in
$(\forall x , y\in {\mathbb R})(x=_{{\mathbb R}}y\rightarrow \Phi (x)=_{{\mathbb R}}\Phi (y))$
. -
(f) The relation ‘
$x\leq _{\tau }y$
’ is defined as in (4.1) but with ‘
$\leq _{0}$
’ instead of ‘
$=_{0}$
’. Binary sequences are denoted ‘
$f^{1}, g^{1}\leq _{1}1$
’, but also ‘
$f,g\in C$
’ or ‘
$f, g\in 2^{{\mathbb N}}$
’. Elements of Baire space are given by
$f^{1}, g^{1}$
, but also denoted ‘
$f, g\in {\mathbb N}^{{\mathbb N}}$
’. -
(g) For a binary sequence
$f^{1}$
, the associated real in
$[0,1]$
is
$\mathbb{r}(f):=\sum _{n=0}^{\infty }\frac {f(n)}{2^{n+1}}$
. -
(h) Sets of type
$\rho $
objects
$X^{\rho \rightarrow 0}, Y^{\rho \rightarrow 0}, \dots $
are given by their characteristic functions
$F^{\rho \rightarrow 0}_{X}\leq _{\rho \rightarrow 0}1$
, i.e., we write ‘
$x\in X$
’ for
$ F_{X}(x)=_{0}1$
.
For completeness, we list the following notational convention for finite sequences.
Notation 4.5 (Finite sequences).
The type for ‘finite sequences of objects of type
$\rho $
’ is denoted
$\rho ^{*}$
, which we shall only use for
$\rho =0,1$
. Since the usual coding of pairs of numbers goes through in
${\textsf {RCA}}_{0}^{\omega }$
, we shall not always distinguish between
$0$
and
$0^{*}$
. Similarly, we assume a fixed coding for finite sequences of type
$1$
and shall make use of the type ‘
$1^{*}$
’. In general, we do not always distinguish between ‘
$s^{\rho }$
’ and ‘
$\langle s^{\rho }\rangle $
’, where the former is ‘the object s of type
$\rho $
’, and the latter is ‘the sequence of type
$\rho ^{*}$
with only element
$s^{\rho }$
’. The empty sequence for the type
$\rho ^{*}$
is denoted by ‘
$\langle \rangle _{\rho }$
’, usually with the typing omitted.
Furthermore, we denote by ‘
$|s|=n$
’ the length of the finite sequence
$s^{\rho ^{*}}=\langle s_{0}^{\rho },s_{1}^{\rho },\dots ,s_{n-1}^{\rho }\rangle $
, where
$|\langle \rangle |=0$
, i.e., the empty sequence has length zero. For sequences
$s^{\rho ^{*}}, t^{\rho ^{*}}$
, we denote by ‘
$s*t$
’ the concatenation of s and t, i.e.,
$(s*t)(i)=s(i)$
for
$i<|s|$
and
$(s*t)(j)=t(|s|-j)$
for
$|s|\leq j< |s|+|t|$
. For a sequence
$s^{\rho ^{*}}$
, we define
$\overline {s}N:=\langle s(0), s(1), \dots , s(N-1)\rangle $
for
$N^{0}<|s|$
. For a sequence
$\alpha ^{0\rightarrow \rho }$
, we also write
$\overline {\alpha }N=\langle \alpha (0), \alpha (1),\dots , \alpha (N-1)\rangle $
for any
$N^{0}$
. By way of shorthand,
$(\forall q^{\rho }\in Q^{\rho ^{*}})A(q)$
abbreviates
$(\forall i^{0}<|Q|)A(Q(i))$
, which is (equivalent to) quantifier-free if A is.
Acknowledgments
We thank Anil Nerode for his valuable advice, especially the suggestion of studying nsc for the Riemann integral, and discussions related to Baire classes. We thank Dave L. Renfro for his efforts in providing a most encyclopedic summary of analysis, to be found online. We express our gratitude towards the latter institution.
Funding
Our research was supported by the Klaus Tschira Boost Fund via the grant Projekt KT43.
Open access
