Existenz von Formelmengen

13.05.2009, 19:03

aRo

Existenz von Formelmengen

Hallo!

Zu folgender Aufgabe finde ich keinen rechten Zugang, ich hoffe ihr könnt mir helfen:

Seien $\begin{eqnarray*} \Phi \end{eqnarray*}$ und $\begin{eqnarray*} \Theta \end{eqnarray*}$ zwei Formelmengen.Wir sagen, dass $\begin{eqnarray*} \Theta \end{eqnarray*}$ aus $\begin{eqnarray*} \Phi \end{eqnarray*}$ folgt wenn jede Formel $\begin{eqnarray*} \theta \in \Theta \end{eqnarray*}$ aus $\begin{eqnarray*} \Phi \end{eqnarray*}$ folgt. Sei $\begin{eqnarray*} (\Phi_i)_{i \in \mathbb N} \end{eqnarray*}$ eine unendliche Folge von erfüllbaren Formelmengen $\begin{eqnarray*} \Phi_i \end{eqnarray*}$ , so dass $\begin{eqnarray*} \Phi_{i+1} \vDash \Phi_i \end{eqnarray*}$ und $\begin{eqnarray*} \Phi_{i} \not \vDash \Phi_{i+1} \end{eqnarray*}$ für alle i aus |N gilt.

Sei $\begin{eqnarray*} \Psi \end{eqnarray*}$ eine erfüllbare Formelmenge, so dass $\begin{eqnarray*} \Psi \vDash \Phi_i \end{eqnarray*}$ für alle i aus |N gilt.
(a) Zeigen Sie, dass die Menge $\begin{eqnarray*} \Psi \end{eqnarray*}$ existiert.
(b) Zeigen Sie, dass keine endliche Formelmenge $\begin{eqnarray*} \Theta \end{eqnarray*}$ existiert, so dass $\begin{eqnarray*} \Psi \vDash \Theta \end{eqnarray*}$ und $\begin{eqnarray*} \Theta \vDash \Psi \end{eqnarray*}$ gilt.

Erstmal nur die a)
Ich habe mir überlegt $\begin{eqnarray*} \Psi = \bigcup_{i \in \mathbb N} {\Phi_i} \end{eqnarray*}$ zu wählen.
Dann würde Psi doch alle Phi_i erfüllen. Aber ich kann nicht recht begründen, warum Psi auch erfüllbar sein muss.

Bin ich auf dem richtigen Dampfer?

Dankeschön!

13.05.2009, 20:30

papahuhn

Auf diesen Beitrag antworten »

RE: Existenz von Formelmengen
Ist schon was her bei mir, musst mal schauen, ob das Sinn ergibt.
Angenommen, $\begin{eqnarray*} \bigcup_{i \in \mathbb N} {\Phi_i} \end{eqnarray*}$ wäre unerfüllbar, dann gibt es (Kompaktheitssatz) ein endliches unerfüllbares $\begin{eqnarray*} \Phi \subseteq \bigcup_{i \in \mathbb N} {\Phi_i} \end{eqnarray*}$ und damit existiert ein $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} \Phi \subseteq \bigcup_{i=1}^n {\Phi_i} \end{eqnarray*}$ . Wie sieht es da mit der Erfüllbarkeit aus? Es gilt $\begin{eqnarray*} \Phi_{n+1} \vDash \bigcup_{i=1}^n {\Phi_i} \end{eqnarray*}$ (warum?). Was ergibt sich daraus für $\begin{eqnarray*} \Phi_{n+1} \end{eqnarray*}$ ?

13.05.2009, 23:13

aRo

Auf diesen Beitrag antworten »

RE: Existenz von Formelmengen
Guten Abend papahuhn! :-)

Zitat:

Original von papahuhn
Es gilt $\begin{eqnarray*} \Phi_{n+1} \vDash \bigcup_{i=1}^n {\Phi_i} \end{eqnarray*}$ (warum?)

Ich fürchte das ist die große Quizfrage. Denn mir ist das leider nicht klar. Zwar folgt jedes einzelne Phi_i aus Phi_{n+1}, aber das heißt doch nicht dass die gesamte Vereinigung auch aus Phi_i folgen muss?

