Fixpunkte in Berechenbarkeit und Logik

Diese Frage wurde auch auf Math.SE gestellt,

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

Ich hoffe, es ist in Ordnung, es auch hier zu posten. Wenn nicht, oder wenn es für CS.SE zu einfach ist, sagen Sie es mir bitte und ich werde es löschen.

Ich möchte die Beziehung zwischen den Festkommasätzen in der Logik und dem Kalkül besser verstehen.$\lambda$

Hintergrund

1) Die Rolle von Fixpunkten bei Unvollständigkeit und Undefinierbarkeit der Wahrheit

Soweit ich weiß, ist neben der Grundidee der Internalisierung der Logik der folgende logische Fixpunktsatz der Schlüssel sowohl für die Beweise von Tarskis Undefinierbarkeit der Wahrheit als auch für Goedels Unvollständigkeitssatz , der in einer konstruktiven, endlichen Metatheorie lebt (ich hoffe, die Formulierung) ist in Ordnung, bitte korrigieren Sie mich, wenn etwas nicht stimmt oder ungenau ist):

Existenz von Fixpunkten in der Logik

Angenommen ist eine ausreichend ausdruck rekursiv enumerable Theorie über die Sprache , und läßt , eine Codierung von -Formeln in , das heißt ein Algorithmus beliebig wohlgeformtes Drehen L -Formeln & phgr; in L mit einer freien variable -Formeln C ( φ ) , ( v ) , so dass für jeden L -Formel & phgr; wir haben T ⊢ ∃ ! v : C ( φ )${\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)$ .

Dann existiert ein Algorithmus ${\mathbf Y}$ Drehen wohlgeformten ${\mathcal L}$ -Formeln in einer freien Variable in geschlossenem wohlgeformten ${\mathcal L}$ -Formeln, so dass für jede ${\mathcal L}$ -Formel in einer freien Variable $\phi$ haben wir

$${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \exists v: {\mathbf C}({\mathbf Y}(\phi))(v)\wedge \phi(v),$$ wobei ${\mathbf C}$ als definiertes Funktionssymbol$\lceil -\rceil$, könnte auch kompakter geschrieben werden als $${\mathscr T}\vdash {\mathbf Y}(\phi)\Leftrightarrow \phi(\lceil{\mathbf Y}(\phi)\rceil).$$

Mit anderen Worten, ist ein Algorithmus zur Konstruktion von Fixpunkten in Bezug auf die -Äquivalenz von -Formeln.T ${\mathbf Y}$${\mathscr T}$${\mathcal L}$

Dies hat mindestens zwei Anwendungen:

• Das Anwenden auf das Prädikat ausdrückt " codiert einen Satz, der, wenn er mit seiner eigenen Codierung instanziiert wird, nicht beweisbar ist." ergibt die Formalisierung von "Dieser Satz ist nicht beweisbar", die im Zentrum von Goedels Argumentation liegt.$\phi(v)$$v$

• Die Anwendung auf für einen beliebigen Satz ϕ ergibt Tarskis Undefinierbarkeit der Wahrheit.$\neg\phi$$\phi$

2) Fixpunkte im untypisierten Kalkül$\lambda$

Im untypisierten Kalkül ist die Konstruktion von Fixpunkten wichtig für die Realisierung von rekursiven Funktionen.$\lambda$

Existenz von Fixpunkten im Kalkül:$\lambda$

Es ist ein Fixpunkt-Kombinator , dh ein -term Y , so dass für jedes λ -term f , haben wir f ( Y f ) ~ & agr; & bgr; Y f $\lambda$$Y$$\lambda$$f$

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

Überwachung

Was mich verblüfft ist, dass der Festkomma-Kombinator im λ- Kalkül spiegelt auf sehr saubere und nichttechnische Weise direkt den üblichen Beweis des logischen Fixpunktsatzes wider:$\lambda f.(\lambda x. f(x x))(\lambda x. f(x x))$$\lambda$

Sehr grob betrachtet man bei gegebener Formel die Formalisierung φ ( v ) der Aussage " v codiert einen Satz, der, wenn er mit sich selbst instanziiert wird, ϕ erfüllt " und setzt A ( ϕ ) : = φ ( ⌈ φ ⌉ ) . Der Satz φ ( v ) ist wie λ x . f ( x x ) und φ ( ⌈ φ ⌉ ) entspricht$\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))$

Frage

Trotz seiner schnell beschriebenen Idee fand ich den Beweis des logischen Fixpunktsatzes ziemlich technisch und in allen Einzelheiten schwierig durchzuführen; Kunen tut dies zum Beispiel in Satz 14.2 seines Buches 'Mengenlehre'. Andererseits ist der Kombinator in λ- Kalkül sehr einfach und seine Eigenschaften können leicht verifiziert werden.$Y$$\lambda$

Folgt der logische Fixpunktsatz konsequent aus Fixpunktkombinatoren im Kalkül?$\lambda$

Kann man zB den Kalkül mit L- Formeln bis zur logischen Äquivalenz modellieren , so dass die Interpretation eines beliebigen Festkomma-Kombinators einen Algorithmus ergibt, wie er im Satz über logische Festkomma beschrieben ist?$\lambda$${\mathcal L}$

Bearbeiten

Angesichts der vielen anderen Fälle desselben in Martins und Codys Antworten beschriebenen Diagonalisierungsarguments sollte man die Frage umformulieren:

