Tarskis Undefinierbarkeitssatz

Tarskis Undefinierbarkeitssatz (Umgeleitet von Tarskis Undefinierbarkeitssatz) Zur Navigation springen Zur Suche springen Der Undefinierbarkeitssatz von Tarski, festgestellt und bewiesen von Alfred Tarski in 1933, ist ein wichtiges einschränkendes Ergebnis in der mathematischen Logik, die Grundlagen der Mathematik, und in der formalen Semantik. Informell, Der Satz besagt, dass arithmetische Wahrheit nicht in Arithmetik definiert werden kann.

Der Satz gilt allgemeiner für jedes ausreichend starke formale System, zeigt, dass die Wahrheit im Standardmodell des Systems nicht innerhalb des Systems definiert werden kann.

Inhalt 1 Geschichte 2 Aussage 3 Generelle Form 4 Diskussion 5 Siehe auch 6 References History In 1931, Kurt Gödel veröffentlichte die Unvollständigkeitssätze, was er teilweise bewies, indem er zeigte, wie man die Syntax der formalen Logik innerhalb der Arithmetik erster Ordnung darstellt. Jedem Ausdruck der formalen Sprache der Arithmetik ist eine eindeutige Nummer zugeordnet. Dieses Verfahren ist verschiedentlich als Gödel-Nummerierung bekannt, Codierung u, allgemeiner, als Arithmetisierung. Im Speziellen, verschiedene Mengen von Ausdrücken werden als Mengen von Zahlen kodiert. Für verschiedene syntaktische Eigenschaften (wie eine Formel, ein Satz sein, usw.), diese Mengen sind berechenbar. Darüber hinaus, Jede berechenbare Menge von Zahlen kann durch eine arithmetische Formel definiert werden. Zum Beispiel, Es gibt Formeln in der Sprache der Arithmetik, die den Satz von Codes für arithmetische Sätze definieren, und für beweisbare arithmetische Sätze.

Der Undefinierbarkeitssatz zeigt, dass diese Kodierung für semantische Konzepte wie Wahrheit nicht durchgeführt werden kann. Es zeigt, dass keine ausreichend reich interpretierte Sprache ihre eigene Semantik repräsentieren kann. Eine Folge davon ist, dass jede Metasprache, die in der Lage ist, die Semantik einer Objektsprache auszudrücken, eine Ausdruckskraft haben muss, die die der Objektsprache übersteigt. Die Metasprache enthält primitive Begriffe, Axiome, und Regeln, die in der Objektsprache fehlen, so dass es in der Metasprache beweisbare Theoreme gibt, die in der Objektsprache nicht beweisbar sind.

Der Undefinierbarkeitssatz wird üblicherweise Alfred Tarski zugeschrieben. Gödel entdeckte auch den Undefinierbarkeitssatz in 1930, während er seine Unvollständigkeitstheoreme beweist, die in veröffentlicht wurden 1931, und lange vor dem 1933 Veröffentlichung von Tarskis Werk (Murawski 1998). Während Gödel nie etwas veröffentlicht hat, das sich auf seine unabhängige Entdeckung der Undefinierbarkeit bezieht, er hat es in a beschrieben 1931 letter to John von Neumann. Tarski hatte fast alle Ergebnisse von ihm erhalten 1933 Monographie "Der Wahrheitsbegriff in den Sprachen der deduktiven Wissenschaften" zwischen 1929 und 1931, und sprach darüber mit dem polnischen Publikum. Jedoch, wie er in der Zeitung betont, der Undefinierbarkeitssatz war das einzige Ergebnis, das er früher nicht erhalten hatte. Nach der Fußnote zum Undefinierbarkeitssatz (Satz I.) des 1933 Monographie, der Satz und die Beweisskizze wurden der Monographie erst hinzugefügt, nachdem das Manuskript an die Druckerei geschickt worden war 1931. Das berichtet Tarski dort, als er im März der Warschauer Akademie der Wissenschaften den Inhalt seiner Monographie vorstellte 21, 1931, er äußerte an dieser Stelle nur einige Vermutungen, basierend teilweise auf eigenen Untersuchungen und teilweise auf Gödels kurzem Bericht über die Unvollständigkeitssätze "Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit" [Einige metamathematische Ergebnisse zur Bestimmtheit der Entscheidung und Konsistenz], Österreichische Akademie der Wissenschaften, Wien, 1930.

Statement We will first state a simplified version of Tarski's theorem, dann formulieren und beweisen Sie im nächsten Abschnitt den Satz, den Tarski bewiesen hat 1933.

Sei L die Sprache der Arithmetik erster Ordnung. Das ist die Theorie der natürlichen Zahlen, einschließlich ihrer Addition und Multiplikation, axiomatisiert durch die Peano-Axiome erster Ordnung. Das ist ein "erste Bestellung" Theorie: die Quantoren erstrecken sich über natürliche Zahlen, aber nicht über Mengen oder Funktionen natürlicher Zahlen. Die Theorie ist stark genug, um rekursiv definierte ganzzahlige Funktionen wie Potenzierung zu beschreiben, Fakultäten oder die Fibonacci-Folge.

