Definisi ordinal dalam berbagai tanda tangan
Baru-baru ini, saya telah mempelajari seperti apa himpunan bagian yang dapat didefinisikan dari ordinal yang dapat dihitung dari perspektif logika orde pertama tanpa tulang (bukan teori himpunan) yang dilengkapi dengan berbagai cara untuk "mengakses" struktur ordinal.
Misalnya, kita mungkin memiliki tanda tangan yang hanya terdiri dari simbol relasional 2-arity $S$ yang kami tafsirkan dalam sebuah struktur $\mathcal{A}$ dengan set yang mendasari $\omega_1$ sebagai set $(\alpha,\beta)$ seperti yang $\beta$ adalah penerus $\alpha$. Kami kemudian dapat mengajukan pertanyaan tentang subset yang mana dari$\mathcal{A}$ dapat ditentukan oleh kalimat logika urutan pertama dengan tanda tangan ini, dengan subset $S\subset\mathcal{A}$ dianggap dapat didefinisikan jika ada kalimat logika urutan pertama $\phi(x)$ yang set penugasannya memuaskan $x$ aku s $S$. Dalam contoh kita, kita dapat mendefinisikan himpunan semua ordinal penerus yang dapat dihitung melalui rumus$\exists y:S(y,x)$.
Kami juga dapat mengajukan pertanyaan seperti "apa ordinal terkecil $\alpha$ seperti yang $\alpha$ tidak dapat didefinisikan dalam arti itu $\{\alpha\}$ tidak dapat didefinisikan "dan semacamnya. Dalam contoh di atas, jelas terlihat bahwa sebenarnya tidak ada ordinal yang dapat ditentukan, jadi ordinal terkecil yang tidak dapat ditentukan adalah nol. Saya sangat tertarik pada bagaimana ordinal terkecil yang tidak dapat ditentukan tumbuh karena kita memiliki tanda tangan yang lebih kuat dan lebih kuat. Misalnya, saya sudah bisa meyakinkan diri saya itu dengan tanda tangan $\{<\}$ dengan interpretasi yang jelas di $\omega_1$ sebagai "kurang dari relasi", ordinal terkecil yang tidak dapat ditentukan adalah $\omega^\omega$ (meskipun saya belum menuliskan argumen saya secara formal).
Pertanyaan saya adalah: apakah ada yang mempelajari pertanyaan seperti ini? Apakah diketahui ordinal terkecil yang dapat didefinisikan untuk berbagai tanda tangan lainnya, seperti$\{ADD(x,y,z)\}$ yang benar untuk semua $x,y,z$ maka $x+y=z$, atau bahkan tanda tangan lain dengan perkalian, eksponensiasi, fungsi veblen, atau lebih? Apakah ada generalisasi yang diketahui dari ide-ide ini? Setiap bantuan atau literatur terkait akan dihargai.
Jawaban
Saya tidak memiliki reputasi yang cukup untuk menambahkan komentar. Makalah berikut ini semoga bermanfaat untuk anda. Ini berisi hasil yang memperluas karya Tarski, Mostowski, dan Doner, serta beberapa tinjauan dan referensi sejarah yang sangat bagus.
Buchi, Siefkes - Ekstensi Lengkap dari Teori Orde Kedua Monadic Ordinals Terhitung.
Logika orde dua monadik lemah sudah muncul dalam karya asli Ehrenfeucht. Bahkan jika Anda secara eksklusif tertarik pada hasil urutan pertama, logika urutan kedua monadik (lemah) dapat berperan.
Misalnya teori urutan pertama penjumlahan ordinal bertepatan dengan teori orde pertama penjumlahan ordinal $\omega^{\omega^{\omega}}$ (oleh Ehrenfeuct), sementara $(\omega^{\omega^{\omega}},+)$ adalah pengurangan kekuatan umum dari $(\omega,+)$ dengan 'eksponen' menjadi versi urutan kedua monadik lemah dari $(\omega^{\omega},<)$(Teorema Feferman-Vaught adalah alat yang tepat untuk memahami ini). Untuk lebih jelasnya ada Thomas - Ehrenfeucht, Vaught, dan decidability of the weak monadic theory of successor , detailnya di sini semuanya benar tetapi menurut saya kesimpulannya memiliki beberapa masalah.
Ada juga pekerjaan yang lebih baru di sisi automata seperti Cachat - Tree Automata Make Ordinal Theory Easy. Saya tidak tahu apa-apa tentang konten ini, tetapi jika Anda ingin gambaran menyeluruh tentang area tersebut, ini mungkin titik awal.