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.
Talks from the
- Wednesday 17/01/2018, 17:00 hrs, Week 1,
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:
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.
- There is always an r.e. one-one family which cannot be behaviourally
- There is always a behaviourally correctly learnable r.e. one-one
family which cannot be learnt vacillatorily;
- For some positive equivalence relation, every vacillatorily learnable
r.e. one-one family is explanatorily learnable;
- There is always an explanatorily learnable r.e. one-one family
which cannot be learnt confidently;
- 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.
- Wednesday 24/01/2018, 17:00 hrs, Week 2,
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,
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,
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,
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,
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,
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
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,
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,
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,
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,
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,
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,
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,
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.