Fachrat Informatik - Forum

Quoted

Original von Sinan
"rekursiv" und "entscheidbar" sind doch zwei Begriffe für eins und dasselbe! oder sehe ich da was nicht?

Ist dasselbe.

Quoted

2. Seite 7:

Quoted

Beispiel: Formeln über L*:

die zweite Formel: wieso existiert da nicht so ein z?

Es hat niemand behauptet, daß diese Formel wahr ist (also ein sogenannter Satz ist). Es wurde lediglich behauptet, daß es sich um Formeln handelt (also daß die syntaktische Korrektheit gewährleistet ist).

Quoted

Original von Sinan
Oder hat der Begriff "Satz" hier eine Doppelbedeutung? Es wurde im Skript auch definiert: "ein Satz ist eine Formel ohne freie Variablen".

Sorry, da hab ich ewas durcheinander gebracht. Jetzt aber korrekt:

Term (term): "syntaktisch korrekte" Kombination von Konstantensymbolen, Variablensymbolen und Funktionssymbolen

Formel (formula): "syntaktisch korrekte" Kombination von Termen, Prädikatsymbolen, logischen Operatoren und Quantoren.

Satz (sentence): Formel ohne freie Variablen (auch geschlossene Formel genannt, engl. closed formula)

Was genau mit "syntaktisch korrekt" gemeint ist, sollte klar sein. Auf http://en.wikipedia.org/wiki/First-order…Formation_rules findet sich eine Übersicht.

Von wahren und falschen Sätzen kann man erst sprechen, wenn man eine zur Sprache passende Interpretation festlegt. Je nach gewählter Interpretation kann ein und derselbe Satz mal wahr und mal falsch sein.

Quoted

Original von Sinan
[Eine ganze Menge Fragen]

OK, fangen wir vorne an.

Die Begriffe Symbolmenge, Term, Formel und Satz kennen wir ja nun. Zudem nehme ich an, daß Dir der Begriff Interpretation aus der Vorlesung bekannt ist.

Ein Satz ist alleine erstmal weder wahr noch falsch. Erst wenn er in Beziehung zu einer Interpretation gesetzt wird, ist er bezüglich dieser Interpretation wahr oder falsch. (Das klappt natürlich nur, wenn die Interpretation zum Satz kompatibel ist, d. h. auf derselben Symbolmenge definiert ist. Davon gehe ich hier und im folgenden aber mal aus.) Ist M eine Interpretation und F ein Satz, so ist F unter M entweder wahr oder falsch. (Frage an dich: Warum? Und wovon hängt es ab, ob F unter M wahr oder falsch ist?)

Nun kommen wir zur logischen Implikation. Es gibt Sätze, die immer dann wahr sind, wenn auch andere Sätze wahr sind, und zwar unter jeder beliebigen Interpretation. Ist G ein Satz, der immer dann wahr ist, wenn der Satz F wahr ist (unter jeder Interpretation!), so schreiben wir F |= G. Man sagt, daß F den Satz G impliziert. Die Implikation läßt sich auch für Mengen von Sätzen definieren. Ist Gamma eine Menge von Sätzen und G ein Satz, so sagen wir, daß Gamma den Satz G impliziert (in Zeichen: Gamma |= G), falls F |= G für alle F aus Gamma gilt. Noch eine letzte Schreibweise: Ist Gamma eine Menge von Sätzen, so bezeichnen wir mit Gamma^(|=) die Menge aller Sätze, die von Gamma impliziert werden. (Man sagt auch, daß Gamma^(|=) der Abschluß von Gamma unter der logischen Implikation ist.)

Erstaunlicherweise kann man die Implikation auch etwas "handlicher" definieren als mit dem Umweg über alle möglichen Interpretationen. In Kapitel 4 des Skriptes wird beschrieben, daß die Implikation sich auch völlig losgelöst von Interpretationen definieren läßt, nämlich über sogenannte Logikkalküle (auch Schlußregeln genannt). Mit diesen Regeln läßt sich auf rein syntaktischer Ebene (also ohne sich überhaupt mit Interpretationen beschäftigen zu müssen) eine Relation |- zwischen Sätzen festlegen. Und zwar gilt für Sätze F und G genau dann F |- G, wenn auch F |= G gilt. Wie das genau geht, ist aber nicht das Thema dieser Vorlesung. Von nun an können wir jedenfalls mit dem Begriff der Implikation arbeiten ohne uns mit Interpretationen beschäftigen zu müssen. Es ist also möglich, zu beweisen, daß der Satz F den Satz G impliziert, indem man eine Kette von Implikationen |- angibt, die bei F startet und bei G endet. Auf diese Weise werden Beweise in der Mathematik geführt. Man geht von Sätzen aus, die man bereits als wahr (unter einer bestimmten Interpretation) bewiesen hat und zeigt mittels der Schlußregeln, die |- ausmachen, daß dann auch andere Sätze (unter derselben Interpretation) wahr sein müssen.

