Effective Ultrapowers of Computable Structures
Open Access DepositedThe 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 acomputability-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: \begin{itemize} \item Equivalence Structures \item Injection Structures \item Two to One Structures \item 2,0:1 Structures \item Partial Injection Structures \item Directed Pseudoforests \item Strongly Locally Finite Graphs \item Abelian $p$-groups \item Number Fields \item Infinite Algebraic Extensions of $\mathbb{Q}$ \end{itemize}
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Srinivasan_gwu_0075A_16914.pdf | 2025-04-09 | Open Access |
|