Logic Seminar in Semester I AY 2019/2020
Talks are Thursday afternoon in Seminar Room S17#06-11
and start at 17:00 hrs. Here an overview over the topics.
- Thursday 15/08/2019, 17:00 hrs, Week 1,
S17#06-11.
No logic seminar.
- Thursday, 22/08/2019, 17:00 hrs, Week 2,
S17#06-11.
Johanna Franklin.
Degrees of isometric isomorphism for Banach spaces.
The degree of isomorphism of a computable presentation of a
structure is the least powerful Turing degree that computes an
isomorphism from this presentation onto the "standard"
copy of the structure, assuming that such a copy exists. I will
discuss the degrees of isometric isomorphism of two of the five
types of nonzero separable Lp spaces and then
consider lowness for isometric isomorphism for these spaces.
Time permitting, I will discuss lowness for isometric isomorphism
and lowness for isometry in a more general context.
This is joint work with Tim McNicholl. Her homepage is
https://people.hofstra.edu/Johanna_N_Franklin/.
- Thursday 29/08/2019, 17:00 hrs, Week 3,
S17#06-11.
Chong Chi Tat.
Revisiting Seetapun's theorem with his disjunction.
Ramsey's theorem RTn2
states that if the n-rtuples of the set of natural numbers
are coloured in either red or blue, then there is an infinite
subset all of whose n-tuples have the same color.
The proof-theoretic strength of RTn2
has been a prominent line of study in reverse mathematics. The first
major breakthrough was obtained by David Seetapun (Seetapun and
Slaman (1995)) who showed that
RT22 is strictly weaker than
RT32. This talk will describe a proof
of this theorem using the technique called ``Seetapun disjunction''
introduced in Chong, Slaman and Yang (2014).
- Thursday 05/09/2019, 17:00 hrs, Week 4,
S17#06-11.
Samuel Alfaro Tanuwijaya.
Pseudo-finite fields.
This talk will introduce pseudofinite fields and how they are axiomatized.
We will see how they are infinite models of the theory of finite fields,
and therefore there is no theory whose models are exactly the finite
fields.
- Thursday 12/09/2019, 17:00 hrs, Week 5,
S17#06-11.
Gao Ziyuan. The one-cop-moves game on planar graphs.
Cops and Robbers is a vertex-pursuit game played on graphs. In
this game, a set of cops and a robber occupy the vertices of the graph
and move alternately along the graph's edges with perfect
information about each other' positions. If a cop
eventually occupies the same vertex as the robber, then the cops win;
the robber wins if she can indefinitely evade capture. Aigner and
Fromme established that in every connected planar graph, three cops
are sufficient to capture a single robber. In this paper, we consider
a recently studied variant of the cops and robbers game, alternately
called the one-active-cop game, one-cop-moves game or the lazy cops
and robbers game, where at most one cop can move during any round.
We show that Aigner and Fromme's result does not generalize to this game
variant by constructing a connected planar graph on which a robber can
indefinitely evade three cops in the one-cop-moves game.
This talk is based on joint work with Boting Yang
(http://www2.cs.uregina.ca/~boting/).
- Thursday 19/09/2019, 17:00 hrs, Week 6,
S17#06-11.
No Logic Seminar.
- Thursday 03/10/2019, 17:00 hrs, Week 7,
S17#06-11.
Dilip Raghavan. All ultrafilters in L(R)[U] are rapid.
We will show that all ultrafilters in the model L(R)[U] are rapid.
This is joint work with Paul Larson.
- Thursday 10/10/2019, 17:00 hrs, Week 8,
S17#06-11.
Ashutosh Kumar.
On partitions into null sets.
Given a partition P of the set of reals into Lebesgue null sets,
let J be the ideal of those subsets of P whose union
is null. We will show that, consistently, J can be countably
saturated.
This is a joint work with Saharon Shelah.
- Thursday 17/10/2019, 17:00 hrs, Week 9,
S17#06-11.
Li Zeyong. A complete problem
for statistical zero knowledge.
This work by Amit Sahai and Salil Vadhan presents the first complete
problem for SZK, the class of promise problems possessing
statistical zero-knowledge proofs (against an honest verifier).
The problem, called STATISTICAL DIFFERENCE, is to decide whether two
efficiently samplable distributions are either statistically
close or far apart. This gives a new characterization of SZK
that makes no reference to interaction or zero knowledge.
The talk (due to time constraint) will focus on the second half (and
arguably the more insightful half) of the completeness theorem, that is,
STATISTICAL DIFFERENCE is SZK-hard. It essentially gives
a constructive proof that any promise problem possessing a statistical
zero-knowledge proof can be reduced to an instance of STATISTICAL
DIFFERENCE in polynomial time.
The paper of Sahai and Vadhan is available at
Sahai's Webpage.
- Thursday 24/10/2019, 17:00 hrs, Week 10,
S17#06-11.
Yang Yue. Ramsey's Theorem on trees
and weak König's Lemma.
Ramsey's Theorem for Pairs has been studied intensively in reverse
mathematics. One of the major breakthroughs is Liu Lu's 2012 result
showing RT22
does not imply WKL0.
Liu's result not only answered an important question in reverse
mathematics, the technique that he used turns out to have wider
applications, for example, in Monin and Patey's separation of
SRT22 and
RT22.
In this talk, we generalize Liu's result to tree.
Let TT22 denote
the combinatorial principle stating that every k-coloring
of pairs of compatible nodes on the full binary tree has a homogeneous
solution, i.e. an infinite perfect tree in which all pairs of
compatible nodes have the same color. We show that over the base
system RCA0, TT22
does not imply weak König's lemma.
This is joint work with Chong Chitat, Li Wei and Liu Lu.
The abstract is also available as a
pdf-file.
- Thursday 31/10/2019, 17:00 hrs, Week 11,
S17#06-11.
Marat Arslanov.
n-c.e. degrees, CEA operators and fixed-point selection
functions.
The subjects listed in the title of my talk belong to my steady
scientific interest. In my talk I will speak about my recent work in
these areas and list few open problems that have arisen as a result
of these studies and that I can not answer.
- Thursday 07/11/2019, 17:00 hrs, Week 12,
S17#06-11.
Chong Chi Tat. The work of Gerald Sacks.
Gerald E Sacks (1933--2019) completed his thesis
under Barkley Rosser at Cornell. He was a visitor at the Institute for
Advanced Study in Princeton and a faculty member at Cornell. He
subsequently moved to MIT and then took up a joint appointment
as Professor of Mathematical Logic at Harvard. Sacks did pioneering
work in recursion theory and higher recursion theory and made
fundamental contributions to logic. This talk will give a sypnosis of
what we think to be Sacks' most significant achievements, and the
impact of his work on the development of logic. Some recollection of
Sacks as a person will also be sprinkled during the talk.
- Thursday 14/11/2019, 17:00 hrs, Week 13,
S17#06-11.
Thilo Volker Weinert.
Partition Relations for Linear Orders in a Choiceless Context.
Most Partition Relations are proved for Ordinals, not
general linear orders. This is due to the Axiom of Choice which I will
consequently ignore during most of the lecture. Some exceptions to the
rule mentioned at the beginning can be found in a 1971 paper by
Erdős, Milner and Rado and I will present some analogous
results for linear orders which are given rise to by lexicographically
ordered sequences of zeros and ones. I will close by discussing an
open problem in this context.
This is joint work (from a few years back) with Philipp Lücke
and Philipp Schlicht, see
the article at the page of Springer.
- Monday 02/12/2019, 17:00 hrs, S17#04-05.
Rupert Hölzl.
Randomness for computable measures and complexity.
We study the possible growth rates of the Kolmogorov complexity of
initial segments of sequences that are random with respect to some
computable measure on the Cantor Space, the so-called proper sequences.
Our main results are as follows:
(1) We show that the initial segment complexity of a proper sequence
X is bounded from below by a computable function (that is,
X is complex) if and only if X is random with respect
to some computable, continuous measure.
(2) We prove that a uniform version of the previous result fails to hold:
there is a family of complex sequences that are random with respect to
a single computable measure such that for every computable, continuous
measure μ, some sequence in this family fails to be random with
respect to μ.
(3) We show that there are proper sequences with extremely
slow-growing initial segment complexity, that is, there is a proper
sequence the initial segment complexity of which is infinitely often
below every computable function, and even a proper sequence the
initial segment complexity of which is dominated by all computable
functions.
(4) We prove various facts about the Turing degrees of such
sequences and show that they are useful in the study of certain
classes of pathological measures on the Cantor Space, namely
diminutive measures and trivial measures.
This is joint work with Christopher P. Porter and a paper is
available as a
technical report
and also at the journal
Annals of Pure and Applied Logic.
Talks from the
previous semesters.