Sei N die Standardstruktur für L, d.h. N besteht aus der gewöhnlichen Menge natürlicher Zahlen und ihrer Addition und Multiplikation. Jeder Satz in L kann in N interpretiert werden und wird dann entweder wahr oder falsch. Daher (L, N) ist der "interpretierte Sprache erster Ordnung der Arithmetik".

Jede Formel φ in L hat eine Gödelzahl g(Phi). Dies ist eine natürliche Zahl, die "kodiert" Phi. Auf diese Art, die Sprache L kann über Formeln in L sprechen, nicht nur um Zahlen. Sei T die Menge von L-Sätzen, die in N wahr sind, und T* die Menge der Gödelzahlen der Sätze in T. Der folgende Satz beantwortet die Frage: Kann T* durch eine Formel der Arithmetik erster Ordnung definiert werden??

Tarskis Undefinierbarkeitssatz: Es gibt keine L-Formel True(n) das definiert T*. Das ist, es gibt keine L-Formel True(n) so dass für jeden L-Satz A, WAHR(g(EIN)) ↔ A gilt in N.

Informell, Der Satz besagt, dass der Wahrheitsbegriff von arithmetischen Aussagen erster Ordnung nicht durch eine Formel in der Arithmetik erster Ordnung definiert werden kann. Dies impliziert eine erhebliche Einschränkung des Anwendungsbereichs "Selbstdarstellung". Es ist möglich, eine Formel True zu definieren(n) dessen Erweiterung T* ist, aber nur unter Rückgriff auf eine Metasprache, deren Ausdruckskraft über die von L hinausgeht. Zum Beispiel, ein Wahrheitsprädikat für Arithmetik erster Ordnung kann in Arithmetik zweiter Ordnung definiert werden. Jedoch, diese Formel wäre nur in der Lage, ein Wahrheitsprädikat für Formeln in der Originalsprache L zu definieren. Um ein Wahrheitsprädikat für die Metasprache zu definieren, wäre eine noch höhere Metametasprache erforderlich, usw.

Um den Satz zu beweisen, wir gehen per Widerspruch vor und nehmen an, dass eine L-Formel wahr ist(n) existiert, die genau dann für die natürliche Zahl n in N gilt, wenn n die Gödelzahl eines Satzes in L ist, der in N wahr ist. Wir könnten dann True verwenden(n) eine neue L-Formel S zu definieren(m) was für die natürliche Zahl m genau dann gilt, wenn m die Gödelzahl einer Formel φ ist(x) (mit einer freien Variablen x) so dass φ(m) ist falsch, wenn es in N interpretiert wird (d.h. die Formel φ(x), bei Anwendung auf die eigene Gödelzahl, ergibt eine falsche Aussage). Betrachten wir nun die Gödelzahl g der Formel S(m), und fragen, ob der Satz S(g) ist in N wahr, wir erhalten einen Widerspruch. (Dies wird als diagonales Argument bezeichnet.) Der Satz ist eine Folge des Satzes von Post über die arithmetische Hierarchie, bewies einige Jahre nach Tarski (1933). Ein semantischer Beweis des Satzes von Tarski aus dem Satz von Post wird durch reductio ad absurdum wie folgt erhalten. Angenommen, T* ist arithmetisch definierbar, es gibt eine natürliche Zahl n, so dass T* durch eine Formel auf der Ebene definierbar ist {Anzeigestil Sigma _{n}^{0}} der arithmetischen Hierarchie. Jedoch, T* ist {Anzeigestil Sigma _{k}^{0}} -hart für alle k. Somit bricht die arithmetische Hierarchie auf Ebene n zusammen, Widerspruch zum Theorem von Post.

General form Tarski proved a stronger theorem than the one stated above, mit einer vollständig syntaktischen Methode. Der resultierende Satz gilt für jede formale Sprache mit Negation, und mit ausreichender Fähigkeit zur Selbstreferenz, die das Diagonallemma hält. Die Arithmetik erster Ordnung erfüllt diese Voraussetzungen, aber der Satz gilt für viel allgemeinere formale Systeme, wie ZFC.

Tarskis Undefinierbarkeitssatz (generelle Form): Lassen (L,N) sei jede interpretierte formale Sprache, die Negation enthält und eine Gödel-Numerierung g hat(Phi) Erfüllung des Diagonallemmas, d.h. für jede L-Formel B(x) (mit einer freien Variablen x) Es gibt einen Satz A mit A ↔ B(g(EIN)) hält in N. Dann gibt es keine L-Formel True(n) mit folgender Eigenschaft: für jeden L-Satz A, WAHR(g(EIN)) ↔ A ist wahr in N.

Der Beweis von Tarskis Undefinierbarkeitssatz in dieser Form erfolgt wiederum durch reductio ad absurdum. Angenommen, eine L-Formel ist wahr(n) wie oben vorhanden, d.h., wenn A ein arithmetischer Satz ist, dann wahr(g(EIN)) gilt in N genau dann, wenn A in N gilt. Also für alle A, die Formel wahr(g(EIN)) ↔ A gilt in N. Aber das Diagonallemma liefert ein Gegenbeispiel zu dieser Äquivalenz, indem man a gibt "Lügner" Formel S so, dass S ↔ ¬True(g(S)) hält in N. Dies ist ein Widerspruch. IST.

