Memperbaiki poin dalam komputasi dan logika

Pertanyaan ini juga telah diposting di Math.SE,

/math/1002540/fixed-points-in-computability-nd-logic

Saya harap tidak apa-apa untuk memposting di sini. Jika tidak, atau terlalu mendasar untuk CS.SE, tolong beri tahu saya dan saya akan menghapusnya.

Saya ingin lebih memahami hubungan antara teorema titik tetap dalam logika dan -calculus.$\lambda$

Latar Belakang

1) Peran poin-poin tertentu dalam ketidaklengkapan & ketidaktentuan kebenaran

Sejauh yang saya mengerti, terlepas dari ide dasar logika internalisasi, kunci untuk kedua bukti dari Tarski yang tidak dapat dibuktikan kebenarannya dan teorema ketidaklengkapan Goedel adalah teorema titik tetap logis berikut , yang hidup dalam metatori finitistik konstruktif, konstruktif (saya berharap formulasi ok, tolong perbaiki saya jika ada yang tidak benar atau tidak tepat):

Keberadaan titik-titik tetap dalam logika

Misalkan adalah teori yang cukup ekspresif, enumerable berulang atas bahasa , dan biarkan menjadi pengkodean -rumus dalam , yaitu , suatu algoritma yang mengubah sewenang-wenang -formulas \ varphi menjadi {\ mathcal L} -formula dengan satu variabel bebas {\ mathbf C} (\ varphi) (v) , sedemikian rupa sehingga untuk setiap {\ mathcal L } -formula \ varphi kami memiliki {\ mathscr T} \ vdash \ ada! v: {\ mathbf C} (\ varphi) (v) .L C L T L φ L C (φ)(v) L φ T ⊢∃! v: C (φ)(v${\mathscr T}$${\mathcal L}$${\mathbf C}$${\mathcal L}$${\mathscr T}$${\mathcal L}$$\varphi$${\mathcal L}$${\mathbf C}(\varphi)(v)$${\mathcal L}$$\varphi$${\mathscr T}\vdash \exists! v: {\mathbf C}(\varphi)(v)$

Kemudian ada algoritma mengubah terbentuk dengan baik dalam satu variabel bebas menjadi terbentuk dengan baik , sehingga untuk setiap di satu variabel gratis kita memiliki yang, menafsirkan sebagai simbol fungsi yang ditentukan , mungkin juga ditulis lebih kompak sebagaiL L L ϕ T ⊢ Y (ϕ)⇔∃v: C ( Y (ϕ))(v)∧ϕ(v), C ⌈-⌉ T ⊢ Y (ϕ)⇔ϕ(⌈ Y (ϕ)⌉)${\mathbf Y}$${\mathcal L}$${\mathcal L}$${\mathcal L}$$\phi$

$${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \exists v: {\mathbf C}({\mathbf Y}(\phi))(v)\wedge \phi(v),$$ ${\mathbf C}$$\lceil -\rceil$ $${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \phi(\lceil{\mathbf Y}(\phi)\rceil).$$

Dengan kata lain, adalah algoritme untuk konstruksi titik-titik tetap sehubungan dengan kesetaraan formula-variabel .T ${\mathbf Y}$${\mathscr T}$${\mathcal L}$

Ini memiliki setidaknya dua aplikasi:

• Menerapkannya ke predikat menyatakan " mengkodekan kalimat yang, ketika dipakai dengan pengkodeannya sendiri, tidak dapat dibuktikan." menghasilkan formalisasi "Kalimat ini tidak dapat dibuktikan" yang terletak di jantung argumen Goedel.$\phi(v)$$v$

• Menerapkannya pada untuk hukuman yang sewenang-wenang menghasilkan Tarski yang tidak dapat dibuktikan kebenarannya.$\neg\phi$$\phi$

2) Memperbaiki poin dalam -calculus yang tidak diketik$\lambda$

Dalam untyped -calculus, konstruksi titik-titik tetap penting dalam realisasi fungsi rekursif.$\lambda$

Keberadaan titik tetap di -calculus:$\lambda$

Ada kombinator titik tetap , yaitu $\lambda$ -term $Y$ sedemikian rupa sehingga untuk setiap $\lambda$ -term $f$ , kita memiliki

$$f(Y f)\sim_{\alpha\beta} Yf.$$

Pengamatan

Yang membuat saya terpana adalah kombinator titik tetap dalam λ -kalkulus secara langsung mencerminkan, dengan cara yang sangat bersih dan nonteknis, bukti umum dari teorema titik tetap logis:$\lambda f.(\lambda x. f(x x))(\lambda x. f(x x))$$\lambda$

Secara sangat kasar , diberikan rumus , seseorang menganggap formalisasi φ ( v ) dari pernyataan " v mengkode kalimat yang, ketika dipakai dengan dirinya sendiri, memenuhi ϕ ", dan menempatkan A ( ϕ ) : = φ ( ⌈ φ ⌉ ) . Kalimat φ ( v ) seperti λ x . f ( x x ) , dan φ ( ⌈ φ ⌉ ) sesuai dengan$\varphi$$\varphi(v)$$v$$\phi$${\mathbf A}(\phi) := \varphi(\lceil\varphi\rceil)$$\varphi(v)$$\lambda x. f(x x)$$\varphi(\lceil\varphi\rceil)$ .$(\lambda x. f(x x))(\lambda x. f(x x))$

Pertanyaan

Terlepas dari ide yang diuraikan dengan cepat, saya menemukan bukti teorema titik tetap logis cukup teknis dan sulit untuk dilakukan dalam semua detail; Kunen melakukannya misalnya dalam Teorema 14.2 dari bukunya 'Set Theory'. Di sisi lain, -combinator dalam λ -calculus sangat sederhana dan sifat-sifatnya mudah diverifikasi.$Y$$\lambda$

Apakah teorema titik tetap logis mengikuti secara ketat dari kombinator titik tetap dalam -kalkulus?$\lambda$

Misalnya, dapatkah salah satu model rumus kalkulus oleh L- hingga kesetaraan logis, sehingga interpretasi dari setiap combinator titik tetap memberikan algoritma seperti yang dijelaskan dalam teorema titik tetap logis?$\lambda$${\mathcal L}$

Edit

Mengingat banyak contoh lain dari argumen diagonalisasi yang sama yang dijelaskan dalam jawaban Martin dan Cody, orang harus mengulangi pertanyaan itu:

Apakah ada generalisasi umum dari argumen diagonalisasi mengikuti prinsip yang diungkapkan dalam -combinator? λ f . ( λ x . f ( x x ) ) ( λ x . f ( x x ) $Y$

$$\lambda f.(\lambda x. f(xx))(\lambda x.f(xx))$$

Jika saya memahaminya dengan benar satu proposal adalah Teorema Titik Tetap Lawvere , lihat di bawah. Sayangnya, saya tidak bisa mengikuti spesialisasi yang relevan di salah satu artikel yang dikutip Martin dalam jawabannya, dan saya akan senang jika ada yang bisa menjelaskannya. Pertama, untuk kelengkapan:

Teorema Titik Tetap Lawvere

Biarkan menjadi kategori dengan produk hingga dan φ : A × A → Y sedemikian rupa sehingga untuk setiap morfisme f : A → Y dalam C ada beberapa ⌈ f ⌉ : 1 → A sedemikian rupa sehingga untuk semua titik p : 1 → A yang memiliki 1 p → A f → Y = 1 p → A ⟨ ⌈ f ⌉ , id ${\mathscr C}$$\varphi: A\times A\to Y$$f: A\to Y$${\mathscr C}$$\lceil f\rceil: 1\to A$$p: 1\to A$

$$1\xrightarrow{p} A\xrightarrow{\ f\ } Y\ \ =\ \ 1\xrightarrow{p} A\xrightarrow{\langle \lceil f\rceil,\text{id}_A\rangle} A\times A\xrightarrow{\varphi} Y.$$

Kemudian untuk setiap endomorfisma , menempatkan f : = A delta → A × A φ → Y g → Y , setiap pilihan ⌈ f ⌉ menimbulkan titik tetap g , yaitu 1 ⟨ ⌈ f ⌉ , ⌈ f ⌉ ⟩ → A × A φ → Y $g: Y\to Y$

$$f\ :=\ A\xrightarrow{\Delta} A\times A\xrightarrow{\varphi} Y\xrightarrow{g} Y,$$ $\lceil f\rceil$$g$ $$1\xrightarrow{\langle\lceil f\rceil,\lceil f\rceil\rangle} A\times A\xrightarrow{\varphi} Y.$$

Ini adalah pernyataan dalam teori urutan pertama (intuitionistic) kategori dengan produk yang terbatas dan karenanya berlaku untuk model apa pun dari yang terakhir.

Sebagai contoh , mengambil seluruh himpunan teoretis himpunan sebagai domain wacana memberikan paradoks Russel (mengambil himpunan set hipotetis, Y : = Ω : = { 0 , 1 } dan ρ : A × A → Ω the ∈ -predicate) dan teorema Cantor (mengambil A setiap set dan ρ : A × A → ohm sesuai dengan hipotesis surjection A → ohm $A$$Y := \Omega := \{0,1\}$$\rho: A\times A\to\Omega$$\in$$A$$\rho: A\times A\to \Omega$$A\to\Omega^A$). Selanjutnya, terjemahan bukti Teorema Lawvere memberikan argumen diagonal yang biasa.

Masalah yang lebih konkret:

Dapatkah seseorang menjelaskan secara rinci penerapan Teorema Lawvere pada fungsi rekursif parsial atau teorema titik tetap logis? Khususnya, kategori apa yang perlu kita pertimbangkan di sana?

Dalam D. Pavlovic, Pada struktur paradoks , penulis menganggap kategori bebas yang dihasilkan oleh dengan Akhir ( N ) fungsi rekursif parsial.${\mathbb N}$${\text{End}}({\mathbb N})$

Sayangnya, saya tidak mengerti apa artinya ini.

Misalnya, bagaimana seharusnya hukum komposisi tentang ? Komposisi fungsi rekursif parsial? Setelah semua, dikatakan bahwa teorema Lawvere ini berlaku dengan A = Y = N , sehingga khususnya setiap morphism N → N harus memiliki titik tetap 1 → N . Jika endomorfisme memang hanya fungsi rekursif parsial dan jika komposisi berarti komposisi fungsi, ini tampak aneh - jika poin 1 → N hanyalah elemen N , maka klaim salah, dan jika morfisme 1 → $\text{End}({\mathbb N})$$A=Y={\mathbb N}$${\mathbb N}\to{\mathbb N}$$1\to {\mathbb N}$$1\to {\mathbb N}$${\mathbb N}$$1\to {\mathbb N}$ hanya fungsi parsial juga, maka dapat didefinisikan, teorema titik tetap sepele.

Apa kategori yang benar-benar ingin dipertimbangkan?

Mungkin tujuannya adalah untuk mendapatkan teorema titik tetap Roger, tetapi kemudian orang harus entah bagaimana membangun pengkodean fungsi rekursif parsial dengan bilangan asli ke dalam definisi kategori, dan saya tidak tahu bagaimana melakukan ini.

Saya akan sangat senang jika seseorang dapat menjelaskan konstruksi konteks yang berlaku Teorema Titik Tetap Lawvere, menimbulkan teorema titik tetap logis atau teorema titik tetap untuk fungsi rekursif parsial.

Terima kasih!

Saya mungkin tidak langsung menjawab pertanyaan Anda, tetapi ada generalisasi matematika umum dari banyak paradoksa, termasuk teorema Gödel dan kombinator Y. Saya pikir ini pertama kali dieksplorasi oleh Lawvere. Lihat juga [2, 3].

1. FW Lawvere, argumen Diagonal dan kategori tertutup kartesian .

2. D. Pavlovic, Tentang struktur paradoks .

3. NS Yanofsky, Pendekatan Universal untuk Paradoks Referensi-Mandiri, Ketidaklengkapan, dan Poin Tetap .

Saya tidak punya jawaban lengkap untuk pertanyaan Anda, tetapi saya punya ini:

Seperti kata Wikipedia

$Q(x, y)$$p$

$$\varphi_p\simeq \lambda y.Q(p, y)$$ $\varphi$$\mathbb{N}$

$\lambda$

$\phi$${\mathscr T}$$n$

$${\mathscr T}\vdash \phi(\overline{n}) \Leftrightarrow {\mathscr T}\vdash \exists y, \varphi_n(y)=0$$

This isn't quite what you want, but an internalization trick can give you the stronger statement

${\mathscr T}\vdash \phi(\overline{n})\leftrightarrow \exists y, \varphi_n(y) = 0$

Now again, this is not quite the logical fixed-point theorem, but it can serve the same purpose.

Proof: Define $Q(x,y)$ to be the recursive function defined by

$$Q(x,y) = 0 \mbox{ iff }{\mathscr T}\vdash \phi(\overline{x})\mbox{ in at most $y$ steps}$$ It is easy to see that $Q$ is (total) recursive. Note that $\exists y, Q(x, y)$ expresses the fact "${\mathscr T}$ proves $\phi(\overline{x})$", and that this is true iff ${\mathscr T}\vdash\exists y,Q(\overline{x}, y)$ (we are assuming $\omega$-consistency). Now a simple application of the Kleene Recursion Theorem on $Q$ gives us the desired conclusion. $\square$

With a little thought, you can probably strengthen this argument to give you the full theorem directly without the internalization.