数理解析研究所講究録
1169 巻 2000 年 76-83

76

Feasibly constructive analysis
Hajime Ishihara
School of Information Science
Japan Advanced Institute of Science and Technology
Tatsunokuchi, Ishikawa 923-1292, Japan.

1

Introduction

In the constructive theory of real numbers developed, for example in [4,of functions on natural numbers
Chapter 5], we assume that a universe:
satisfies certain closure conditions; a very weak axiom of choice$\mathcal{U}$$\mathrm{Q}\mathrm{F}- \mathrm{A}\mathrm{C}_{00}$$\forall\vec{m}\exists nA(\vec{m}, n)\Rightarrow\exists\alpha\in \mathcal{U}\forall\vec{m}A(\vec{m}, \alpha(\vec{m}))$(A quantifier-free)

is closed under recursive in is assumed in [4,expressing the fact thatChapter 5].
On the other hand, various classes of functions on natural numbers havebeen defined as function algebras [1]; a function algebra is the smallest classof functions containing certain initial functions and closed under certain operations (especially composition and recursion scheme). For example, A.
Cobham [2] characterized the polynomial time computable functions as thesmallest class closed under bounded recursion on notation; see [3] for othercharacterizations of the polytime functions.
We give some elementary results and problems on the constructive theoryof real numbers and analysis with a universe which contains zero-function$0(m)=0$ , projection $P_{k}^{n}(m_{1}, \ldots, m_{n})=m_{k}$ , the binary successor functions$s_{0}(m)=2\cdot m,$ $s_{1}(m)=2\cdot m+1$ , the length in binary function $|m|=$, cut-off subtraction $-(m-n=m-n$ if $m\geq n$otherwise) and pad $(m, n)=2^{|n|}\cdot m$ , and closed under composition: if
such that, then there is an,$\mathcal{U}$$\mathcal{U}$$\lceil\log_{2}(m+1)\rceil,$$\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}+$$0$$g_{1},$$\ldots$$g_{k},$$h\in \mathcal{U}$$f\in \mathcal{U}$$f(\vec{m})=h(g_{1}(\vec{m}), \ldots, g_{k}(\vec{m}))$.

77

Furthermore we assume that a universe
and its inverses
such that$\pi_{1},$$\langle m, n\rangle$

contains a pairing function,$\pi_{2}(\langle m, n\rangle)=n$code the integer $m-n,$;$\langle m, n\rangle=_{\mathbb{Z}}\langle m’, n’\rangle$

if $m+n’=m’+n$ ,,$\langle m, n\rangle+_{\mathbb{Z}}\langle m’, n’\rangle$$:=$$\langle m+m’, n+n’\rangle$$-\langle m, n\rangle$$:=$$\langle n, m\rangle$$|\langle m, n\rangle|$$:=$$(m-n)+(n-m)$ ,$pad_{\mathbb{Z}}(\langle m, n\rangle, l)$$:=$$\langle(pad(m, l),pad(n, l))$etcetc; and then$\langle i, m\rangle=_{\mathbb{Q}}\langle j, n\rangle$$\langle i, m\rangle$

if$\langle\cdot, \cdot\rangle$$\pi_{2}$$\pi_{1}(\langle m, n\rangle)=m$

for then$\mathcal{U}$,code the dyadic rationals,$i/2^{|m|}$where is an inte.ger,$i$$pad_{\mathbb{Z}}(i, n)=_{\mathbb{Z}}pad_{\mathbb{Z}}(j, m)$$\langle i, m\rangle+_{\mathbb{Q}}\langle j, n\rangle$$:=$$\langle pad_{\mathbb{Z}}(i, n)+pad_{\mathbb{Z}}(j, m),pad(m, n)\rangle$$-\langle i, m\rangle$$:=$$\langle-i, m\rangle$$|\langle i, m\rangle|$$:=$$\langle|i|, m\rangle$,,

etcetc.

2Real numbers

Definition 1. A real number is a sequencethat$\{p_{n}\}_{n}$of dyadic rationals such$\forall mn(|p_{m}-p_{n}|<2^{-|m|}+2^{-|n|})$We shall use a notation$\{p_{n}\}_{n}\in \mathbb{R}$Definition 2. Let $x:=\{p_{n}\}_{n},$to mean$\{p_{n}\}_{n}$$y:=\{q_{n}\}_{n}\in \mathbb{R}$is a real number.

