Say that a (countable, computable-language) structure $\mathfrak{A}$ has computable dimension $\omega$ iff there are infinitely many computable copies of $\mathfrak{A}$ up to computable isomorphism. The simplest example of such a structure is probably the linear order $\mathfrak{O}=(\omega;<)$.

Now $\mathfrak{O}$ - and all "natural" such structures that I'm aware of - satisfy a kind of "productivity" condition, where given a computable sequence of computable copies we can computably produce a new computable copy not computably isomorphic to any of the copies in the sequence. On the other hand, there are more artificial structures with computable dimension $\omega$ for which no infinite set of computable copies exists at all, which of course prevents productivity. (See here for details.)

I'm interested in whether a third extreme behavior can occur. Say that a structure $\mathfrak{A}$ is listable iff there is some computable sequence of computable copies of $\mathfrak{A}$ such that every computable copy of $\mathfrak{A}$ is computably isomorphic to one of those copies. Listability clearly contradicts both of the behaviors mentioned in the previous paragraph.

Is there a listable structure with computable dimension $\omega$?

  • $\begingroup$ I believe the tag algebraic-systems would perfectly fit here but unfortunately I believe you wouldn't keep the tag. $\endgroup$ – YCor Nov 29 '20 at 20:37
  • $\begingroup$ @YCor I do dislike that tag, but I agree that granting it in the first place it's appropriate for this question. I'd only remove it if it crowded out a tag I considered more appropriate. Feel free to add it. $\endgroup$ – Noah Schweber Nov 29 '20 at 21:06
  • $\begingroup$ Thanks! I find it useful to gather a certain type of questions about general structures. $\endgroup$ – YCor Nov 29 '20 at 21:14
  • $\begingroup$ Why does listable contradict productivity? If the productive function gave an index from your list, you could use the recursion theorem to contradict it, but what if your productive function gives you a different sort of index? $\endgroup$ – Dan Turetsky Nov 30 '20 at 2:49
  • 1
    $\begingroup$ I don’t know where the “algebraic-systems” tag comes from, but this is nonstandard terminology, and the name of the tag is quite misleading, as in common terminology an “algebraic structure” is one with no relations, only functions. I corrected some of the weird terminology in the tag summary, which wrote “laws” for what algebraists call “operations”, and logicians call “functions”. (This is quite bizarre, actually. Presumably, someone backformed it from the archaic phrase “group law” meaning “a rule that defines a group operation”.) $\endgroup$ – Emil Jeřábek Nov 30 '20 at 11:55

Yes. Hirschfeldt and Khoussainov built such a structure. See the start of section 3, on page 1208. In fact, their listing is injective (into equivalence classes modulo computable isomorphism). Interestingly, they also consider idea of a productive structure, although they call it "effectively infinite computable dimension"; see page 1200.

  • $\begingroup$ Lovely, thanks! There are of course remaining open questions (e.g. behavior on a cone) but this answers the last of the basic questions I had. $\endgroup$ – Noah Schweber Nov 30 '20 at 7:09

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.