Zeigen mit Endlichkeitssatz

12.11.2009, 20:40

EvilTwin

Zeigen mit Endlichkeitssatz

Hey

also ich muss eine Aufgabe per Endlichkeitssatz beweisen.

Zitat:

Aufgabe
Sei M eine undendliche Formelmenge und F eine Formel. Zeigen Sie, dass die beiden folgenden Aussagen äquivalent sind:
i) M l= F
ii) Es gibt eine endliche Teilmenge N c* M, für die gilt: N l= F
(c* = echte Teilmenge)

Also das ganze von i) => ii) zu zeigen ist ja eigentlich kein Problem...ich frage mich nur ob es nun reicht hinzuschreiben:

Wenn (M l= F) dann gilt nach Endlichkeitssatz (Eine Formelmenge X ist genau dann erfüllbar, wenn jede endliche Teilmenge von X erfüllbar ist), dass ii) es auch eine echte, endliche Teilmenge aus M gibt, für welche gilt: (N l= F).
Reicht das nun?

Und wie zeige ich das in die andere Richtung? Also ich hab beim stöbern im Netz folgendes gefunden:

Zitat:

Bemerkung: Es gilt M1 c* M2 c* M3 ...

heisst das, dass wenn N praktisch dieses M1 ist und damit auch alle anderen Teilmengen l= M sind?? Oder nehm ich das aus dem Zusammenhang?
(Quelle: http://www.fmi.uni-stuttgart.de/szs/teaching/ws0607/logik/folien/endlich-4.pdf)

Danke schonmal im Voraus!
Gruß EvilTwin!!

13.11.2009, 12:41

Urza

Auf diesen Beitrag antworten »

Also ihr habt bereits einen Endlichkeitssatz der Form ("Eine Formelmenge X ist genau dann erfüllbar, wenn jede endliche Teilmenge von X erfüllbar ist") bewiesen und jetzt willst du damit die angegebene Aufgabe lösen?

Auf jeden Fall ist (ii)=>(i) trivial. Anscheinend ist dir das nicht klar, also nehme ich an (tut mir leid wenn ich mich irre!), dass du die Bedeutung des Zeichens " $\begin{eqnarray*} \models \end{eqnarray*}$ " nicht richtig verstanden hast.

Also die Definition, die ich kenne:
Wenn $\begin{eqnarray*} \mathcal{A} \end{eqnarray*}$ eine Struktur (über einer gewissen Sprache/einem gewissen Alphabet) ist und $\begin{eqnarray*} \Phi \end{eqnarray*}$ eine Formelmenge (über ebendieser Sprache/ebendiesem Alphabet), dann bedeutet $\begin{eqnarray*} \mathcal{A}\models \Phi \end{eqnarray*}$ (" $\begin{eqnarray*} \mathcal{A} \end{eqnarray*}$ ist ein Modell von $\begin{eqnarray*} \Phi \end{eqnarray*}$ "), dass jede Formel $\begin{eqnarray*} \varphi\in\Phi \end{eqnarray*}$ in $\begin{eqnarray*} \mathcal{A} \end{eqnarray*}$ erfüllt/wahr ist.

Ist $\begin{eqnarray*} \Psi \end{eqnarray*}$ eine weitere Formelmenge, dann bedeutet $\begin{eqnarray*} \Psi\models\Phi \end{eqnarray*}$ ("Aus $\begin{eqnarray*} \Psi \end{eqnarray*}$ folgt $\begin{eqnarray*} \Phi \end{eqnarray*}$ "), dass für jede Struktur $\begin{eqnarray*} \mathcal{A} \end{eqnarray*}$ mit $\begin{eqnarray*} \mathcal{A}\models\Psi \end{eqnarray*}$ auch $\begin{eqnarray*} \mathcal{A}\models\Phi \end{eqnarray*}$ gilt.

Stimmt das mit deiner Definition überein? Ist dir jetzt (ii)=>(i) klargeworden?

13.11.2009, 16:09

EvilTwin

Auf diesen Beitrag antworten »

Öhm sorry aber der Zeichenhaufen verwirrt mich jetzt. Ich dachte halt, dass wenn F l= M ist bedeutet das, dass eine Belegung für die F wahr ist diese Belegung auch M wahr macht....oder nicht???

PS: Könnt ihr mit bitte noch n bisschen was dazu sagen? Das geht mir nicht ganz rein...

Zitat:

Bemerkung: Es gilt M1 c* M2 c* M3 ...

Danke auf jeden Fall schonmal!
Gruß
ET

14.11.2009, 07:12

Urza

Auf diesen Beitrag antworten »

Zitat:

Original von EvilTwin
Öhm sorry aber der Zeichenhaufen verwirrt mich jetzt. Ich dachte halt, dass wenn F l= M ist bedeutet das, dass eine Belegung für die F wahr ist diese Belegung auch M wahr macht....oder nicht???

Habt ihr nicht definiert, was eine Struktur ist? Geht es nicht um Prädikatenlogik? Schreib doch mal eure Definition des Zeichens $\begin{eqnarray*} \models \end{eqnarray*}$ hin (eine exakte werdet ihr ja wohl bekommen haben!).

15.11.2009, 09:34

EvilTwin

Auf diesen Beitrag antworten »

Hey,

das ist ja das Problem, es gab niemals eine wirkliche Definition! Einmal in der Vortragsübung wurde es kurz angesprochen und ich glaube einfach, dass es "semantisch gleich" bedeutet...habe aber keine wirkliche Ahnung. Was genau ist denn eure Definition?

Und jetzt mal unabhängig von der Bedeutung vom diesem "l=". Ich weiss nicht wie ich bei einem "Zeigen Sie die Äquivaenz..." vorgehen soll, bei welcher ich nicht einfach umformen kann. Bitte ein wenig Hilfe!

Danke nochmal
Gruß ET

15.11.2009, 09:42

kiste

Auf diesen Beitrag antworten »

Nanana nicht lügen, lieber das Skript genau durchlesen.
Auf Seite 56 steht die Definition, welche natürlich dieselbe ist die Urza vorgeschlagen hat.
Mit ein wenig Skript lesen ist die Aufgabe übrigens auch sehr einfach

15.11.2009, 09:48

EvilTwin

Auf diesen Beitrag antworten »

Wir haben zum einen die Folien, mit welchen die Vorlesung gemacht wird. Und dann noch so ein Skript bei dem ich aber absolut nichts verstehe. Das is so komisch geschrieben, dass garnix geht. Aber wenn ihr das sagt dann schau ich einfach mal rein!

Danke
Gruß ET

15.11.2009, 09:53

kiste

Auf diesen Beitrag antworten »

Ich meine die Folien, ein offizielles Skript kenne ich nicht, mhh? (kannst mir den Link dazu schicken?)

Aber die Folien zu lesen wird erstmal eine gute Idee sein, das ist das erste was du machen solltest wenn du Aufgaben bekommst.

15.11.2009, 12:56

EvilTwin

Auf diesen Beitrag antworten »

Also habe in das Skript geschaut und tatsächlich was gefunden! ^_^

Naja und F l= M heisst demnach, dass für jede Belegung die für F passend ist, diese auch zu M passt.
Passend: Sei F eine Formel und A eine Belegung.
A heißt passend zu F, falls sie auf allen Atomen in F definiert ist.

Also...ist A(M) auch A(F), weil F eben eine echte Teilmenge von M ist. Nein?

Danke nochmals
Gruß ET

15.11.2009, 13:04

kiste

Auf diesen Beitrag antworten »

Nein so hat die Definition nicht gelautet. Du musst aufmerksamer lesen.
Dort steht: "...falls für jede Belegung die sowohl für F als auch für G passend ist gilt: ..."

Zur Aufgabenlösung selbst darf ich leider nichts sagen Augenzwinkern

Neue Frage »

Antworten »

Zeigen mit Endlichkeitssatz

Verwandte Themen