Cohesive Powers of Linear Orders

Abstract: Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. The aim is also to compare and contrast properties of cohesive powers with those of classical ultrapowers. Classically, an ultrapower of a structure is elementarily equivalent to the base structure by Łoś's theorem. Effectively, Łoś's theorem holds for cohesive powers of decidable structures. For cohesive powers of $n$-decidable structures, Łoś's theorem need only hold up to $\Delta_{n+3}$-expressible sentences. In fact, every $\Sigma_{n+3}$ sentence true of an $n$-decidable structure is also true of all of its cohesive powers, but this is optimal in general. Classically, ultrapowers of isomorphic structures over a fixed ultrafilter are isomorphic. Effectively, cohesive powers of computably isomorphic computable structures over a fixed cohesive set are isomorphic. However, it is possible for isomorphic (but not computably isomorphic) computable structures to have non-elementarily equivalent (hence non-isomorphic) cohesive powers. Classically, the Keisler–Shelah theorem states that two structures are elementarily equivalent if and only if there is an ultrafilter over which the corresponding ultrapowers are isomorphic. Effectively, an analogous result holds for decidable structures. If the structures are computable that are not necessarily decidable, then the effective version of the Keisler–Shelah theorem can fail in either direction. Classically, for a countable language, ultrapowers over countably incomplete ultrafilters are $\aleph_1$-saturated. Effectively, cohesive powers of decidable structures are recursively saturated. Furthermore, cohesive powers of n-decidable structures are $\Sigma_n$-recursively saturated. Most interestingly, if the cohesive set is assumed to be co-c.e., then we obtain an additional level of saturation: cohesive powers of n-decidable structures over co-c.e. cohesive sets are $\Sigma_{n+1}$-recursively saturated.

We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of $\omega$. If $\mathcal{L}$ is a computable copy of $\omega$ that is computably isomorphic to the standard presentation of $\omega$, then every cohesive power of $\mathcal{L}$ has order-type $\omega + \zeta\eta$. However, there are computable copies of $\omega$, necessarily not computably isomorphic to the standard presentation, having cohesive powers not elementarily equivalent to $\omega + \zeta\eta$. For example, we show that there is a computable copy of $\omega$ with a cohesive power of order-type $\omega + \eta$. Our most general result is that if $X \subseteq \mathbb N \setminus \{0\}$ is a Boolean combination of $\Sigma_2$ sets, thought of as a set of finite order-types, then there is a computable copy of $\omega$ with a cohesive power of order-type $\omega + \bm{\sigma}(X \cup \{\omega + \zeta\eta + \omega^*\})$, where $\bm{\sigma}(X \cup \{\omega + \zeta\eta + \omega^*\})$ denotes the shuffle of the order-types in $X$ and the order-type $\omega + \zeta\eta + \omega^*$. Furthermore, if $X$ is finite and non-empty, then there is a computable copy of $\omega$ with a cohesive power of order-type $\omega + \bm{\sigma}(X)$.

This is a joint work with Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer and Stefan Vatev.

It was partially supported by Bulgarian National Science Fund KP-06-Austria-04/06.08.2019, FNI-SU 80-10-134/20.05.2022.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic