Time: Thursday, October 7, 4:30-5:30PM
Speaker: Philip White, GWU
Title: Definability, computability, relativization and forcing
Abstract: If a property has a characterizing feature definable using computable formulas in our computable base structure, then it follows that this property holds in every computable copy of the base structure. Conversely, if we have the property in every computable copy, it is not always the case that we can define the characterizing feature in our base structure. However, Ash and Nerode proved that under certain additional algorithmic conditions we have this equivalence. If we ease our focus and allow for arbitrary copies of our base structure instead of only computable copies and “relativize the property”, it turns out that a similar argument goes through, only now the effectiveness conditions can be dropped. We will look at this relativized version. The technique used for it will be forcing. Just to mention: Forcing is the same renowned technique developed by Paul Cohen to prove the independence of the continuum hypothesis and the axiom of choice.