Submitted by jonas on
Spreker: Rachel Epstein (Chicago)
Titel: Definability and the Computably Enumerable Sets
De lezing vereist geen specifieke voorkennis en is bedoeld als een introductie tot recursieve functies.
The computably enumerable (c.e.) sets are sets of natural numbers whose elements can be computably listed in some order. They appear in many areas of mathematics. For example, the word problem for groups is a c.e. set. Nearly all noncomputable sets that appear anywhere in mathematics are c.e. The primary way of classifying c.e. sets is by jump classes, which are classes of sets with similar levels of information content. We can ask which jump classes are definable in the language of set inclusion. The definability of all jump classes has previously been determined except for the class of nonlow Turing degrees. I will discuss the history of this problem and touch upon the ideas used in my proof that the nonlow Turing degrees are in fact not definable.