[FOM] Primitive recursive reals

Harvey Friedman friedman at math.ohio-state.edu
Wed Apr 19 09:38:32 EDT 2006

I have no idea whether the following claims are new.

They certainly can be substantially sharpened, although it is not clear what
the ultimate interesting sharpenings are.

THEOREM 1. Let b1 and b2 be two bases, neither of which is a power of the
other. There exists a real number that is (extremely) primitive recursive in
base b1 but not primitive recursive in base b2.

THEOREM 2. There is a real x (extremely) primitive recursive in base 2 such
that 3x, x + 1/3, x^2 are not primitive recursive in base 2.

THEOREM 3. Let b be a base. The reals primitive recursive in base b are not
closed under addition, not closed under multiplication, not closed under

Presumably, we know that e is primitive recursive to every base.

QUESTION: Is e + pi primitive recursive in base 2, base 10, or even (as
expected) primitive recursive in every base?

The following is strong enough to derive Theorems 2 and 3.

THEOREM 4. Let f:[0,1] into R, and let f:Z+ into Z+ be a recursive function.
Assume that f restricted to rationals is recursive in the appropriate sense.
Assume that if |x-y| < 1/f(n) then |x-y| < 1/n, and if |x-y| > 1/n then
|f(x)-f(y)| > 1/f(n). Assume that f maps no b-adic rational to a b-adic
rational. Then there exists a real x that is (extremely) primitive recursive
in every base, but f(x) is not primitive recursive in any base.

There should be much nicer theorems than this.

Harvey Friedman

More information about the FOM mailing list