Zitat:

Original von papahuhn
Was ergibt sich daraus für $\begin{eqnarray*} \Phi_{n+1} \end{eqnarray*}$ ?

Wenn obiges gelten würde, dann würde gelten $\begin{eqnarray*} \Phi_{n+1} \vDash \Phi \end{eqnarray*}$ . Weil Phi_{n+1} erfüllbar ist, also dann im Widerspruch zur Annahme.

13.05.2009, 23:36

papahuhn

Auf diesen Beitrag antworten »

RE: Existenz von Formelmengen

Zitat:

Original von aRo
Ich fürchte das ist die große Quizfrage. Denn mir ist das leider nicht klar. Zwar folgt jedes einzelne Phi_i aus Phi_{n+1}, aber das heißt doch nicht dass die gesamte Vereinigung auch aus Phi_i folgen muss?

Du müsstest zeigen:
Wenn $\begin{eqnarray*} A \vDash B \vDash C \end{eqnarray*}$ dann $\begin{eqnarray*} A \vDash B \cup C \end{eqnarray*}$ , für Formelmengen $\begin{eqnarray*} A, B, C \end{eqnarray*}$ . Der Rest ist Induktion.

13.05.2009, 23:57

aRo

Auf diesen Beitrag antworten »

hmm...ich denke du hast recht.

z.z.: Wenn $\begin{eqnarray*} A \vDash B \vDash C \Rightarrow A \vDash B \cup C \end{eqnarray*}$

Angenommen $\begin{eqnarray*} A \not \vDash B \cup C \end{eqnarray*}$ . Dann ex Interpretation J mit $\begin{eqnarray*} J \vDash A \end{eqnarray*}$ aber $\begin{eqnarray*} J \not \vDash B \cup C \end{eqnarray*}$ . D.h. ex $\begin{eqnarray*} x \in B \cup C \end{eqnarray*}$ mit J(x)=0.

Ist x aus B, dann Widerspruch, weil J A erfüllt und B aus A folgt.
Ist x aus C, dann Widerspruch, weil:
Jedes Modell von A ist auch Modell von B. Jedes Modell von B ist auch Modell von C laut Voraussetzung => Jedes Modell von A ist auch Modell von C.
J ist Modell von A aber nicht von C -> Widerspruch!

Also gilt die Aussage.

Cool, damit hätte ich die a) gezeigt, denk ich.

zur b)
Da gibt es noch einen Hinweis, von dem ich leider 1. nicht weiß wie man ihn zeigt und 2. auch gar nicht recht verstehe, was er mir bringen würde.

Hier der Hinweis:
Zeigen Sie zuerst, dass eine Folge $\begin{eqnarray*} (\Phi'_i)_{i \in \mathbb N} \end{eqnarray*}$ existiert, so dass für alle i aus |N die Formelmengen $\begin{eqnarray*} \Phi'_i \end{eqnarray*}$ und $\begin{eqnarray*} \Phi_i \end{eqnarray*}$ die gleichen Modelle haben und Folgendes gilt:
$\begin{eqnarray*} \Phi'_{i+1} \vDash \Phi'_i, \Phi'_i \not \vDash \Phi'_{i+1} \mbox{ und } \Phi'_i \subset \Phi'_{i+1} \end{eqnarray*}$

hmm... verwirrt

14.05.2009, 12:23

papahuhn

Auf diesen Beitrag antworten »

Ich denke, dass $\begin{eqnarray*} \Phi'_i := \bigcup_{k=1}^i~\Phi_k \end{eqnarray*}$ die Forderungen erfüllt. Inwiefern das hilft, weiß ich gerade leider auch nicht, sorry.

14.05.2009, 14:53

aRo

Auf diesen Beitrag antworten »

:-)

genau das habe ich heute morgen auch noch gemacht. Die Forderungen habe ich glaube ich auch bewiesen, aber den Beweis dennoch nicht zu Ende geführt, weil ich eben den Hinweis nicht recht verwerten konnte.

Naja, Montag werd ichs erfahren!

Neue Frage »

Antworten »

Existenz von Formelmengen

Verwandte Themen