Nun kommen wir zum Kern der Vorlesung. Dazu etwas Vorgeschichte: Ein spezielles (und ein historisch besonders bedeutsames) Gebiet der Mathematik ist die sogenannte Zahlentheorie. Sie beschäftigt sich (grob gesagt) mit Aussagen über die Menge der natürlichen Zahlen (Beispiel: "Es gibt unendlich viele Primzahlen"). Man versucht in der Zahlentheorie also für bestimmte Sätze über der Symbolmenge L* der Arithmetik zu beweisen, ob sie unter der Standardinterpretation N* der Arithmetik wahr oder falsch sind. (Das obige Beispiel läßt sich beispielsweise als Satz über L* formulieren. Dieser Satz ist sogar wahr in der Interpretation N*.)

Bis zu den 1930er-Jahren war man in der Mathematik davon überzeugt, daß man für jeden Satz über L*, der unter N* wahr ist, auch beweisen kann, daß dieser wahr ist. Die Idee ist dabei die folgende: Man geht von einer Menge von Sätzen über L* aus, von denen man weiß, daß sie wahr unter L* sind. Aus diesen Sätzen erzeugt man nun mittels der logischen Implikation immer wieder neue (wahre) Sätze bis man den zu beweisenden Satz erreicht hat. Um dieses Vorgehen zu vereinfachen, haben sich Russell and Whitehead in den 1920er- und 1930er-Jahren zusammengesetzt und versucht, eine geeignete Menge von wahren Sätzen zu finden, von denen man bei Beweisen als Startpunkt ausgehen kann. Solche Mengen von Sätzen nennt man Axiome, in der Zahlentheorie wäre zum Beispiel der Satz "Jede Zahl hat einen Nachfolger" ein solches Axiom.

Zusammengefaßt: Gesucht wurde also eine Menge Gamma von Sätzen über L*, so daß Gamma^(|-) genau die Menge der wahren Sätze unter N* ist.

Die Auswahl von Gamma ist nicht einfach.

Zum einen kann es passieren, daß man eine Menge Gamma auswählt, die zu "klein" ist, Gamma^(|-) ist dann eine echte Teilmenge der Menge aller wahren Sätze unter N* (in diesem Fall nennen wir Gamma unvollständig, weil wir damit ja die Menge der wahren Sätze unter N* nicht vollständig durch Implikation erzeugen können). Es gibt dann also Sätze über L*, von denen mittels Gamma weder bewiesen werden kann, daß sie in N* wahr sind, noch daß sie in N* falsch sind. (Frage an dich: Warum ist das so?)

Andererseits kann es aber auch sein, daß Gamma widersprüchlich ist, daß heißt, daß Gamma sowohl einen Satz F als auch seine Negation NOT F enthält. In diesem Fall wäre Gamma^(|-) identisch mit der Menge aller Sätze über L* (Frage an dich: Warum?).

Aus den obigen Betrachtungen ergibt sich der Begriff der Theorie. Eine Theorie ist eine Menge von Sätzen, die unter der Implikation abgeschlossen ist. Eine Theorie ist also immer von der Form Gamma^(|-), wobei Gamma eine Menge von Sätzen ist. Eine spezielle Theorie ist die Menge aller wahren Sätze unter einer Interpretation M, kurz mit Th(M) bezeichnet. Wir nennen eine Theorie T vollständig, falls für jeden Satz F gilt, daß F oder NOT F in T enthalten ist. Gibt es eine Formel F, so daß sowohl F als auch NOT F in T enthalten sind, so nennen wir T widersprüchlich. Man beachte: Vollständigkeit von Mengen von Sätzen ist etwas anderes als Vollständigkeit von Theorien. (Frage an dich: Was ist der Unterschied?) Man kann zeigen, daß für jede Interpretation M gilt, daß Th(M) vollständig ist. (Frage an dich: Warum ist das so?)

