Computable reals and r.e./Diophantine

[nomadreid]

TL;DR Summary

If recursive sets correspond to computable reals, what reals do recursive enumerable sets (Diophantine sets) correspond to?

To not get caught up on side issues, I will assume that the Church Thesis is true, whether or not the assumption is necessary.

That said: I start with the rough definitions:
[1] A recursive set A is a set A for which there exists an algorithm that can tell in a finite time, for any given a, whether or not a is an element of A.
[2] A recursively enumerable (r.e., or computably enumerable) set is a set A for which there exists an algorithm that, for any given a, will either stop to (correctly) signal that a is a member of A, or keep working otherwise. (That is, it is not necessary that it can tell that a is not in A.)

Every subset of the natural numbers corresponds to a real number (easier: to a real number between 0 and 1), and every recursive subset of ℕ correspond to a computable real number. (Obviously there are fewer computable real numbers than real numbers, and there are more r.e. sets than there are recursive sets.) So, what collection of reals do the r.e. sets correspond to? (This is equivalent to asking what set of real numbers correspond to the Diophantine sets.)

 

[SSequence]

It depends on how a correspondence is created. Consider the simple example of the collection of:
a-- "partial recursive functions"
b-- "total recursive function"
with the range being restricted suitably to $0,1$. For a function which is partial if $a$ is the smallest value at which $f(a)$ is undefined then we might want to consider the function as representing a terminating decimal [at least partially, this seems like a matter of convention]. So, in that case both the classes of functions (a) and (b) above represent the same set of reals [since the functions that are partial but not total will always merely be representing a rational number].

===================

But I think you are asking something slightly different. There is a natural way to associate a subset of ℕ with a real number. In this sense, the recursive sets correspond to class-(b) above. The r.e. sets will definitely correspond to a bigger class of reals than class-(b) ... simply because there is an r.e. set which isn't recursive.

Here is something quite basic, but which might help. Let's define the following subsets of ℕ.
A0 --- recursive sets
A1 --- r.e. sets (that aren't recursive)
A2 --- co-r.e. sets (that aren't recursive)
A3 --- sets that are halt computable but neither r.e. nor co-r.e.

The union of all these:
B0=A0 υ A1 υ A2 υ A3
is the collection of 0'-computable sets (halt computable). Iteration of this to arbitrary natural numbers leads to arithmetic sets (of which there are several equivalent classifications).

===================

There are two directions to your question. The first is that you might search for a reasonable phrase like "computable analysis" [usually here you would find the definition based on intervals]. The other is that what kind of collection of subsets (of ℕ) should you consider that they satisfy the properties of real numbers (under the decimal expansion def. for example) such as closure under addition, multiplication, least-upper-bound etc. [So, in that sense, the given collection could be thought of as "sort of" a mini-universe of real numbers]. The arithmetic sets suffice for it. I think any reasonably "closed" collection of subsets of ℕ would suffice. But the recursive don't seem to suffice for it (https://en.wikipedia.org/wiki/Specker_sequence). It seems plausible (just guessing) that r.e. sets might not suffice either but I will need to think about it though as I haven't really thought about this topic at all in quite some time [and I am not proficient at it either].

===================

Finally, here is a link to few papers that you might find interesting if you are interested in decimal expansion based definition:
"Terminating Decimals in the Cantor Ternary Set"
"Real numbers as infinite decimals and irrationality of √2"
"Defining Arithmetical Operations on Infinite Decimals"I haven't studied any of these, but regarding the last paper, it seems to show that there is an algorithmic way to determine the product [if my cursory reading is correct]. For addition it is easy enough to see, but not for product.

 

[nomadreid]

Thanks, SSequence. I have downloaded the three articles (thanks to arXiv for two of them), and will go through them later.

Also thanks for the link to Specker sequences. I had not known of this concept.

In the meantime, your analysis is helpful, but I am not quite sure what you mean hy "halt-computable" (0'-computable). Could you explain? (Once I have that in hand, I will carry through on the conclusion that the iteration of the process leads to the arithmetic sets, so it is possible that I will come back with another question.)

 

[SSequence]

In the meantime, your analysis is helpful, but I am not quite sure what you mean hy "halt-computable" (0'-computable). Could you explain? (Once I have that in hand, I will carry through on the conclusion that the iteration of the process leads to the arithmetic sets, so it is possible that I will come back with another question.)

The sets computable given (ordinary) programs which have (say) an extra command of the form:
u:=H(v,w)
where u,v,w are variables (which take on natural numbers values). So, essentially we can inquire whether a given program with index "v" halts when given an input "w".

One can simplify it a fair amount. One would normally find (in books or online) one of these commands:
u:=H(v,v)

It doesn't matter in the sense that the "strength" of the two models [in the sense of sets they generate] should be same no matter which of the extra command one adds [there are also some relatively elementary reducibility arguments, which I don't remember off-hand now]. The reason for using the latter seems to be that we can think of a function of one argument instead of two.

This iteration of halt-oracles when done $n \in \mathbb{N}$ times [in a "reasonable manner"] leads to $0^{(n)}$-computable sets [1]. When one considers union of all $0^{(n)}$-computable sets (for arbitrary $n \in \mathbb{N}$), the result is arithmetic sets.

I didn't mention the logic-based def. in previous post [which is the actual one so to speak]. It's just that I have "nearly" forgotten the logic-based definition [it would necessarily involve some details about primitive recursive functions too I think]. In any case, the equivalence between the logic and computability definition is shown by showing inclusions in both directions. The inclusion in one direction is easy, but in the other direction is harder. If you are interested in details you might search for "Kleene-Post Theorem" (along with the keyword "arithmetic").

===================

Though it doesn't matter that much if you are already familiar with the definition of arithmetic sets from logic. I just briefly wrote the above in-case it might be helpful or interesting.

The main point I was trying to make was that once we have a collection/set of real numbers which can be (loosely) thought of as "mini-universe of real numbers" (in the sense of closure of addition,multiplication,l.u.b. etc.) then a lot of theorems of analysis translate directly within that particular collection too. Exactly the details [which I am not familiar with] as to which ones do and don't translate would seem to depend on "size" of the collection I suppose.

===================

[1] Setting this up requires some work (and different ways setting-up would be fine too), but it shouldn't be particularly difficult

 

[nomadreid]

Thanks again, SSequence. I will work on the details.