21
$\begingroup$

Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable."

Say that a computable structure $A$ is compact for computability iff for each sequence $(R_i)_{i\in\omega}$ of automorphically-fixed relations on $A$, the following are equivalent:

  • For each $n$ there is a computable copy $B_n$ of $A$ such that $R_i^{B_n}$ is computable for each $i<n$.

  • There is a computable copy $B_\infty$ of $A$ such that $R_i^{B_\infty}$ is computable for each $i$.

Basically: $A$ is compact for computability iff whenever I have a family of relations, any finite subset of which is computably presentable, I can whip up a computable copy of $A$ on which each of the relations is computable (although perhaps non-uniformly so). We restrict attention to automorphically-fixed relations since otherwise things just go terribly (see earlier edits).

Compactness-for-computability is trivial for finite-computable-dimension (= number of computable copies up to computable isomorphism) structures; meanwhile, see the end of this answer for a proof that there is a computable structure which is not compact-for-computability in the first place.

Question: is there a computable structure $A$ with infinite computable dimension which is compact-for-computability? In particular, is $(\omega;<)$ compact-for-computability?

Chapter 4 of Harrison-Trainor's Degree spectra of relations on a cone (which is excellent) is the most relevant source I can find, since it proves that $(\omega;<)$ is compact for computability with respect to arbitrary sets of $\Sigma_1^c$ predicates (see the proof of Proposition 4.12 (4.14 in the arxiv version)). But the full status of $(\omega;<)$ is still open.


Here's a sketch of a construction of a computable structure which is not compact-for-computability. The computability-theoretic lemma we need is that there is a $\Pi_2$-sequence of graphs $(G_i)_{i\in\omega}$, each of which is individually computably presentable, but which are not uniformly computably presentable; I don't know who this is originally due to, but I'm sure it's old. Take this for granted (the proof isn't hard) and let $X=(G_i)$ be such a sequence of graphs. We form a structure $S(X)$ based on $X$ as follows:

Starting with a copy of the naturals (with successor) and fixing a sequence of presentations of the $G_n$s, we'll attach to each $n\in\omega$ a Marker-extended version of (that presentation of) $G_n$. Basically, we add a sort $V_n$ of vertices, for each pair $(v,w)\in V_n$ a sort $E_{n,v,w}$ of "edge-witnesses," and a unary relation $U$ holding on infinitely many elements of $E_{n,v,w}$ iff there is an edge from $v$ to $w$ in $G_n$.

The point is that computable presentations of $S(X)$ correspond appropriately to $\Pi_2$ descriptions of the sequence $X$, and so in particular $S(X)$ is computably presentable. Given a copy of $S(X)$, let $R_n$ be the relation on the $V_n$-sort which is described in a $\Pi_2$ way via $U$ above. For any $k$ there is a computable copy of $S(X)$ in which $R_n$ is computable for each $k<n$, but no computable copy of $S(X)$ has each $R_n$ computable simultaneously.

$\endgroup$
3
  • $\begingroup$ @FrançoisG.Dorais Fixed, thanks! $\endgroup$ Commented Oct 3 at 3:49
  • $\begingroup$ Could you clarify precisely what you mean by 'automorphically-fixed`? $\endgroup$ Commented Oct 4 at 0:02
  • $\begingroup$ @FrançoisG.Dorais Fixed by all automorphisms. (Equivalently, "$\mathcal{L}_{\omega_1,\omega}$-definable.") The point is that this is the hypothesis needed to unambiguously make sense of $R^B$ when $B$ is an isomorphic copy of $A$ but we haven't specified an isomorphism $A\cong B$. $\endgroup$ Commented Oct 4 at 0:05

0

You must log in to answer this question.

Browse other questions tagged .