Invitation to the Logic Seminar at the National University of Singapore
Please find below the invitation to the logic seminar. Note that we will
also fix the timetable for the logic seminar in this semester in the first
meeting; in the case that you want to speak but cannot come, please reply
to this email with timings possible for you; you can consult the webpage
of the seminar for possible time-slots.
Date: Wednesday, 15 January 2013, 17:00 hrs
Room: S17#04-05, Department of Mathematics, NUS
Speaker: Frank Stephan
Title: Closed left-r.e. sets
A set A is called many-one closed left-r.e. iff every set many-one
reducible to A is a left-r.e. set. Similarly one can define the notions
of ascending closed left-r.e. sets, conjunctive closed left-r.e. sets,
disjunctive closed left-r.e. sets and positive closed left-r.e. sets.
The implications r.e. => positive closed left-r.e. =>
many-one closed left-r.e. => ascending closed left-r.e. =>
left-r.e. hold and no arrow can be reversed. Cohesive,
r-cohesive and weakly 1-generic sets are not r.e.
but can be many-one closed left-r.e.; furthermore there is
an ascending closed left-r.e. set which is cohesive and not
many-one closed left-r.e.; however every cohesive left-r.e.
set is also an ascending closed left-r.e. set.
The initial segment complexity of ascending closed left-r.e.
sets is sublinear and can be kept near to linear; for
many-one closed left-r.e. sets, one can obtain such bounds
infinitely often; for conjunctive / disjunctive / positive closed
left-r.e. sets the bound is logarithmic.
This talk reports on joint work with Sanjay Jain and Jason Teutsch
and has been presented at CCR 2013; the results extend those presented
on 24 August 2011 in the logic seminar.