Archives of: NUS logic seminar

Ashutosh Kumar: Order dimension of Turing degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 27 March 2019, 17:00 hrs

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

Speaker: Ashutosh Kumar

Title: Order dimension of Turing degrees

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

The order dimension of a partially ordered set (P,<)
is the smallest size of a family F of linear orders,
each extending <, such that the intersection of F is
the given ordering <.

Higuchi, Lempp, Raghavan and Stephan asked if the order dimension
of Turing degrees could be decided in ZFC. We show that the answer is no.

This is joint work with Dilip Raghavan.

Wong Tin Lok: End extensions and subsystems of second-order arithmetic

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 13 March 2019, 17:00 hrs

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

Speaker: Wong Tin Lok

Title: End extensions and subsystems of second-order arithmetic

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

Abstract:
Investigations in reverse mathematics reveal that most naturally
occurring theorems in mathematics are equivalent to one of five
arithmetic axioms nowadays known as the BIG FIVE. These provide
strong empirical evidence for the importance of the Big Five.
In the talk, I will attempt to explain their importance mathematically
in terms of the characteristics of their models.

The work to be presented is joint with Stephen G. Simpson (Vanderbilt).

Dilip Raghavan: A small ultrafilter number

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 6 March 2019, 17:00 hrs

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

Speaker: Dilip Raghavan

Title: A small ultrafilter number

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

Abstract: It is proved to be consistent relative to a measurable
cardinal that there is a uniform ultrafilter on the real numbers which
is generated by fewer than the maximum possible number of sets. It is
also shown to be consistent relative to a supercompact cardinal that
there is a uniform ultrafilter on aleph_{omega+1} which is generated
by fewer than 2^{aleph_{omega+1}} sets.

This is joint work with Saharon Shelah.

Liu Yong: There is no strong minimal pair

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 20 February 2019, 17:00 hrs

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

Speaker: Liu Yong.

Title: There is no strong minimal pair.

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

Abstract:
A strong minimal pair in r.e. degrees is defined to be a pair of
A, B such that they are incomparable and for any non-recursive r.e. set W
below A, B+W computes A. Historically, this was a difficult problem.
Slaman showed a weaker version of this (i.e. B+W computes a third set C,
instead of A), and it is called Slaman-Triple nowadays. Only recently,
people showed that there is a strong minimal pair. However, we realized
that there is a problem in that paper. Then we turned the problem into a
proof that there is no strong minimal pair. In this talk, we will sketch
the proof.

Matthias Baaz: On the benefit of unsound rules: Henkin quantifiers and beyond

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 13 February 2019, 17:00 hrs

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

Speaker: Matthias Baaz

Title: On the benefit of unsound rules: Henkin quantifiers and beyond

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

Abstract:
We give examples of analytic sequent calculi LK+ and LK++ that
extend Gentzen’s sequent calculus LK by unsound quantifier rules
in such a way that (i) derivations lead only to true sequents
(ii) cut free proofs may be non-elementary shorter than cut free LK proofs.
This research is based on properties of Hilbert’s epsilon calculus and
is part of efforts to complement Hilber’s stepwise concept of proof by
useful global concepts.
We use these ideas to provide analytic calculi for Henkin quantifiers and
demonstrate soundness, (cut free) completeness and cut elimination.
Furthermore, we show, that in the case of quantifier macros such as Henkin
quantifiers for a partial semantics global calculi are the only option to
preserve analyticity.

Feng Qi: On investigation of some foundational problems of economics

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 30 January 2019, 17:00 hrs

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

Speaker: Feng Qi

Title: On investigation of some foundational problems of economics

Abstract: I shall present some of my toughts regarding some foundational
problems of economics from mathematical logic point of view.

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

Logic Seminar 23 Jan 2019 17:00 hrs at NUS

Invitation to the Logic Seminar at the National University of Singapore

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

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

Speaker: Keita Yokoyama

Title: Ekeland’s variational principle in reverse mathematics

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

Abstract: Ekeland’s variational principle is a key theorem used in various
areas of analysis such as continuous optimization, fixed point theory and
functional analysis. It guarantees the existence of pseudo minimal
solutions of optimization problems on complete metric spaces. Let f be
a positive real valued continuous (or lower semi-continuous) function
on a complete metric space (X,d). Then, a point x in X is said to be a
pseudo minimum if f(x)=f(y)+d(x,y) implies x=y. Now, Ekeland’s
variational principle says that for any point a in X, there exists a
pseudo minimum x such that f(x)<=f(a)-d(a,x). In reverse
mathematics, it is observed that many theorems for continuous
optimization problems are provable within the system of arithmetical
comprehension (ACA-0), and thus most such problems have arithmetical
solutions. However, this is not the case for pseudo minima. We will
see that Ekeland’s variational principle or its restriction to the
space of continuous functions C([0,1]) are both equivalent to
Pi-1-1-comprehenstion. This is a joint work with Paul Shafer and David
Fernandez-Duque.

