# Calculus on computable reals (does it differ from the reals)?

The integral is defined as the limit of a Riemann sum

$$\lim_{\Delta x\to 0^+} \sum_{i=1}^n f(x_i) \Delta x_i = \int_a^b f(x) dx$$

We also recall the definition of the limit as:

$$\lim_{x\to a}f(x)=L$$

iff there exists $$\epsilon$$ and $$\delta$$ such that

$$0<|x-a|<\delta \implies 0<|f(x)-L|<\epsilon$$

As far as I can tell the definition of the limit holds for the computable reals $$\mathbb{R}_c \subset \mathbb{R}$$.

Indeed, there exists a computable real in-between every computable real. Suppose $$a,b \in \mathbb{R}_c$$, then I define $$c=(a+b)/2$$. If $$a\neq b$$, then clearly $$c$$ is in-between $$a$$ and $$b$$. Since we can take $$a=0$$, then one can define a computable number that approaches $$0$$ as closely as one is willing to let the computation take it: $$c=(0+b)/2$$, then $$c_1=(0+c)/2$$, then $$c_2=(0+c_1)/2$$. From this, the definition of the limit holds.

Therefore,

$$\lim_{\Delta x\to 0^+} \sum_{i=1}^n f(x_i) \Delta x_i = \int_a^b f(x) dx$$

where $$x,a,b \in \mathbb{R}_c$$.

I am surprised to see that integral (a notation normally associated with uncountability) is here applied to $$\mathbb{R}_c$$, a computable set.

From this, integrating over the interval $$[0,1]\in\mathbb{R}_c$$ produces:

$$\int_0^1 x dx = 1 +c$$

I am skeptical of my argument because I do not understand how the area under a set of discrete points can be non-zero?

Edit: I realized that a better definition of continuity can be constructed using open sets from the perspective of topology. Then, functions from $$f:\mathbb{R}_c \to \mathbb{R}_c$$ would be continuous and would admit derivatives. With topological definitions, are notions of integration/derivative over the computable reals equivalent to the reals?

• I think this winds up fairly close to: math.stackexchange.com/questions/1512163/integral-of-rationals In that link there is some definition of integral definition. It looks like you are going with the Riemann integral definition? If I'm not mistaken this boils down to the density/distribution of the uncomputable reals among the computable reals. – Kitter Catter Aug 16 '19 at 16:57
• When you start talking about computability, the definition of limits becomes quite a bit trickier, because computable reals aren't limit-closed; you can't talk about 'the limit of a computable sequence' because from the perspective of the computable reals, such a thing doesn't necessarily exist! – Steven Stadnicki Aug 16 '19 at 20:23
• Re @StevenStadnicki's comment, see en.wikipedia.org/wiki/Specker_sequence – r.e.s. Aug 21 '19 at 4:01

The definition of a Riemann integral is only intuitively the "area under a curve." Let's expand out all the definitions even more: we say that $$L=\int_a^b f(x)\,dx$$ if

for every $$\epsilon>0$$, there is an $$N>0$$ such that, for all integers $$n\geq N$$, $$\left\lvert L - \sum_{i=0}^{n-1} f(x_i)\Delta x_i\right\rvert < \epsilon,$$ where we may as well let $$x_i=a+\frac{1}{n}(b-a)i$$ and $$\Delta x_i=\frac{1}{n}$$.

Generally speaking, when you've shown an integral exists, you have actually found a (possibly non-constructive) procedure to figure out how many terms you need in the sum to calculate $$L$$ to as much precision as you want (if $$\epsilon=10^{-k}$$, then you get $$k$$ digits of precision after the decimal point). To get more precision, you need a bigger $$N$$, but any particular sum under consideration is always a finite sum.

For the computable reals, everything works out, so long as you take $$a$$ and $$b$$ to be computable reals and $$f$$ to be a computable function. Part of the definition of the existence of an integral is that $$L$$ be computable, too.

Remember that integral rules in calculus are all quick ways to prove that an integral exists while also giving you the $$L$$, and I think all of them have proofs that carry over to computable reals, too. For example, $$\int_0^1x^n\,dx$$ has a rule where this is $$[\frac{1}{n+1}x^{n+1}]_0^1=\frac{1}{n+1}$$. The fraction $$\frac{1}{n+1}$$ is certainly a computable real!

In standard calculus, there is a theorem that for every continuous function $$f$$, the integral $$\int_a^b f(x)\,dx$$ exists. I do not know the corresponding statement for computable reals (I suspect the concept of continuity needs to keep track of how $$\delta$$ is a function of $$\epsilon$$ and $$x$$ so that you can estimate a good-enough $$N$$). One version is that if you have $$f$$ that is computable and uniformly continuous (for every $$\epsilon>0$$ there is a $$\delta>0$$ such that for every $$x\in[a,b]$$ and every $$x'\in[a,b]$$ with $$\lvert x'-x\rvert <\delta$$, then $$\lvert f(x') - f(x)\rvert < \epsilon$$) such that $$\delta$$ is a computable function of $$\epsilon$$, then the integral exists and is a computable real.

• As a physicist, it sounds like I can define the domain of all of my functions (Lagrangian, Hamiltonian, Differential entropy, etc) to be over the computable reals instead of the reals, and everything (derivative, anti-derivative, general relativity, etc.) will just work. Essentially, computable reals are a drop-in replacement for the reals? – Alexandre H. Tremblay Aug 16 '19 at 21:14
• @AlexandreH.Tremblay I don't know enough about this to know under what conditions solutions to PDEs exist, which seems pretty important for physics applications. Unfortunately there's a bit of a gap between definitions still making sense and whether theorems still apply. (For an example in a more restrictive domain, you can define square roots over $\mathbb{Q}$, but $2$ doesn't have one.) – Kyle Miller Aug 16 '19 at 21:23