Teorema kelengkapan aritmetika
Dalam makalah Kikuchi, kompleksitas Kolmogorov dan teorema ketidaklengkapan kedua ia menyatakan "teorema kelengkapan aritmetika" sebagai berikut:
Membiarkan $T$ menjadi teori aksiomatizable rekursif dalam suatu bahasa $\mathcal{L}$, $C$ menjadi satu set konstanta baru dan $\overline{\mathcal{L}}=\mathcal{L}\cup C$. Kami mengatakan formula$\phi(x)$ di $\mathcal{L}_{A}$ mendefinisikan model $T$ dalam sebuah teori $S$ di $\mathcal{L}_{A}$ jika kita bisa membuktikannya $S$ bahwa set
$$ \{ \sigma : \text{$\ sigma$ is a sentence in $\ overline {\ mathcal {L}}$ that satisfies $\ phi (\ ulcorner \ sigma \ urcorner)$} \} $$
membentuk diagram dasar dari model $T$ dengan alam semesta dari $C$.
Teorema 4.1. (Teorema kelengkapan aritmetika). Ada rumusnya$\text{Tr}_{T}({\ulcorner}x{\urcorner})$ di $\mathcal{L}_{A}$ [bahasa aritmatika] yang mendefinisikan model $T$ di $\text{PA} + \text{Con}(T)$ , dimana $\text{Con}(T)$ adalah kalimat dalam $\mathcal{L}_{A}$ itu berarti $T$ konsisten.
Ada beberapa aspek dari teorema ini yang tidak saya mengerti:
Gagasan tentang rumus yang mendefinisikan model $T$ di $\text{PA} + \text{Con}(T)$ melibatkan set $ \{ \sigma : \text{$\ sigma$ is a sentence in $\ overline {\ mathcal {L}}$ that satisfies $\ phi (\ ulcorner \ sigma \ urcorner)$} \} $. Saya tidak tahu bagaimana memformalkannya$\text{PA}$, apalagi membuktikan sesuatu tentang itu.
Hal yang sama dengan pembicaraan tentang model $T$. Mengatakan$T = \text{ZFC}$, lalu bagaimana Anda bisa menyatakan dalam bahasa aritmatika yang ada modelnya $T$ dengan properti ini dan itu (diagram dasarnya adalah himpunan di atas dan alam semesta)?
Jenis pertanyaan yang berbeda: apa gunanya teorema ini (secara umum, di luar makalah yang disebutkan)? Mengapa disebut teorema kelengkapan aritmetika?
Jawaban
Kembali: $(1)$, ada lebih sedikit di sini daripada yang terlihat. Poin kuncinya adalah kita bisa membuat formula$\theta$ yang mendefinisikan himpunan bilangan Godel $\overline{\mathcal{L}}$-sentences; dengan ini di tangan, kami hanya melihat$$S=\{x: \theta(x)\wedge\phi(x)\}.$$ Ini bisa didefinisikan dengan sangat membosankan.
Sekarang saat kita mengatakan itu $S$ adalah diagram dasar dari beberapa struktur dengan domain $C$, maksud kami itu $S$ memenuhi properti biasa dari diagram dasar - dan karena ini adalah properti sintaksis, kita dapat melalui penomoran Godel menyatakan bahwa $S$memiliki atau tidak memilikinya. Misalnya, kami menginginkan masing-masing dari yang berikut:
Jika $\ulcorner\sigma_0\urcorner$, $\ulcorner\sigma_1\urcorner\in S$ kemudian $\ulcorner\sigma_0\wedge\sigma_1\urcorner\in S$.
Jika $\ulcorner \exists x\sigma(x)\urcorner\in S$ lalu untuk beberapa $c\in C$ kita punya $\ulcorner\sigma(c)\urcorner\in S$. (Ini membahas "dengan alam semesta dari$C$"bit.)
$\ulcorner\perp\urcorner\not\in S$.
Sedikit lebih akurat, kami memiliki fungsi rekursif primitif yang sesuai dengan misalnya konjungsi dan untuk kuantifikasi eksistensial sehubungan dengan beberapa variabel tetap, dan dua poin pertama di atas berjumlah untuk kondisi penutupan / keberadaan yang sesuai di $S$sehubungan dengan fungsi-fungsi ini. Poin peluru ketiga sementara itu mencegah hal sepele.
Pada dasarnya, intinya adalah bahwa properti menjadi diagram dasar dari beberapa struktur dengan domain $\mathbb{N}$ adalah urutan pertama yang dapat diekspresikan (karena ini berarti "kondisi penutupan / keberadaan / ketiadaan lokal" sesuai yang disebutkan di atas).
Kembali: $(2)$, secara intuitif intinya adalah bahwa kita tidak berbicara tentang model sewenang-wenang misalnya $\mathsf{ZFC}$, tetapi hanya yang memiliki domain $\mathbb{N}$. Struktur dengan domain$\mathbb{N}$ sepenuhnya dijelaskan oleh satu set bilangan asli $X$, dan "$X$ adalah diagram atom dari model $\mathsf{ZFC}$"sesuai dengan urutan pertama yang diekspresikan di atas: kami hanya mengatakan"$X$ memiliki properti sintaksis dasar di atas, dan masing-masing $\mathsf{ZFC}$-axiom masuk $X$. "
Saya pikir ini mungkin dibuat lebih misterius karena biasanya kita memikirkan model $\mathsf{ZFC}$karena sangat rumit dan jelas tidak memiliki domain$\mathbb{N}$. Tapi per ke bawah Lowenheim-Skolem,$\mathsf{ZFC}$(dengan asumsi itu konsisten sama sekali) juga memiliki banyak model dengan domain$\mathbb{N}$. Ini adalah model yang dapat kami pertimbangkan dalam pendekatan ini.
Kembali: $(3)$, intinya adalah pengungkapan yang biasa dari teorema kelengkapan
setiap teori yang konsisten memiliki model
benar-benar gila dalam konteks aritmatika. Pada dasarnya, kita hanya dapat secara langsung berbicara tentang himpunan hingga dalam bahasa aritmatika, jadi jika kita secara naif "frase aritmatika" kalimat "Aritmatika Presburger tidak memiliki model" kita mendapatkan sesuatu yang benar.
(Lihat misalnya interpretasi Ackermann . Kita dapat lulus dari (katakanlah)$\mathsf{PA}$ ke teori himpunan yang setara secara tepat, tetapi teori itu membuktikan "Setiap himpunan terbatas.")
Jadi, jika kita ingin beberapa versi teorema kelengkapan dipegang dalam teori aritmatika, "model" -nya harus terdiri dari hubungan di seluruh alam semesta; dan tentu saja mereka harus terdiri dari hubungan yang dapat didefinisikan , karena kita tidak dapat berbicara tentang hubungan yang tidak dapat ditentukan secara internal.
Pilihan lain adalah menggunakan ekstensi konservatif yang dapat berbicara tentang himpunan tak terbatas secara langsung; ini adalah contoh pendekatan yang diambil di sini . Dalam semua konteks yang saya mainkan dengan pendekatan ini bekerja dan jadi saya biasanya lebih suka itu. Yang mengatakan,$(i)$ jika saya ingat dengan benar, ada situasi di mana pendekatan ini menjengkelkan atau mengaburkan informasi berharga (menurut saya ini terjadi dengan teori aritmatika yang sangat lemah) dan $(ii)$ Fakta bahwa kita bisa mendapatkan teorema kelengkapan hanya dalam bahasa aritmatika orde pertama adalah hal yang menarik.