, and put$x<y:=\exists n(q_{n}-p_{n}>2^{-|n|+2})$

Lemma 3. Let$x,$ $y,$$z\in \mathbb{R}$. Then1. $\neg(x<y\wedge y<x)$ ,2. $x<y\Rightarrow x<z\vee z<y$ .

.

.

78

Proof. (1). Let

and $y=\{q_{n}\}_{n}$ , and suppose that $x<y$ A $y<x$ .
such that$x=\{p_{n}\}_{n}$Then there exist $n,$ $n’$$q_{n}-p_{n}>2^{-|n|+2}$and$p_{n’}-q_{n’}>2^{-|n’|+2}$,

and hence$0$$=$$(q_{n}-p_{n})+(p_{n’}-q_{n’})-(p_{n’}-p_{n})-(q_{n}-q_{n’})$$>$$2^{-|n|+2}+2^{-|n’|+2}-(2^{-|n’\{}+2^{-|n|})-(2^{-|n|}+2^{-|n’|})$$=$$2^{-|n|+1}+2^{-|n’|+1}$

$>$

$0$

,

a contradiction.

(2). Let $x=\{p_{n}\}_{n},$ $y=\{q_{n}\}_{n}$ and $z=\{r_{n}\}_{n}$ , and suppose that $x<y$ .
Then there exists such that$n$$q_{n}-p_{n}>2^{-|n|+2}$.

Letting $N:=8n+7$ , either $(p_{n}+q_{n})/2<r_{N}$ or $r_{N}\leq(p_{n}+q_{n})/2$ . In theformer case, we have$r_{N}-p_{N}$$>$$\frac{p_{n}+q_{n}}{2}-p_{N}$$=$$\frac{p_{n}+q_{n}}{2}-p_{n}-(p_{N}-p_{n})$$=$$\frac{q_{n}-p_{n}}{2}-(p_{N}-p_{n})$$>$$2^{-|n|+1}-(2^{-|n|-3}+2^{-|n|})$$=$$7\cdot 2^{-|n|-3}>2^{-|N|+2}$,

and hence, $x<z$ . In the latter case, we have$q_{N}-r_{N}$and hence $z<y$ .

$\geq$$q_{N}- \frac{p_{n}+q_{n}}{2}$$=$$(q_{N}-q_{n})+q_{n}- \frac{p_{n}+q_{n}}{2}$$=$$(q_{N}-q_{n})+ \frac{q_{n}-p_{n}}{2}$$>$$-(2^{-|n|-3}+2^{-|n|})+2^{-|n|+1}$$>$$2^{-|N|+2}$,$\square$79

Definition 4. For$x,$ $y\in \mathbb{R}$, define

1. $x\# y:=(x<y\vee y<x)$ ,2. $x=y:=\neg(x\# y)$ ,3. $x\leq y:=\neg(y<x)$ .
Lemma 5. Let$x,$ $y,$$z\in \mathbb{R}$. Then

1. $x\# y\Leftrightarrow y\# x$ ,2. $x\# y\Rightarrow x\neq z\vee z\# y$ .

Proof. Straightforward.
Proposition 6. Let$x,$ $y,$$\square$$z\in \mathbb{R}$. Then

1. $x=x$ ,2. $x=y\Rightarrow y=x$ ,3. $x=y\mathrm{A}y=z\Rightarrow x=z$ .

Proof. (1), (2). Trivial(3). If $x=y$ A $y=z$ , then $\neg(x\# y)\Lambda\neg(y\neq z)$ , and hence $\neg(x\# y\vee y\# z)$ .
Therefore $\neg(x\# z)$ by Lemma 5 (2), and so $x=z$ .

$\square$Proposition 7. Let$x,$ $x’,$ $y,$ $y’\in \mathbb{R}$. Then

1. $x=x’$ A $y=y’\wedge X<y\Rightarrow x’<y’$ ,2. $\neg\neg(x<y\vee x=y\vee y<x)$ ,3. $x<y$ A $y<z\Rightarrow X<Z$ .

Proof. (1). Suppose that $x=x’$ A $y=y’$ A $x<y$ . Then either $x<x’$

or $x’<y$ by Lemma 3 (2). In the former case, we have $x\# x’$ , and hence$\neg(x=x’)$ , a contradiction. In the latter case, we have $x’<y’\vee y’<y$ ; if$y’<y$ , then $\neg(y’=y)$ , a contradiction, and hence $x’<y’$ .
(2). Trivial.
(3). Suppose that $x<y\wedge y<z$ Then either $x<z$ or $z<y$ . In the lattercase, we have a contradiction by Lemma 3 (1). Thus the former must be thecase.

$\square$80

Corollary 8. Let $x,$ $x’,$$y,$ $y’,$$z\in \mathbb{R}$. Then

1. $x=x’\mathrm{A}y=y’\wedge x\# y\Rightarrow x’\# y’$ ,2. $x=x’$ A $y=y’$ A $x\leq y\Rightarrow x’\leq y’$ ,3. $x\leq y\Leftrightarrow\neg\neg(x<y\vee x=y)$ ,4.

$\neg\neg(x\leq y\vee y\leq x)$,

5. $x\leq y\Lambda y\leq x\Rightarrow x=y$,

6. $x<y\wedge y\leq z\Rightarrow X<Z$ ,7. $x\leq y\wedge y<z\Rightarrow X<Z$ ,8. $x\leq y$ A $y\leq z\Rightarrow x\leq z$ .

Proof. (1), (2), (3), and (4) are straightforward.

(5). Suppose that $x\leq y\wedge y\leq x$ Then $\neg(y<x\vee x<y)$ , and hence. Thus $x=y$ .
(6). Suppose that $x<y\wedge y\leq z$ Then either $x<z$ or $z<y$ . In the latter
case, we have a contradiction. Thus the former must be the case.
(7). Similar to (6).
(8). Suppose that $x\leq y\wedge y\leq z$ and $z<x$ . Then either $z<y$ or $y<x$ .
In the former case, we have $y<y$ by (7), a contradiction. In the latter case,
we have $x<x$ , a contradiction. Thus $x\leq z$ .
$\urcorner(x\# y)$$\square$Lemma 9. For each

, we have$x:=\{p_{n}\}_{n}\in \mathbb{R}$$\forall n(|p_{n}-x|\leq 2^{-|n|})$.

Proof. Suppose that $|p_{n}-x|>2^{-|n|}$ . Then there exists$m$such that$2^{-|m|+2}<|p_{n}-p_{2m+1}|-2^{-|n|}<2^{-|m|-1}$ ,a contradiction.

$\square$81

3CompletenessDefinition 10. A sequence of real numbersof dyadic rationals such that$\{\{p_{n}^{m}\}_{n}\}_{m}$$\{p_{n}^{m}\}_{n}\in \mathbb{R}$Definition 11. A sequence
ifulus$\{x_{n}\}_{n}$is a double sequence
for each $m$ .

$\{x_{m}\}_{m}$of reals is said to converge to$x$

with mod-$\beta\in \mathbb{N}arrow \mathbb{N}$$\forall kn(|x-x_{\beta k+n}|<2^{-|k|)}$

Then

$x$

is said to be the limit ofDefinition 12. A sequence
ifwith modulus$\{x_{n}\}_{n}$$\{x_{n}\}_{n}$.

.

of reals is said to be a Cauchy sequence$\alpha\in \mathbb{N}arrow \mathrm{N}$$\forall kmn(|x_{\alpha k+m}-x_{\alpha k+n}|<2^{-|k|})$.

Theorem 13. Each Cauchy sequence of reals converges to a limit.

Proof. Let$\alpha$$\{x_{m}\}_{m}:=\{\{p_{n}^{m}\}_{n}\}_{m}$be a Cauchy sequence of reals with modulus, i.e.

$\forall kmn(|x_{\alpha k+m}-x_{\alpha k+n}|<2^{-|k|})$and define a sequence$\{q_{n}\}_{n}$,of dyadic rationals by$q_{n}:=p_{2n+1}^{\alpha(2n+1)}$.

Then since $|q_{n}-x_{\alpha(2n+1)}|\leq 2^{-|n|-1}$ ) for all , we have$n$$|q_{m}-q_{n}|$$\leq$$\leq$$|q_{m}-x_{\alpha(2m+1)}|+|x_{\alpha(2m+1)}-x_{\alpha(2n+1)}|+|x_{\alpha(2n+1)}-q_{n}|$$2^{-|m|-1}+2^{-|m|-1}+2^{-|n|-1}+2^{-|m|-1}=2^{-|m|}+2^{-|n|}$.

Therefore $x:=\{q_{n}\}_{n}$ is a real number. Furthermore we have$|x-x_{\alpha(4k+3)+m}|$$\leq$$<$and hence$\{x_{n}\}_{n}$$|x-q_{2k+1}|+|q_{2k+1}-x_{\alpha(4k+3)}|+|x_{\alpha(4k+3)}-x_{\alpha(4k+3)+m}|$$2^{-|k|-1}+2^{-|k|-2}+2^{-|k|-2}=2^{-|k|}$converges to$x$,

with a modulus $\beta n:=\alpha(4n+3)$ .

$\square$82

4Intermediate-value

In this section, we assume that our universe is closed under full concatenation recursion on notation (FCRN) which is used in [3] to characterize the$h_{1}(m,\vec{n}, l)\leq 1$ , thenwithpolytime functions: ifsuch that
there is an$\mathcal{U}$$g,$$h_{0},$$h_{1}\in \mathcal{U}$$h_{0}(m,\vec{n}, l),$$f\in \mathcal{U}$,$f(0,\vec{n})$$=$$g(\vec{n})$$f(s_{i}(m),\vec{n})$$=$$s_{h_{i}(m,\overline{n},f(m,\overline{n}))}(f(m,\vec{n}))$(if $i\neq 0$ or $m\neq 0$ )Theorem 14. Let $f\in[0,1]arrow \mathbb{R}$ be continuous with $f(0)\leq 0\leq f(1)$ . Then$\forall k\exists x\in[0,1](|f(x)|<2^{-|k|}$

Proof. Let$\lambda(n, k, m)$be the characteristic function of the predicate$(f( \frac{2m+1}{2^{|n|+1}}))_{2k+1}<0$

define a function$\phi$.

,by FCRN$\phi(0, k)$

$=$

$0$

$\phi(s_{i}(n), k)$$=$$S_{\lambda(n,k,\phi(n,k))(\phi(n,k))}$(if $i\neq 0\vee n\neq 0$ ),and let$p_{n,k}:= \frac{\phi(n,k)}{2^{|n|}}$and$q_{n,k}:= \frac{\phi(n,k)+1}{2^{|n|}}$Then we can show, by induction, that for each$(f(p_{n,k}))_{2k+1}\leq 0$

and.

$n$

$(f(q_{n,k}))_{2k+1}\geq 0$.

They are trivial when $n=0$ . Suppose that $n=s_{i}(n’)$ and $i\neq 0\vee n’\neq 0$ .
Then either $\lambda(n’, k, \phi(n’, k))=0$ or $\lambda(n’, k, \phi(n’, k))=1$ . In the former case,since$p_{n,k}= \frac{s_{0}(\phi(n’,k))}{2^{|s_{0}(n)|}},=\frac{2\phi(n’,k)}{2^{|n|+1}},=p_{n’,k}$we have$(f(p_{n,k}))_{2k+1}=(f(p_{n’,k}))_{2k+1}\leq 0$,

83

by the induction hypothesis, and since $\lambda(n’, k, \phi(n’, k))=0$ , we have$(f(q_{n,k}))_{2k+1}=(f( \frac{2\phi(n’,k)+1}{2^{|n|+1}},))_{2k+1}\geq 0$.

Similarly, in the latter case, we have the inequalities. Therefore we have$f(p_{n,k})\leq(f(p_{n,k}))_{2k+1}+2^{-|k|-1}\leq 2^{-|k|-1}$

and$f(q_{n,k})\geq(f(q_{n,k}))_{2k+1}-2^{-|k|-1}\geq-2^{-|k|-1}$.

Letting $x:=\{p_{n,k}\}_{n}$ and $y:=\{q_{n,k}\}_{n}$ , we have
and $x=y$ . Since
converge to and is continuous, we have$x,$ $y\in \mathbb{R}$$x$$f$$|f(x)|\square \leq$$2^{-|k|-1}<2^{-|k|}\{p_{n,k}\}_{n}\mathrm{a}\mathrm{n}\mathrm{d}\{.q_{n,k}\}_{n}$References[1] P. Clote, Computational models and functional algebras, in E.R. Griffored., Handbook of Computability Theory, North-Holland, forthcomming.
[2] A. Cobham, The intrinsic computational difficulty of functions, in Y.
Bar-Hillel ed., Logic, Methodology and Philosophy ofII, NorthHolland, 1965, 24-30.

S.cience[3] H. Ishihara, Function algebraic characterizations of the p.. olytime functions, Computational Complexity, to appear.

[4] A. S. Troelstra and D. van Dalen, Constructivism in Mathematics, Vol.
1, North-Holland, 1988.