April 4
Valentina Harizanov,
George Washington University
Computable structures and their effective products
We consider a computability-theoretic version of the ultraproduct construction for an infinite uniformly computable sequence of structures, where the role of an ultrafilter is played by an infinite set of natural numbers that cannot be split into two infinite subsets by any computably enumerable set. For computable structures, effective powers preserve only the first-order sentences of lower levels of quantifier complexity. Additional decidability of the structure increases preservation of the fragments of its theory in an effective power, so that a structure with a computable elementary diagram is elementarily equivalent to its effective power. We will present a number of recent collaborative results.