Computability Seminar MSRI program on DDC-Cohesive powers of linear orders

Organizer: V. Harizanov

For link contact [email protected]

Friday, October 30 12:00-1:00 ET on Zoom

Speaker: Paul Shafer, University of Leeds, UK

Title: Cohesive powers of linear orders

Abstract: A cohesive power of a computable structure is an effective analog of an ultrapower, where a cohesive set acts as an ultrafilter.  We investigate the following question.  Fix a cohesive set C and a computably presentable structure A, and consider the various computable copies B of A.  How do the cohesive powers of B by C vary as B varies?
Let omega, zeta, and eta denote the respective order-types of (N, <), (Z, <), and (Q, <).  We take omega as our computably presentable structure, and we consider the cohesive powers of its computable copies.  If L is a computable copy of omega that is computably isomorphic to the standard presentation (N, <), then all of L’s cohesive powers have order-type omega + (zeta x eta), which is familiar as the order-type of countable non-standard models of PA.
We show that it is possible to realize a variety of order-types other than omega + (zeta x eta) as cohesive powers of computable copies of omega (that are necessarily not computably isomorphic to the standard presentation).  For example, we show that if C is a co-c.e. cohesive set, then there is a computable copy L of omega where the cohesive power of L by C has order-type omega + eta.  More generally, we show that it is possible to achieve order-types of the form omega + certain shuffle sums as cohesive powers of computable linear orders of type omega.
This work is joint with Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Alexandra Soskova, and Stefan Vatev.