Apakah teori orde pertama dari struktur hingga telah membatasi peringkat quantifier?

Biarkan menjadi struktur berhingga apa pun. Apakah teori urutan pertama telah membatasi peringkat quantifier, dalam arti ada sedemikian rupa sehingga untuk semua dengan ada dengan dan ? $\mathfrak{A}$ $\mathfrak{T} := \mathfrak{TH}(\mathfrak{A})$ $q\in\mathbb{N}$ $\varphi\in\mathfrak{T}$ $qr(\varphi) > q$ $\varphi'\in\mathfrak{T}$ $qr(\varphi')\leq q$ $\varphi'\equiv\varphi$

co.combinatorics lo.logic relational-structures D. Rusin
sumber

Bukankah ini pertanyaan untuk Mathoverflow daripada teori CS?

Andrej Bauer

@Andrej, teori model hingga dan kompleksitas deskriptif juga dianggap sebagai bagian dari TCS.

Kaveh

Luar biasa, jadi seperti yang pernah dikatakan Bob Harper: matematika adalah kasus khusus ilmu komputer.

Andrej Bauer

Ilmu komputer juga merupakan kasus khusus matematika, dan keduanya juga merupakan kasus logika khusus, dan sebaliknya.

fhyve

Jawaban:

Teori dari setiap struktur hingga adalah model yang lengkap. Bahkan, mudah untuk melihat bahwa rumus apa pun setara dengan rumus eksistensial dengan satu quantifier per setiap elemen struktur, setelah itu semua quantifiers dari rumus asli dapat disimulasikan oleh konjungsi dan disjungsi. Secara khusus, jumlah pengukur (karenanya peringkat pengukur) dibatasi oleh ukuran struktur.

Emil Jeřábek
sumber

Sebenarnya, diperlukan satu penjumlahan universal tambahan, yang memungkinkan untuk menyatakan bahwa tidak ada elemen lebih lanjut. Dalam semua jawaban ada satu asumsi yang harus dibuat eksplisit: keberadaan o kualitas, yaitu, bahwa x = y adalah rumus atom yang diperbolehkan.

Thomas S

Tidak diperlukan kuantifier tambahan. Ingatlah bahwa kita tidak mencoba untuk melakukan aksioma teori struktur, tetapi untuk menemukan formula yang setara dengan modulo teori tertentu. Dan kehadiran kesetaraan adalah standar universal untuk logika orde pertama klasik. Its tidak adanya perlu dinyatakan.

Emil Jeřábek

Ah. Kamu benar. "Teori Modulo". Mengenai kesetaraan: karena kami mencoba menjelaskan hal-hal mudah kepada orang-orang dari luar Logika, tidak ada salahnya untuk membuat kerangka kerja eksplisit. Satu lagi komentar: mengganti pembilang dengan konjungsi dan disjungsi sangat baik. Namun, ada alternatif: karena rumus dengan, katakanlah, variabel bebas mendefinisikan hubungan m-ary dari A, rumus baru dapat, setelah menebak semua elemen dan memeriksa yang mana (modulo automorphisms), juga secara eksplisit "menghitung" semua tuple, di mana rumus lama menghasilkan "true".

Thomas S

Untuk membuat apa yang dikatakan Emil sedikit lebih konkret: pertimbangkan rumus yang menyatakan keberadaan k objek yang berbeda. Itu menunjukkan bahwa kita membutuhkan jumlah bilangan tak terbatas.

Sekarang Anda memiliki rumus dengan q quantifiers dan model Anda memiliki objek k di dalamnya, Anda dapat mengekspresikan rumus dengan menyatakan bahwa ada objek yang berbeda dan hubungan di antara mereka dapat dinyatakan sebagai CNF.

Kaveh
sumber