Recursive sets and recursive numbers: relationship?

1. May 2, 2015

nomadreid

Given the two standard definitions
(1) A computable set is a set for which there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set.
(2) A computable number is a number which can be approximated to any degree of accuracy by a computable function
I am tempted to say that a computable number is one that corresponds to a computable set, but
(a) I am not sure this is correct, and
(b) even if it is correct, I am not sure what "corresponds to" would mean. There are ways to make any subset of the natural numbers correspond to a real number, but I am not sure whether these would be appropriate.
Thanks.

2. May 3, 2015

+Jace090+

It would make sense that a computable number belongs in a computable set. I would agree.

3. May 3, 2015

nomadreid

Thanks, +Jace90+, but that's not quite right. A computer number does not necessarily belong in a computable set -- that is, it doesn't have to be a member of a computable set. A computable set is a set of natural numbers, whereas a computable number need not be a natural number. For example, pi is computable, but is not in a computable set. The idea is that each computable set of natural numbers corresponds to a single computable real number. {1,3,5} might correspond to 0.010101 or something like that.Since both the set of the computable numbers and the set of the computable sets are countable, there exists a 1-1 correspondence, but would this correspondence correspond to a section of an explicit one-to-one correspondence between ℝ and P(ℕ) that was not simply set up artificially in order to work backwards? This was the intent of my question; sorry for not making it clearer the first time.

4. May 4, 2015

Svein

Check out "Gödel, Escher, Bach" for a long discussion of FLoop vs. BLoop.

5. May 4, 2015

nomadreid

Thanks, Svein. I read the book a long time ago (in fact, I have met Hofstadter, and I know well the official translator of GEB to Russian): it's very good, and the Floop (primitive recursive functions) and Bloop (recursive functions) programs are a nice way to make his point that Gloop (a program to solve the halting problem) is impossible, but I am afraid that I do not see that this answers my question. Could you be more explicit?

6. May 4, 2015

Svein

Sorry, I just thought I should point you in that direction. Since you already have read it, I don't have anything else to add (my thesis was in function algebras, not in mathematical logic).

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook