Naprawiono punkty w obliczalności i logice

To pytanie zostało również opublikowane na Math.SE,

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

Mam nadzieję, że opublikowanie go tutaj jest również w porządku. Jeśli nie, lub jeśli jest to zbyt podstawowe dla CS.SE, powiedz mi, a ja go usunę.

Chciałbym lepiej zrozumieć związek między twierdzeniami o stałym punkcie w logice a -calculus.$\lambda$

tło

1) Rola stałych punktów w niekompletności i nieokreśloności prawdy

O ile rozumiem, oprócz podstawowej idei internalizacji logiki, kluczem zarówno do dowodów nieokreśloności prawdy Tarskiego, jak i twierdzenia Goedela, jest następujące logiczne twierdzenie o stałym punkcie , żyjące w konstruktywnej, finitystycznej metateorii (mam nadzieję, że sformułowanie jest w porządku, popraw mnie, jeśli coś jest niepoprawne lub nieprecyzyjne):

Istnienie punktów stałych w logice

Załóżmy, że jest wystarczająco ekspresyjne rekurencyjnie wyliczalnych teorii na język L i niech C za kodujący L -formulas w T , to znaczy algorytmu obracając dowolna dobrze uformowane L -formulas cp do L -formulas z jednej zmiennej wolnej C ( φ ) ( V ) tak, że dla każdego L -formula cp mamy 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)$

Następnie istnieje algorytm skrętu oraz uformowaną -formulas jednej zmiennej wolnej do zamkniętych sensownych -formulas, tak, że przy każdym -formula jednej zmiennej wolnej mamy który interpretując jako zdefiniowany symbol funkcji , można również zapisać bardziej jako${\mathbf Y}$L L ϕ T ⊢ Y (ϕ)⇔∃v: C ( Y (ϕ))(v)∧ϕ(v), C ⌈-⌉ T ⊢ Y (ϕ)⇔ϕ(⌈ 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).$$

Innymi słowy, jest algorytmem do konstruowania punktów stałych w odniesieniu do równoważności jednej zmiennej .T ${\mathbf Y}$${\mathscr T}$${\mathcal L}$

Ma to co najmniej dwie aplikacje:

• Zastosowanie go do predykatu wyrażającego „ koduje zdanie, którego utworzenie z własnym kodowaniem nie jest możliwe do udowodnienia”. daje sformalizowanie „To zdanie nie jest możliwe do udowodnienia”, które leży u podstaw argumentu Goedela.$\phi(v)$$v$

• Zastosowanie go do celu wykonania dowolnego zdania powoduje, że Tarski nie jest w stanie zdefiniować prawdy.$\neg\phi$$\phi$

2) Stałe punkty w nietypowym -calculus$\lambda$

W nietypowym -calculus konstrukcja punktów stałych jest ważna w realizacji funkcji rekurencyjnych.$\lambda$

Istnienie punktów stałych w -calculus:$\lambda$

Istnieje kombinator punktowy , tj. -term taki, że dla każdego -term mamyY λ f f ( Y f ) ∼ α β Y f $\lambda$$Y$$\lambda$$f$

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

Obserwacja

To, co mnie oszołomiło, to to, że kombinator stałoprzecinkowy w -calculus bezpośrednio odzwierciedla, w bardzo czysty i nietechniczny sposób, zwykły dowód na logiczne twierdzenie o stałym punkcie:$\lambda f.(\lambda x. f(x x))(\lambda x. f(x x))$$\lambda$

Z grubsza , biorąc pod uwagę formułę , rozważa się sformalizowanie wyrażenia „ koduje zdanie, które po utworzeniu z siebie spełnia ”, i umieszcza . Zdanie jest jak , a odpowiada .φ ( v ) v ϕ A ( ϕ ) : = φ ( ⌈ φ ⌉ ) φ ( v ) λ x . f ( x x ) φ ( ⌈ φ ⌉ ) ( λ x . f ( x x ) ) ( λ x . f ( x x ) $\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))$

Pytanie

Pomimo szybko opisanego pomysłu znalazłem dowód na logiczne twierdzenie o punkcie stałym dość techniczne i trudne do zrealizowania we wszystkich szczegółach; Kunen robi to na przykład w Twierdzeniu 14.2 swojej książki „Teoria zbiorów”. Z drugiej strony, kombinator w -calculus jest bardzo prosty, a jego właściwości można łatwo zweryfikować.$Y$$\lambda$

Czy logiczne twierdzenie o punkcie stałym wynika rygorystycznie z kombinatorów punktów stałych w -calculus?$\lambda$

Np. Czy można modelować -kalkul według wzorów do logicznej równoważności, aby interpretacja dowolnego kombinatora punktów stałych dawała algorytm opisany w logicznym twierdzeniu o punkcie stałym?$\lambda$${\mathcal L}$

Edytować

Biorąc pod uwagę wiele innych przypadków tego samego argumentu diagonalizacji opisanego w odpowiedziach Martina i Cody'ego, należy przeformułować pytanie:

