Löwenheim Skolem ?! < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:52 So 18.01.2015 | | Autor: | Steffi88 |
| Aufgabe | | Zeigen Sie, dass jede Theorie T (der Prädikatenlogik erster Stufe), die ein unendliches Modell besitzt, auch ein überabzählbares Modell besitzt. |
Hallo zusammen,
dies ist eine weitere Klausuraufgabe bei der ich keinen Ansatz finde. Soweit ich herausgefunden habe ist es eigentlich eine Form des Satzes von Löwenheim. Leider finde ich überhaupt keinen Beweisansatz hierfür und stecke total fest :/ den Hinweis den ich bekommen habe vom Tutor hilft mir da leider auch überhaupt gar nicht weiter :*/ (siehe unten)
Kann mir vielleicht jemand helfen?
Von meinem Tutor habe ich noch den Hinweis bekommen:
Erweitere zunächst die Sprache der Theorie um Konstantensymbole [mm] c_{r} [/mm] für jedes r [mm] \in \IR. [/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:19 So 18.01.2015 | | Autor: | hippias |
Du koenntest nun noch Deine Theorie um die Saetze [mm] $\neg c_{r}\equiv c_{r'}$, [/mm] wobei $r [mm] \neq [/mm] r'$, zu einer Theorie $T'$ erweitern. Ist Dir klar, dass ein Modell von $T'$ Deine Aufgabe loesen wuerde?
Um die Existenz eines solchen Modells herzuleiten bemuehe den Endlichkeitssatz (Kompaktheitssatz).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:22 So 18.01.2015 | | Autor: | Steffi88 |
hmm, danke erstmal für die schnelle Antwort. So ganz verstehe ich es leider noch nicht :/
Ich muss meine Theorie T erweitern mit dem was du geschrieben hast und dann den Kompaktheitssatz anwenden? Man braucht also Löwenheim und Skolem gar nicht?
Das mit dem Kompaktheitssatz ist mir irgendwie nicht so ganz einleuchtend sorry.
Er besagt ja:
Sei S eine unendliche Menge von geschlossenen Formeln einer Sprache der Prädikatenlogik erster Stufe. Ist jede endliche Teilmenge von S erfüllbar, so ist S erfüllbar??
Oder bin ich hier falsch? Nur wie hilft mir das bei meiner Aufgabe...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:30 So 18.01.2015 | | Autor: | hippias |
> hmm, danke erstmal für die schnelle Antwort. So ganz
> verstehe ich es leider noch nicht :/
> Ich muss meine Theorie T erweitern mit dem was du
> geschrieben hast und dann den Kompaktheitssatz anwenden?
> Man braucht also Löwenheim und Skolem gar nicht?
Wie lautet denn der Satz von Löwenheim-Skolem?
>
> Das mit dem Kompaktheitssatz ist mir irgendwie nicht so
> ganz einleuchtend sorry.
> Er besagt ja:
> Sei S eine unendliche Menge von geschlossenen Formeln
> einer Sprache der Prädikatenlogik erster Stufe. Ist jede
> endliche Teilmenge von S erfüllbar, so ist S erfüllbar??
Naja, ich denke ihr habt ihn kaum als Frage formuliert, aber sonst ganz brauchbar.
>
> Oder bin ich hier falsch? Nur wie hilft mir das bei meiner
> Aufgabe...
Wie bereits erwaehnt: Damit kannst Du die Existenz eines Modells zu der vom mir vorgeschlagenen Theorie beweisen. Versuche es einma: Sei [mm] $X\subseteq [/mm] T'$ endlich. Zu zeigen: Es gibt ein Modell von $X$...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:04 So 18.01.2015 | | Autor: | Steffi88 |
Sorry, stehe immernoch auf dem Schlauch :( tut mir echt leid das ich mich so doof anstelle...
Satz von Löwenheim findet man viele Formulierung, bei uns im Script ist es diese: Ist T eine konsistente Theorie in einer abzählbaren Sprache, ¨
so besitzt T ein abzählbares Modell.
Komme einfach nicht rein in die Aufgabe, also vom Ansatz... Irgendwie eine komische Aufgabe...
> Wie bereits erwaehnt: Damit kannst Du die Existenz eines
> Modells zu der vom mir vorgeschlagenen Theorie beweisen.
> Versuche es einma: Sei [mm]X\subseteq T'[/mm] endlich. Zu zeigen: Es
> gibt ein Modell von [mm]X[/mm]...
Ja, nach dem Satz könnte man irgendwie zeigen das jede endliche Teilmenge X erfüllbar ist und somit wäre es komplett erfülllbar?!?
Ohje :/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:30 So 18.01.2015 | | Autor: | hippias |
> Sorry, stehe immernoch auf dem Schlauch :( tut mir echt
> leid das ich mich so doof anstelle...
> Satz von Löwenheim findet man viele Formulierung, bei uns
> im Script ist es diese: Ist T eine konsistente Theorie in
> einer abzählbaren Sprache, ¨
> so besitzt T ein abzählbares Modell.
Aha. Und weil Du ein ueberabzaehlbares Modell finden sollst, ist das ja wohl kaum der fuer Dein Problem richtige Satz.
>
> Komme einfach nicht rein in die Aufgabe, also vom Ansatz...
> Irgendwie eine komische Aufgabe...
>
> > Wie bereits erwaehnt: Damit kannst Du die Existenz eines
> > Modells zu der vom mir vorgeschlagenen Theorie beweisen.
> > Versuche es einma: Sei [mm]X\subseteq T'[/mm] endlich. Zu zeigen: Es
> > gibt ein Modell von [mm]X[/mm]...
>
> Ja, nach dem Satz könnte man irgendwie zeigen das jede
> endliche Teilmenge X erfüllbar ist und somit wäre es
> komplett erfülllbar?!?
Vielleicht koenntest Du Dich einfach einmal konzentrieren und nicht nur irgendwelche Fuellworte in die Tastatur kloppen. Nach dem Endlichkeitssatz kannst Du nicht "irgendwie zeigen das jede endliche Teilmenge X erfüllbar ist".
Wenn Du, Steffi88, gezeigt hast, dass jede endliche Teilmenge der Theorie erfuellbar ist, dann kannst nach dem Endlichkeitssatz schlussfolgern, dass die gesamte Theorie erfuellbar ist.
Nocheinmal: Ist Dir klar, dass Deine Aufgabe geloest ist, wenn Du ein Modell fuer die nach meinem Vorschlag erweiterte Theorie gefunden hast?
Auch hier nocheinmal: Theorie $T$ hat unendliche Modell $A$. Setze $T':= [mm] T\cup\underbrace{\{\neg c_{r}\equiv c_{r'}|r,r'\in\IR, r\neq r'\}}_{=:C}$. [/mm] Nun sei [mm] $X\subseteq [/mm] T'$ endlich. Ueberlege Dir nun, wieso $X$ erfuellbar ist. Tip: $A$ "erfuellt" $X$.
>
> Ohje :/
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:38 Di 20.01.2015 | | Autor: | Steffi88 |
vielen Dank für deine viele Mühe mir das näher zu bringen!!! Nicht so ganz leicht, dass weiss ich :D
Habe am Wochenende nochmal mit deinem Vater versucht der Aufgabe Herr zu werden, leider ohne Erfolg (er ist auch schon etwas länger aus der uni...). Mir ist einfach nicht klar was ich hier machen muss...
Ich habe eine Theorie T mit unendlichen Modellen A bedeutet ja das unter A jede Formelmenge "wahr" wird) Nun sagst du "Setze $ T':= [mm] T\cup\underbrace{\{\neg c_{r}\equiv c_{r'}|r,r'\in\IR, r\neq r'\}}_{=:C} [/mm] $
und sei $ [mm] X\subseteq [/mm] T' $ endlich". Da die endliche Teilmenge [mm] X\subseteq [/mm] T' ein Modell hat ist sie auch erfüllbar und nach dem endlichkeitssatz das auch die gesamte Theorie erfüllbar ist. richtig?
Nun haben wir eine erfüllbare Theorie die ein unendliches Modell hat, wie hilft uns das aber weiter um zu zeigen das sie auch ein überabzählbares Modell besitzt?
Bin glaube ich einfach zu doof .... Könntest du mir noch ein bisschen mehr helfen? Tut mir wirklich leid, würde die Aufgabe einfach gerne verstehen und lösen, ist immerhin ein ziemlich wichtiger Satz :/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:36 Mi 21.01.2015 | | Autor: | hippias |
> vielen Dank für deine viele Mühe mir das näher zu
> bringen!!! Nicht so ganz leicht, dass weiss ich :D
Kein Problem.
>
> Habe am Wochenende nochmal mit deinem Vater versucht der
> Aufgabe Herr zu werden, leider ohne Erfolg (er ist auch
> schon etwas länger aus der uni...). Mir ist einfach nicht
> klar was ich hier machen muss...
>
> Ich habe eine Theorie T mit unendlichen Modellen A bedeutet
> ja das unter A jede Formelmenge "wahr" wird)
Sage besser: $A$ erfuellt $T$; oder jeder Satz aus $T$ gilt in $A$ etc.
> Nun sagst du
> "Setze [mm]T':= T\cup\underbrace{\{\neg c_{r}\equiv c_{r'}|r,r'\in\IR, r\neq r'\}}_{=:C}[/mm]
>
> und sei [mm]X\subseteq T'[/mm] endlich". Da die endliche Teilmenge
> [mm]X\subseteq[/mm] T' ein Modell hat ist sie auch erfüllbar
Das ist das Problem: Wieso sagst Du die endliche Teilmenge hat ein Modell? Das musst Du beweisen! Da $A$ das einzige Modell weit und breit ist, das Dir zur Verfuegung steht, solltest Du versuchen es so anzupassen, dass es auf $T'$ anwendbar wird.
> und
> nach dem endlichkeitssatz das auch die gesamte Theorie
> erfüllbar ist. richtig?
Wenn gezeigt ist, dass jede endliche Teilmenge ein Modell hat, dann kannst Du den Endlichkeitssatz anwenden.
>
> Nun haben wir eine erfüllbare Theorie die ein unendliches
> Modell hat, wie hilft uns das aber weiter um zu zeigen das
> sie auch ein überabzählbares Modell besitzt?
Ich weiss nicht, weshalb Du Dich wiederholt weigerst mir die Frage zu beantworten, ob Dir klar ist, dass ein Modell der erweiterten Theorie ueberabzaehlbar ist. Sei es drum. Mache Dir zuerst klar, dass dies der Fall ist. Dann sehen wir weiter.
> Bin glaube ich einfach zu doof .... Könntest du mir noch
> ein bisschen mehr helfen? Tut mir wirklich leid, würde die
> Aufgabe einfach gerne verstehen und lösen, ist immerhin
> ein ziemlich wichtiger Satz :/
Das ist loeblich, und da helfe ich gerne. Aber die Punkte, die eventuell fuer die Loesung des Problems als Belohnung ausgesetzt sind, musst Du Dir selber verdienen. Alles andere waere unfair denen gegenueber, die diese Aufgabe selbst loesen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:47 Mi 21.01.2015 | | Autor: | Steffi88 |
> Ich weiss nicht, weshalb Du Dich wiederholt weigerst mir
> die Frage zu beantworten, ob Dir klar ist, dass ein Modell
> der erweiterten Theorie ueberabzaehlbar ist. Sei es drum.
> Mache Dir zuerst klar, dass dies der Fall ist. Dann sehen
> wir weiter.
So ganz klar ist mir das leider nicht. Ich muss also nun ersteinmal eine Struktur aufstellen welche T' immer erfüllt. Aber was meinst du mit A anpassen? Ich weiss ja eigentlich gar nichts von A. Ist es nicht immer so das bei einer endlichen Teilmenge von einer Theorie mit einem Modell auch immer ein Modell besitzt?
> Das ist loeblich, und da helfe ich gerne. Aber die Punkte,
> die eventuell fuer die Loesung des Problems als Belohnung
> ausgesetzt sind, musst Du Dir selber verdienen. Alles
> andere waere unfair denen gegenueber, die diese Aufgabe
> selbst loesen.
>
Hmm, Punkte gibt es leider hier keine :) Die Aufgabe habe ich von einem Klausurvorbereitungsblatt für die Logik Vorlesung hier im schönen Tübingen :) Deshalb interessiert mich auch mehr der Weg zur Lösung, leider finde ich ihn nicht. Sowas in der Art, wahrscheinlich nicht der Beweis aber eine Aufgabe dazu, kommt zu 96,5% (aussage des profs) in der Klausur dran...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:36 Do 22.01.2015 | | Autor: | hippias |
> > Ich weiss nicht, weshalb Du Dich wiederholt weigerst mir
> > die Frage zu beantworten, ob Dir klar ist, dass ein Modell
> > der erweiterten Theorie ueberabzaehlbar ist. Sei es drum.
> > Mache Dir zuerst klar, dass dies der Fall ist. Dann sehen
> > wir weiter.
>
> So ganz klar ist mir das leider nicht. Ich muss also nun
> ersteinmal
Nein, Du solltest Dir zuerst klarmachen, dass ein Modell fuer $T'$ zu finden Dein Problem loest.
> eine Struktur aufstellen welche T' immer
> erfüllt.
Immer erfuellt? Was soll das? Kennst Du Modelle, die Saetze nur zu bestimmten Tageszeiten erfuellen?
> Aber was meinst du mit A anpassen?
Waere nett, wenn Du Dir darueber Gedanken machen wuerdest. Jedenfalls wird $A$ so wie es gegeben ist, die Theorie $T'$ nicht ohne weiteres erfuellen.
> Ich weiss ja
> eigentlich gar nichts von A. Ist es nicht immer so das bei
> einer endlichen Teilmenge von einer Theorie mit einem
> Modell auch immer ein Modell besitzt?
Diesen Satz verstehe ich nicht.
Mein Vorschlag: Gegeben ist Symbolmenge $S$. Es sei $T$ eine $S$-Theorie und $A$ ein $S$-Modell von $T$, das ein abzaehlbar unendliches Universum hat.
1. Ich erweitere $S$ um die Konstantensymbole [mm] $c_{r}$, $r\in \IR$, [/mm] zu $S'$.
2. Ich bilde sie $S'$-Theorie $T':= [mm] T\cup\{\neg c_{r}\equiv c_{s}|r\neq s\}$.
[/mm]
3. Ueberlege Dir folgende Aussage: Es sei $M$ ein $S'$-Modell von $T'$ ist mit Universum $X$. Dann gibt es eine injektive Abbildung [mm] $f:\IR\to [/mm] X$.
4. Beweise nun: Die Restriktion der $S'$-Struktur $M$ zu der $S$-Struktur $M'$ erfuellt $T$.
3. und 4. liefern also die Existenz eines ueberabzaehlbaren Modells. Vorlaeufiges Fazit: Es genuegt die Existenz eines Modells von $T'$ zu zeigen.
Die Konstruktion von $M$ soll mit dem Endlichkeitssatz geschehen.
5. Sei [mm] $Y\subseteq [/mm] T'$ endlich. Zeige, dass Du die $S$-Struktur $A$ so anpassen kannst, dass Du ein Modell von $Y$ erhaelst.
6. Der Endlichkeitssatz liefert Dir ein Modell von $T'$, welches nach 3. und 4. den Satz beweist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:19 Do 22.01.2015 | | Autor: | Steffi88 |
Guten morgen,
mal wieder danke, leider verstehe ich es immer noch nicht :/ Fühl mich richtig doof...
> 4. Beweise nun: Die Restriktion der $ S' $-Struktur $ M $ zu der $ S $-
> Struktur $ M' $ erfuellt $ T $.
Eine Restriktion der Struktur? Das habe ich leider noch nie gehört und google findet dazu auch nicht so viel.
Zu meinem Satz den du nicht verstehst, ist es nicht so das jede Theorie T ein Modell besitzt wenn jede endliche Teilmenge T' ein Modell enthält? Und mir ist immernoch nichr klar wie man mit deinen Tipps darauf kommt das jede Theorie T die ein unendliches Modell hat auch ein überabzählbares Modell hat? Nach dem endlichkeitssatz weiss ich ja nur das die Theorie erfüllbar ist, aber nicht mit welcher Art von Modell?!
So wie du es aufgeschrieben hast klingt es ein bisschen wie der Kompaktheitssatz mit dem man zeigen kann: "Eine Theorie T besitzt genau dann ein Modell, wenn jede endlich axiomatisierte Teiltheorie von T ein Modell besitzt"
Hierzu habe ich auch einen Beweis, der mir auch nicht so ganz einleuchtet :/
Bin ganz verzweifelt, die restlichen VorbereitungsAufgaben habe ich alle einigermaßen hinbekommen und die einzige die fast sicher morgen in der Klausur dran kommt komme ich einfach nicht weiter :*(
Danke nochmal für deine super viele Mühe, aber hier stehe ich wohl komplett auf dem Schlauch... Mir leuchtet einfach nicht ein wie man hier vorgeht... Habe mit der Aufgabe nun schon sooo viele Stunden verbracht, hilft alles nichts :/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:44 Do 22.01.2015 | | Autor: | hippias |
> Guten morgen,
>
> mal wieder danke, leider verstehe ich es immer noch nicht
> :/ Fühl mich richtig doof...
> > 4. Beweise nun: Die Restriktion der [mm]S' [/mm]-Struktur [mm]M[/mm] zu
> der [mm]S [/mm]-
> > Struktur [mm]M'[/mm] erfuellt [mm]T [/mm].
>
> Eine Restriktion der Struktur? Das habe ich leider noch nie
> gehört und google findet dazu auch nicht so viel.
Ich meinte das Redukt der Struktur. Salopp gesprochen, schmeissen wir die Konstanten wieder raus, weil wir eine $S$-Struktur, und keine $S'$-Struktur, brauchen.
> Zu meinem Satz den du nicht verstehst, ist es nicht so das
> jede Theorie T ein Modell besitzt wenn jede endliche
> Teilmenge T' ein Modell enthält?
Du meinst vermutlich "wenn jede endliche Teilmenge T' ein Modell hat"; ja, das ist der Kompaktheitssatz.
> Und mir ist immernoch
> nichr klar wie man mit deinen Tipps darauf kommt das jede
> Theorie T die ein unendliches Modell hat auch ein
> überabzählbares Modell hat?
Ja, das scheint der Fall zu sein.
> Nach dem endlichkeitssatz
> weiss ich ja nur das die Theorie erfüllbar ist, aber nicht
> mit welcher Art von Modell?!
Arten von Modellen sagen mir nun wieder nichts.
>
> So wie du es aufgeschrieben hast klingt es ein bisschen wie
> der Kompaktheitssatz mit dem man zeigen kann: "Eine
> Theorie T besitzt genau dann ein Modell, wenn jede endlich
> axiomatisierte Teiltheorie von T ein Modell besitzt"
> Hierzu habe ich auch einen Beweis, der mir auch nicht so
> ganz einleuchtet :/
>
> Bin ganz verzweifelt, die restlichen VorbereitungsAufgaben
> habe ich alle einigermaßen hinbekommen und die einzige die
> fast sicher morgen in der Klausur dran kommt komme ich
> einfach nicht weiter :*(
>
> Danke nochmal für deine super viele Mühe, aber hier stehe
> ich wohl komplett auf dem Schlauch... Mir leuchtet einfach
> nicht ein wie man hier vorgeht... Habe mit der Aufgabe nun
> schon sooo viele Stunden verbracht, hilft alles nichts :/
Viel Erfolg fuer morgen!
|
|
|
|
