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 i niech za kodujący -formulas w , to znaczy algorytmu obracając dowolna dobrze uformowane -formulas do -formulas z jednej zmiennej wolnej tak, że dla każdego -formula mamy . ${\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}$ ${\mathcal L}$ ${\mathcal L}$ ${\mathcal L}$ $\phi$
$T ⊢ Y (ϕ) \Leftrightarrow \exists v : C (Y (ϕ)) (v) \land ϕ (v),$ ${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \exists v: {\mathbf C}({\mathbf Y}(\phi))(v)\wedge \phi(v),$ ${\mathbf C}$ $\lceil -\rceil$ $T ⊢ Y (ϕ) \Leftrightarrow ϕ (⌈ Y (ϕ) ⌉) .$ ${\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 . ${\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 mamy $\lambda$ $Y$ $\lambda$ $f$
$fa (Y fa) \sim_{α β} Y fa .$ $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 . $\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 ? $Y$
$λ f . (λ x . f (x x)) (λ x . f (x x))$ $\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 ${\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 \overset{p}{\to} A \overset{f}{\to} Y = 1 \overset{p}{\to} A \overset{⟨ ⌈ f ⌉, {id}_{A} ⟩}{\to} A \times A \overset{φ}{\to} Y .$ $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 $g: Y\to Y$
$f := A \overset{Δ}{\to} A \times A \overset{φ}{\to} Y \overset{g}{\to} Y,$ $f\ :=\ A\xrightarrow{\Delta} A\times A\xrightarrow{\varphi} Y\xrightarrow{g} Y,$ $\lceil f\rceil$ $g$ $1 \overset{⟨ ⌈ f ⌉, ⌈ f ⌉ ⟩}{\to} A \times A \overset{φ}{\to} Y .$ $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!

lo.logic computability lambda-calculus

— Hanno Becker
źródło

Cóż, techniczną częścią twierdzenia Gödela o punkcie stałym jest udowodnienie, że funkcje rekurencyjne mogą być reprezentowane numerycznie w teorii, i nie ma na to szansy, ponieważ musisz w pewnym momencie użyć czegoś, co odróżnia, powiedzmy , od różnych rozstrzygalne teorie. Jeśli chcesz, możesz myśleć o tym jak o implementacji -calculus w arytmetyce.

Q

$Q$

λ

$\lambda$

— Emil Jeřábek wspiera Monikę

@ EmilJeřábek: Dziękuję za komentarz! Rozumiem, że nie będzie możliwości obejścia kodowania funkcji rekurencyjnych, ale chciałbym wyraźnie rozdzielić, co dotyczy kodowania, a co potem jest formalne.

— Hanno Becker,

@ EmilJeřábek: Chciałbym zrozumieć, czy można wywrzeć rygorystyczne wrażenie, że część dotycząca kodowania rodzi pewien model modelu -calculus, za pomocą którego można interpretować kombinator wywoływać różne ustalone twierdzenia punktowe.

λ

$\lambda$

Y

$Y$

— Hanno Becker,

Twierdzenie Lawmore'a o punkcie stałym może być względnie trywialnie stosowane do częściowych funkcji rekurencyjnych, biorąc pod uwagę, że istnieje (rekurencyjne) wyliczenie częściowych funkcji rekurencyjnych, tj. Obliczalne obalenie w kategorii częściowych funkcji rekurencyjnych. Twierdzenie o punkcie stałym mówi: „każda funkcja rekurencyjna (typu ) ma stały punkt ”, który jest dokładnie kombinatorem

φ

$\varphi$

N \to (N \to N)

$\mathbb{N}\rightarrow(\mathbb{N}\rightarrow\mathbb{N})$

(N \to N) \to (N \to N)

$(\mathbb{N}\rightarrow\mathbb{N})\rightarrow(\mathbb{N}\rightarrow\mathbb{N})$

Y

$Y$

— cody

Cody, czy mógłbyś dokładnie opracować kategorię, której używasz, ponieważ w tym momencie nie mogę śledzić innych źródeł.

— Hanno Becker,

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].

FW Lawvere, argumenty diagonalne i kartezjańskie kategorie zamknięte .
D. Pavlovic, O strukturze paradoksów .
NS Yanofsky, Uniwersalne podejście do paradoksów, niekompletności i punktów stałych .

— Martin Berger
źródło

Dziękuję Martin, to są bardzo ciekawe referencje! Mam jednak problem z wyodrębnieniem z sytuacji logicznej kategorycznego kontekstu, do którego logiczne twierdzenie Lawvere'a odnosi się dosłownie. Na przykład w artykule Yanofsky'ego wątpię, aby operacja zastąpienia

{Lind}^{1} \times {Lind}^{1} \to {Lind}^{0}

$\text{Lind}^1\times\text{Lind}^1\to\text{Lind}^0$

@ HannoBecker Może to być dość trudne i wrażliwe na kodowanie.

— Martin Berger,

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

Jak mówi Wikipedia

Dla każdej częściowej funkcji rekurencyjnej istnieje indeks taki, że $Q(x, y)$ $p$
$φ_{p} ≃ λ y . Q (p, y)$ $\varphi_p\simeq \lambda y.Q(p, y)$ $\varphi$ $\mathbb{N}$

$\lambda$

Dla każdej formuły i ponownej teorii zawierającej arytmetykę istnieje indeks taki, że $\phi$ ${\mathscr T}$ $n$
$T. ⊢ ϕ (\bar{n}) \Leftrightarrow T. ⊢ \exists y, φ_{n} (y) = 0$ ${\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 iff T. ⊢ ϕ (\bar{x}) co najwyżej y kroki$ $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.

— cody
źródło

φ : N ≅ C (N, N)

$\varphi:{\mathbb N}\cong\text{C}({\mathbb N},{\mathbb N})$

do ({N.}^{2)}, N.) \to Mapa (N., do (N., N.)) ≅ Mapa (N., N.)

$\text{C}({\mathbb N}^2,{\mathbb N})\to\text{Map}({\mathbb N},\text{C}({\mathbb N},{\mathbb N}))\cong\text{Map}({\mathbb N},{\mathbb N})$

C (N, N)

$\text{C}({\mathbb N},{\mathbb N})$

N^{2} \to N

${\mathbb N}^2\to{\mathbb N}$

(n, m) \mapsto φ (n) (m)

$(n,m)\mapsto\varphi(n)(m)$

Y

$Y$

λ

$\lambda$

— Hanno Becker,

φ

$\varphi$

Y

$Y$

Y f ≃ f (Y f)

$Y\ f\simeq f(Y\ f)$

p := Y Q

$p:= Y\ Q$

λ

$\lambda$ quoteeval

Y

$Y$