|
|
Peter Webb wrote:
> In a recent discussion of Zorn's Lemma, I made a throw away line about how
> "it is impossible to define an explicit choice function over the set of
> uncomputable Reals". A respondent implied but did not state this was false,
> and considered the substance of my question and not this specific example.
>
> So I thought about it, and now realise that I was wrong, and that an
> explicit choice function can be provided over the uncomputable Reals in
> (0,1).
>
> I am obviously out of my depth here, but here goes...
>
> You can explicitly choose Chaitin's constant. This is uncomputable, but is a
> well defined number.
>
> Insofar as different TMs (may) produce different Chaitins constants, you can
> choose a countable (and presumably infinite) number of uncomputable Reals in
> this way. Furthermore, each uncomputable number generated in this way
> provides a countably infinite number of other uncomputable numbers, through
> arithmetic, digit interleaving, etc and all the other functions available to
> generate computable numbers.
>
> Getting further out of my depth here ...
>
> Consider a heirachy of Oracle machines that produce Reals (or subsets of N)
> which are uncomptable by the next lowest Oracle machine, with TMs at the
> bottom. I know we cannot compute (in the sense of enumerate the digits) the
> output of any of these within ZF, but we can certainly define them.
>
> These are all functions N -> R, and whilst the function is not computable,
> its range certainly exists. The function takes an order pair of N (which can
> of course be bijected with N), with f(a,b) is the b'th result of the a'th
> Oracle machine. If a UTM is a first level Oracle machine, then {f(1,n)} are
> the computable numbers, {f(2,n)} includes all Chaitan's constants, etc.
>
> Massively out of my depth ...
>
> Lets call Reals that can be defined by this heirarchy of constants
> "definable". This is certainly a superset of computable numbers, as the
> computable numbers are generated by level-1 Oracle machines (ie TMs). Its
> clearly (?) also countable, and indeed we can presumably diagonalise the
> output of a countable number of Oracle machines to show that undefinable
> numbers exist.
>
> Lets call the other Reals "undefinable".
>
> Now comes the simple question with an incredibly complicated answer ...
>
> Is there an explicit choice function over the undefinable Reals (0,1) ?
>
No, as far as is known. Because if we could choose an undefinable
real, it would definable by that choice function, which is a
contradiction.
> More generally, is there any known non-empty subset of (0,1) for which an
> explicit choice function is not known?
No. If you give me any known non-empty subset of the reals, I can give
you an explicit choice function for it.
|
|