Logic Seminar in Semester I AY 2017/2018
Talks are Wednesday afternoon in Seminar Room S17#04-04
and start at 17:00 hrs. Here an overview over the topics.
- Wednesday 16/08/2017, 17:00 hrs, Week 1,
S17#04-04.
No Talk, IMS Programme at this Time.
- Wednesday 23/08/2017, 17:00 hrs, Week 2,
S17#04-04.
No Talk, IMS Programme at this Time.
- Wednesday 30/08/2017, 17:00 hrs, Week 3,
S17#04-04.
No Talk, IMS Programme at this Time.
- Wednesday 06/09/2017, 17:00 hrs, Week 4,
S17#04-04.
No Talk, IMS Programme at this Time.
- Wednesday 13/09/2017, 17:00 hrs, Week 5,
S17#04-04.
No Talk, IMS Programme at this Time.
- Wednesday 20/09/2017, 17:00 hrs, Week 6,
S17#04-04.
No Talk.
- Wednesday 04/10/2017, 17:00 hrs, Week 7,
S17#04-04.
No Talk.
- Wednesday 11/10/2017, 17:00 hrs, Week 8,
S17#04-04.
Gao Ziyuan.
Erasing pattern languages distinguishable by a
finite number of strings.
Pattern languages have been an object of study in various subfields of
computer science for decades. We introduce and study a decision
problem on patterns called the finite distinguishability problem:
given a pattern π, are there finite sets
T+ of positive and T- of negative
example string such that the only pattern language containing all
positive example strings and no negative example strings is the one
generated by π?
This problem is related to the complexity of teacher-directed
learning, as studied in computational learning theory, as well as to
the long-standing open question whether the equivalence of two
patterns is decidable. We show that finite distinguishability is
decidable if the underlying alphabet is of size other than 2 or 3, and
provide a number of related results, such as (i) partial solutions for
alphabet sizes 2 and 3, and (ii) decidability proofs for variants of
the problem for special subclasses of patterns, namely, regular,
1-variable, and non-cross patterns. For the same subclasses, we
further determine the values of two complexity parameters in
teacher-directed learning, namely the teaching dimension and the
recursive teaching dimension.
- Wednesday 18/10/2017, 17:00 hrs, Week 9,
S17#04-04.
No talk, Deepavali.
- Wednesday 25/10/2017, 17:00 hrs, Week 10,
S17#04-04.
Yu Liang. Two basis theorems on
Σ12 sets.
We prove the following two basis theorems on
Σ12 sets of reals:
(1) Every non-thin
Σ12 set has a perfect
Δ12 subset if and only if there
is a nonconstructible reals in the set;
(2) Every uncountable
Σ12 sets of reals has an uncountable
Δ12 subset if and only if either
every real is constructible or (ω1)L is
countable.
This is joint work with Chong Chi Tat and Wu Liuzhen.
- Wednesday 01/11/2017, 17:00 hrs, Week 11,
S17#04-04.
Peng Cheng. On transfinite levels of the Ershov hierarchy.
In this talk, we first present some classical properties about the
finite levels of the Ershov hierarchy, especially in the d.r.e. case.
Some properties about d.r.e. sets are related to the transfinite
levels of the Ershov hierarchy. We will present some results which
we are considering and show the weak density theorem and
nondensity theorem for transfinite levels.
- Wednesday 08/11/2017, 17:00 hrs, Week 12,
S17#04-04.
Desmond Lau. p, t and me.
The question of whether p, the pseudointersection number, and t,
the tower number, are equal had been longstanding open problem
until it was proven in the affirmative by Malliaris and Shelah
in 2012 in a preprint. The proof involves the study of a new class
of problems called cofinality spectrum problems. Malliaris and Shelah
would go on to develop their cofinality spectrum theory to solve
many other model theoretic problems.
In 2016, I gave a month-long seminar on the first main theorem
of cofinality spectrum theory and how it is used to prove p = t.
This talk is about the things I learned in that seminar.
- Wednesday 15/11/2017, 17:00 hrs, Week 13,
S17#04-04.
Lim Wei Quan. Complete predicative type theory.
Russell's paradox is frequently misused to argue that every
reasonable foundation for mathematics cannot have a universal type.
But that is in fact false. I shall describe a new foundational
system that takes seriously the philosophical cogency of
a universal type, and avoids the usual paradoxes in
a philosophically meaningful way. CPTT is based on 3-valued logic,
but still interprets (classical) higher-order arithmetic.
Also, CPTT is self-reflective, having a native meta logic.
Finally, CPTT is meant to be user-friendly and yet fully formal.
CPTT arose from my personal search for an alternative practical
foundation for mathematics that has a 'clear' yet 'complete'
ontology, and I wish to ask for feedback on it.
Talks from the
previous semesters.