MATH 7810 - Seminar in Logic

Richard Shore, fall 2016.

The logic seminar will meet twice a week for 75 minutes each time. One meeting will, generally, be devoted to participants and visitors speaking about their current reading or research. The other day will be devoted to participants lecturing on papers about a single topic.

One strong possibility for the fall semester topic is the study of various notions of computable reducibility between sets of reals and "problems". By a problem we mean the problem of finding for every real $X$ (say representing a graph or some other structure) a real $Y$ with some property (being a coloring of something else). A reducibility here means a way of taking any instance one "problem" (the $X$) to an instance $X'$ of a second problem so that from any solution $Y'$ to the second problem for $X'$ one can get a solution $Y$ to the first problem for $X$. If the processes of going from $X$ to $X'$ and from $Y$ to $Y'$ are in some sense computable, then one has some kind of reduction of the first problem to the second. We will also study the relationships between the existence or nonexistence of such reductions and reverse mathematics and perhaps computable structure theory.

Other suggestions will be entertained.