4
$\begingroup$

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$?

Improve this question
$\endgroup$
8
  • $\begingroup$ I believe the tag algebraic-systems would perfectly fit here but unfortunately I believe you wouldn't keep the tag. $\endgroup$
    – YCor
    Commented Nov 29, 2020 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
    Commented Nov 29, 2020 at 21:06
  • $\begingroup$ Thanks! I find it useful to gather a certain type of questions about general structures. $\endgroup$
    – YCor
    Commented Nov 29, 2020 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
    Commented Nov 30, 2020 at 2:49
  • 2
    $\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
    Commented Nov 30, 2020 at 11:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Nov 30, 2020 at 7:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .