Non-computable models of certain first order theories
Gábor Sági, Ramon Horvath · 2017
Let D be a complexity class. A countable first order structure is defined to be D-presented if all of its basic relations and functions are in D. We show, that if T is a first order theory with at least one uncountable Stone space then T has a countable model not isomorphic to any D-presented one. We also show that there is a countable N0-categorical structure in a finite language which is not isomorphic to any D-presented structure; in addition, there exists a consistent first order theory in a finite language that does not have D-presented models, at all. Our proofs utilize model theoretic methods and do not involve any nontrivial recursion theoretic notion or construction.