Effective Ultrapowers of Computable Structures

Abstract

The ultraproduct construction is a major mathematical construction that is used in algebra, mathematical logic, and other areas. It allows us to construct new models of theories from old ones. The ultraproduct is a quotient of the direct product of structures modulo an equivalence relation determined by an ultrafilter. The ultraproduct construction has some striking applications, such as a very elegant proof of the compactness theorem in first-order logic, and the construction of nonstandard models of analysis.

Dimitrov introduced the notion of an effective ultraproduct construction for structures, which 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 non-standard 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.

The computable structures for which we classify cohesive powers for include the following:

• Equivalence Structures

• Injection Structures

• Two to One Structures

• 2,0:1 Structures

• Partial Injection Structures

• Directed Pseudoforests

• Strongly Locally Finite Graphs

• Abelian p-groups

• Number Fields

• Infinite Algebraic Extensions of Q