Logic Seminar in Semester II AY 2015/2016
Talks are Wednesday afternoon in Seminar Room S17#05-11
and start at 17:00 hrs. Here an overview over the topics.
- Wednesday 20/01/2016, 17:00 hrs, Week 2, S17#05-11.
Dilip Raghavan. Cardinal invariants above the continuum.
I will give an overview of cardinal invariants at regular uncountable
cardinals. I outline the proof of my joint result with Shelah that
sκ ≤ bκ,
for all uncountable regular κ.
There are lots of open questions
in the area. I will end with some of them.
- Wednesday 27/01/2016, 17:00 hrs, Week 3, S17#05-11.
Wang Wei. Relative Definability of n-generic.
Jockusch proved that every 1-generic G is recursively
enumerable in some X <T G and every
2-generic H is properly
Σ2 in some Y <T H.
So he conjectured that every n-generic G is properly
Σn in some X <T G.
Recently I confirmed Jockusch's conjecture. Here I will
sketch the solution.
The paper is available at
http://arxiv.org/pdf/1511.08875.pdf.
- Wednesday 03/02/2016, 17:00 hrs, Week 4, S17#05-11.
Alexander Melnikov. Constructive abelian groups.
First, we will briefly discuss the history of the old subject of computable
(constructive) abelian groups, and how it fits into the modern computable
structure theory. Then we will discuss why a question of Goncharov on
Δn-categorical groups is central to the theory
of computable abelian groups (terminology to be clarified), and what
the question really asks.
Finally, we will briefly outline the key steps of my recent technical proof
showing such groups exist, at the level of an informal idea. (No solid
background in group theory is assumed.)
- Wednesday 10/02/2016, 17:00 hrs, Week 5, S17#05-11.
Chinese New Year, no logic seminar.
- Wednesday 17/02/2016, 17:00 hrs, Week 6, S17#05-11.
Eric Martin.
Logic programming as
classical inference.
We propose a denotational semantics for logic programming based on a
classical notion of logical consequence which is apt to capture the
main proposed semantics of logic programs. In other words, we show
that any of those semantics can be viewed as a relation of the form T
⊨* X where T is a theory which naturally represents
the logic program under consideration together with a set of
formulas playing the role of "hypotheses", in a way which is dictated
by that semantics, ⊨* is a notion of logical
consequence which is classical
because negation, disjunction and existential quantification receive
their classical meaning, and X represents what can be inferred from
the logic program, or an intended interpretation of that logic program
(such as an answer-set, its well-founded model, etc.). The logical
setting we propose extends the language of classical modal logic as it
deals with modal operators indexed by ordinals.
We make use of two kinds of basic modal formulas:
▢αφ which intuitively means that the
logical program can generate φ by stage α
of the generation process, and
◊α▢βφ
with α > β, which intuitively means that φ
can be used as a hypothesis from stage β
of the generation process onwards, possibly expecting to confirm φ
by stage α (so expecting ▢αφ
to be generated). This allows us to
capture Rondogiannis and Wadge's version of the well-founded semantics
where a member of the well-founded model is a closed atom which
receives an ordinal truth value of trueα or
falseα for some ordinal α: in our
framework, this corresponds to having
T ⊨* ▢αφ or
T ⊨* ▢α¬φ, respectively,
with T being the natural representation of the logic program under
consideration and the right set of "hypotheses" as dictated by the
well-founded semantics.
The framework we present goes much beyond the
proposed traditional semantics for logic programming, as it can for
instance let us investigate under which conditions a set of hypotheses
can be minimal, with each hypothesis being activated as late as
possible and confirmed as soon as possible, setting the theoretical
foundation to sophisticated ways of making local use of hypotheses in
knowledge-based systems, while still being theoretically grounded in a
classical notion of logical consequence.
- Thursday 25/02/2015, 17:00 hrs, Recess Week, S17#04-06.
Andre Nies.
The complexity of isomorphism between profinite groups.
A topological group G is profinite if it is compact and totally
disconnected. Equivalently, G is the inverse limit of a surjective
system of finite groups carrying the discrete topology. An example is the
additive group of 2-adic integers.
We discuss how to represent a countably based profinite group as a point
in a Polish space. Thereafter, we study the complexity of their
isomorphism using the theory of Borel reducibility in descriptive set
theory. For topologically finitely generated groups this complexity is the
same as the one of identity for reals. In general, it is the same as the
complexity of isomorphism for countable graphs.
- Wednesday 02/03/2016, 17:00 hrs, Week 7, S17#05-11.
Wolfgang Merkle. Being low for K along sequences and
elsewhere.
Given a set D of strings, say a sequence X is low for prefix-free
Kolmogorov complexity K on D in case access to X as an oracle does not
improve the prefix-free complexity of any string in D by more than an
additive constant. Furthermore, say X is weakly low for K on D in case
X is low for K on some, then necessarily infinite, subset of D. The
usual notions of being low for K and being weakly low for K are
obtained by letting D be equal to the set of all strings. We
investigate into the question what can be said about sequences that
are low for K or weakly low for K on specific sets of strings, e.g.,
on the set of initial segments of some sequence. Accordingly, say X is
low or weakly low for K along a sequence A in case X is low or weakly
low, respectively, for K on the set of initial segments of A. More
specifically, for an infinite subset I of the natural numbers, say X
is low or weakly low for K along A on I in case X is low or weakly
low, respectively, for K on the set of initial segments of A with
length in I.
Among others, we demonstrate the following results. If a sequence X is
not low for K, then for any sequence A and any infinite computable set
I, the sequence X is not low along A on I. As an immediate corollary,
a sequence X is low for K if and only if X is low along all sequences
on all infinite computable sets if and only if X is low along some
sequence on some infinite computable set. Furthermore, in case a
sequence X is weakly low for K, then X is weakly low along almost all
sequences (in the sense of Lebesgue measure). Hence X is weakly low
for K if and only if X is weakly low for K along almost all sequences
if and only if X is weakly low for K along some sequence. Finally, for
any infinite set D of strings, the set of sequences X such that X is
low for K on D has measure 0 whereas the set of sequences X such that
X is weakly low for K on D has measure 1.
This talk is based on joint work with Yu Liang which was presented
at the conference CCR 2016 in Hawaii.
- Wednesday 09/03/2016, 17:00 hrs, Week 8, S17#05-11.
Frank Stephan.
Learning automatic families of languages.
A class of languages is automatic if it is uniformly regular
using some regular index set for the languages.
This survey is about the work on learnability in the limit of
automatic classes of languages, with some special emphasis to
automatic learners.
This is joint work with Sanjay Jain who presented the talk at
SOFSEM 2016; a paper is available.
- Wednesday 16/03/2016, 17:00 hrs, Week 9, No Talk.
- Wednesday 23/03/2016, 17:00 hrs, Week 10, S17#05-11.
Liu Yong.
On the structure of d.r.e. degrees.
We will review some important results about d.r.e. degrees
and then give an introduction on the topic of final segments of d.r.e.
degrees, which is to determine what kind of finite lattice can be
embedded into d.r.e. degrees as final segments.
- Wednesday 30/03/2016, 17:00 hrs, Week 11, S17#05-11.
Peng Cheng. Final segments of the d.r.e. degrees.
We will give an introduction on the topic of
finial segments of d.r.e. degrees. We first review what
kind of finite lattice can be embedded into the d.r.e. degrees
as final segments. We then will focus on what kind
of finite lattice are not embeddable into the d.r.e. degrees
as finial segment, we will give the ideas try to show that the
five-element lattice M3 is not embeddable
into the d.r.e. degrees as final segments.
- Wednesday 06/04/2016, 17:00 hrs, Week 12, S17#05-11.
Borisa Kuzeljevic. A long chain of P-points.
We will construct, under CH, a sequence of P-points
{Uα:α<ω2}
in such a way that for every α,β
with α<β<ω2
the ultrafilter Uα is Rudin-Keisler
reducible to Uβ while the ultrafilter
Uβ is not Tukey reducible to
Uα.
This is joint work with Dilip Raghavan.
- Wednesday 13/04/2016, 17:00 hrs, Week 13, S17#05-11.
Xu Tianyi. Strong projective absoluteness.
Strong projective absoluteness is the statement that
V[G1]ω+1 ≺
V[G2]ω+1. This can be expressed as
a statement about projective sets "retaining their identities"
across generic extensions. A universally Baire set is a set of reals
with a Suslin representation that can be computed in generic
extensions. We will show, under suitable large cardinal hypotheses,
that every projective set is universally Baire, and the construction
is canonical from the defining formula. From these strong projective
absoluteness can be deduced.
We will introduce the notion of (weakly) homogeneous trees, which
plays a crucial role in the construction. The large cardinals are
used to prove the (weak) homogeneity of certain trees.
This talk is based on Hugh Woodin's 2014 talk in
the IMS Summer School in Logic.
- Monday 25/04/2016, 15:00 hrs, S17#04-06.
Matthias Baaz.
Towards a proof theory of analogical reasoning.
In this lecture we compare three types of analogies based on
generalizations and their instantiations:
- Generalization w.r.t. to invariant parts of proofs, for example,
graphs of rule applications.
- Generalization w.r.t. to an underlying meaning: Here proofs and
calculations are considered as trees
of formal expressions. We analyze the well-known calculation attributed
to Euler demonstrating that the 5th Fermat
number is compound, i.e., that Fermat's claim is false, that all Fermat
numbers are primes.
- Generalization w.r.t. to the premises of a proof: This type of
analogies is especially important for juridical reasoning.
The interested reader is referred to the article
Generalizing proofs in monadic languages by Matthias Baaz and
Piotr Wojtylak for further studies.
Talks from the
previous semesters.