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