“Produtivo = dimensão $\omega$”Para estruturas computáveis?
Em analogia com a terminologia para conjuntos , dizer que um (linguagem computável contável,) estrutura$\mathfrak{A}$é produtivo se houver uma maneira computável de expandir adequadamente qualquer lista computável de tipos de isomorfismo computável de cópias computáveis de$\mathfrak{A}$. Isso é,$\mathfrak{A}$ é produtivo se houver alguma função computável parcial $F$ tal que para todos $a,b$:
E se $W_a=\overline{W_b}$, e cada elemento de $W_a$ é um índice para uma cópia computável de $\mathfrak{A}$, então $F(a,b)$ é definido e é um índice para uma cópia computável de $\mathfrak{A}$ não isomórfico computacionalmente a qualquer uma das cópias com índices em $W_a$.
(O "$W_a=\overline{W_b}$"-bita apenas diz isso $W_a$ é na verdade um conjunto computável, não apenas ce, de nomes para cópias de $\mathfrak{A}$, e estamos dando este conjunto para $F$ como um conjunto computável em vez de um conjunto CE.)
Lembre-se de que a dimensão computável de uma estrutura é o número de cópias computáveis que ela possui até o isomorfismo. Obviamente, qualquer estrutura produtiva deve ter uma cópia computável (pegue$W_a=\emptyset$) e deve ter dimensão computável $\omega$ (iterar $F$adequadamente). No entanto, o contrário não está claro para mim. Minha pergunta é:
É toda estrutura computável com dimensão computável $\omega$ produtivo?
Todos os exemplos "naturais" em que posso pensar são facilmente considerados produtivos, mas não vejo nenhum princípio de aplicação geral em ação aqui. Existem vários resultados na literatura de "sabor" semelhante, como o trabalho de Montalban sobre jogos de copiar / diagonalizar, mas nenhum que eu saiba parece diretamente aplicável.
Minha suspeita é que a resposta a esta pergunta é "frágil" no sentido de que há uma estrutura computável com dimensão computável infinita que não é produtiva, mas que toda estrutura é computavelmente categórica em um cone ou "produtiva em um cone" no sentido apropriado; isto é motivado pela (perversidade geral e) a combinação do teorema de Goncharov de que existem estruturas computáveis de dimensão computável estritamente entre$1$ e $\omega$, e o teorema de McCoy de que toda estrutura é computavelmente categórica em um cone ou tem dimensão computável $\omega$ em um cone.
Respostas
A resposta à sua primeira resposta é não.
Minha resposta é baseada em uma construção minha, mas pode haver uma abordagem mais simples. Nisso, você pega uma árvore computável em$\omega^{<\omega}$ e obter um $\Delta^0_3$transformação da árvore e uma estrutura categórica computacionalmente tal que automorfismos não triviais da estrutura são basicamente caminhos através da árvore transformada. Se sua árvore inicial não tem$\Delta^0_3$caminhos, e então você marca um elemento específico da estrutura com uma constante, as cópias do isomorfismo computável do módulo da estrutura expandida correspondem a subconjuntos finitos de nós extensíveis de altura 1 na árvore. Se você tivesse uma função produtiva como descreve, permitiria enumerar um conjunto infinito de nós extensíveis (na árvore transformada, a partir da qual você poderia voltar à árvore original por meio de um$\Delta^0_3$mapa). Portanto, se você começar com uma árvore com um número infinito de nós extensíveis de altura 1, mas não$\Delta^0_3$ conjunto deles, teria dimensão $\omega$ mas não seja produtivo.
Compartilho sua intuição de que esse comportamento deve desaparecer em um cone.