Effective ultrapowers of graphs and other structures
Valentina Harizanov, Keshav Srinivasan · Contemporary mathematics - American Mathematical Society · 2025
The effective ultraproduct construction for structures is a computability-theoretic analog of the classical ultraproduct construction, where the structures are uniformly computable and the role of an ultrafilter is played by a cohesive set. A cohesive set is an infinite set of natural numbers, which cannot be split into two infinite parts by any computably enumerable set. While the elements of the classical ultraproduct are equivalence classes of arbitrary sequences of elements of structures, in the effective case, these sequences are partial computable, and in some cases computable. Hence the effective ultraproduct construction allows us to build countable nonstandard models with interesting properties. We investigate the isomorphism types and other model-theoretic properties of cohesive powers of computable structures, focusing on certain graphs and equivalence structures. We show how computable structures can have effective ultrapowers with new properties, while preserving some old ones, as expressed in a formal language. For graphs we show that every graph can be embedded into the cohesive power of a certain kind of special graph.