|
|
lugita15@xxxxxxxxx wrote:
> 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.
This is incorrect. There is no definable well-ordering of the reals.
|
|