Czy istnieje powszechne uogólnienie argumentów diagonalizacji zgodnie z zasadą wyrażoną w kombinatorze ? λ f . ( λ x . f ( x x ) ) ( λ x . f ( x x ) $Y$

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

Jeśli dobrze to rozumiem, jedną propozycją jest twierdzenie Lawpointa o stałym punkcie , patrz poniżej. Niestety nie mogę śledzić odpowiednich specjalizacji w żadnym z artykułów cytowanych przez Martina w odpowiedzi i byłbym szczęśliwy, gdyby ktoś mógł je wyjaśnić. Po pierwsze, dla kompletności:

Twierdzenie Lawpointa o punkcie stałym

Niech będzie kategorią ze skończonymi produktami i tak, że dla każdego morfizmu w jest trochę taki, że dla wszystkich punktów ma φ:x→YF:A→Y C ⌈F⌉:1→s:1→1 P → F → Y=1, p → ⟨ ⌈ F ⌉ , identyfikator ⟩ → xA cp → Y${\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.$$

Następnie dla każdego endomorfizmu , umieszczając dowolny wybór daje początek stałego punktu , a mianowicie F : = Æ → x cp → Y g → Y , ⌈ F ⌉ g 1 ⟨ ⌈ F ⌉ , ⌈ F ⌉ ⟩ → x cp → 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.$$

Jest to stwierdzenie w (intuicyjnej) teorii pierwszego rzędu kategorii ze skończonymi produktami, a zatem ma zastosowanie do każdego modelu tego ostatniego.

Na przykład , przyjmując cały świat teoretyczną jako domenę mowy daje paradoksu Russela (podjęcie hipotetyczny zestaw kompletów, i the -predicate) i twierdzenie Cantora (weź dowolny zestaw i odpowiadający hipotetycznemu przypuszczeniu ). Ponadto tłumaczenie dowodu twierdzenia Lawvere'a podaje typowe przekątne argumenty.$A$$Y := \Omega := \{0,1\}$$\rho: A\times A\to\Omega$$\in$$A$$\rho: A\times A\to \Omega$$A\to\Omega^A$

Bardziej konkretny problem:

Czy ktoś może szczegółowo wyjaśnić zastosowanie twierdzenia Lawvere'a do częściowych funkcji rekurencyjnych lub logicznych twierdzeń o stałym punkcie? W szczególności, jakie kategorie musimy tam wziąć pod uwagę?

W D. Pavlovic, O strukturze paradoksów , autor uważa kategorię swobodnie generowaną przez pomocą częściowymi funkcjami rekurencyjnymi.${\mathbb N}$${\text{End}}({\mathbb N})$

Niestety nie rozumiem, co to znaczy.

Na przykład, jakie powinno być prawo kompozycji na ? Składanie częściowych funkcji rekurencyjnych? W końcu mówi się, że twierdzenie Lawvere'a ma zastosowanie dla , tak że w szczególności każdy morfizm powinien mieć ustalony punkt . Jeśli endomorfizmy są rzeczywiście tylko częściowymi funkcjami rekurencyjnymi i jeśli skład oznacza składanie funkcji, wydaje się to dziwne - jeśli punkty są tylko elementami , to twierdzenie jest błędne, a jeśli morfizm jest również tylko funkcją częściową, dlatego może być niezdefiniowany, twierdzenie o punkcie stałym jest banalne.$\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}$

Jaką kategorię naprawdę chcesz wziąć pod uwagę?

Być może celem jest uzyskanie twierdzenia Rogera o punkcie stałym, ale wtedy w jakiś sposób należy zbudować kodowanie funkcji cząstkowych rekurencyjnych liczbami naturalnymi do definicji kategorii, a ja nie mogę wymyślić, jak to zrobić.

Byłbym bardzo szczęśliwy, gdyby ktoś mógł wyjaśnić budowę kontekstu, do którego odnosi się twierdzenie Lawpointa o punkcie stałym, dając podstawę do logicznego twierdzenia o punkcie stałym lub twierdzenia o punkcie stałym dla częściowych funkcji rekurencyjnych.

Dziękuję Ci!

Prawdopodobnie nie odpowiadam bezpośrednio na twoje pytanie, ale istnieje powszechne matematyczne uogólnienie wielu paradoksów, w tym twierdzeń Gödla i kombinatora Y. Myślę, że to po raz pierwszy zbadał Lawvere. Zobacz także [2, 3].

1. FW Lawvere, argumenty diagonalne i kartezjańskie kategorie zamknięte .

2. D. Pavlovic, O strukturze paradoksów .

3. NS Yanofsky, Uniwersalne podejście do paradoksów, niekompletności i punktów stałych .

Nie mam pełnej odpowiedzi na twoje pytanie, ale mam to:

Jak mówi Wikipedia

Dla każdej częściowej funkcji rekurencyjnej istnieje indeks p taki, że φ $Q(x, y)$$p$

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

$\lambda$

Dla każdej formuły i ponownej teorii T zawierającej arytmetykę istnieje indeks n taki, że T ⊢ ϕ ( ¯ $\phi$${\mathscr T}$$n$

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

Nie jest to dokładnie to, czego chcesz, ale sztuczka internalizacji może dać mocniejsze stwierdzenie

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

Znowu nie jest to logiczne twierdzenie o stałym punkcie, ale może służyć temu samemu celowi.

$Q(x,y)$

$$Q(x,y) = 0 \mbox{ iff }{\mathscr T}\vdash \phi(\overline{x})\mbox{ in at most $y$ steps}$$ $Q$$\exists y, Q(x, y)$${\mathscr T}$$\phi(\overline{x})$${\mathscr T}\vdash\exists y,Q(\overline{x}, y)$$\omega$$Q$$\square$

Przy odrobinie namysłu możesz prawdopodobnie wzmocnić ten argument, aby dać ci pełne twierdzenie bezpośrednio bez internalizacji.