David Chodounsky: How to kill a P-point

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 14 March 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: David Chodounsky

Title: How to kill a P-point

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
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.

Sibylle Schwarz: Many-valued logic, Automata and Languages

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 21 February 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Sibylle Schwarz

Title: Many-valued logic, Automata and Languages.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
In 1960, Buechi, 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.

Wang Wei: Combinatorics and Probability in First and Second Order Arithmetic

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 14 February 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Wang Wei

Title: Combinatorics and Probability in First and Second Order Arithmetic

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
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 axiom WWKL-0. 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.



David Belanger: Randomness versus induction

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 07 February 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: David Belanger

Title: Randomness versus induction

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

We look at some recent work towards finding the axiomatic strength of the
statement: There is a Martin-Loef random set of natural numbers.

Dilip Raghavan: An application of PCF theory to cardinal invariants above the continuum

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 24 January 2018, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Dilip Raghavan

Title: An application of PCF theory to cardinal invariants above the continuum

Abstract: It will be proved in ZFC that if kappa
is any regular cardinal greater than beth_omega, then
d(kappa) leq r(kappa). Here d(kappa) is the
smallest size of dominating family of functions from kappa
to kappa and r(kappa) is the smallest size of a family
of subsets of kappa which decide every other subset of kappa.
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 Shelah.

Gao Ziyuan: Erasing pattern languages distinguishable by a finite number of strings

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 11 October 2017, 17:00 hrs

Room: S17#04-04, Department of Mathematics, NUS

Speaker: Gao Ziyuan

Title: Erasing pattern languages distinguishable by a finite number of strings

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
Pattern languages have been an object of study in various subfields of
computer science for decades. We introduce and study a decision
problem on patterns called the finite distinguishability problem:
given a pattern pi, are there finite sets T+ and T- of
strings such that the only pattern language containing all strings in
T+ and none of the strings in T- is the language generated by
pi? This problem is related to the complexity of teacher-directed
learning, as studied in computational learning theory, as well as to
the long-standing open question whether the equivalence of two
patterns is decidable. We show that finite distinguishability is
decidable if the underlying alphabet is of size other than 2 or 3, and
provide a number of related results, such as (i) partial solutions for
alphabet sizes 2 and 3, and (ii) decidability proofs for variants of
the problem for special subclasses of patterns, namely, regular,
1-variable, and non-cross patterns. For the same subclasses, we
further determine the values of two complexity parameters in
teacher-directed learning, namely the teaching dimension and the
recursive teaching dimension.

Frank Stephan: Finitely generated semiautomatic groups

Update on the Logic Seminar at the National University of Singapore
(the originally announced speaker is ill and will speak on 12 April 2017)

Date: Wednesday, 22 March 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: Finitely generated semiautomatic groups

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

The present work shows that Cayley automatic groups are semiautomatic
and exhibits some further constructions of semiautomatic groups.
Furthermore, the present work establishes that every finitely
generated group of nilpotency class $3$ is semiautomatic.

André Nies: Structure within the class of K-trivial sets

SEMINAR ANNOUNCEMENT

Title: Structure within the class of K-trivial sets

Prof. André Nies
Department of Computer Science
University of Auckland
Date:    6 February 2017 (Monday)
Time:      4.00pm – 5.00pm
Venue:     MAS Executive Classroom 1 #03-06,
School of Physical and Mathematical Sciences  and quantum settings

The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Since 2002, many  alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked quite amorphous. More recently, internal structure has been found. Bienvenu et al. (JEMS 2016) showed that there is a “smart” K-trivial set, in the sense that any random oracle computing it computes all K-trivials. Greenberg, Miller and Nies(submitted)  showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches using cost functions. ML-reducibility (A is below B if every random oracle computing B also computes A) appears to a good way to compare the complexity of K-trivials, but the vexing question remains whether this reducibility is arithmetical.

Jonathan Verner: A Ramsey Theorem for metric spaces

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 16 November 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Jonathan Verner

Title: A Ramsey Theorem for metric spaces

Abstract: attached.

Joint Work With Saharon Shelah

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

David Belanger: An effective perfect-set theorem

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 9 Nov 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: David Belanger

Title: An effective perfect-set theorem

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: We gauge the difficulty of finding a perfect subtree in a tree
of a given Cantor-Bendixson rank. To simplify the analysis we introduce
half-derivative, and extend the definition of rank to include values of
the form n-and-a-half; each increase of one-half in the rank corresponds
to one added jump in the perfect-subtree problem.