Keita Yokoyama: Ekeland’s variational principle in reverse mathematics

Invitation to the Logic Seminar at the National University of Singapore

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

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

Speaker: Keita Yokoyama

Title: Ekeland’s variational principle in reverse mathematics

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

Abstract: Ekeland’s variational principle is a key theorem used in various
areas of analysis such as continuous optimization, fixed point theory and
functional analysis. It guarantees the existence of pseudo minimal
solutions of optimization problems on complete metric spaces. Let f be
a positive real valued continuous (or lower semi-continuous) function
on a complete metric space (X,d). Then, a point x in X is said to be a
pseudo minimum if f(x)=f(y)+d(x,y) implies x=y. Now, Ekeland’s
variational principle says that for any point a in X, there exists a
pseudo minimum x such that f(x)<=f(a)-d(a,x). In reverse
mathematics, it is observed that many theorems for continuous
optimization problems are provable within the system of arithmetical
comprehension (ACA-0), and thus most such problems have arithmetical
solutions. However, this is not the case for pseudo minima. We will
see that Ekeland’s variational principle or its restriction to the
space of continuous functions C([0,1]) are both equivalent to
Pi-1-1-comprehenstion. This is a joint work with Paul Shafer and David
Fernandez-Duque.

Frank Stephan: Lampligher groups and automata

Invitation to the Logic Seminar at the National University of Singapore

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

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

Speaker: Frank Stephan

Title: Lampligher groups and automata

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

Joint work with:
Sanjay Jain, Birzhan Moldagaliyev and Tien Dat Tran.

Abstract:
This talk is about representing lamplighter groups using
computational models from automata theory. It will be shown that
if G can be presented such that the full group operation
is recognised by a transducer, then the same is true for the lampgligher
group of G created by taking the restricted wreath product of
G with the group of integers Z. Furthermore, Cayley presentations,
where only multiplications with constants are recognised by transducers,
are used to study generalised lampglighter groups where one
takes the restricted wreath product of G over a d-dimensional
copy of the integers or the free group with d generators.
Additionally, if G is a finite group then the restricted wreath
product of G over the two-dimensional group of integers is Cayley
tree automatic.

The paper is available at
http://www.comp.nus.edu.sg/~fstephan/transducergroup.ps

Konstantin Slutsky: Orbit equivalences of Borel flows

Invitation to the Logic Seminar at the National University of Singapore

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

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

Speaker: Konstantin Slutsky

Title: Orbit equivalences of Borel flows

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

Abstract:
The purpose of this talk is to provide an overview of the orbit
equivalence theory of Borel R^n-flows.
An orbit equivalence of two group actions is a bijective map
between phase spaces that maps orbits onto orbits.
Such maps are often further required to posses regularity properties
depending on the category of group actions that is being considered.
For example, Borel dynamics deals with Borel orbit equivalences,
ergodic theory considers measure-preserving maps, topological dynamics
assumes continuity, etc.

Since its origin in 1959 in the work of Henry Abel Dye,
the concept of orbit equivalence has been studied quite extensively.
While traditionally larger emphasis is given to actions of
discrete groups, in this talk we concentrate on free actions
of R^n-flows taking the viewpoint of Borel dynamics.

For a free R^n-action, an orbit can be identified
with an “affine” copy of the Euclidean space, which allows us
to transfer any translation invariant structure from R^n
onto each orbit. The two structures of utmost importance will be
that of Lebesgue measure and standard Euclidean topology.
One may then consider orbit equivalence maps that furthermore
preserve these structures on orbits. Resulting orbit equivalences
are called Lebesgue orbit equivalence (LOE) and time-change
equivalence respectively.

It turns out that properties of LOE maps correspond most closely to
those of orbit equivalence maps between their discrete
counterparts – free Z^n actions.
We illustrate this by outlining a proof of the analog for
R^n-flows of Dougherty-Jackson-Kechris classification
of hyperfinite equivalence relations.
Orbit equivalences of flows often arise as extensions of maps between
cross sections – Borel sets that intersect each orbit in a
non-empty countable set. Furthermore, strong geometric restrictions
on cross-sections are often necessary. As a concrete example,
we explain why one-dimensional R-flows posses
cross sections with only two distinct distances between adjacent
points, and show how this implies classification of R-flows
up to LOE.

We conclude the talk with an overview of time-change equivalence,
emphasizing the difference between Borel dynamics and ergodic theory
and mentioning several open problems.
The interest reader is referred to the technical report on
http://arxiv.org/abs/1504.00958.