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
|