Apakah “produktif = dimensi $\omega$"Untuk struktur yang dapat dihitung?

Nov 29 2020

Dalam analogi dengan terminologi untuk set , mengatakan bahwa (dihitung, bahasa dihitung) struktur$\mathfrak{A}$adalah produktif jika ada cara komputasi untuk benar memperluas setiap daftar dihitung dari jenis isomorfisma dihitung salinan dihitung dari$\mathfrak{A}$. Itu adalah,$\mathfrak{A}$ produktif jika ada beberapa fungsi yang dapat dihitung parsial $F$ seperti itu untuk semua $a,b$:

Jika $W_a=\overline{W_b}$, dan setiap elemen $W_a$ adalah indeks untuk salinan yang dapat dihitung dari $\mathfrak{A}$, kemudian $F(a,b)$ didefinisikan dan merupakan indeks untuk salinan yang dapat dihitung $\mathfrak{A}$ tidak dapat dihitung isomorfik ke salah satu salinan dengan indeks dalam $W_a$.

("$W_a=\overline{W_b}$"-bit baru saja mengatakan itu $W_a$ sebenarnya adalah kumpulan nama yang dapat dihitung, bukan hanya ce, untuk salinan $\mathfrak{A}$, dan kami memberikan set ini ke $F$ sebagai himpunan komputasi daripada himpunan ce.)

Ingatlah bahwa dimensi komputasi dari suatu struktur adalah jumlah salinan yang dapat dihitung yang dimilikinya hingga isomorfisme. Jelas setiap struktur produktif harus memiliki salinan yang dapat dihitung (take$W_a=\emptyset$) dan harus memiliki dimensi yang dapat dihitung $\omega$ (pengulangan $F$dengan tepat). Namun kebalikannya tidak jelas bagi saya. Pertanyaanku adalah:

Apakah setiap struktur yang dapat dihitung dengan dimensi yang dapat dihitung $\omega$ produktif?

Semua contoh "alami" yang dapat saya pikirkan dengan mudah terlihat produktif, tetapi saya tidak melihat prinsip yang berlaku umum bekerja di sini. Ada berbagai hasil dalam literatur tentang "rasa" yang serupa seperti karya Montalban tentang permainan salin / diagonalisasi tetapi tidak ada yang saya sadari tampaknya dapat diterapkan secara langsung.

Kecurigaan saya adalah bahwa jawaban atas pertanyaan ini adalah "rapuh" dalam arti ada struktur yang dapat dihitung dengan dimensi komputasi tak terbatas yang tidak produktif, tetapi setiap struktur dikategorikan secara komputasi pada kerucut atau "produktif pada kerucut" dalam arti yang tepat; Hal ini dimotivasi oleh (kesesatan umum dan) kombinasi teorema Goncharov bahwa ada struktur yang dapat dihitung dari dimensi yang dapat dihitung secara ketat antara$1$ dan $\omega$, dan teorema McCoy bahwa setiap struktur dapat dikategorikan secara komputasi pada kerucut atau memiliki dimensi yang dapat dihitung $\omega$ di atas kerucut.

Jawaban

2 DanTuretsky Nov 29 2020 at 13:32

Jawaban atas jawaban pertama Anda adalah tidak.

Jawaban saya didasarkan pada konstruksi saya, tetapi mungkin ada pendekatan yang lebih sederhana. Di dalamnya, Anda mengambil pohon yang dapat dihitung$\omega^{<\omega}$ dan dapatkan a $\Delta^0_3$transformasi pohon dan struktur kategorikal yang dapat dihitung sedemikian rupa sehingga automorfisme nontrivial pada dasarnya adalah jalur melalui pohon yang diubah. Jika pohon awal Anda tidak memiliki$\Delta^0_3$paths, dan Anda kemudian menandai elemen tertentu dari struktur dengan konstanta, salinan isomorfisma computable modulo struktur yang diperluas sesuai dengan himpunan bagian hingga dari node yang dapat diperpanjang dengan tinggi 1 di pohon. Jika Anda memiliki fungsi produktif seperti yang Anda gambarkan, ini akan memungkinkan Anda menghitung kumpulan node yang dapat diperpanjang yang tak terbatas (di pohon yang ditransformasi, dari mana Anda dapat kembali ke pohon asli melalui$\Delta^0_3$peta). Jadi jika Anda memulai dengan pohon dengan banyak simpul tak terhingga dengan tinggi 1, tapi tidak$\Delta^0_3$ set mereka, itu akan memiliki dimensi $\omega$ tapi tidak produktif.

Saya berbagi intuisi Anda bahwa perilaku ini harus menghilang dalam bentuk kerucut.