Discussion The formal machinery of the proof given above is wholly elementary except for the diagonalization which the diagonal lemma requires. Der Beweis des Diagonallemmas ist ebenfalls überraschend einfach; zum Beispiel, es ruft in keiner Weise rekursive Funktionen auf. Der Beweis geht davon aus, dass jede L-Formel eine Gödel-Zahl hat, aber die Besonderheiten eines Codierungsverfahrens sind nicht erforderlich. Daher ist der Satz von Tarski viel einfacher zu motivieren und zu beweisen als die berühmteren Sätze von Gödel über die metamathematischen Eigenschaften der Arithmetik erster Ordnung.

Smullyan (1991, 2001) hat nachdrücklich argumentiert, dass Tarskis Undefinierbarkeitssatz einen Großteil der Aufmerksamkeit verdient, die von Gödels Unvollständigkeitssätzen auf sich gezogen wird. Dass die letzteren Sätze viel über die gesamte Mathematik zu sagen haben und kontroverser sind, zu vielen philosophischen Themen (z.B., Lukas 1961) ist weniger als offensichtlich. Satz von Tarski, auf der anderen Seite, geht es nicht direkt um Mathematik, sondern um die inhärenten Beschränkungen jeder formalen Sprache, die ausreichend ausdrucksstark ist, um von wirklichem Interesse zu sein. Solche Sprachen sind notwendigerweise zu ausreichender Selbstreferenz fähig, damit das Diagonallemma auf sie angewendet werden kann. Die breitere philosophische Bedeutung von Tarskis Theorem ist auffallender offensichtlich.

Eine interpretierte Sprache ist genau dann stark semantisch selbstrepräsentativ, wenn die Sprache Prädikate und Funktionssymbole enthält, die alle für die Sprache spezifischen semantischen Konzepte definieren. Daher umfassen die erforderlichen Funktionen die "Semantische Bewertungsfunktion" Abbildung einer Formel A auf ihren Wahrheitswert ||EIN||, und die "semantische Bezeichnungsfunktion" Abbildung eines Begriffs t auf das Objekt, das er bezeichnet. Der Satz von Tarski verallgemeinert sich dann wie folgt: Keine ausreichend mächtige Sprache ist stark semantisch selbstrepräsentativ.

Das Undefinierbarkeitstheorem verhindert nicht, dass die Wahrheit in einer Theorie in einer stärkeren Theorie definiert wird. Zum Beispiel, der Satz von (Codes für) Formeln der Peano-Arithmetik erster Ordnung, die in N wahr sind, sind durch eine Formel in Arithmetik zweiter Ordnung definierbar. Ähnlich, die Menge der wahren Formeln des Standardmodells der Arithmetik zweiter Ordnung (oder Arithmetik n-ter Ordnung für jedes n) kann durch eine Formel in ZFC erster Ordnung definiert werden.

See also Gödel's incompleteness theorems – Limitative results in mathematical logic References J. L. Glocke, und M. Machover, 1977. Ein Kurs in mathematischer Logik. Nordholland. G. Boolos, J. Bürger, und R. Jeffrey, 2002. Berechenbarkeit und Logik, 4Das D. Cambridge University Press. J. R. Lukas, 1961. "Geist, Maschinen, und Gödel". Philosophie 36: 112–27. R. Murawski, 1998. Undefinierbarkeit der Wahrheit. Das Problem der Priorität: Tarsky vs. Gödel. Geschichte und Philosophie der Logik 19, 153–160 R. Smullyan, 1991. Gödels Unvollständigkeitssätze. Oxford Univ. Drücken Sie. R. Smullyan, 2001. "Gödels Unvollständigkeitssätze". In L. Göbel, ed., Der Blackwell-Leitfaden zur philosophischen Logik, Schwarzwell, 72–89. EIN. Tarski, 1933. Der Wahrheitsbegriff in den Sprachen der Erziehungswissenschaften. Herausgegeben von der Warschauer Wissenschaftlichen Gesellschaft. EIN. Tarski (1936). "Der Wahrheitsbegriff in den formalisierten Sprachen" (Pdf). Philosophische Studien. 1: 261–405. Vom Original archiviert (Pdf) an 9 Januar 2014. Abgerufen 26 Juni 2013. EIN. Tarski, tr. J. H. Woodger, 1983. "Der Wahrheitsbegriff in formalisierten Sprachen". Englische Übersetzung von Tarskis 1936 Artikel. In einem. Tarski, ed. J. Corcoran, 1983, Logik, Semantik, Metamathematik, Hackett. show vte Metalogik und Metamathematik show vte Wahrheit show vte Mathematische Logik Kategorien: Mathematische LogikMetatheoremePhilosophie der LogikTheoreme in den Grundlagen der MathematikWahrheitstheorien