Logic Seminar in Semester II AY 2009/2010
Talks are Wednesday afternoon in Seminar Room S17#06-11
The general scheme of the seminar is
- 15:30 hrs: first hour tutorial;
- 16:45 hrs: second hour scientific talk.
Here an overview over the topics.
- 13/01/2010, Week 1
16:30 hrs: Organizational meeting.
- 20/01/2010, Week 2
15:30 hrs: Frank Stephan.
Tutorial Complexity theory.
16:45 hrs: Wu Guohua.
Talk Doing cupping in the Ershov Hierarchy.
Abstract: In this talk, I will give a brief survey of cupping
recursively enumerable degrees to 0' in the Ershov hierarchy. In
particular, I will focus on the construction of almost universal
cupping degrees (a recent joint work with Liu Jiang), and the
related topics.
- 27/01/2010, Week 3
15:30 hrs: Frank Stephan.
Tutorial Complexity theory.
16:45 hrs: Chong Chi Tat.
Talk Π11-conservation of combinatorial
principles weaker than Ramsey's Theorem for Pairs.
Abstract: We report on recent joint work with Yang Yue and Theodore A
Slaman. Arising from the earlier investigations of Cholak, Jockusch and
Slaman (2001) and Hirschfeldt and Shore (2007), the relative strengths of
Ramsey's Theorem for pairs with respect to combinatorial principles such
as COH and CAC have been clarified and, in some cases, understood.
Π11-conservation of these principles over
weaker theories, however, have been restricted to strong induction
schema such as Σ02. In this talk we will
discuss the new ideas that lead to the proof of
Π11-conservation of principles such as COH
and CAC over Σ02-bounding, in the absence
of Σ02-induction. It had been observed
previously that this was the best possible.
- 03/02/2010, Week 4
15:30 hrs: Frank Stephan.
Tutorial Complexity theory.
16:45 hrs: Fang Chengling.
Talk Nonhemimaximal degrees and high/low hierarchy.
Abstract:
In the study of the structure C, the lattice of c.e. sets,
an important program is the classification of the orbits under
Aut(C), the automorphism group of C.
Soare proved that maximal sets form an orbit in 1974;
Downey and Stob proved that hemimaximal sets form an orbit in 1992,
where an incomputable
c.e. set H is a hemimaximal set if there is an incomputable c.e. set
A disjoint from H such that the union of H and A is maximal.
At the same time, Downey and Stob proved several relative results:
(1) Every high degree contains a hemimaximal set;
(2) There exists a nonhemimaximal degree;
(3) Nonhemimaximal degree is dense in the low c.e. degrees.
So any nonhemimaximal degree is not high. Downey, Lempp and Shore proved
that there is a high2 nonhemimaximal degree in 1993.
Downey and Stob showed that there is a low2
but not low nonhemimaximal degree.
In their proof, they made use of the fact that m-topped degree is
low2 but not low. In this talk, we give another approach to this
result by a direct construction of low2 but not low degrees.
Here, we will see that the combination of many strategies is another
important part of the construction, but not a simple pile of basic
strategies. Our construction provides us an easy way to understand
the low2 but not low nonhemimaximal degrees.
- 10/02/2010, Week 5
15:30 hrs: Frank Stephan.
Tutorial Complexity theory.
16:45 hrs: John Case.
Talk A medley of three computability theory topics:
1. Machine self-reference and the theater of consciousness,
2. Learning secrets interactively, and
3. Cautious virus detection: bad news and, then, good news.
Abstract:
I will present, back to back, three 20 minute topics I hope will
interest my NUS Math Logic colleagues and which are, also, typical of my
research interests.
The connecting thread, such as it is, pertains to
machine self-reference techniques.
In the first Topic I provide an elementary example and discuss
what, I believe, machine self-reference has to do with the reflective
component of consciousness.
The second is within computational learning theory, my main research
focus, and is joint work with Timo Kötzing, my most recent and
14th finished Ph.D. student.
The third is a theoretical exploration of
an unpleasant kind of computer virus and is joint work with
Samuel E. Moelius, my 13th finished Ph.D. student.
I'll argue (with theorems) that this kind of virus is, happily,
not likely to be found in the real world.
Some of the theorems of the 2nd and 3rd topic are
proven (but not in my talk) by infinitary machine
self-reference techniques of mine. I'll also provide a slide on these
tools between Topics One and Two.
- 24/02/2010, Week 6
15:30 hrs: Benjamin Miller.
Talk A generalization of Silver's dichotomy theorem.
Abstract: We will establish the generalization of Silver's dichotomy
theorem to co-κ-Souslin, ω-universally Baire equivalence
relations. The only prerequisite knowledge is a basic understanding
of point-set topology and Baire category.
16:45 hrs: Zhu Huiling.
Talk Borel's conjecture.
Abstract:
Consider ideals on the set of reals. The ideal of Lebesgue
measure zero sets contains the ideal of countable sets, and the ideal of
strong measure zero sets lies between them. Borel conjectured that every
set with strong measure zero is countable, which is false under the
assumption of continuum hypothesis. Laver proved Borel's conjecture is
consistent (with ZFC). This proof made use of iterated forcing with
countable support, and initiated the study of Axiom A forcing and proper
forcing. In the talk, I'll show an alternative proof of consistency of
Borel's conjucture (by Baumgartner).
- 03/03/2010, Week 7
15:30 hrs: Yang Yue.
Tutorial Cut elimination and applications.
16:45 hrs: Shao Dongxu.
Talk Closed Game Representation.
Abstract: In my talk, I will first introduce some basic properties
of scales, which is a very important concept in descriptive set
theory. Then I will proof that every set of reals admitting
a closed game representation admits a scale. In the proof,
there are some interesting methods to transfer scales between
pointclasses using games. This work is due to Moschovakis.
- 10/03/2010, Week 8
15:30 hrs: Yang Yue.
Tutorial Cut elimination and applications.
16:45 hrs: Peng Yinhe.
Talk Partition relations in ZFC.
Abstract: An r-partition of X into γ colours is a function
f: [X]r → γ. The partition relations are
relations between |X|, r, γ and |Y|. It all starts from
Ramsey theorem which describes the countable case.
When |X| is countable, the relations are easy and clear, but when |X|
becomes larger, the relations will be complicated and interesting.
- 17/03/2010, Week 9
15:30 hrs: Yang Yue.
Tutorial Cut elimination and applications.
16:45 hrs: Li Wei.
Talk Infinite chains and antichains in computable partial
orderings.
Abstract: For an infinite partial ordering, it has either an
infinite chain or an infinite antichain. In this talk, we will
discuss some results about computable partial ordering on N by
Herrmann. Firstly, it will be shown that every computable partial
ordering has either a Δ2 chain or a Π2
antichain. In the second part of the talk, we will prove it is the best
estimation by constructing a computable partial ordering without any
Δ2 chain or Δ2 antichain.
- 24/03/2010, Week 10
15:30 hrs: Shi Xianghui.
Tutorial Posner-Robinson type theorems.
16:45 hrs: Li Yanfang.
Talk Bqo theory and Fraisse's conjecture.
Abstract: Fraisse's conjecture about countable linear ordered set is
the set of all countable linearly ordered sets contains no infinite
descending sequence and no infinite antichain. Laver proved this
conjecure is true using better quasiordering theory (Bqo theory).
I will give some introduction of bqo theory and a sketch of Laver's proof.
- 31/03/2010, Week 11
15:30 hrs: Shi Xianghui.
Tutorial Posner-Robinson type theorems.
16:45 hrs: Cheng Yong.
Talk Borel determinacy and its metamathematics.
Abstract: Topic in this talk is Harvey Friedman's result on Borel
Determinacy (BD): ZC can not prove BD. We will introduce the problem,
background and a general picture of the proof. Also we will have a quick
review of Martin's proof of BD in ZFC and some metamathematical property
of BD will be discussed.
- 07/04/2010, Week 12
15:30 hrs: Shi Xianghui.
Tutorial Posner-Robinson type theorems.
16:45 hrs: Frank Stephan.
Talk Learnability of co-r.e. classes.
Abstract: Angluin gave a characterisation for the learnability
of uniformly recursive classes in terms of a condition with
tell-tale sets. In the present talk, it is shown that this
condition can be generalised to characterise which classes
of co-r.e. sets have a conservative learner. Further comparisons
and relations between the learnability notions for uniformly
recursive, r.e. and co-r.e. classes are given.
This is joint work with Gao Ziyuan.
- 14/04/2010, Week 13
15:30 hrs: Shi Xianghui.
Tutorial Posner-Robinson type theorems.
16:45 hrs: Wang Shenling.
Talk The structure of quasi-degrees.
Abstract: In 1944, Post asked a question: Does there exists an r.e. set
which is neither recursive nor T-complete?
To attack Post's Problem, a natural way is to try first with simpler
versions of it and, once a solution is found for them, proceed to
more difficult cases, in the hope of finally reaching the solution
of the original problem.
In this talk, First, we will follow the path of solving Post's
problem to introduce some basic facts about Quasi-reducibility.
Then, we will focus on some important results on the c.e. sets
and Quasi-reducibility done by Downey, LaForte, and Nies in 1998.
In their paper, they proved that there exists a single Turing
degree containing a branching of 0 in the c.e. Q-degrees.
And they also showed that the existence of nonbranching c.e.
Q-degrees and the c.e. Q-degrees form a dense partial order.
We will discuss their construction of nonbranching c.e. Q-degrees.
Finally, we will introduce some results done by Arslanov and
Omanadze recently, they proved that noncappable c.e. degree
exists and properly n-c.e. Q-degrees are dense in the c.e. Q-degrees.
Talks from the last semester.