Thursday November 6  4:00 412 SEO<br>
Speaker: Steffen Lempp<br>
Title: Constructive models of uncountably categorical theories<br>
(joint work with B. Herwig and M. Ziegler)<br><br>
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.