# Logic Seminar in Semester II AY 2017/2018

Talks are Wednesday afternoon in Seminar Room S17#04-06 and start at 17:00 hrs. Here an overview over the topics.
• Wednesday 17/01/2018, 17:00 hrs, Week 1, S17#04-06.
Frank Stephan. Learnability and Positive Equivalence Relations.
A positive equivalence relation is an r.e. equivalence relation on the natural numbers which has infinitely many equivalence classes. The present work studies for various positive equivalence relations which learning criteria can be separated by r.e. one-one families of sets closed under the equivalence relation. The learning criteria considered are finite, confident, explanatory, vacillatory and behaviourally correct learning from positive data. The general results are the following:
1. There is always an r.e. one-one family which cannot be behaviourally correctly learnt;
2. There is always a behaviourally correctly learnable r.e. one-one family which cannot be learnt vacillatorily;
3. For some positive equivalence relation, every vacillatorily learnable r.e. one-one family is explanatorily learnable;
4. There is always an explanatorily learnable r.e. one-one family which cannot be learnt confidently;
5. Some positive equivalence relations do not admit r.e. one-one families which can be learnt confidently; however, when such a family exisits, then there is also such a family which cannot be learnt finitely.
Note that the implications finitely learnable ⇒ confidently learnable ⇒ explanatorily learnable ⇒ vacillatorily learnable ⇒ behaviourally correctly learnable hold, independently of the chosen positive equivalence relation, as these implications follow directly from the definitions.

• Wednesday 24/01/2018, 17:00 hrs, Week 2, S17#04-06.
Dilip Raghavan. An application of PCF theory to cardinal invariants above the continuum.
It will be proved in ZFC that if κ is any regular cardinal greater than בω, then d(κ) ≤ r(κ). Here d(κ) is the smallest size of dominating family of functions from κ to κ and r(κ) is the smallest size of a family of subsets of κ which decide every other subset of κ. This result partially dualizes an earlier result of myself and Shelah. The proof uses the revised GCH, which is an application of PCF theory.
This is joint work with Saharon Shelah.

