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

255 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.