Existe uma estrutura "listável" de dimensão computável $\omega$?

Question

Digamos que uma (computável-language contável,) estrutura$\mathfrak{A}$tem dimensão computável$\omega$ se houver infinitas cópias computáveis ​​de $\mathfrak{A}$até isomorfismo computável. O exemplo mais simples de tal estrutura é provavelmente a ordem linear$\mathfrak{O}=(\omega;<)$.

Agora $\mathfrak{O}$- e todas essas estruturas "naturais" que eu conheço - satisfazem um tipo de condição de "produtividade", onde dada uma sequência computável de cópias computáveis, podemos produzir computavelmente uma nova cópia computável não isomórfica computacionalmente a qualquer uma das cópias no seqüência. Por outro lado, existem mais estruturas artificiais com dimensão computável$\omega$para o qual não existe nenhum conjunto infinito de cópias computáveis, o que obviamente impede a produtividade. (Veja aqui os detalhes.)

Estou interessado em saber se um terceiro comportamento extremo pode ocorrer. Diga que uma estrutura$\mathfrak{A}$é listável se houver alguma sequência computável de cópias computáveis ​​de$\mathfrak{A}$ de modo que cada cópia computável de $\mathfrak{A}$é computavelmente isomórfico a uma dessas cópias. Listabilidade contradiz claramente ambos os comportamentos mencionados no parágrafo anterior.

Existe uma estrutura listável com dimensão computável $\omega$?

Answer 1

Sim. Hirschfeldt e Khoussainov construíram essa estrutura. Consulte o início da seção 3, na página 1208. Na verdade, sua listagem é injetiva (em classes de equivalência por módulo de isomorfismo computável). Curiosamente, eles também consideram a ideia de uma estrutura produtiva, embora a chamem de "dimensão computável efetivamente infinita"; consulte a página 1200.