Logic Seminar in Semester I AY 2014/2015
Talks are Wednesday afternoon in Seminar Room S17#04-04
and start at 17:00 hrs. Here an overview over the topics.
- 13/08/2014, 17:00 hrs, Week 1, S17#04-04.
Frank Stephan.
The complexity of verbal and pattern languages over groups.
The talk presents the complexity of verbal languages and pattern
languages of Thurston automatic groups in terms of the Chomsky hierarchy.
Here the language generated by a pattern is taken as the set of
representatives of all strings obtained when chosing values for the
various variables. For noncommutative free groups,
it is shown that the complexity of the verbal and pattern languages
(in terms of level on the Chomsky hierarchy) does not depend on the
Thurston automatic representation, that verbal languages cannot
be context-free (unless they are either the empty word or the full group)
and that pattern languages cannot be regular (unless they are either a
singleton or the full group). Verbal languages and pattern languages can,
however, be indexed languages.
Furthermore, it is shown that in the general case, it might depend on
the exactly chosen Thurston automatic representation which level a
verbal language takes in the Chomsky hierarchy. There are
examples of groups where, in an appropriate representation, all pattern
languages are regular or context-free, respectively.
This is joint work with Sanjay Jain and Alexei Miasnikov; the talk builds
on and extends work presented at LICS 2012.
- 20/08/2014, 17:00 hrs, Week 2, S17#04-04.
Dilip Raghavan.
On embedding certain partial orders into the P-points under Tukey
and RK reducibility.
The study of the global structure of the P-points was initiated
mainly by Blass in 1970s. In a paper in 1973 he asked what partially
ordered sets can be embedded into the P-points under the ordering of
Rudin-Keisler reducibility. This question is of most interest under some
hypothesis that guarantees the existence of many P-points, such as
Martin's axiom for σ-centered posets. In the 1973 paper he
showed under this assumption that both ω1 and
the reals can be embedded. This result was later generalized
to the coarser notion Tukey reducibility. We will prove that under
Martin's axiom for σ-centered posets P(ω)/FIN can
be embedded into the P-points both under Rudin-Keisler
and Tukey reducibilities. Since P(ω)/FIN is universal for partial
orders of size at most continuum, this a good step towards giving a
complete answer to Blass' original question.
This is joint work with Saharon Shelah.
- 27/08/2014, 17:00 hrs, Week 3, S17#04-04.
Four talks at the Department of Mathematics within the framework of the
I.C.M. Day;
no logic seminar on this day. A logic-related talk at the I.C.M. Day
is the following.
Vladimir Voevodsky. Computer proof assistants - the
future of mathematics.
I will tell about the movement to create new foundations of mathematics,
new common language and new commonly accepted methods of inference,
to be used to express mathematics in forms that can be verified by
computer proof assistants. Almost miraculously the new ideas that were
required to resolve some of the outstanding problems that stalled the
development of such foundations came from homotopy theory. There is now a
growing new synthesis of constructive mathematics with Grothendieck style
pure mathematics that can be effectively developed using existing proof
assistants such as Coq.
- 03/09/2014, 17:00 hrs, Week 4, S17#04-04.
No talk. There is the
IMS-JSPS Joint Workshop in Mathematical Logic and Foundations of
Mathematics; see the
IMS page for talks at the IMS in that week.
- 10/09/2014, 17:00 hrs, Week 5, S17#04-04.
Liu Yiqun.
Another decomposition of c.e. degrees.
It's known that R is a disjoint union of Prompt Simple degrees (simply
as P.S. degrees) and Cappable degrees (denoted as M, namely all degrees
which are parts of c.e. minimal pair or 0).
We specify another decomposition of c.e. degrees R as (disjoint) union
of P.S. degrees and the degrees of the base sets for all Slaman Triples
(simply as BSLT degrees). Slaman Triple is a triple of nontrivial c.e.
degrees, say (a,b,c), such that c is not strictly below b and for any c.e.
We < a, c < b + We or We is computable.
In such triple, a is defined to be the base set for Slaman triple.
BSLT degree is also Cappable degree since (a,b) is a minimal pair.
As a corollary of two decompositions, Cappable degree is also a BSLT
degree. Thus, base for SLT is equivalent to Cappable as set property
in Turing degree structure.
- 17/09/2014, 17:00 hrs, Week 6, S17#04-04.
Yang Yue.
On a question of Cholak and Downey.
In a paper entitled "On the Cantor-Bendixon rank of recursively
enumerable sets" (JSL 1993), Cholak and Downey showed that for every
recursive ordinal &alpha and every nonrecursive r.e. degree
d, there is an r.e. set of rank α and degree
d. They also asked if one can generalize the result to
Δ02 degrees, i.e., for every recursive
ordinal α and every nonrecursive Δ02
degree d there is a Δ02 set of rank
α and degree d. I will show the answer is positive.
This is a joint work with Rod Downey and Guohua Wu.
- 24/09/2014, 17:00 hrs, Recess Week, S17#04-04.
No Talk.
- 01/10/2014, 17:00 hrs, Week 7, S17#04-04.
Ng Keng Meng. Constructing minimal pairs.
We show how to use the determinacy of finite games to construct
minimal pairs in the truth-table degrees.
- 08/10/2014, 17:00 hrs, Week 8, S17#04-04.
Peng Ningning.
Defining a randomness notion via another.
In this talk, we ask whether a given randomness notion can be
defined via another randomness notion. If so, How can we define it? We
will formalize this questions using the concept relativization of
randomness. And, give some solutions to our formalized questions.
- 15/10/2014, 17:00 hrs, Week 9, S17#04-04.
Wu Guohua. Nonhemimaximal sets and degrees.
In this talk, I will present a recent work with Mustafa and
Yamaleev on the Turing degrees of nonhemimaximal sets, proving that
the nonhemimaximal degrees are nowhere dense in the low2 c.e.
degrees. This answers a question of Downey and Stob.
- 22/10/2014, 17:00 hrs, Week 10, S17#04-04.
Deepawali, no talk.
- 29/10/2014, 17:00 hrs, Week 11, S17#04-04.
Chong Chi Tat.
Lowness of reals in higher randomness.
This talk will discuss the problem of the existence of
nontrivial reals which are low for various notions of higher
randomness, reporting on the works of several authors.
- 05/11/2014, 17:00 hrs, Week 12, S17#04-04.
Rupert Hölzl.
Universality, optimality, and randomness deficiency.
A Martin-Löf test U is universal if it captures all
sequences which are not Martin-Löf random. A test is
optimal if for every Martin Löf test V there is a c ∈ ω
such that
∀n ( Vn+c ⊆ Un). We study
the computational differences between universal and optimal
Martin-Löf tests as well as the effects
that these differences have on both the notion of layerwise
computability and the Weihrauch
degree of LAY, the function that produces a bound for a given
Martin-Löf random sequence’s
randomness deficiency. We prove several robustness results
concerning the Weihrauch degree
of LAY. Along similar lines we also study the principle RD, a
variant of LAY outputting the precise
randomness deficiency of sequences instead of only an upper bound as
LAY.
This is joint work with Paul Shafer.
- 12/11/2014, 17:00 hrs, Week 13, S17#04-04.
Liu Yong. The strength of Carlson-Simpson Lemma VW(k,l).
It is known that the Carlson-Simpson Lemma (VW(k,l)) is the
combinatorial core of the Dual Ramsey Theorem. This talk is
an introduction to the combinatorial principles VW(k,l) and OVW(k,l)
from the perspective of reverse mathematics. For example, WKL0
does not prove VW(k,l) and VW(k,l+1) is equivalent to VW(k,l).
- 19/11/2014, 17:00 hrs, S17#04-04.
Teng Dan. Semiautomatic structures.
Semiautomatic structures generalise automatic structures in the sense
that for some of the relations and functions in the structure one only
requires the derived relations and structures are automatic when all
but one input are filled with constants. One can also
permit that this applies to equality in the structure so that only
the sets of representatives equal to a given element of the structure
are regular while equality itself is not an automatic relation on the
domain of representatives. It is shown that one can find semiautomatic
representations for the field of rationals and also for finite algebraic
field extensions of it. Furthermore, it is shown that there are
semiautomatic ordered rings consisting of the integers augmented
by the multiples of the square-root of a non-square integer; here
the order is the same as the corresponding order on the real numbers.
- 26/11/2014, 17:30 hrs, S17#04-05.
Kihara Takayuki.
Recursion theoretic methods in topological dimension theory.
By introducing the notion of generalized Turing degrees in any admissibly
represented space (represented second-countable T0-quotient
space), we provide a refinement of Roman Pol's solution to Pavel
Alexandrov's old problem in infinite dimensional topology.
Formally, we show that there is
an embedding of an uncountable partial ordering into the
σ-embeddability ordering of weakly infinite dimensional metrizable
compacta (indeed, metrizable C-compacta, also known as selectively
screenable compacta Sc(O,O) in set theoretic topology).
This is a joint work with Arno Pauly.
Talks from the
previous semesters.