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: Enumerability with variations
Replies: 1   Last Post: Jun 16, 2013 9:51 PM

 Messages: [ Previous | Next ]
 DBatchelo1 Posts: 236 Registered: 12/12/04
Enumerability with variations
Posted: Jun 16, 2013 9:27 AM

An enumerable set is one in which each member can be associated with a (different) integer.

A Language is an enumerable set of functions, variables etc.

The Domain of a language is the set that includes every element that is in the range of any of the functions in the language.

A couple of examples:-

Consider the language, T, generated by all simple Turing Machines. Sets that are in its domain include
The integers
Primes
etc.
In fact, any set which is recursively-enumerable is in the domain of T

Sets NOT in its domain include;-
The set, ~K, of Turing Machines that do not stop on their own Godel Number
etc
In fact, any set which is NOT recursively-enumerable.

A more powerful language is obtained if one appends to the Turing Machines the ability to recognize whether or not an object is in the set ~K.\Sets in this domain include:-
~K (of course)
and many others.
The set of Computable Reals is not in this domain.

Extend the language again. Let it be able to recognize if a Turing Machine is complete (stops whenever started with any integer on its tape. This language DOES have Computable reals in its domain.

So, there is a distinction between sets in the domain and not. I think that this is important, so let me introduce terminology to handle it. For a language, L, call a set ?listable? if it is in the domain of L

Skolem was a Norwegian mathematician who disd much work in logic. Among has results is ?Skolem?s Paradox.? In a book I own book (Boolos & Jeffrey) this is stated as:-
?... Skolem?s paradox? is that there exist certain interpretations in which a certain sentence, which seems to say that non-enumerably many sets of natural numbers exist, is true, even though the domains of these interpretations contain only enumerably many sets of natural numbers...?

Whew! This is hard to make sense of! However, I believe that it can be expressed far more simply:-
?Let L be a language. Not all enumerable sets are listable in Language L?

The explaination of Skolem?s paradox in Boolos & Jeffrey is rather complicated but I believe it is essentially the above. A set behaves as if it is not enumerable if its enumerator is not in the appropriate domain.

Let me reinterpret my previous examples.
The set of Computable reals is certainly enumerable. (Each of its members can be associated with an integer, the Godel number of the Turing Machine that computes it.) However this set is not recursively-enumerable. If it were, then Cantor?s ?diagonalization procedure? would produce a new real that was computable and was not in the set, a contradiction.
The set of Computable reals is enumerable, but is not listable in the language defined by simple Turing Machines.

A consequence of this is that Cantor?s construction DOES NOT prove that a set is not enumerable.. It ONLY proves that it is not listable (in the language being used to produce it).

A couple of other thoughts:-
1. Is there a maximumly powerful language? Clearly NO. Given any Language L, if you add to it the ability to recognise if a particular element is or is not in its domain, you will get a new, more powerful language.
2. Is there a language so powerful that there is no enumerable set that it cannot list? Again, NO. No such machine can solve its own halting problem.
3. Is there an enumerable set which is not Listable in any Language? I believe there is; the set of all Hyperarithmetic numbers.

Dick

Date Subject Author
6/16/13 DBatchelo1
6/16/13 William Elliot