Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Set construction
Replies: 2   Last Post: Oct 11, 2017 4:55 PM

 Messages: [ Previous | Next ]
 magidin@math.berkeley.edu Posts: 11,749 Registered: 12/4/04
Re: Set construction
Posted: Oct 11, 2017 4:40 PM

On Wednesday, October 11, 2017 at 2:44:10 PM UTC-5, 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 e-th 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

Date Subject Author
10/11/17 agapito martinez
10/11/17 magidin@math.berkeley.edu
10/11/17 agapito martinez