Skip to main content
4 of 6
Typographical

Totally computable least real upper bounds for bounded recursive sets of totally computable real numbers?

A recursive set $Y$ is a set with a characteristic total computable function $\chi_Y$ so that $\chi_Y(n)=0$ iff $n\in Y$ and $\chi_Y(n)=1$ iff $n\notin Y$. Let a $recursive \ condition$ be one which defines a recursive set. Let a recursive condition $Q(n)$ for "is a rational number" be given. A totally computable real number is here taken as a natural number $\ulcorner M\urcorner$ which encodes a Turing machine M and such that for some recursive condition $A(x)$, $\ulcorner M\urcorner$ is the least natural number $U(\mu zT(\ulcorner M\urcorner,z,x)=0\leftrightarrow Q(x)\wedge A(x))\wedge U(\mu zT(\ulcorner M\urcorner,z,x))=1\leftrightarrow\lnot (Q(x)\wedge A(x)) $; it is presupposed that $Q(x)\wedge A(x)$ amounts to a Dedekind cut. For instance, the Turing Machine $g$ given by $(U(\mu zT(\ulcorner g\urcorner,z,x))=0\leftrightarrow Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x)\wedge (U(\mu zT(\ulcorner g\urcorner,z,x))=1\leftrightarrow\lnot (Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x)) $

prints $0$ if it is given the input of a rational number $x$ fulfilling the recursive condition $Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x$ and prints $1$ if it is given the recursive condition $\lnot (Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x)$ as input.

It is known by a result of Specker that bounded computable sets of computable real numbers do not always have a computable real number as a least upper bound. Is the situation different for totally computable real numbers as here so that recursive sets of totally computable real numbers with an upper bound have a least upper bound which is totally computable?