Die Menge aller unter N* wahren Sätze in L* nennen wir Arithmetik (das ist übrigens dasselbe wie Th(N*)).

Zurück zu dem Problem der Herren Russell und Whitehead. Mit unseren neuen Begriffen lautet das Problem also: "Gesucht wird eine Menge Gamma, so daß Gamma^(|-) = Th(N*) gilt." Genauer gesagt, suchen wir nicht irgendeine solche Menge, sondern eine entscheidbare (sonst könnten wir ja direkt Gamma als Th(N*) definieren). Entscheidbar deswegen, weil wir natürlich feststellen müssen, welche Sätze wir als wahr annehmen können und welche nicht. Noch besser wäre es natürlich, wenn Gamma eine endliche Menge wäre, dann könnten wir uns unsere Menge von wahren Sätzen, mit denen wir starten, einfach aufschreiben.

Jede entscheidbare Menge von Sätzen nennen wir Axiomensystem. Mit den Definitionen von oben wissen wir nun auch, was ein vollständiges Axiomensystem ist. (Frage an dich: Nämlich was?) Eine Theorie T nennen wir axiomatisierbar, falls es ein Axiomensystem Gamma gibt mit der Eigenschaft Gamma^(|-) = T.

OK, nun ein letzter Anlauf an das Problem von Russell und Whitehead mit diesem Begriff: "Gesucht wird ein Axiomensystem für Th(N*)".

Leider trat Mitte der 1930er-Jahre Kurt Gödel auf die Bühne der Mathematik und bewies, daß es kein Axiomensystem für Th(N*) gibt, also daß Th(N*) nicht axiomatisierbar ist. Das fanden Russell und Whitehead (und viele andere Mathematiker) natürlich nicht besonders toll, weil sie doch die letzten Jahre darin investiert haben, sich ein Axiomensystem auszudenken und mehrere Bücher darüber geschrieben haben, welche Sätze aus der Arithmetik sie mit Hilfe dieses Axiomensystems beweisen konnten.

Das bedeutet also: Für jedes Axiomensystem Gamma über L* gilt: Entweder ist Gamma unvollständig oder Gamma^(|-) ist eine echte Obermenge von Th(N*) und damit widersprüchlich. (Frage an dich: Warum ist Gamma^(|-) in diesem Fall widersprüchlich?)

Gödel hat sogar gezeigt, daß sogar eine vereinfachte Form von Th(N*) nicht axiomatisierbar ist. (Das ist die Menge Q, die Du als die Menge der rationalen Zahlen gelesen hat. Wirf mal einen Blick auf Seite 22 im Skript, dort wird Q definiert.)

Diese Resultate wurden zwar für die Zahlentheorie aufgestellt, sind aber auch auf allen anderen Disziplinen der Mathematik übertragbar. Das kuriose Resultat ist damit, daß es in der Mathematik Sätze gibt, die zwar wahr sind, aber nicht als wahr bewiesen werden können.

So, ich hoffe, daß ich auf die Schnelle nicht zuviele Fehler gemacht habe. Falls doch: korrigiere mich! :)

(Achso: Die Fragen an dich, die ich in den Text eingestreut habe, sollen Dir beim Verständnis helfen. Hier im Forum brauchst Du sie daher nicht zu beantworten.)

Wirklich beeindruckend. Joachim, du solltest mal ein Buch darüber schreiben oder so

Wie leite ich denn her, daß Th(N*) vollständig ist?

Ist das so, weil N* eine Interpretation über eine Sprache L ist, mithin also eine Interpretation (M), und für jede solche gilt, daß Th(M) immer vollständig ist (S. 15 unten)?

[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]

Oder wie? Oder was?

Quoted

Original von absynth
[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]

Exakt.

Quoted

Original von Joachim

Quoted

Original von absynth
[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]

Exakt.

Huch. Das ist ja direkt anschaulich. Ich bin bestürzt.

hat sich schon erledigt.

Eine syntaktische Frage hätte ich: Auf Seite 16, Kapitel 5 wird erstmals eine Notation eingeführt mit

Quoted

(n_1, ..., n_k) element aus M gdw. F(n_1, ..., n_k) gilt.

Diese Unterstreichung wird vorher als Kurzform für S_n(0,y) eingeführt, aber in L* existiert das ja nicht. Später wird sie als Kurzform für das Gödel-Numeral eingeführt, aber diese Definition ist ja an der Stelle noch nicht bekannt. Was ist es nun...?

