Logic Seminar in Semester I AY 2012/2013
Talks are Wednesday afternoon in Seminar Room S17#04-05 and start
at 17:00 hrs. Here an overview over the topics.
- 15/08/2012, 17:00 hrs, Week 1.
Organisatorial Meeting.
- 22/08/2012, 17:00 hrs, Week 2.
Tatsuta Makoto.
Non-Commutative First-Order Sequent Calculus.
This talk investigates a non-commutative first-order sequent calculus
NCLK. For that, this talk extends a non-commutative positive fragment
to a full first-order sequent calculus LK- having antecedent-grouping
and no right exchange rule. This talk shows (1) NCLK is equivalent to
LJ, (2) NCLK with the exchange rule is equivalent to LK, (3) LK- is
equivalent to LJ, and (4) translations between LK- and NCLK.
- 29/08/2012, 17:00 hrs, Week 3.
Yang Yue.
A Low Seetapun Generic Set - Part 1.
We work in a model M of weak fragments of arithmetic and
show that for any Delta2 set A, either A or the complement of A
contains an infinite low subset. This removed a crucial obstacle of
finding homogenous sets for stable colouring in omega models. This is
part of proof obtained with Chong Chitat and Ted Slaman that Stable
Ramsey Theorem for pairs does not implies Ramsey Theorem for pairs.
- 05/09/2012, 17:00 hrs, Week 4.
Yang Yue.
A Low Seetapun Generic Set - Part 2.
In this part, we will provide more technical details of the construction
sketched in the previous talk.
- 12/09/2012, 17:00 hrs, Week 5.
Dilip Raghavan.
The closed almost disjointness number.
Brendle and Khomskii recently introduced a new cardinal
invariant called aclosed, which is closely related to
the almost disjointness number a, but behaves differently
from a. In joint work with Brendle, I showed that it is
consistent to have b < aclosed. I will give
some background and details of the proof.
- 19/09/2012, 17:00 hrs, Week 6.
Tran Chieu Minh.
O-minimal structures and Diophantine geometry.
Recently, the theory of o-minimal structures, a part of Model Theory,
has been applied to obtain new results in Diophantine Geometry. These
include a new proof of Manin-Mumford conjectures by Pila-Zannier, a
proof of a new special case of Pinks relative Manin-Mumford Conjecture
by Masser-Zannier and an unconditional proof of Andre'-Oort conjecture
by Pila (the known proof assumes Generalized Riemann Hypothesis for
imaginary quadratic fields). This talks aims to give a survey on the
central Model theoretic tool, the Pila-Wilkie theorem, as well as the
common strategy in the proofs of these new results.
- 03/10/2012, 17:00 hrs, Week 7.
Rod Downey.
The Finite Intersection Property and Computability Theory.
A family of sets F ={Ai|i∈J} has FIP
iff for any finite I⊂J, the intersection of all
Ai with i ∈ I is non-empty.
The FIP principle says that any collection of sets has a maximal
subcollection with FIP. The reverse maths and effective content of
this principle, classically equivalent to AC, was initiated by
Dzharfarov and Mummert. They showed, for instance, that there is a
computable family with no computable maximal FIP subfamily.
We say that a degree a is FIP iff it has the ability
to compute a solution to any computable instance of FIP.
Dzharfarov and Mummert's result says that 0 is not
FIP. Dzharfarov and Mummert showed that each nonzero c.e. degree
is FIP, all FIP degrees are hyperimmune, and several classes of
1-generics were FIP.
We extend these investigations by giving new (shorter) proofs of some
of Dzharfarov and Mummert's work, and showing that all 1-generics
are FIP and by showing that for
Δ02 degrees, the FIP degrees
are precisely the ones that bound 1-generic degrees.
We could hope that this characterization extends to the
general hyperimmune case, since hyperimmune degrees resemble
the Δ02 ones. However, we can also
show that there is a minimal Δ03
FIP degree. This last result has some technical complexity as it is a
full approximation argument constructing a hyperimmune
Δ03 degree, which does not seem
to have occurred in the literature hitherto.
This is joint work with David Diamondstone, Noam
Greenberg and Dan Turetsky.
- 10/10/2012, 17:00 hrs, Week 8.
Wu Guohua.
Cupping in the d.c.e. degrees.
An incomplete d.c.e. degree d>0 has almost universal-cupping
property if d cups all the c.e. degrees not below it to
0'. We will prove that any nonzero cappable c.e. degree can
have an isolated d.c.e. degree with almost universal-cupping property
as a complement. This result has several known results on d.c.e.
degrees as direct corollaries, and one of which is Li-Yi's cupping
theorem: there two d.c.e. degrees d1 and
d2 such that any nonzero c.e. degree w cups one
of d1 and d2 to 0'. In this
talk, we will describe basic ideas of the construction.
This is a work joint with Fang and Liu.
- 17/10/2012, 17:00 hrs, Week 9.
Bakhadyr Khoussainov.
On finitely presented expansions
of semigroups, groups, and algebras.
Finitely presented algebraic systems are of foundational interest in
algebra, computability, and complexity.
In this talk we will discuss finitely presented expansions of standard
algebraic systems such as semigroups,
groups, and algebras. The talk will be based on the following two papers:
(1) Bakhadyr Khoussainov, Alexei Miasnikov. Finitely presented expansions
of semigroups, groups, and algebras.
Transactions of the American Mathematical Society. To appear.
(2) Denis Hirschfedlt, Bakhadyr Khoussainov. On finitely presented
expansions of semigroups. Algebra and Logic. To appear.
Basic undergraduate knowledge of algebra and computability will
suffice to follow the talk.
- 31/10/2012, 17:00 hrs, Week 11.
Ng Keng Meng.
The complexity of equivalence relations.
The study of effective equivalence relations has been active recently.
I will discuss some recent results in this topic, including structural and
completeness results. This is an expanded version of a similar talk I
gave in Guangzhou recently.
- 07/11/2012, 17:00 hrs, Week 12.
Alexander Gavryushkin.
Computable models of small theories.
This is a survey talk devoted to the following fundamental question of
the theory of computable structures:
What models of a given theory can be presented effectively?
When the question of effectiveness arises, it is natural to restrict
ourselves to the class of theories having at most countably many
countable models. And if a theory has at most countably many countable
models, then it is small, that is, has at most countably many first
order types. We start with one description of the space of types of
such theories. Then we introduce the notion of spectra of decidable
(computable, automatic) models of small theories as a tool of
describing the spectra. For example, we prove that the spectra of
computable models of small theories having order-type ω+1 are
not necessarily uniouns of finitely many intervals. This theorem is
not true in the class of decidable presentations. It is a longstanding
open problem whether it is true in the class of aleph-1-categorical
theories. It is also not known whether the theorem holds in the class
of automatic presentations. Another result is that every finite
lattices is realisable as a spectrum.
This is a joint work with Bakhadyr Khoussainov.
- 14/11/2012, 17:00 hrs, Week 13.
Tahereh Jafarikhah.
Computable Riesz Representation Theorem on the Dual of C[0;1].
By the Riesz representation theorem, for every linear functional F there
is a bounded variation function g such that
F(h)= ∫x∈[0,1] h(x) dg(x) for all h∈C[0;1].
In this article we present a computable proof for this theorem.
We first give a new proof for the classical theorem and then derive
the computable version easily. We use the framework of TTE, the
representation approach for computable analysis, which allows to define
natural concepts of computability for the operators under consideration.
This is joint work with Klaus Weihrauch.
Talks from the
previous semesters.