- 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 <**and every_{T}G**2**-generic**H**is properly**Σ**in some_{2}**Y <**. So he conjectured that every_{T}H**n**-generic**G**is properly**Σ**in some_{n}**X <**. Recently I confirmed Jockusch's conjecture. Here I will sketch the solution._{T}G

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**Δ**-categorical groups is central to the theory of computable abelian groups (terminology to be clarified), and what the_{n}**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**M**is not embeddable into the d.r.e. degrees as final segments._{3}

- 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**in such a way that for every_{α}:α<ω_{2}}**α,β**with**α<β<ω**the ultrafilter_{2}**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[G**. 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._{1}]_{ω+1}≺ V[G_{2}]_{ω+1}

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.

- Generalization w.r.t. to invariant parts of proofs, for example,
graphs of rule applications.