# Andrej Bauer: Instance reducibilities

Date: 14. 11. 2016

Source: Mathematics and theoretical computing seminar

Source: Mathematics and theoretical computing seminar

Torek, 15. 11. 2016, od 12h do 14h, Plemljev seminar, Jadranska 19

**Abstract:** Starting from a common proof technique for showing that one universal statement implies another universal statement, we identify a notion of logical reduction, which we call *instance reducibility*. We study instance reducibilities in a constructive setting (because it is trivial in classical logic) and show that it has rich structure. We then relate the instance reducibilities to Weirauch reducibility in computable mathematics. The relationship suggests a generalization of Weirauch reducibility that gives a better behaved structure of degrees.

This is joint work with Kazuto Yoshimura from JAIST.