Apakah ada struktur "yang dapat didaftar" dari dimensi yang dapat dihitung $\omega$?

Question

Katakanlah bahwa (dihitung, dihitung-bahasa) struktur$\mathfrak{A}$memiliki dimensi yang dapat dihitung$\omega$ jika ada banyak salinan yang dapat dihitung dari $\mathfrak{A}$hingga isomorfisme yang dapat dihitung. Contoh paling sederhana dari struktur semacam itu mungkin adalah orde linier$\mathfrak{O}=(\omega;<)$.

Sekarang $\mathfrak{O}$- dan semua struktur "alami" yang saya ketahui - memenuhi semacam kondisi "produktivitas", di mana dengan urutan yang dapat dihitung dari salinan yang dapat dihitung, kita dapat secara komputasi menghasilkan salinan baru yang dapat dihitung yang tidak bersifat isomorfik secara komputasi untuk salinan mana pun di urutan. Di sisi lain, terdapat lebih banyak struktur artifisial dengan dimensi yang dapat dihitung$\omega$yang tidak ada sama sekali kumpulan salinan yang dapat dihitung, yang tentu saja mencegah produktivitas. (Lihat di sini untuk detailnya.)

Saya tertarik apakah perilaku ekstrim ketiga dapat terjadi. Katakan itu sebuah struktur$\mathfrak{A}$dapat didaftar jika ada beberapa urutan yang dapat dihitung dari salinan yang dapat dihitung$\mathfrak{A}$ sedemikian rupa sehingga setiap salinan yang dapat dihitung $\mathfrak{A}$secara komputasi isomorfik untuk salah satu salinan tersebut. Sifat mudah mendengar jelas-jelas bertentangan dengan kedua perilaku yang disebutkan di paragraf sebelumnya.

Apakah ada struktur yang dapat didaftar dengan dimensi yang dapat dihitung $\omega$?

Answer 1

Iya. Hirschfeldt dan Khoussainov membangun struktur seperti itu. Lihat awal bagian 3, di halaman 1208. Nyatanya, daftar mereka adalah injektif (ke dalam kelas ekivalen modulo computable isomorphism). Menariknya, mereka juga mempertimbangkan gagasan tentang struktur produktif, meskipun mereka menyebutnya "dimensi komputasi tak terbatas yang efektif"; lihat halaman 1200.