INTRODUCTION

Chang and Keisler [8] famously defined model theory as the sum of logic and universal algebra. In the same spirit, one might describe computable model theory to be the investigation of the constraints on information content imposed by algebraic structure. The analogue of the interplay between syntactical objects and the algebraic structure they define is the connection between definability and complexity. One asks: How complicated are the constructions of model theory and algebra? What kind of information can be coded in structures like groups, fields, graphs, and orders? What mathematical distinctions are unearthed when “boldface” notions such as isomorphism are replaced by their “lightface” analogues such as, say, computable isomorphism? ...

Start Free Trial

No credit card required