Tennenbaum-like theorems for cohesive powers

Abstract

We investigate the encoding ability of the cohesive power construction. We compute a graph $\mathcal{G}$ where the cohesive power ${\prod }_C\mathcal{G}$ of $\mathcal{G}$ by any ${\Delta }_2$ cohesive set $C$ has degree $0^{\prime \prime }$. That is, $0^{\prime \prime }$ computes a presentation of ${\prod }_C\mathcal{G}$, and every presentation of ${\prod }_C\mathcal{G}$ computes $0^{\prime \prime }$. We also compute a linear order $\mathcal{L}$ where no cohesive power of $\mathcal{L}$ has a computable presentation. We accomplish this by ensuring that if $\mathcal{P}$ is a presentation of a cohesive power of $\mathcal{L}$, then ${\mathcal{P}}^{\prime \prime }$ has $\mathrm{PA}$-degree relative to $0^{\prime \prime }$.