Vollständigkeitssatz für unendliche Logik

26.08.2016, 14:08

Kääsee

Vollständigkeitssatz für unendliche Logik

Hallo ihr Lieben, ich habe eine Denkblockade. Versuche gerade, einen "Beweis" zum Vollständigkeitstheorem in $\begin{eqnarray*} L_{\omega_1\omega} \end{eqnarray*}$ aus einem Buch nachzuvollziehen.
Zuerst einmal das Theorem:

Zitat:

Für jeden Satz $\begin{eqnarray*} \varphi\in L_{\omega_1\omega} \end{eqnarray*}$ gilt $\begin{eqnarray*} \vDash\varphi \end{eqnarray*}$ genau dann, wenn $\begin{eqnarray*} \vdash\ _{L_{\omega_1\omega}}\varphi \end{eqnarray*}$ .

Zum Beweis muss ich euch nun noch einige Vorinformationen bringen:
-C soll einen abzählbare Menge von Konstanten sein, die nicht in L enthalten sind
-M die Sprache, die durch Hinzufügen aller c aus C resultiert und $\begin{eqnarray*} M_{\omega_1\omega} \end{eqnarray*}$ die zugehörige unendliche Sprache.
-Dann habe ich ein paar Axiome und Folgerungsregeln für $\begin{eqnarray*} L_{\omega_1\omega} \end{eqnarray*}$ gegeben (aber nicht so wichtig)
-Ich habe schon gezeigt, dass $\begin{eqnarray*} \vdash\ _{L_{\omega_1\omega}}\varphi \end{eqnarray*}$ genau dann, wenn $\begin{eqnarray*} \vdash\ _{M_{\omega_1\omega}}\varphi \end{eqnarray*}$
-auch habe ich schon nachgewiesen, dass folgende Menge S eine "consistency property" (ich weiß nicht mal, was das auf Deutsch heißt, meine Lektüre ist in englisch) ist:
S soll die Menge aller endlichen Mengen s von Sätzen aus $\begin{eqnarray*} M_{\omega_1\omega} \end{eqnarray*}$ sein, sodass nur endlich viele c in s vorkommen und $\begin{eqnarray*} \nvdash _{M_{\omega_1\omega}} \neg \bigwedge s \end{eqnarray*}$
-Außerdem bekannt: (Model existence theorem) Fall S eine consistency property ist und $\begin{eqnarray*} s_0\in S \end{eqnarray*}$ , dann besitzt $\begin{eqnarray*} s_0 \end{eqnarray*}$ ein Modell.

Jetzt zum Beweis:
Die Richtung $\begin{eqnarray*} "\Leftarrow" \end{eqnarray*}$ ist ja noch ganz "einfach", denn ich weiß, dass jedes Theorem in $\begin{eqnarray*} L_{\omega_1\omega} \end{eqnarray*}$ auch gültig ist, denn die Axiome sind gültig und die Folgerungsregeln erhalten die Gültigkeit.

Nun hab ich aber Probleme mit der Hinrichtung.
D.h., gegeben hab ich $\begin{eqnarray*} \vDash\varphi \end{eqnarray*}$ und will zeigen, dass dann $\begin{eqnarray*} \vdash _{L_{\omega_1\omega}}\varphi \end{eqnarray*}$ .
Nach oben genanntem reicht es dabei, zu zeigen, dass $\begin{eqnarray*} \vdash _{M_{\omega_1\omega}}\varphi \end{eqnarray*}$ .
Ich weiß ja, dass jedes s aus S ein Modell besitzt und dass alle Strukturen aus L auch Modelle von $\begin{eqnarray*} \varphi \end{eqnarray*}$ sind. Also ist, wenn s kein Modell besitzt, s nicht in S enthalten. Ich kann aber nicht automatisch sagen, dass, wenn s nicht in S ist, s kein Modell hat!?
Ich habe durch einen Widerspruch angefangen, also angenommen, dass $\begin{eqnarray*} \nvdash _{M_{\omega_1\omega}}\varphi \end{eqnarray*}$ . Wäre $\begin{eqnarray*} \varphi \end{eqnarray*}$ in einem s aus S enthalten, dann müsste $\begin{eqnarray*} \varphi \end{eqnarray*}$ endlich viele c enthalten und es müsste gelten $\begin{eqnarray*} \vdash _{M_{\omega_1\omega}}\varphi \end{eqnarray*}$ , da $\begin{eqnarray*} \nvdash _{M_{\omega_1\omega}} \neg \bigwedge s \end{eqnarray*}$ . Stimmt das soweit?
Da aber $\begin{eqnarray*} \varphi \end{eqnarray*}$ ein Satz aus $\begin{eqnarray*} L_{\omega_1\omega} \end{eqnarray*}$ ist, wissen wir, dass $\begin{eqnarray*} \varphi \end{eqnarray*}$ gar keine, also insbesondere endlich viele c aus C enthält, oder? Dies gilt auch für $\begin{eqnarray*} \neg \varphi \end{eqnarray*}$ . Kann ich dann sagen, dass $\begin{eqnarray*} \neg \varphi \end{eqnarray*}$ in einem s aus S enthalten ist, dieses s, also auch $\begin{eqnarray*} \neg \varphi \end{eqnarray*}$ ein Modell besitzt?
Und impliziert dies, dass dieses Modell kein Modell von $\begin{eqnarray*} \varphi \end{eqnarray*}$ ist, was im Widerspruch dazu steht, dass $\begin{eqnarray*} \varphi \end{eqnarray*}$ gültig ist (d.h. alle L-Strukturen Modelle sind)?

Hab das Gefühl, mich im Kreis zu drehen^^ Wäre super, wenn mir jemand etwas weiterhelfen könnte.
LG

Neue Frage »

Antworten »

Vollständigkeitssatz für unendliche Logik

Verwandte Themen