Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Set construction
Posted:
Oct 11, 2017 4:40 PM


On Wednesday, October 11, 2017 at 2:44:10 PM UTC5, agapito wrote: > Consider set W= {W_e e in N}, shere the W_e's are all the enumerable sets of natural numbers.
What does "are all the enumerable sets of natural numbers" mean?
Are you talking about effective enumerability (there exists a Turing Machine that lists the elements of the SUBset)? Some other version? What is your definition of "enumerable" here?
> Define set > > K = {e  e in W_e} > > It is claimed that the complement of K cannot be identical to any W_e.
Meaning, the complement of K is not (effectively) enumerable?
> Can someone please indicate why this should be so?
Assuming that you mean that what you have is some notion of "effective enumerability", say, "there exists a Turing Machine that lists the set", and you have some fixed way of enumerating such Turing Machines, so that W_e is the subset of the natural numbers that is effectively enumerated by the eth Turing Machine...
Let T be the complement of K. If there is a Turing Machine M that effectively enumerates T, then M corresponds to some index e in your fixed enumeration. That is, T = W_e for some index e.
However, the Turing Machine must effectively list the elements of T. Note that x is in T if and only if x is not in W_x.
In particular, is e in T?
If e is in T if and only if e is not in W_e; but W_e is T. Thus, e is in T if and only if e is not in T. This is impossible.
The contradiction arises from the assumption that T is effectively enumerable; hence T cannot be effectively enumerable; i.e., there is no Turing Machine M with the property that M lists the elements of T.
 Arturo Magidin