Gibt es eine gemeinsame Verallgemeinerung der Diagonalisierungsargumente nach dem im Kombinator ausgedrückten Prinzip ? λ f . ( λ x . f ( x x ) ) ( λ x . f ( x x ) $Y$

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

Wenn ich es richtig verstehe, ist ein Vorschlag Lawvere's Fixed Point Theorem , siehe unten. Leider kann ich in keinem der Artikel, die Martin in seiner Antwort zitiert hat, den einschlägigen Fachgebieten folgen, und ich würde mich freuen, wenn jemand sie erklären könnte. Erstens der Vollständigkeit halber:

Lawvere's Fixpunktsatz

Lassen eine Kategorie mit endlichen Produkten und sein φ : A × A → Y , so dass für jeden morphism f : A → Y in C gibt einige ist ⌈ f ⌉ : 1 → A , so daß für alle Punkte p : 1 → A hat man 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.$$

Dann gilt für jeden Endomorphismus , setzen f : = A & Dgr; → A × A & phgr; → Y g → Y , jede Wahl von ⌈ f ⌉ führt zu einem festen Punkt von g , nämlich 1 ⟨ ⌈ f ⌉ , ⌈ f ⌉ ⟩ → A × A & phiv; → 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.$$

Dies ist eine Aussage in der (intuitionistischen) Kategorietheorie erster Ordnung mit endlichen Produkten und gilt daher für jedes Modell der letzteren.

Zum Beispiel ergibt sich Russels Paradoxon, wenn man das theoretische Universum der ganzen Menge als Bereich des Diskurses betrachtet (nimm die hypothetische Menge von Mengen, Y : = Ω : = { 0 , 1 } und ρ : A × A → Ω das ∈ -Predikat). und Cantors Satz (nimm A eine beliebige Menge und ρ : A × A → Ω entsprechend der hypothetischen Surjektion A → Ω $A$$Y := \Omega := \{0,1\}$$\rho: A\times A\to\Omega$$\in$$A$$\rho: A\times A\to \Omega$$A\to\Omega^A$). Ferner liefert die Übersetzung des Beweises von Lawvere's Theorem die üblichen diagonalen Argumente.

Konkretes Problem:

Kann jemand eine Anwendung von Lawvere's Theorem auf partielle rekursive Funktionen oder die logischen Fixpunktsätze im Detail erklären? Welche Kategorien müssen wir dort besonders berücksichtigen?

In D. Pavlovic über die Struktur von Paradoxien betrachtet der Autor die von frei erzeugte Kategorie mit End ( N ) als partielle rekursive Funktionen.${\mathbb N}$${\text{End}}({\mathbb N})$

Leider verstehe ich nicht, was das bedeutet.

Wie sollte beispielsweise das Zusammensetzungsgesetz für lauten? Zusammensetzung partieller rekursiver Funktionen? Immerhin heißt es, dass Lawvere mit A = Y = N gilt , so dass insbesondere jeder Morphismus N → N einen festen Punkt 1 → N haben sollte . Wenn die Endomorphismen tatsächlich nur teilweise rekursive Funktionen sind und wenn Komposition Komposition von Funktionen bedeutet, erscheint dies seltsam - wenn die Punkte 1 → N nur Elemente von N sind , dann ist die Behauptung falsch, und wenn ein Morphismus 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}$ ist auch nur eine Teilfunktion, kann also undefiniert sein, der Fixpunktsatz ist trivial.

Was ist die Kategorie, die man wirklich berücksichtigen möchte?

Vielleicht ist das Ziel, Rogers Fixpunktsatz zu erhalten, aber dann sollte man irgendwie eine Codierung partieller rekursiver Funktionen durch natürliche Zahlen in die Definition der Kategorie einbauen, und ich kann nicht herausfinden, wie das geht.

Es würde mich sehr freuen, wenn jemand die Konstruktion eines Kontexts erklären könnte, auf den Lawvere's Fixed Point Theorem zutrifft, und so ein logisches Fixed Point Theorem oder ein Fixed Point Theorem für partielle rekursive Funktionen entstehen lässt.

Vielen Dank!

Ich beantworte Ihre Frage wahrscheinlich nicht direkt, aber es gibt eine allgemeine mathematische Verallgemeinerung vieler Paradoxa, einschließlich der Sätze von Gödel und des Y-Kombinators. Ich denke, dies wurde zuerst von Lawvere untersucht. Siehe auch [2, 3].

1. FW Lawvere, Diagonale Argumente und kartesische geschlossene Kategorien .

2. D. Pavlovic, Über die Struktur von Paradoxien .

3. NS Yanofsky, Ein universeller Ansatz für selbstreferentielle Paradoxe, Unvollständigkeit und Fixpunkte .

Ich habe keine vollständige Antwort auf Ihre Frage, aber ich habe diese:

Laut Wikipedia heißt es

$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$$

Dies ist nicht ganz das, was Sie wollen, aber ein Internalisierungstrick kann Ihnen die stärkere Aussage geben

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

Auch dies ist nicht ganz der logische Fixpunktsatz, aber er kann denselben Zweck erfüllen.

$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$

Mit ein wenig Überlegung können Sie dieses Argument wahrscheinlich verstärken, um Ihnen den vollständigen Satz direkt ohne die Internalisierung zu geben.