IMS-JSPS Joint Workshop in Mathematical Logic and Foundations of Mathematics
(1 - 5 Sep 2014)

~ Abstracts ~


Randomness in the absence of full induction
Chi Tat Chong, National University of Singapore

We examine properties of algorithmic randomness in systems weaker than Peano arithmetic. In particular, we exhibit some particular models for case study.

« Back...


A new kind of computability theory on reals
Longyun Ding, Nankai University, China

We will introduce a new kind of computability theory on reals, and also on higher types. We define new kinds of unlimited register machine (URM) and recursion functions. We show that the computable functions of this new URMs are coincide with the new recursion functions. We will compare our new computability theory with many kinds of known theories: Oracle Turing machine, BSS machine, Kleene's recursion theory on higher types, and M-S machine.

« Back...


Intuitionistic provability and uniformly provability in RCA
Makoto Fujiwara, Tohoku University, Japan

For Pi^1_2 statements, their sequential versions are investigated in reverse mathematics, revealing the necessity of the non-uniformity of their proofs in RCA. We see the relationship between the provability in the intuitionistic version EL of RCA and the uniform provability in RCA for such Pi^1_2 statements.

« Back...


Weak lowness notions for Kolmogrov complexity
Ian Herbert, National University of Singapore

The (prefix-free) Kolmogorov complexity of a finite binary string is the length of the shortest description of the string given by some universal decoding machine. This gives rise to some `standard' lowness notions for reals: A is K-trivial if its initial segments have the lowest possible complexity and A is low for K if using A as an oracle does not decrease the complexity of strings by more than a constant factor. We discuss various ways of weakening these notions and the relations between these weakenings. Kolmogorov complexity also induces some reducibility notions that are weaker than Turing reducibility, and we discuss the behavior of these new lowness notions with respect to these reducibilities.

« Back...


The theory of universally Baire sets in 2^{\omega_1}
Daisuke Ikegami, Kobe University, Japan

The goal of this research is to understand the theory of subsets of \omega_1 under ZFC + large cardinals + forcing axioms as much as the theory of subsets of \omega under ZFC + large cardinals.

The theory of universally Baire sets of reals has been proven to be crucial to understand the theory of subsets of \omega. Universally Baire sets of reals are the key mathematical objects connecting large cardinals, determinacy, generic absoluteness, and inner model theory.

In this talk, we introduce the notion of universally Baireness for subsets of 2^{\omega_1} and develop the basic theory of universally Baire sets in 2^{\omega_1} under ZFC + large cardinals + forcing axioms. This is joint work with Matteo Viale.

« Back...


Non-principal ultrafilters, program extraction and higher order reverse mathematics
Alexander Kreutzer, National University of Singapore

We investigate the strength of the existence of a non-principal ultrafilters over fragments of higher order arithmetic.

Let (U) be the statement that a non-principal ultrafilter on N exists and let ACA_0^w be the higher order extension of ACA_0 (arithmetical comprehension).

We show that ACA_0^w+(U) is \Pi^1_2-conservative over ACA_0^w and thus that ACA_0^w+(U) is conservative over PA.

Moreover, we provide a program extraction method and show that from a proof of a strictly Pi^1_2 statement \forall f \exists g A_qf(f,g) in ACA_0^w+(U)$ a realizing term in Gödel's system T can be extracted. This means that one can extract a term t, such that \forall f A_qf(f,t(f)).

« Back...


Coloring on trees and Ramsey's theorem for pairs
Wei Li, University of Vienna, Austria

In this talk, we prove that over RCA_0, TT^1 and RT^2_2 are independent of each other. This is a joint work with Professor Chong Chi Tat in NUS.

« Back...


Some RF-type theorems in reverse mathematics
Shota Murakami, Tohoku University, Japan

Ramseyan factorization theorem (RF for short) is a Ramsey-type theorem which is used in automata theory. In a joint work with Takeshi Yamazaki and Keita Yokoyama, we showed that RF^2_2 is equivalent to RT^2_2 over RCA_0 and its weak version is in between ADS and CAC. In this talk, we consider some other variations of RF and discuss their relative strength.

« Back...


Measuring the relative strength of sets of natural numbers
Keng Meng Ng, Nanyang Technological University

The study of algorithmic randomness, in particular of lowness properties in randomness has led to many exciting recent developments in the area. In particular this has provided us a tool to compare the amount of inherent "information" present in sets of natural numbers, using what is known as "weak reducibilities". In this talk we will mention some related results, and explore the notion of an LR-base for randomness. We present several new results about this class, and investigate its position in the jump-traceable hierarchy. This is joint work with Johanna Franklin and Reed Solomon.

« Back...


Expressibility of simple unary generalized quantifier
Shohei Okisaka, Tohoku University, Japan

Generalized quantifier was introduced by Mostowski and extended by Lindstrom, which is related to computational complexity in the context of finite model theory. Generalized quantifier corresponding to the class of finite structures which vocabulary has only one unary relation symbol is called simple unary. Today I will talk about comparability between two simple unary generalized quantifiers.

« Back...


Lindelöf group with non-Lindelöf square and strong negative partition relation
Yinhe Peng, Chinese Academy of Sciences, China

This talk is based on a joint work with Liuzhen Wu. We generalize Justin Moore's construction of an L space to get an L group -- a topological group which is an L space -- and prove that its square is not Lindelöf. This answers a question asked by Arhangelskii in the 1980s. We also show that strong negative partition relations on $\omega_1$ (such as $pr_0(\omega_1,\omega_1,n)$) hold and apply it to finite powers of L spaces and answer several questions concerning regular spaces and their squares.

« Back...


Some properties of probability theory in reverse mathematics
Ningning Peng, National University of Singapore

In this talk, we will deal with some basic properties in probability theory, for example, the properties on independent random variables, and give some results in the context of reverse mathematics.

« Back...


On embedding certain partial orders into the P-points under Tukey and RK reducibility
Dilip Raghavan, National University of Singapore

The study of the global structure of the P-points was initiated mainly by Blass in 1970s. In a paper in 1973 he asked what partially ordered sets can be embedded into the P-points under the ordering of Rudin-Keisler reducibility. This question is of most interest under some hypothesis that guarantees the existence of many P-points, such as Martin's axiom for sigma-centered posets. In the 1973 paper he showed under this assumption that both {\omega}_{1} and the reals can be embedded. This result was later generalized to the coarser notion Tukey reducibility. We will prove that under Martin's axiom for sigma-centered posets P(\omega)/FIN can be embedded into the P-points both under Rudin-Keisler and Tukey reducibilities. Since P(\omega)/FIN is universal for partial orders of size at most continuum, this a good step towards giving a complete answer to Blass' original question. This is joint work with Saharon Shelah.

« Back...


The role of the axiom DOM in reverse mathematics and its applications to model inductive inference
Frank Stephan, National University of Singapore

Weakly represented families of functions are families coded into some set where for valid indices all values are coded while for invalid indices, only finitely many indices are coded. The axiom DOM says that for every weakly represented family of functions there is a function in the second order model which dominates this family. This axiom turns out to be important for various properties related to uniformly represented and weakly represented families of sets. For example, it implies the axiom COH, but not vice versa. Furthermore, in the framework of inductive inference, there is a close relation between the axiom DOM and the various formalisations of learnability theorems which provide sufficient or characterising criteria on when a uniformly represented family or a weakly represented family of sets is learnable in the limit from positive data. This talk gives an overview on recent results obtained with Rupert Hoelzl, Sanjay Jain, Dilip Raghavan and Jing Zhang.

« Back...


Variants of infinite games and their strength
Kazuyuki Tanaka, Tohoku University, Japan

Recently, much effort has been made to characterize the determinacy of Gale-Stewart Borel games within second order arithmetic. On the other hand, Borel hierarchies and Wadge hierarchies based on less powerful machines have been extensively studied in theoretical computer science, and so a winning strategy of a game in such a hierarchy is very often computable. In this talk, I will review these two lines of studies and their relations, and consider some problems in the intersecting area.

« Back...


Definability of the ground model and large cardinals
Toshimichi Usuba, Kobe University, Japan

Woodin and Laver independently showed that, in the forcing extension, the ground model is a definable class with some parameters. In this talk, we prove that the ground model is a Pi_2-definable class with some parameters, and, using this, we also prove that some large cardinals are destructible under various forcing notions.

« Back...


Beyond Peano arithmetic?
Tin Lok Wong, University of Vienna, Austria

In the 1960s, Scott and Keisler found appealing notions of elementary extensions that respectively characterize measurability in set theory and Peano arithmetic (PA) in first-order arithmetic. Such characterizations were brought into second-order arithmetic by Kirby and Paris in the late 1970's by means of cuts, but none of the known results applies to theories stronger than PA. I will discuss some recent attempts in changing this situation.

« Back...


On exact d.c.e. degrees
Guohua Wu, Nanyang Technological University

In this talk, we will talk about exact degrees, a concept related to degrees of Lachlan sets of d.c.e. sets. Given a d.c.e. degree d, we consider the d.c.e. sets in d and the Turing degrees of their Lachlan sets. Ishmukhametov provided a systematic investigation of such c.e. degrees, and proved that there are d.c.e. degrees d such that the class of its c.e. predecessors in which d is c.e. (denoted as R[d]) can be a singleton or an interval of c.e. degrees. Along this line, Fang, Wu and Yamaleev proved the existence of a d.c.e. degree d such that the class R[d] has no minimal element, giving a positive answer to a problem of Ishmukhametov. On the other hand, according to Ishmukhametov, a d.c.e. degree with R[d] a singleton is called an exact degree. We are interested in the distribution of such exact degrees. Recently, with Liu and Yamaleev, we proved that exact d.c.e. degrees are downwards dense in the c.e. degrees. We will also talk about problems of bubble degrees.

« Back...


Some fixed point theorems and reverse mathematics
Takeshi Yamazaki, Tohoku University, Japan

In general, a fixed point theorem asserts that, under certain conditions, a function f will have a point x such that f(x)=x. Today, we have many results of this kind in various fields of mathematics. In this talk, we will pick up some of them from different areas and discuss their reverse-mathematical aspect.

« Back...


Some remarks on computation on reals
Yue Yang, National University of Singapore

In this talk, I will first present a model of computation on real numbers. It is a natural generalization of standard Turing machines. This model fits more closely to the intuition of working mathematicians, for example, the exponential function and the equality predicate are both computable. I will also compare it with other existing models, such as BSS and TTE models. Finally I will present a Normal Form Theorem which is a joint work with Keng Meng Ng from NTU and Nazanin Tavana from IPM, Iran.

« Back...


Whitehead problem and ACA_0
Sen Yang, Inner Mongolia University, China

Stein's theorem says any coutable Whitehead group is free. We formalize this problem in second-order arithmetic and prove that it is a consequence of ACA_0, and WKL_0 plus Stein's theorem implies ACA_0.

« Back...


Termination theorem and Ramsey's theorem
Keita Yokoyama, Japan Advanced Institute of Science and Technology, Japan

Ramsey-like methods are often used in computer science. One of such examples is the Rybalchenko Podelski termination theorem which is often used in the study of termination checking. In this talk we will compare several versions of termination theorems with (restricted) Ramsey's theorem in the context of Reverse Mathematics. Then, we will discuss the possibility of some applications of proof-theoretic methods into the study of program termination.

« Back...

Best viewed with IE 7 and above