Saturday, 7 March 2015
10:00 - 10:45 Makoto Fujiwara (Tohoku University)
Title : Weak marriage theorems in second-order arithmetic

#### Abstract

The so-called (symmetric) marriage theorem states that every countable locally finite bipartite graph which satisfies Hall condition has a perfect matching. It is known in reverse mathematics that this marriage theorem is equivalent to ACA over RCA_0. In this talk, we introduce some strengthened versions of Hall condition which make computable locally finite bipartite graphs have computable perfect matchings. Then we discuss the interrelations between marriage theorems with those conditions and induction axiom schemata in second-order arithmetic.
11:00 - 11:45 Keng Meng Ng (Nanyang Univ. of Tech.)
Title : Finitary reducibilities for arithmetical equivalence relations

#### Abstract

The comparison of equivalence relations is usually done by a computable many-one function. This is sometimes seen as being too uniform, for instance, there are no Pi^0_n-complete equivalence relation under the many-one reducibility. We introduce a different reducibility, the finitary reducibility, and show that in many cases this is a more natural way to compare arithmetical equivalence relations.
Lunch
14:00 - 14:45 Daisuke Ikegami (Kobe University)
Title : Wadge reducibility for the real line

#### Abstract

Wadge reducibility is an analogue of many-one reducibility in recursion theory via continuous functions from a topological space to itself, and it proves to be useful when one considers the complexity of subsets of a topological space in many contexts including automata theory and descriptive set theory. In 1980s, Wadge investigated the Wadge reducibility for the Baire space ($\omega^{\omega}$) and analyzed the structure of Borel subsets of the Baire space via Wadge reducibility by connecting it with the determinacy of Borel sets. In this talk, we present some results on the Wadge reducibility for the real line and compare it with the Wadge reducibility for the Baire space. This is joint work with Philipp Schlicht and Hisao Tanaka.
15:00 - Free discussions / Excursion