Thursday November 6 4:00 412 SEO
Speaker: Steffen Lempp
Title: Constructive models of uncountably categorical theories
(joint work with B. Herwig and M. Ziegler)

Abstract: By a well-known theorem of Baldwin and Lachlan, the countable models of an uncountably but not totally categorical theory form an elementary chain of length omega+1. If the theory is decidable, these models must all be decidable (i.e., have a decidable elementary diagram) by a result of Harrington and Khisamiev. Otherwise, however, assuming a recursive language, some of these models may be constructive (i.e., have a decidable open diagram) while the others do not, as was established in a variety of results by Goncharov, Kudaibergenov, and Khoussainov/Nies/Shore. All these results use infinite languages in an essential way. Recently, Herwig, Lempp, and Ziegler were able to show that even for a language of one binary relation, the prime model may be constructive while the other models are not. The prime model consists of a disjoint union of finite Cayley graphs, whose associated finite groups approximate a recursively presented group with unsolvable word problem. Only the non-prime model, however, can decode this unsolvable word problem and can therefore not be constructive. A related open question asks exactly how complicated the non-constructive models can be, assuming one of the models if constructive, in particular, whether all of them must be arithmetical.