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''$. That is, $0''$ computes a presentation of $\prod_C \mathcal{G}$, and every presentation of $\prod_C \mathcal{G}$ computes $0''$. 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}''$ has $\mathrm{PA}$-degree relative to $0''$.