Effective Ultrapowers and Applications; Aspects of Computation and Automata Theory with Applications
Greenberg, Noam; Jain, Sanjay; Ng, Keng Meng; Schewe, Sven; Stephan, Frank; Wu, Guohua; Yang, Yue
(Ed.)
We give a systematic account of the current state of knowledge of an e↵ective analogue of the ultraproduct construction. We start with a product of a uniformly computable sequence of computable structures indexed by the set of natural numbers. The equality of elements and sat- isfaction of formulas are defined modulo a subset of the index set, which is cohesive, i.e., indecomposable with respect to computably enumerable sets. We present an analogue of Lo ́s’s theorem for e↵ective ultraprod- ucts and a number of results on definability and isomorphism types of the e↵ective ultrapowers of the field of rational numbers, when the com- plements of cohesive sets are computably enumerable. These e↵ective ultraproducts arose naturally in the study of the automorphisms of the lattice of computably enumerable vector spaces. Previously, a number of authors considered related constructions in the context of nonstandard models of fragments of arithmetic.
more »
« less
An official website of the United States government

