# Recursive sets and recursive numbers: relationship?

1. May 2, 2015

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

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