University Seminar CCAS (Computability, Complexity, and Algebraic Structure)-A Computability Theoretic Forcing Framework

Time: Wednesday, October 23, 2:20 – 3:20pm

Place: Rome Hall, Room 352

Speaker:  Philip White, GWU

Title: A Computability Theoretic Forcing Framework

Abstract:  We present a computability theoretic framework for forcing to construct an isomorphic copy B of a computable structure A. The forcing poset P is the set of finite one-to-one partial functions from N (the collection of natural numbers) onto N, ordered by reverse inclusion. A specialized forcing language is introduced, incorporating symbols for both our isomorphism and for distinguished computable sets. We then precisely define the forcing relation for different types of formulas, ensuring properties like monotonicity and consistency. Finally, we prove a Rasiowa-Sikorski type lemma for our isomorphism g, but instead of allowing g to be fully generic, we use just enough genericity for the argument to go through. Important results, such as the Truth and Forcing lemma and the Transition Lemma, are presented to show the connection between truth in B and the arithmetical hierarchy.