Adding Skolem functions to simple theories (Q701730)

The author examines the conditions under which one can keep simplicity and categoricity after adding a Skolem function to a theory. Let \(M\) be an \(L\)-structure, and \(\phi(x,\bar y)\) an \(L\)-formula, \(\bar y=(y_1,\dots,y_k)\). An algebraic Skolem function for \(\phi\) is defined to be a function \(f:M^k\to M\) such that for every \(k\)-tuple \(\bar a\) in \(M\) we have \(f(\bar a)\in\phi(M,\bar a)\) whenever \(\phi(M,\bar a)\) is finite and nonempty, and \(f(\bar a)=a_1\) otherwise. A first-order \(L\)-theory \(T\) is called algebraically bounded if for any \(\phi\) there is \(n_\phi\) such that, for any model \(M\) of \(T\) and \(\bar a\) in \(M\), if \(\phi(M,\bar a)\) is finite then \(| \phi(M,\bar a)| \leq n_\phi\). In this case for any \(\phi\) there is a first-order theory \(T_\phi\) in the language \(L\cup\{f\}\) whose models are the expansions of models of \(T\) by algebraic Skolem functions for~\(\phi\). Suppose \(T\) is complete, model-complete, and algebraically bounded. \textit{P. M. Winkler} [Lect. Notes Math. 498, 408--463 (1975; Zbl 0324.02035)] showed that for any \(\phi\) the theory \(T_\phi\) has a model-completion \(T^*_\phi\) which is algebraically bounded as well. The author proves, using the method of \textit{Z. Chatzidakis} and \textit{A. Pillay} [Ann. Pure Appl. Logic 98, 71--92 (1998; Zbl 0929.03043)], that if \(T\) is (super)simple then any completion of \(T^*_\phi\) is (super)simple. Iterating this, for a simple \(T\) he constructs a simple expansion of \(T\) in which the algebraic and definable closures coincide. It is shown that if \(T\) is \(\omega\)-categorical then any completion of \(T^*_\phi\) is \(\omega\)-categorical; moreover, adding recursively for every \(n<\omega\) finitely many \(n\)-ary algebraic Skolem functions, the author constructs an expansion of \(T\) which has a model-completion all whose completions are \(\omega\)-categorical with algebraic closure equal to definable closure. Similar results fail for uncountable categoricity: it is shown that if \(T\) is the theory of algebraically closed fields of characteristic \(\neq 2\) and \(\phi\) is the formula \(x^2=y\) then \(T^*_\phi\) interprets the theory of random graphs, and so is unstable. Now suppose in addition that \(T\) admits quantifier elimination, and all subsets of models of \(T\) are algebraically closed. For a set \(X\) of positive integers, let \(T_X=\{f^n(x)\neq x: n\in X\}\), where \(f\) is a new unary function symbol. It is shown that \(T\cup T_X\) has a model completion which is simple (stable) if \(T\) is simple (stable).