[EDIT]Hätte ich mal genauer gelesen. Hier stand einiges, aber wenig passendes. Das folgende lasse ich aber stehen:[/EDIT]

Durch das Unterstreichen wird (verkürzt) das Symbol einer Konstante von ihrer Interpretation unterschieden, Symbol 3, Interpretation 3.

Quoted

Original von Informatik Minister
So meine Auffassung, bzw. kürzer: durch das Unterstreichen wird (verkürzt) das Symbol einer Konstante von ihrer Interpretation unterschieden, Symbol 3, Interpretation 3.

Und nun noch einmal zurück zu S.16 bzw. n_k vs. n_k: n_k ist das Symbol, n_k die vereinfachende Schreibweise für die Interpretation unter N*?

Anmerkung: Seite 11 spricht natürlich von einer ganz anderen Symbolmenge als Seite 7 bzw. Seite 16, also lasse ich das jetzt mal außer Acht.

Quoted

Original von absynth
Und nun noch einmal zurück zu S.16 bzw. n_k vs. n_k: n_k ist das Symbol, n_k die vereinfachende Schreibweise für die Interpretation unter N*?

Nein, jetzt noch einmal ohne die (mich) verwirrende Seite 11.

n_k stellt eine Abkürzung für einen Term über L* dar.
Beispiel: 5 steht abkürzend für 0’’’’’, einen Term über L* (ohne Bedeutung), n_k also für den Term 0 gefolgt von n_k-mal ’.

n_k ist dann die Interpretation von n_k, bzw. dem dahinterstehenden Term über L*, also die n_k-male Ausführung der Nachfolgerfunktion, angefangen bei 0, im Beispiel also der fünfte Nachfolger von 0, also 5.

Das Ganze ist der Tribut, den man an die spärliche Ausstattung von L* zahlen muss, denn dort gibt es ja u.a. nur 0 als Konstantensymbol und ein Symbol für die Nachfolgerfunktion.

Erbärmlicher Nachtrag:
Da ich inzwischen selbst ein wenig verwirrt bin, da die Vereinfachung in ganz anderem Zusammenhang eingeführt wurde (wie von absynth schon anfangs bemerkt und von mir konsequent überlesen), lasse ich mich gerne verbessern.

Gelten Korrektheits- und Gödelscher Vollständigkeitssatz

a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?

Baut die Definition von |- "durch passende Schlußregeln", die zum Satz von der Rekursiven Aufzählbarkeit von Gamma^(|-) führt, auf dieser Definition auf, d.h. gilt alles auf S.15 genannte gleichzeitig?

Warum kann ich mit fast 28 das griechische Alphabet immer noch nicht komplett? Werde ich es je lernen?

Fragen über Fragen...

Quoted

Original von absynth
Gelten Korrektheits- und Gödelscher Vollständigkeitssatz

a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?

Die Definition von |- beruht auf besagten Schlußregeln, damit auch die von Dir genannten Sätze. Diese Sätze sind jedoch nicht für beliebige Sammlungen von Schlußregeln wahr. Es gibt allerdings eine Sammlung einfacher Schlußregeln (dies wird in der Vorlesung nicht thematisiert), mit denen |- so definiert werden kann, daß die von Dir genannten Sätze wahr sind.

Quoted

Original von Joachim

Quoted

Original von absynth
Gelten Korrektheits- und Gödelscher Vollständigkeitssatz

a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?

Die Definition von |- beruht auf besagten Schlußregeln, damit auch die von Dir genannten Sätze. Diese Sätze sind jedoch nicht für beliebige Sammlungen von Schlußregeln wahr. Es gibt allerdings eine Sammlung einfacher Schlußregeln (dies wird in der Vorlesung nicht thematisiert), mit denen |- so definiert werden kann, daß die von Dir genannten Sätze wahr sind.

Und Gamma |- F <=> Gamma |= F? Folgt das (unter den oben erwähnten Schlußregeln) aus den beiden Sätzen?

Quoted

Original von absynth
Und Gamma |- F <=> Gamma |= F? Folgt das (unter den oben erwähnten Schlußregeln) aus den beiden Sätzen?

Ja, steht doch so im Skript.

Die Idee dahinter: Logische Implikation kann äquivalent sowohl auf semantischer Ebene (|=, über alle möglichen Interpretationen) als auch auf syntaktischer Ebene (|-, über die Schlußregeln) definiert werden.