3
$\begingroup$

In analogy with the terminology for sets, say that a (countable, computable language) structure $\mathfrak{A}$ is productive if there is a computable way to properly expand any computable list of computable isomorphism types of computable copies of $\mathfrak{A}$. That is, $\mathfrak{A}$ is productive iff there is some partial computable function $F$ such that for all $a,b$:

If $W_a=\overline{W_b}$, and every element of $W_a$ is an index for a computable copy of $\mathfrak{A}$, then $F(a,b)$ is defined and is an index for a computable copy of $\mathfrak{A}$ not computably isomorphic to any of the copies with indices in $W_a$.

(The "$W_a=\overline{W_b}$"-bit just says that $W_a$ is in fact a computable, not just c.e., set of names for copies of $\mathfrak{A}$, and we're giving this set to $F$ as a computable set rather than a c.e. set.)

Recall that the computable dimension of a structure is the number of computable copies it has up to isomorphism. Obviously any productive structure must have a computable copy (take $W_a=\emptyset$) and must have computable dimension $\omega$ (iterate $F$ appropriately). However the converse is not clear to me. My question is:

Is every computable structure with computable dimension $\omega$ productive?

All the "natural" examples I can think of are easily seen to be productive, but I don't see any generally-applicable principle at work here. There are various results in the literature of similar "flavor" such as Montalban's work on copy/diagonalize games but none that I'm aware of seem directly applicable.

My suspicion is that the answer to this question is "fragile" in the sense that there is a computable structure with infinite computable dimension which is non-productive, but that every structure is either computably categorical on a cone or "productive on a cone" in the appropriate sense; this is motivated by (general perversity and) the combination of Goncharov's theorem that there are computable structures of computable dimension strictly between $1$ and $\omega$, and McCoy's theorem that every structure is either computably categorical on a cone or has computable dimension $\omega$ on a cone.

$\endgroup$
3
  • $\begingroup$ As a quick point of clarification re: the last sentence, McCoy didn't actually phrase his result that way but what I've written is a quick corollary of his argument via Martin's cone theorem. I don't know who first observed this corollary, I think it's either McCoy elsewhere or folklore, but please let me know if it has a separate attribution. $\endgroup$ – Noah Schweber Nov 29 '20 at 3:18
  • $\begingroup$ The words "not computably isomorphic" made me wonder whether it is allowed for them to be non-computably isomorphic, and whether "computably non-isomorphic" should be used, if this makes sense at all. $\endgroup$ – მამუკა ჯიბლაძე Nov 29 '20 at 6:50
  • 1
    $\begingroup$ @მამუკაჯიბლაძე They do have to be classically isomorphic, since they're copies of $\mathfrak{A}$. I don't know what "computably non-isomorphic" would mean, it sounds stronger than merely "not computably isomorphic." $\endgroup$ – Noah Schweber Nov 29 '20 at 6:51
2
$\begingroup$

The answer to your first answer is no.

My answer is based on a construction of mine, but there may be a simpler approach. In that, you take a computable tree in $\omega^{<\omega}$ and obtain a $\Delta^0_3$ transformation of the tree and a computably categorical structure such that nontrivial automorphisms of the structure are basically paths through the transformed tree. If your starting tree has no $\Delta^0_3$ paths, and you then tag a particular element of the structure with a constant, the copies of the expanded structure modulo computable isomorphism correspond to finite subsets of extendible nodes of height 1 in the tree. If you had a productive function as you describe, it would let you enumerate an infinite set of extendible nodes (in the transformed tree, from which you could get back to the original tree via a $\Delta^0_3$ map). So if you start with a tree with infinitely many extendible nodes of height 1, but no $\Delta^0_3$ set of them, it would have dimension $\omega$ but not be productive.

I share your intuition that this behavior should disappear on a cone.

$\endgroup$
2
  • $\begingroup$ That's gorgeous, thanks! (I'll accept it when I've had time to read it when I'm not about to sleep.) Incidentally, this raises a followup question: is there a computable-dimension-$\omega$ structure with a computable enumeration of representatives of its computable isomorphism types (that is, a computable sequence $(n_i)_{i\in\omega}$ such that each computable copy is computably isomorphic to a structure with index $n_i$ for some $i$)? Such a structure would also be non-productive, but very differently from your example. $\endgroup$ – Noah Schweber Nov 29 '20 at 6:44
  • $\begingroup$ I've asked my comment as a follow-up question. $\endgroup$ – Noah Schweber Nov 29 '20 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.