Archives of: NUS logic seminar

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.

Liu Yong: Revisit maximal d.r.e. degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Friday, 4 November 2016, 13:00 hrs and 14:00 hrs

Room: S17#07-24, Department of Mathematics, NUS

Talk 1 – Speaker: Liu Yong.

Title: Revisit maximal d.r.e. degrees.

Abstract: We will begin with a brief review of maximal d.r.e. construction,
and show that for any cappable r.e. set A, there is a maximal d.r.e. set D,
which computes A. We also show how to build a maximal d.r.e. set D, avoiding
upper cone of two nonrecursive r.e. sets.

Talk 2 – Speaker: Peng Cheng

Title: A brief introduction to the Ershov hierarchy.

Abstract: Ershov generalized the n-r.e. hierarchy to transfinite levels
based on Kleene’s ordinals. It is a natural measure to study the sets below K.
We will survey some early work by Ershov and others on the Ershov hierarchy
and present the most fundamental results. We will also provide some questions
we are thinking now.

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

Wu Huishan: Avoiding degrees of orders on torsion-free abelian groups

Invitation to the Logic Seminar at the National University of Singapore

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

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

Speaker: Wu Huishan, Nanyang Technological University

Title: Avoiding degrees of orders on torsion-free abelian groups.

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

An abelian group admits an order iff it is torsion-free,
we consider degrees of orders on computable torsion-free abelian groups.
For a computable torsionfree abelian group G, Solomon (2003) showed
that if G has rank 1, then it has exactly two computable orders;
if G has finite rank 2 or more, then it has orders of all Turing
degrees; and if G has infinite rank, then it has orders of
all degrees greater equal 0′.
Motivated by the question whether the set of all degrees of orders
on a computable torsion-free abelian group is closed upwards,
Kach, Lange and Solomon (2013) constructed a computable
torsion-free abelian group G of infinite rank with exactly
two computable orders and a noncomputable, computably enumerable
set C such that every C-computable order on G
is computable, so this G has no orders in deg(C) > 0,
but has orders in 0, a negative answer is provided for
above question.
One proposed research topic is to study the computational complexity
of above computably enumerable set C from the standpoint of
classical computability theory, we will present a recent work on
this topic from the viewpoint of high/low hierarchy.
This is a joint work with my supervisor Wu Guohua.