Logic Seminar in Semester II AY 2013/2014
Talks are Wednesday afternoon in Seminar Room S17#04-05
and start at 17:00 hrs. Here an overview over the topics.
- 15/01/2014, 17:00 hrs, Week 1, S17#04-05.
Frank Stephan.
Closed left-r.e. sets.
A set A is called many-one closed left-r.e. iff every set many-one
reducible to A is a left-r.e. set. Similarly one can define the notions
of ascending closed left-r.e. sets, conjunctive closed left-r.e. sets,
disjunctive closed left-r.e. sets and positive closed left-r.e. sets.
The implications r.e. ⇒ positive closed left-r.e. ⇒
many-one closed left-r.e. ⇒ ascending closed left-r.e. ⇒
left-r.e. hold and no arrow can be reversed. Cohesive,
r-cohesive and weakly 1-generic sets are not r.e.
but can be many-one closed left-r.e.; furthermore there is
an ascending closed left-r.e. set which is cohesive and not
many-one closed left-r.e.; however every cohesive left-r.e.
set is also an ascending closed left-r.e. set.
The initial segment complexity of ascending closed left-r.e.
sets is sublinear and can be kept near to linear; for
many-one closed left-r.e. sets, one can obtain such bounds
infinitely often; for conjunctive / disjunctive / positive closed
left-r.e. sets the bound is logarithmic.
This talk reports on joint work with Sanjay Jain and Jason Teutsch
and has been presented at CCR 2013; the results extend those presented
on 24 August 2011 in the logic seminar.
- 22/01/2014, 17:00 hrs, Week 2, S17#04-05.
Dilip Raghavan.
Constructing special almost disjoint families.
We will survey some recent progress in constructing almost
disjoint families with strong combinatorial properties. The recent
constructions are based on ideas introduced by Shelah in 2011. The use of
cardinal invariants plays an important role in these constructions.
- 29/01/2014, 17:00 hrs, Week 3, S17#04-05.
Ding Longyun. Actions by Sequence Spaces.
We investigate the Borel reducibility between equivalence relations of
the form as ℝω/G where G is a Borel subgroup of
ℝω. We are mainly interested on special cases
in which G is a Borel linear subspace. This kind of research
begin from Dougherty and Hjorth, while G is one of the classical
sequence spaces: ℓp (p≥1) or c₀
In this talk, we will recall some old results and introduce some new
results on this topic.
- 05/02/2014, 17:00 hrs, Week 4, S17#04-05.
Peng Ningning. The Query Complexity of Read-once
Boolean Functions.
We study the query complexity of algorithms with randomness.
We consider the deterministic and the randomized decision tree
complexities for Boolean functions, denoted D(f) and R(f),
respectively. A major open problem is how small R(f) can be with
respect to D(f). The well-known Saks-Wigderson's Conjecture is the
statement that for any Boolean function f, R(f) =
Ω(n0.753), where n is the number of inputs.
In this talk, we will show some positive evidences of this conjecture.
We also introduce the latest results on this topic.
- 12/02/2014, 17:00 hrs, Week 5, S17#04-05.
Chong Chi Tat.
TT1, Part II.
In the previous part I, Li Wei gave the following talk:
TT1 says that for any colouring of the binary tree with
finitely many colours, there is a homogeneous perfect subtree.
Classically, TT1 is proved by Σ2 Induction.
In this talk, we will examine TT1 without Σ2
Induction and show that for some recursive colouring,
no homogeneous perfect subtree is below 0".
This is now the second part of this series of talks on
TT1.
- 19/02/2014, 17:00 hrs, Week 6, S17#04-05.
Omori Hitoshi. A dialetheic approach to Russell's paradox.
Dialetheism is the metaphysical view which claims that there are
true contradictions. And Russell's paradox together with the liar's
paradox has been one of the main motivations for defending dialetheism.
Now, the aim of the talk is twofold. First, we try to explain why the
dialetheic approach to Russell's paradox might be interesting. Here, we
consider some of the discussions given by Graham Priest who is the modern
founder and defender of dialetheism. Second, we outline how one may take
an approach towards a dialetheic set theory. To this end, we present a
system of non-classical logic that replaces classical logic, and then
develop a set theory based on the newly introduced system.
- 26/02/2014, 17:00 hrs, Recess Week, S17#04-05.
No Talk.
- 05/03/2014, 17:00 hrs, Week 7, S17#04-05.
Rupert Hölzl. Randomness in the Weihrauch degrees.
The Weihrauch degrees are a degree structure that can be used to
classify how complex it is to find solutions to certain mathematical
tasks, that typically arise from classical mathematical theorems, for
example in analysis. We will give an overview over recent work about
interactions between these degrees and the field of algorithmic
randomness. In particular we will discuss where two different models of
randomized computation are located in this lattice: computation with
access to a Martin-Löf random oracles and computation with a Las Vegas
algorithm. We will see that these two models can be separated in the
Weihrauch degree, which is in contrast to results in the related field
of reverse maths, where they are known to coincide. After briefly
discussing some other results relating the two subjects mentioned above,
we present some open questions.
- 12/03/2014, 17:00 hrs, Week 8, S17#04-05.
Ian Herbert.
Weak Lowness Notions and Weak Reducibilities.
The prefix-free Kolmogorov complexity of a finite binary string is the
length of the shortest description of the string, according to some
universal decoding machine. This gives rise to some `standard' lowness
notions for reals: A is K-trivial if its initial segments have the
lowest possible complexity and A is low for K if using A as an oracle
does not decrease the complexity of strings by more than a constant
factor. We discuss various ways of weakening these notions and the
relations among these weakenings and between them and standard
notions. We also discuss how these notions behave under reducibilities
that are based on Kolmogorov complexity and are weaker than Turing
reducibility.
- 19/03/2014, 17:00 hrs, Week 9, S17#04-05.
Alexander Kreuzer.
Non-principal ultrafilters, program extraction and higher order
reverse mathematics.
We investigate the strength of the existence of a non-principal
ultrafilters over fragments of higher order arithmetic.
Let (U) be the statement that a non-principal ultrafilter on N exists
and let ACA0w be the higher order extension of
ACA0 (arithmetical comprehension).
We show that ACA0w is
Π12-conservative over
ACA0w and thus
ACA0w+(U) is conservative over PA.
Moreover, we provide a program extraction method and show that from a
proof that a strictly Π12 statement
∀ f ∃ g [Aqf(f,g)]
is in ACA0w+(U), one can extract
a realizing term in Gödel's system T. This
means that one can extract a term t, such that
∀ f [Aqf(f,t(f))].
- 26/03/2014, 17:00 hrs, Week 10, S17#04-05.
Massoud Pourmahdian.
Some generalizations of metric model theory.
In this talk, first of all, I will explain how to generalize
metric theory to get a new logic, called ultrametric logic. Secondly, I
will explain how to extend the notion of metric structures so that the
uniformizable structures are included.
- 02/04/2014, 17:00 hrs, Week 11, S17#04-05.
Liu Yiqun.
IΣ3 and Universal Cupping degrees
In this talk, we use the typical 0'''-Injury method to re-tackle the
Universal Cupping degree theorem which asserts there exists a
ω-c.e. degree d < 0' such that for any nonzero c.e. w,
the join of w and d is 0'. Based on this, we claim
P- + IΣ3 proves the existence of the universal
cupping degree.
- 09/04/2014, 17:00 hrs, Week 12, S17#04-05.
Wu Guohua. On a theorem of Seetapun.
In this talk, we will consider local noncappability property of
recursively enumerable degrees, which was proposed by Seetapun in his
thesis in 1991. We will give an improvement of this theorem, which
will have several known results as direct corollaries. This talk
is based on joint work with Frank Stephan.
- 16/04/2014, 17:00 hrs, Week 13, S17#04-05.
Bakhadyr Khoussainov.
Algorithmically random algebraic structures.
In this talk we introduce the concept of algorithmically random
algebraic structure. In particular, we construct algorithmically
random structures in the classes of graphs, trees, universal
algebras, and monoids. We prove that there exist computably
enumerable algorithmically random trees. We also build
algorithmically random universal algebras and graphs
computable in the halting set.
Talks from the
previous semesters.