On a Question of Hamkins'

Die Arbeit zeigt, dass es keine extensionale Rosser-Formel beliebiger Komplexität gibt, beantwortet die Frage von Hamkins jedoch positiv für den Fall der „bedingten Extensionalität" und lässt die Frage nach der „konsistenten Extensionalität" offen.

Das Wesentliche

Hier ist eine einfache Erklärung des wissenschaftlichen Artikels von Albert Visser, die sich an ein allgemeines Publikum richtet. Wir verwenden dafür ein paar kreative Analogien, um die komplexen mathematischen Ideen greifbar zu machen.

Das große Rätsel: Ein unentscheidbares Urteil

Stellen Sie sich vor, Sie haben einen riesigen, unendlichen Regelkatalog für Mathematik, den wir PA (Peano-Arithmetik) nennen. Dieser Katalog sagt uns, was in der Welt der Zahlen wahr ist und was nicht.

Der Mathematiker Joel Hamkins stellte eine faszinierende Frage:
„Können wir eine spezielle Formel (eine Art ‚magisches Urteil' namens $\rho$) erfinden, die über jede beliebige mathematische Aussage $\phi$ entscheidet?"

Die Anforderungen an dieses Urteil waren streng:

1. Unabhängigkeit: Wenn die Aussage $\phi$ mit den Regeln vereinbar ist (also keinen Widerspruch erzeugt), dann sollte das Urteil $\rho(\phi)$ sowohl „wahr" als auch „falsch" sein können, ohne dass die Mathematik kollabiert. Es soll also eine echte Grauzone bleiben.
2. Extensionalität (Die „Gleichheits-Regel"): Das ist der knifflige Teil. Wenn zwei Aussagen $\phi$ und $\psi$ mathematisch gesehen genau dasselbe bedeuten (man kann sie gegeneinander austauschen, ohne dass sich etwas ändert), dann muss auch das Urteil $\rho$ für beide genau dasselbe Ergebnis liefern.

Die Analogie:
Stellen Sie sich $\rho$ wie einen Richter vor.

• Unabhängigkeit: Der Richter darf bei einem fairen Prozess (konsistente Theorie) entscheiden: „Schuldig" oder „Unschuldig" – beides ist möglich, ohne dass das Gericht in Chaos versinkt.
• Extensionalität: Wenn zwei Angeklagte A und B exakt dieselbe Tat begangen haben (mathematisch äquivalent sind), muss der Richter für beide das exakt gleiche Urteil fällen. Er darf nicht sagen: „A ist schuldig, aber B ist unbescholten", nur weil sie unterschiedliche Namen haben.

Das Ergebnis: Die gute Nachricht und die schlechte Nachricht

Albert Visser untersucht diese Frage und kommt zu einem überraschenden Ergebnis, das in zwei Teile zerfällt:

1. Die schlechte Nachricht: Der perfekte Richter existiert nicht

Visser beweist, dass es keine solche Formel geben kann, die beide Bedingungen gleichzeitig erfüllt.

Die Analogie:
Stellen Sie sich vor, Sie versuchen, einen Richter zu bauen, der immer fair ist (Extensionalität) und immer eine Grauzone lässt (Unabhängigkeit). Visser zeigt, dass dieser Richter in eine logische Falle tappen würde.
Wenn Sie versuchen, ihn auf eine Aussage anzuwenden, die sich selbst auf das Urteil bezieht (ein sogenannter „Fixpunkt"), entsteht ein Paradoxon. Es ist, als würde der Richter sagen: „Ich bin schuldig, wenn ich unschuldig bin." Das System würde sich selbst aufheben.
Fazit: Man kann keine Formel finden, die für alle mathematisch gleichen Aussagen das gleiche Urteil fällt und dabei gleichzeitig immer eine echte Entscheidungsoption offen lässt.

2. Die gute Nachricht: Ein cleverer Kompromiss ist möglich

Aber! Visser zeigt, dass man das Problem lösen kann, wenn man die „Gleichheits-Regel" (Extensionalität) ein wenig lockert. Er nennt dies „Bedingte Extensionalität".

Die neue Regel:
Der Richter muss nur dann das gleiche Urteil fällen, wenn die Ausgangsaussage $\phi$ selbst bereits in der Theorie bewiesen werden kann. Wenn $\phi$ und $\psi$ gleich sind, aber $\phi$ noch nicht bewiesen ist, darf der Richter vielleicht anders entscheiden.

Unter dieser etwas schwächeren Bedingung findet Visser eine Lösung!
Er konstruiert eine Formel $\rho$, die:

• Flexibel ist: Sie kann sich an jede Situation anpassen (sie ist „$\Pi^0_1$-flexibel"). Das bedeutet, sie kann so formuliert werden, dass sie zu fast jeder anderen Aussage passt, ohne Widersprüche zu erzeugen.
• Bedingt fair ist: Solange die Grundregeln eingehalten werden, verhält sie sich konsistent.

Die Analogie für die Lösung:
Statt eines starren Richters, der immer sofort urteilt, bauen wir einen intelligenten Assistenten.

• Dieser Assistent wartet ab. Wenn die Situation (die Theorie) klar ist, gibt er ein Urteil ab, das mit anderen ähnlichen Situationen übereinstimmt.
• Aber er ist „flexibel": Er kann seine Antwort so anpassen, dass sie zu einem gewünschten Ergebnis passt, solange das nicht gegen die Grundgesetze verstößt.
• Visser nutzt dafür ein Konzept namens „langsame Beweisbarkeit". Stellen Sie sich vor, der Assistent prüft Beweise nicht sofort, sondern nur, wenn sie „klein genug" sind oder bestimmte Bedingungen erfüllen. Diese „langsame" Prüfung erlaubt ihm, die starren Grenzen der Mathematik zu umgehen, ohne sie zu brechen.

Was bleibt offen? (Die offene Frage)

Visser lässt eine Tür einen Spalt offen. Es gibt eine mittlere Variante der „Gleichheits-Regel", die er „Konsistente Extensionalität" nennt.

• Das wäre: Der Richter muss fair sein, wenn die Theorie konsistent ist.
• Visser sagt: „Wir wissen, dass die strenge Regel nicht geht. Wir wissen, dass die lockere Regel geht. Aber was ist mit dieser mittleren Regel?"
  Das ist wie ein Puzzle, bei dem wir das Eckstück und das Mittelstück haben, aber das Stück dazwischen noch fehlt.

Zusammenfassung für den Alltag

1. Das Problem: Man wollte eine mathematische Regel, die immer fair ist (bei gleichen Dingen gleiches Urteil gibt) und gleichzeitig immer eine echte Unsicherheit lässt.
2. Das Ergebnis: Das ist unmöglich. Die Logik verbietet es. Wenn man Fairness verlangt, muss man auf die volle Flexibilität verzichten (oder umgekehrt).
3. Die Lösung: Wenn man die Fairness-Regel etwas anpasst (nur anwenden, wenn die Situation schon bewiesen ist), findet man eine brillante, flexible Regel, die funktioniert.
4. Die Bedeutung: Dies zeigt uns die Grenzen und Möglichkeiten der mathematischen Logik auf. Es gibt keine „perfekte" Maschine für alle Entscheidungen, aber es gibt clevere Tricks, um mit den Einschränkungen zu leben.

Der Artikel ist also eine Reise von einer unmöglichen Utopie hin zu einer cleveren, funktionierenden Realität in der Welt der mathematischen Beweise.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers von Albert Visser auf Deutsch.

Titel und Kontext

Titel: On a Question of Hamkins' (Zu einer Frage von Hamkins)
Autor: Albert Visser
Hintergrund: Das Papier adressiert eine Frage von Joel Hamkins (aus [Ham22], Frage 28) bezüglich der Existenz einer spezifischen Formel in der Peano-Arithmetik (PA), die sowohl Unabhängigkeits- als auch Extensionalitätseigenschaften besitzt.

---

1. Das Problem

Hamkins fragte, ob es eine $\Pi^0_1$-Formel $\rho(x)$ gibt, die zwei spezifische Bedingungen erfüllt:

1. Unabhängigkeit (Independence): Wenn die Theorie $PA + \varphi$ konsistent ist, dann sind sowohl $PA + \varphi + \rho(\ulcorner\varphi\urcorner)$ als auch $PA + \varphi + \neg\rho(\ulcorner\varphi\urcorner)$ konsistent.
2. Extensionalität (Extensionality): Wenn $PA \vdash \varphi \leftrightarrow \psi$, dann gilt $PA \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$.

Eine solche Formel wird als extensionale Rosser-Formel bezeichnet. Hamkins erlaubte dabei Formeln beliebiger Komplexität, fragte aber speziell nach einer $\Pi^0_1$-Lösung.

---

2. Methodik und Beweistechniken

Visser nutzt eine Kombination aus Fixpunktsätzen, Beweistheorie und Modifikation von Rosser- und Gödel-Sätzen.

• Negativer Beweis (Sektion 2):
  Visser zeigt, dass keine extensionale Rosser-Formel existieren kann, indem er einen Widerspruch herleitet. Er konstruiert zwei Fixpunkte:

  • $\varphi_0 \leftrightarrow \rho(\ulcorner\varphi_0\urcorner)$
  • $\varphi_1 \leftrightarrow \neg \rho(\ulcorner\varphi_1\urcorner)$
    Durch die Unabhängigkeitsbedingung folgt, dass beide $\varphi_0$ und $\varphi_1$ widerlegbar sind ($\vdash \neg \varphi_0$ und $\vdash \neg \varphi_1$). Dies impliziert $\varphi_0 \leftrightarrow \bot$ und $\varphi_1 \leftrightarrow \bot$.
    Durch die Extensionalität folgt dann $\rho(\ulcorner\varphi_0\urcorner) \leftrightarrow \rho(\ulcorner\bot\urcorner)$ und $\rho(\ulcorner\varphi_1\urcorner) \leftrightarrow \rho(\ulcorner\bot\urcorner)$.
    Kombiniert man dies mit den Fixpunktgleichungen, erhält man $\varphi_0 \leftrightarrow \rho(\ulcorner\bot\urcorner)$ und $\varphi_1 \leftrightarrow \neg \rho(\ulcorner\bot\urcorner)$. Da beide $\varphi$ widerlegbar sind, folgt sowohl $\vdash \neg \rho(\ulcorner\bot\urcorner)$ als auch $\vdash \rho(\ulcorner\bot\urcorner)$, was einen Widerspruch zur Konsistenz der Basis-Theorie darstellt.
    Ergebnis: Es gibt keine extensionale Rosser-Formel (auch nicht von höherer Komplexität) für Theorien, die die Robinson-Theorie $R$ interpretieren.

• Positiver Beweis (Sektion 4):
  Um eine positive Antwort zu geben, schwächt Visser die Bedingung der Extensionalität ab. Er führt das Konzept der Slow Provability (langsame Beweisbarkeit) ein, basierend auf früheren Arbeiten von Shavrukov und Visser [SV14] sowie Visser [Vis21].

  • Uniforme Beweisbarkeit: Er definiert eine Relation $\preceq_n$, die besagt, dass eine Aussage aus einer anderen folgt, wenn sie durch Propositionallogik plus Beweise der Länge $\le n$ aus der Basis-Theorie herleitbar ist.
  • Kleinheit (Smallness): Eine Zahl $x$ ist $\varphi$-klein ($S_\varphi(x)$), wenn alle $\Sigma^0_1$-Sätze $\sigma \le x$, die aus $\varphi$ mit Beweisen der Länge $\le x$ herleitbar sind, tatsächlich wahr sind.
  • Langsame Beweisbarkeit ($\triangle_\varphi$): $\triangle_\varphi \psi$ bedeutet, dass $\psi$ aus Axiomen von $U + \varphi$ beweisbar ist, die "klein" sind (d.h. ihre Gödelnummern erfüllen die Kleinheitsbedingung).

---

3. Wichtige Beiträge und Ergebnisse

A. Negative Antwort auf die ursprüngliche Frage

Das Papier beweist, dass Hamkins' ursprüngliche Frage mit Nein zu beantworten ist. Es existiert keine Formel, die gleichzeitig Unabhängigkeit und volle Extensionalität erfüllt. Dies gilt für eine breite Klasse von Theorien, die $R$ erweitern.

B. Positive Antwort unter "Conditional Extensionality"

Visser zeigt, dass die Frage positiv beantwortet werden kann, wenn man die Extensionalität durch Conditional Extensionality ersetzt:

• Bedingung: Wenn $PA \vdash \varphi \leftrightarrow \psi$, dann gilt $PA + \varphi \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$.
  (Hinweis: Die Äquivalenz wird nur innerhalb der Theorie $PA + \varphi$ gefordert, nicht in der reinen PA.)

Unter dieser Bedingung konstruiert Visser eine $\Pi^0_1$-Formel $\rho(x)$ (speziell $\triangle_\varphi \top$), die folgende starke Eigenschaften besitzt:

1. $\Pi^0_1$-Flexibilität: Wenn $PA + \varphi$ konsistent ist, dann ist für jedes $\Pi^0_1$-Sentence $\pi$ die Theorie $PA + \varphi + (\rho(\ulcorner\varphi\urcorner) \leftrightarrow \pi)$ konsistent.
   • Dies ist eine starke Verallgemeinerung der Unabhängigkeit. Während Unabhängigkeit nur $\top$ und $\bot$ als Optionen bietet, erlaubt Flexibilität die Äquivalenz zu jedem $\Pi^0_1$-Satz.
2. Conditional Extensionality: Wie oben definiert.

Die Formel $\rho(x)$ ist im Wesentlichen ein "slow consistency statement" (langsame Konsistenzaussage) für die Theorie $PA + \varphi$. Sie ist fixpunktfrei konstruiert.

C. Offene Frage: "Consistent Extensionality"

Das Papier lässt eine wichtige Zwischenfrage offen (Question 1.2):
Gibt es eine Rosser-Formel, die Consistent Extensionality erfüllt?

• Definition: Wenn $PA \nvdash \neg \varphi$ (d.h. $\varphi$ ist konsistent) und $PA \vdash \varphi \leftrightarrow \psi$, dann gilt $PA \vdash \rho(\ulcorner\varphi\urcorner) \leftrightarrow \rho(\ulcorner\psi\urcorner)$.
• Dies liegt zwischen voller Extensionalität (die unmöglich ist) und Conditional Extensionality (die möglich ist). Visser stellt fest, dass das Problem als ungelöst gilt, solange diese Frage offen bleibt.

---

4. Signifikanz und Einordnung

• Klarstellung der Grenzen: Das Papier setzt eine klare Grenze für die Möglichkeit, Rosser-artige Sätze zu konstruieren, die sowohl unabhängig als auch extensional sind. Es zeigt, dass Extensionalität und Unabhängigkeit in der starken Form unvereinbar sind.
• Verfeinerung des Begriffs der Flexibilität: Die Arbeit verbindet die klassischen Inkomplettheitsresultate (Gödel) mit dem Konzept der Flexibilität (Kripke). Sie zeigt, dass Flexibilität für $\Pi^0_1$-Sätze erreichbar ist, wenn man die Extensionalität appropriately abschwächt.
• Technische Innovation: Die Verwendung von "Slow Provability" (langsame Beweisbarkeit) und der "Outside-Big-Inside-Small"-Prinzipien (Objekte, die in der Außenwelt groß sind, sind im Inneren klein) ermöglicht die Konstruktion der gewünschten Formel, ohne die Konsistenz der Basis-Theorie zu verletzen.
• Verbindung zu früheren Arbeiten: Das Ergebnis baut auf Shavrukov und Visser [SV14] auf, die eine $\Delta^0_2$-Formel mit Conditional Extensionality fanden. Visser verbessert dies hier auf eine $\Pi^0_1$-Formel, behält aber die Conditional Extensionality bei.

Zusammenfassung

Albert Visser beantwortet Hamkins' Frage negativ für den Fall der vollen Extensionalität, beweist aber positiv, dass eine $\Pi^0_1$-Formel existiert, die Conditional Extensionality und $\Pi^0_1$-Flexibilität erfüllt. Dies wird durch eine Konstruktion mittels "slow provability" erreicht. Die Existenz einer Formel mit "Consistent Extensionality" bleibt als offene Frage bestehen. Das Papier ist ein wichtiger Beitrag zur Verständnis der Grenzen von Rosser-Sätzen und der Struktur von Unentscheidbarkeit in der Arithmetik.