Seite 1 von 1

Übung14, G1 d)

Verfasst: 29. Aug 2010 20:05
von Mayumi
Hallo,

ich habe eine Frage über Übung 14 G1 d). Die Aufgabe ist : VAL(FO) := {φ ∈ FO : φ allgemeingültig}

In der Musterlösung stand: "Wegen des Kompaktheitssatzes ist diese Menge rekursiv aufzählbar."
Laut des Skrips ist mir klar, dass es für die allgemeingültige FO rekursiv aufzählbar ist. Somit ist diese rekursiv aufzählbar.

Ich verstehe nicht warum man an dieser Stelle Aufzählbarkeit mit dem Kompaktheitssatz beweisen kann.
Kompaktheitssatz ist: wenn jede endliche, beliebige Teilmenge von der unendlichen Formelmenge erfüllbar, dann ist die unendliche Formelmenge auch erfüllbar.
Also ist es dieser Satz erstmal mit der Allgemeingültigkeit nicht zu tun. Allgemeingültig ist nur dann wenn alle Formel von der Formelmenge erfüllbar ist.
In diesem Fall kann es meiner Meinung nach aufgrund der unendlichen Formelmenge nicht gehen.

Ich würde mich auf die Antwort freuen, wenn jemand erklären könnte, warum man die Aufzählbarkeit bezüglich VAL(FO) := {φ ∈ FO : φ allgemeingültig} mit dem Kompaktheitssatz beweisen kann. Vielen Dank.

Re: Übung14, G1 d)

Verfasst: 2. Sep 2010 22:38
von John
Jetzt, wo du das sagst, frag ich mich das auch. Wenn ich eins sagen kann, dann allerdings, dass immerhin ein gewisser Zusammenhang zwischen Kompaktheitssatz und rekursiver Aufzählbarkeit existiert.

Laut Vollständigkeitssatz sind nämlich alle allgemeingültigen Formeln rekursiv aufzählbar [1]. Der Kompaktheitssatz ist außerdem eine Folgerung des Vollständigkeitssatzes [2]. Aber näher darauf eingegangen, was nun der Kompaktheitssatz mit rekursiver Aufzählbarkeit zu tun hat, wird hier nicht. Vielleicht kann man auch den Vollständigkeitssatz aus dem Kompaktheitssatz folgern, aber das erscheint mir unlogisch. Vielleicht ist die Musterlösung auch schlicht weg falsch.

[1] Der Satz besagt, dass \(\Phi \models \varphi\ gdw.\ \Phi \vdash \varphi\); wenn nun \(\varphi\) allgemeingültig ist, wähle man einfach für \(\Phi\) die leere Menge und hat ebendiese Korrespondenz
[2] Aufgrund der Definition des Sequenzenkalküls gilt \(\Phi \vdash \varphi\ gdw.\ \Phi_0 \vdash \varphi\) für eine endliche Teilmenge \(\Phi_0 \subseteq \Phi\)

Re: Übung14, G1 d)

Verfasst: 7. Sep 2010 12:18
von Mayumi
Hallo,

ich habe von einem Assistent dafür eine Antwort gekriegt & hiermit zitiere ich die Antwort.

"du hast recht, die Aufzählbarkeit von VAL(FO) kann nicht mit dem
Kompaktheitssatz bewiesen werden. Die Musterlösung ist an dieser Stelle
falsch. Richtig wäre, dass VAL(FO) wegen des Vollständigkeitsatzes
rekursiv aufzählbar ist.
........
Der Vollständigkeitssatz sagt jetzt aus,
dass es einen solchen Beweis für \phi gibt, wenn \phi allgemeingültig
ist."

Somit ist es klar, dass die Aufzählbarkeit laut des Vollständigkeitssatzes bewiesen werden kann.