• Wednesday 31/01/2018, 17:00 hrs, Week 3, S17#04-06.
Ben Blumson. Relevance and Verification.
According to A. J. Ayers' (1936) first empiricist criterion of meaning, "... we may say that it is the mark of a genuine factual proposition ... that some experiential propositions can be deduced from it in conjunction with certain other premises without being deducible from those other premises alone." Ayer's criterion was supposed to distinguish scientifically verifiable statements from unverifiable nonsense, but it's well known to be trivial: if S is an arbitrary statement and O any observation statement, then S entails O in combination with "if S then O" even if "if S then O" does not entail O by itself (alternatively, if "if S then O" does entail O on its own, S is a tautology). In this talk, I will argue that Ayer's criterion can be defended from triviality by the adoption of the relevant logic R, a non-classical logic in which the antecedent of a conditional is supposed to be relevant to its consequent (I won't presuppose knowledge of Ayer or relevant logic).

• Wednesday 07/02/2018, 17:00 hrs, Week 4, S17#04-06.
David Belanger. Randomness versus induction.
We look at some recent work towards finding the axiomatic strength of the statement: There is a Martin-Löf random set of natural numbers.

• Wednesday 14/02/2018, 17:00 hrs, Week 5, S17#04-06.
Wang Wei. Combinatorics and Probability in First and Second Order Arithmetic.
Recent years see emergence of connections between the reverse mathematics of Ramsey theory and computable measure theory or algorithmic randomness. Here we consider two simple propositions in measure theory which have interesting connections to the reverse mathematics of Ramsey theory. The first is that every set X in Cantor space of positive Lebesgue measure is non-empty. If X is assumed to be effectively closed then this is the well-known WWKL0. However, if X is allowed to be a little wilder and the proposition is twisted a bit, then it could help in understanding the first order theory of some Ramseyan theorems. The second is that every set X in Cantor space of positive measure has a perfect subset. This proposition is somehow related to a tree version of Ramsey's theorem. But unlike the first one, it is not familiar to people either in algorithmic randomness or reverse mathematics.

• Wednesday 21/02/2018, 17:00 hrs, Week 6, S17#04-06.
Sibylle Schwarz. Many-valued logic, automata and languages.
In 1960, Büchi, Elgot, Trakhtenbrot discovered a correspondence between finite automata and monadic second order logic on words: A language of nonempty words is regular if and only if it is MSO-definable. Many-valued logics with truth values from MV-algebras and weighted automata with weights from semirings are generalizations of classical two-valued logics and finite automata, respectively.
In this talk, I give some examples of corresponding MV-algebras and semirings and present translations between many-valued MSO-formulae and weighted automata that define the same language.

• Wednesday 07/03/2018, 17:00 hrs, Week 7, S17#04-06.
Wong Tin Lok. Induction and collection in arithmetic.
The classic Friedman–Paris conservation result tells us that the Σn+1 collection scheme and the Σn induction scheme prove the same Πn+2 sentences. Clote, Hájek and Paris asked whether one of these schemes is more efficient than the other in proving such sentences. We give an answer to their question via a syntactic approach to forcing developed by Avigad.
This research is joint with Leszek Kołodziejczyk (University of Warsaw) and Keita Yokoyama (Japan Advanced Institute of Science and Technology).

• Wednesday 14/03/2018, 17:00 hrs, Week 8, S17#04-06.
David Chodounsky. How to kill a P-point.
The existence of P-points (also called P-ultrafilters) is independent of the axioms of set theory ZFC. I will present the basic ideas behind a new and simple proof of the negative direction of this fact; a new forcing method for destroying P-points.

• Wednesday 21/03/2018, 17:00 hrs, Week 9, S17#04-06.
Birzhan Moldagaliyev. Automatic Randomness Tests.
In this talk we will talk about a notion of automatic randomness tests (ART) which capture measure theoretic typicalness of infinite binary sequences within the framework of automata theory. An individual ART is found to be equivalent to a deterministic Büchi automaton recognising ω-language of (Lebesgue) measure zero. A collection of ART's induce a notion of automatic random sequence. Surprisingly, there is a purely combinatorial characterisation of automatic randomness in terms of disjunctivity property.

• Wednesday 28/03/2018, 17:00 hrs, Week 10, S17#04-06.
Wu Guohua. A result towards Kierstead's conjecture for linear orders.
In this talk, I will present a recent work on Kierstead's conjecture for linear orders, generalizing the work of Cooper, Harris and Lee. In particular, we will show that Kierstead's conjecture is true for the order types Σ limq ∈ QF(q), where F is an extended 0'-limitwise monotonic function, (i.e., F can take the value ζ). In contrast to Cooper, Harris and Lee's work, the linear orders in our consideration can have finite and infinite blocks simultaneously. Our result also covers one case of Downey and Moses' work.
This is joint work with Maxim Zubkov from Kazan.

• Wednesday 04/04/2018, 17:00 hrs, Week 11, S17#04-06.
Liu Yong. Lattice embedding problems in local degree structures.
In this talk, we will discuss various results in local degree structures. In particular, we will show that every finite distributive lattice can be embedded into the structure of d.r.e. degrees as a final segment.

• Wednesday 11/04/2018, 17:00 hrs, Week 12, S17#04-06.
Xu Tianyi. Categorical semantics of type theory.
Types can be regarded as a generalization of sorts, allowing operations between them to produce new types. In the first part of this talk, we will start with the observation that the rules of natural deduction system for intuitionistic logic formally correspond to the rules of some type systems. We will introduce the notion of cartesian closed categories and show that they provide a common interpretation for both systems, thus establishing a three-way correspondence between logic, type theory, and category theory. Moreover, we will explain how this correspondence extends to other flavors of type theories.
In the second part, we will focus on homotopy type theory and describe how equality types can be interpreted as paths between points. We will introduce the notion of ∞-groupoids to provide an interpretation of types in homotopy type theory.

• Wednesday 18/04/2018, 17:00 hrs, Week 13, S17#04-06.
Samuel Alfaro Tanuwijaya. Introduction to surreal numbers.
In this talk, I will introduce the basic definitions of the surreal numbers and their ordering given in the book by Harry Gonshor, and their relations to the definitions given by Conway and Knuth. I will then continue with the definitions operations on the numbers, such as addition, multiplication, and division, and then prove that the surreal numbers form a field. I will then establish that the surreal numbers contain the real numbers and the ordinals.

• Thursday 26/04/2018, 17:00 hrs, Week 13, S17#04-05.
Yokoyama Keita. On the first-order strength of Ramsey's theorem for pairs.
Analyzing the strength of various versions of Ramsey's theorem is a long-term project in the study of reverse mathematics. In this talk, I will explain a brief idea of the result on the first-order strength of Ramsey's theorem for pairs and finitely many colors (RT2), which is a joint work with Theodore A. Slaman.
Talks from the previous semesters.