The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
magidin@math.berkeley.edu

Posts: 11,740
Registered: 12/4/04
Re: Set construction
Posted: Oct 11, 2017 4:40 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.