Tarski's chain-lemma < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Angenommen [mm] $\mathcal{M}=(M,\dotso)$ [/mm] ist eine L-Struktur, [mm] $(I,\leq)$ [/mm] ist eine lineare Ordnung und [mm] $(M_i|i\in [/mm] I)$ ist eine Folge von L-Strukturen von [mm] $\mathcal{M}$ [/mm] mit [mm] $\mathcal{M}_i=(M_i,\dotso)$ [/mm] und [mm] $M=\bigcup_{i\in I} M_i$.
[/mm]
Wenn [mm] $M_i\prec M_j$ [/mm] für [mm] $i,j\in [/mm] I$ mit [mm] $i\leq [/mm] j$, dann gilt [mm] $\mathcal{M}_i\prec\mathcal{M}$ [/mm] für alle [mm] $i\in [/mm] I$. |
Hallo,
ich habe eine Frage zu dieser Aufgabe.
Für den Beweis möchte ich Tarski's Test benutzen. Demnach sind äquivalent:
Angenommen [mm] \mathcal{M}=(M,\dotso) [/mm] ist eine Substruktur von [mm] $\mathcal{N}=(N,\dotso)$
[/mm]
1) [mm] $\mathcal{M}$ [/mm] ist eine elementare Substruktur von [mm] $\mathcal{N}$.
[/mm]
2) Für alle L-Formeln [mm] $\varphi(x;x_0,\dotso, x_n)$ [/mm] und [mm] $a_0,\dotso, a_n\in [/mm] M$ gilt, wenn es ein [mm] $b\in [/mm] N$ gibt mit [mm] $\mathcal{N}\models\varphi[b,a_0,\dotso,a_n]$, [/mm] dann gibt es ein [mm] $a\in [/mm] M$ mit [mm] $\mathcal{N}\models\varphi[a,a_0,\dotso,a_n]$
[/mm]
Dies würde ich hier gerne verwenden.
Ich möchte also zeigen, dass 2) gilt.
Ich hätte vorerst aber ein paar Fragen. Nämlich zu der Menge $I$. Dies ist ja eine Indexmenge. Geht man bei Indexmengen immer davon aus, dass [mm] $I\subset\mathbb{Z}$ [/mm] ist?
Des Weiteren sollte diese Aussage erst interessant sein, wenn I eine unendliche Indexmenge ist, also kein größtes (oder auch kleinstes) Element hat.
Zum Beweis:
Mit der angesprochenen Äquivalenz kommt mir der Beweis eigentlich "trivial" vor, weshalb ich bestimmt irgendwas übersehe, bzw. es einen Harken geben muss...
Zu erst einmal ist klar, dass [mm] $M_i\subseteq [/mm] M$ für alle [mm] $i\in [/mm] I$ gilt.
Nun sind [mm] $\mathcal{M}_i$ [/mm] und [mm] $\mathcal{M}_j$ [/mm] für [mm] $i\leq [/mm] j$ elementar äquivalent. Also Formeln die in [mm] $\mathcal{M}_i$ [/mm] gelten, gelten auch in [mm] $\mathcal{M}_j$. [/mm] Währe $I$ nun eine endliche Menge, dann könnte man $j$ maximal wählen und wäre fertig.
Allgemein ist ja folgendes zu tun:
Wenn ich zeigen kann, dass für alle L-Formeln [mm] $\varphi(x; x_0,\dotso, x_n)$ [/mm] und alle [mm] $a_0,\dotso, a_n\in M_i$ [/mm] ein [mm] $b\in M_i$ [/mm] existiert mit [mm] $\mathcal{M}_i\models\varphi[b,a_0,\dotso,a_n]$ [/mm] dann gibt es ein [mm] $a\in [/mm] M$ mit [mm] $\mathcal{M}\models\varphi[a,a_0,\dotso,a_n]$.
[/mm]
Und die Existenz eines solchen a's ist zu zeigen.
Was ich mir aber denke ist, dass ich einfach a=b wählen kann, weil [mm] $b\in [/mm] M$, da [mm] $b\in M_i$ [/mm] und [mm] $M_i\subseteq [/mm] M$.
Es kann aber wohl kaum so einfach sein...
Was ist also der Harken bei dieser Aufgabe?
Über Hilfestellung und Korrekturen jeglicher Art würde ich mich sehr freuen.
Vielen Dank im voraus.
mfg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:16 So 03.05.2015 | | Autor: | hippias |
> Angenommen [mm]\mathcal{M}=(M,\dotso)[/mm] ist eine L-Struktur,
> [mm](I,\leq)[/mm] ist eine lineare Ordnung und [mm](M_i|i\in I)[/mm] ist eine
> Folge von L-Strukturen von [mm]\mathcal{M}[/mm] mit
> [mm]\mathcal{M}_i=(M_i,\dotso)[/mm] und [mm]M=\bigcup_{i\in I} M_i[/mm].
>
> Wenn [mm]M_i\prec M_j[/mm] für [mm]i,j\in I[/mm] mit [mm]i\leq j[/mm], dann gilt
> [mm]\mathcal{M}_i\prec\mathcal{M}[/mm] für alle [mm]i\in I[/mm].
>
> Hallo,
>
> ich habe eine Frage zu dieser Aufgabe.
>
> Für den Beweis möchte ich Tarski's Test benutzen. Demnach
> sind äquivalent:
>
> Angenommen [mm]\mathcal{M}=(M,\dotso)[/mm] ist eine Substruktur von
> [mm]\mathcal{N}=(N,\dotso)[/mm]
>
> 1) [mm]\mathcal{M}[/mm] ist eine elementare Substruktur von
> [mm]\mathcal{N}[/mm].
>
> 2) Für alle L-Formeln [mm]\varphi(x;x_0,\dotso, x_n)[/mm] und
> [mm]a_0,\dotso, a_n\in M[/mm] gilt, wenn es ein [mm]b\in N[/mm] gibt mit
> [mm]\mathcal{N}\models\varphi[b,a_0,\dotso,a_n][/mm], dann gibt es
> ein [mm]a\in M[/mm] mit [mm]\mathcal{N}\models\varphi[a,a_0,\dotso,a_n][/mm]
>
> Dies würde ich hier gerne verwenden.
> Ich möchte also zeigen, dass 2) gilt.
>
> Ich hätte vorerst aber ein paar Fragen. Nämlich zu der
> Menge [mm]I[/mm]. Dies ist ja eine Indexmenge. Geht man bei
> Indexmengen immer davon aus, dass [mm]I\subset\mathbb{Z}[/mm] ist?
Nein, Indexmengen sind beliebige, nichtleere Mengen.
> Des Weiteren sollte diese Aussage erst interessant sein,
> wenn I eine unendliche Indexmenge ist, also kein größtes
> (oder auch kleinstes) Element hat.
>
> Zum Beweis:
>
> Mit der angesprochenen Äquivalenz kommt mir der Beweis
> eigentlich "trivial" vor, weshalb ich bestimmt irgendwas
> übersehe, bzw. es einen Harken geben muss...
>
> Zu erst einmal ist klar, dass [mm]M_i\subseteq M[/mm] für alle [mm]i\in I[/mm]
> gilt.
>
> Nun sind [mm]\mathcal{M}_i[/mm] und [mm]\mathcal{M}_j[/mm] für [mm]i\leq j[/mm]
> elementar äquivalent. Also Formeln die in [mm]\mathcal{M}_i[/mm]
> gelten, gelten auch in [mm]\mathcal{M}_j[/mm]. Währe [mm]I[/mm] nun eine
> endliche Menge, dann könnte man [mm]j[/mm] maximal wählen und
> wäre fertig.
>
> Allgemein ist ja folgendes zu tun:
>
> Wenn ich zeigen kann, dass für alle L-Formeln [mm]\varphi(x; x_0,\dotso, x_n)[/mm]
> und alle [mm]a_0,\dotso, a_n\in M_i[/mm] ein [mm]b\in M_i[/mm] existiert mit
> [mm]\mathcal{M}_i\models\varphi[b,a_0,\dotso,a_n][/mm] dann gibt es
> ein [mm]a\in M[/mm] mit
> [mm]\mathcal{M}\models\varphi[a,a_0,\dotso,a_n][/mm].
Nein, das ist nicht die Aussage des Lemmas, denn es besagt, dass wenn es $a$ in der Oberstruktur gibt, das die Formel erfuellt, dann gibt es auch ein solches in der Substruktur. Umgekehrt waere es in der Tat witzlos.
>
> Und die Existenz eines solchen a's ist zu zeigen.
> Was ich mir aber denke ist, dass ich einfach a=b wählen
> kann, weil [mm]b\in M[/mm], da [mm]b\in M_i[/mm] und [mm]M_i\subseteq M[/mm].
>
> Es kann aber wohl kaum so einfach sein...
> Was ist also der Harken bei dieser Aufgabe?
P.S. Harke= Rechen; Haken= gebogene Aufhaengvorrichtung.
>
> Über Hilfestellung und Korrekturen jeglicher Art würde
> ich mich sehr freuen.
> Vielen Dank im voraus.
>
> mfg
|
|
|
| |
|
> Nein, Indexmengen sind beliebige, nichtleere Mengen.
Okay.
> Nein, das ist nicht die Aussage des Lemmas, denn es besagt, dass wenn es $ a $ > in der Oberstruktur gibt, das die Formel erfuellt, dann gibt es auch ein solches in > der Substruktur. Umgekehrt waere es in der Tat witzlos.
Okay, dann habe ich das wohl falsch verstanden...
Also das Problem wäre dann ja, dass es in $I$ nicht unbedingt ein Maximum gibt, weil ansonsten kann man den Tarski-Test ja "absteigend" anwenden.
Eigentlich kommt mir die Aussage recht intuitiv vor.
Wenn [mm] $\mathcal{M}_i$ [/mm] elementar äquivalent zu [mm] $\mathcal{M}_j$ [/mm] ist, für [mm] $i\leq [/mm] j$ also es eine Substruktur von [mm] $\mathcal{M}$ [/mm] gibt, in der schon die gleichen Formeln erfüllbar sind, wie in [mm] $\mathcal{M}_i$, [/mm] dann ist es einleuchtend, dass die Formeln auch in [mm] $\mathcal{M}$ [/mm] gelten, weil ich ja lediglich mehr zur Verfügung habe.
Die Formeln werden also im Grunde nur immer "leichter zu erfüllen"...
Wie gesagt wäre meine Idee, dass ich den Tarski-Test im Grunde induktiv anwende. Das Problem dabei ist, dass ich kein Minimum oder Maximum in $I$ haben muss und ich irgendeinen Start fixieren müsste.
> P.S. Harke= Rechen; Haken= gebogene Aufhaengvorrichtung.
Ich schwöre es gab eine Zeit, wo ich das nicht durcheinander gebracht habe. :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:41 So 03.05.2015 | | Autor: | hippias |
Obwohl Du keine Frage gestellst hast, will ich trotzdem versuchen Dir auf die Spruenge zu helfen.
Behauptung: Wenn [mm] $M_{i}\prec M_{j}$ [/mm] fuer alle [mm] $i\leq [/mm] j$, dann gilt fuer alle [mm] $i\in [/mm] I$, dass [mm] $M_{i}\prec [/mm] M$.
Beweis. Sei [mm] $i\in [/mm] I$ beliebig und [mm] $\phi$ [/mm] eine $L$-Formel und [mm] $a_{0},\ldots, a_{n}\in M_{i}$ [/mm] und [mm] $b\in [/mm] M$ so, dass [mm] $M\models \phi(b,a_{0},\ldots, a_{n})$.
[/mm]
Nun ist zu zeigen, dass man sogar [mm] $a\in M_{i}$ [/mm] waehlen kann, sodass [mm] $M\models \phi(a,a_{0},\ldots, a_{n})$.
[/mm]
Tip: Wende zuerst zuerst die Voraussetzung $M= [mm] \cup_{i\in I} M_{i}$ [/mm] auf $b$ an.
|
|
|
| |
|
Entschuldigung, dass ich in meiner letzten "Frage" keine konkrete Frage gestellt habe.
Als Frage war eigentlich vorgesehen ob meine Idee richtig ist, bzw. wie man diese unter Umständen anpassen könnte.
Folgendes habe ich mir bisher überlegt:
Wegen [mm] $M=\bigcup_{i\in I} M_i$ [/mm] existiert ein [mm] $k\in [/mm] I$ mit [mm] $b\in M_k$ [/mm] und [mm] $b\notin M_i$ [/mm] für alle $i<k$. Da [mm] $\mathcal{M}_i\preceq\mathcal{M}_k$ [/mm] und eine L-Formel [mm] $\phi(b,a_0,\dotso, a_n)$ [/mm] existiert so, dass
[mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)$ [/mm] existiert ein [mm] $a_i\in M_i$ [/mm] mit
[mm] $\mathcal{M}_i\models\phi(a_i,a_0,\dotso, a_n)$.
[/mm]
Insbesondere ist [mm] $b\in [/mm] M$ also [mm] $\mathcal{M}_i\preceq \mathcal{M}$ [/mm] für alle [mm] $i\in [/mm] I$.
Denn für alle $j>k$ ist die Aussage trivial, weil dann [mm] $b\in M_j$. [/mm] Für die $i<k$ gilt aufgrund der elementaren Äquivalenz, dass ich ein Element [mm] $a_i$ [/mm] finde, so dass die entsprechende Formel erfüllt ist.
Also gilt bereits [mm] $\mathcal{M}_i\preceq\mathcal{M}$ [/mm] für alle [mm] $i\in [/mm] I$, um es nochmal zusammenzufassen wie der Gedankengang nun war.
Ich bin überzeugt, bist du es auch? ...
:)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:31 So 03.05.2015 | | Autor: | hippias |
Ja, auch mich hast Du ueberzeugt. Aber Dein Beweis enthaelt noch ein paar von Schludrigkeiten (Indices!), die Du ausbessern musst.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:55 So 03.05.2015 | | Autor: | tobit09 |
Hallo zusammen!
Mich überzeugt die Argumentation leider nicht.
Ich vermute darüber hinaus, dass ein Beweis mithilfe von Tarskis Test nicht gelingen wird.
Der übliche Beweis von Tarskis Ketten-Lemma wird anders geführt.
> Wegen [mm]M=\bigcup_{i\in I} M_i[/mm] existiert ein [mm]k\in I[/mm] mit [mm]b\in M_k[/mm]
Ja.
> und [mm]b\notin M_i[/mm] für alle [mm]i
Nein, warum sollte so ein $k$ existieren?
Aber das verwendest du ja ohnehin im Weiteren gar nicht.
> Da
> [mm]\mathcal{M}_i\preceq\mathcal{M}_k[/mm]
Dazu benötigen wir [mm] $k\ge [/mm] i$.
(Das ist aber behebbar, indem wir k durch [mm] $\max(k,i)$ [/mm] ersetzen.)
> und eine L-Formel
> [mm]\phi(b,a_0,\dotso, a_n)[/mm] existiert so, dass
> [mm]\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)[/mm]
Du meinst: Es gilt [mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)$, [/mm] wobei [mm] $\phi$ [/mm] die (beliebig vorgegebene) L-Formel bezeichnet, die hippias eingeführt hat.
Genau hier finde ich kein Argument, dass tatsächlich [mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)$ [/mm] gelten soll.
> existiert ein
> [mm]a_i\in M_i[/mm] mit
> [mm]\mathcal{M}_i\models\phi(a_i,a_0,\dotso, a_n)[/mm].
Folgerichtig.
> Insbesondere ist [mm]b\in M[/mm]
(b war ja auch von Anfang an als Element von M gewählt.)
> also [mm]\mathcal{M}_i\preceq \mathcal{M}[/mm]
> für alle [mm]i\in I[/mm].
Bei deiner Formulierung von Tarskis Test müsste man noch [mm] $\mathcal{M}\models\phi(a_i,a_0,\dotso, a_n)$ [/mm] zeigen.
Auch hierfür sehe ich kein Argument.
> Denn für alle [mm]j>k[/mm] ist die Aussage trivial, weil dann [mm]b\in M_j[/mm].
(Welche Aussage?)
> Für die [mm]i
(Du meinst [mm] $i\le [/mm] k$ statt $i<k$ und [mm] "$M_i\preceq M_k$" [/mm] statt "elementare Äquivalenz".)
> dass ich ein Element [mm]a_i[/mm] finde, so dass die entsprechende
> Formel erfüllt ist.
(Vergiss nicht zu sagen, in welcher Struktur. Das ist nämlich entscheidend.)
Der übliche Beweis von Tarskis Ketten-Lemma geht so:
Zeige per Induktion nach [mm] $\phi(x_1,\ldots,x_n)$:
[/mm]
Für alle [mm] $i\in [/mm] I$ und alle [mm] $a_1,\ldots,a_n\in M_i$ [/mm] gilt die Äquivalenz
[mm] $\mathcal{M}_i\models\phi(a_1,\ldots,a_n)\iff \mathcal{M}\models\phi(a_1,\ldots,a_n)$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
Schade.
> Nein, warum sollte so ein $ k $ existieren?
Ich hatte gedacht, da die jeweiligen Trägermengen [mm] $M_i$ [/mm] der Strukturen [mm] $\mathcal{M}_i=(M_i,\dotso)$ [/mm] Teilmengen voneinander sind, also wenn ich etwa [mm] $I=\mathbb{N}$ [/mm] hätte, dann würde gelten
[mm] $M_0\subseteq M_1\subseteq M_2\subseteq ...\subseteq M_n$
[/mm]
Im dem Fall, dass Trägermengen gleich sind, könnte ich die "doppelten" auch rausnehmen so das die Inklusion "echt" ist. Also muss es ab einem bestimmten Index ein Element $b$ geben, was in den vorherigen Trägermengen nicht vorkam. Das hatte ich gedacht und auch jetzt sehe ich nicht wieso dies nicht der Fall sein sollte, außer man geht von einem recht trivialem Fall aus.
> Genau hier finde ich kein Argument, dass tatsächlich
> [mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n) [/mm] $ gelten soll.
Ich hatte gedacht, dass die Existenz einer solchen Formel im Grunde durch die elementare Äquivalenz mitgeliefert wird. Sehe aber nun wohl auch das Problem, denn warum sollte so eine Formel gerade für $b$ existieren?
> Denn für alle $ j>k $ ist die Aussage trivial, weil dann $ [mm] b\in M_j [/mm] $.
> (Welche Aussage?)
Ich meinte die Aussage [mm] $M_k\preceq M_j$
[/mm]
> (Vergiss nicht zu sagen, in welcher Struktur. Das ist nämlich entscheidend.)
Gemeint war jeweils die Struktur [mm] $\mathcal{M}_i=(M_i,\dotso)$ [/mm] und [mm] $a_i\in M_i$.
[/mm]
> Der übliche Beweis von Tarskis Ketten-Lemma geht so:
>
>
> Zeige per Induktion nach $ [mm] \phi(x_1,\ldots,x_n) [/mm] $:
>
> Für alle $ [mm] i\in [/mm] I $ und alle $ [mm] a_1,\ldots,a_n\in M_i [/mm] $ gilt die Äquivalenz
>
> $ [mm] \mathcal{M}_i\models\phi(a_1,\ldots,a_n)\iff\mathcal{M}\models\phi(a_1,\ldots,a_n) [/mm] $.
Meinst du hier Induktion über den Formelaufbau?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:08 So 03.05.2015 | | Autor: | tobit09 |
> > Nein, warum sollte so ein [mm]k[/mm] existieren?
>
> Ich hatte gedacht, da die jeweiligen Trägermengen [mm]M_i[/mm] der
> Strukturen [mm]\mathcal{M}_i=(M_i,\dotso)[/mm] Teilmengen
> voneinander sind, also wenn ich etwa [mm]I=\mathbb{N}[/mm] hätte,
> dann würde gelten
>
> [mm]M_0\subseteq M_1\subseteq M_2\subseteq ...\subseteq M_n[/mm]
In diesem Spezialfall [mm] $I=\IN$ [/mm] mit der gewöhnlichen Ordnung darauf stimmt dies.
Dann kann man auch ein kleinstes [mm] $k\in [/mm] I$ mit [mm] $b\in M_k$ [/mm] finden.
Im Allgemeinen kann I jedoch auch ganz anders aussehen.
(Denke z.B. an [mm] $I=\IR$ [/mm] mit der gewöhnlichen Ordnung darauf.)
> > Genau hier finde ich kein Argument, dass tatsächlich
> > [mm]\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)[/mm] gelten soll.
>
> Ich hatte gedacht, dass die Existenz einer solchen Formel
> im Grunde durch die elementare Äquivalenz mitgeliefert
> wird. Sehe aber nun wohl auch das Problem, denn warum
> sollte so eine Formel gerade für [mm]b[/mm] existieren?
Es geht gar nicht um die Existenz einer solchen Formel (natürlich gibt es IRGENDWELCHE Formeln [mm] $\phi(x,x_0,\ldots,x_n)$, [/mm] die [mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)$ [/mm] erfüllen).
Vielmehr geht es darum, ob für die von hippias eingeführte Formel [mm] $\phi$ [/mm] die Eigenschaft [mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)$ [/mm] erfüllt ist.
Wir wissen [mm] $\mathcal{M}\models\phi(b,a_0,\dotso,a_n)$, [/mm] benötigen aber [mm] $\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)$.
[/mm]
> > Denn für alle [mm]j>k[/mm] ist die Aussage trivial, weil dann [mm]b\in M_j [/mm].
>
> > (Welche Aussage?)
>
> Ich meinte die Aussage [mm]M_k\preceq M_j[/mm]
Ja, für $j>k$ ist [mm] $\mathcal{M}_k\preceq M_j$ [/mm] vorausgesetzt.
Das hat aber nichts mit [mm] $b\in M_j$ [/mm] zu tun.
> > Der übliche Beweis von Tarskis Ketten-Lemma geht so:
> >
> >
> > Zeige per Induktion nach [mm]\phi(x_1,\ldots,x_n) [/mm]:
> >
> > Für alle [mm]i\in I[/mm] und alle [mm]a_1,\ldots,a_n\in M_i[/mm] gilt die
> Äquivalenz
> >
> >
> [mm]\mathcal{M}_i\models\phi(a_1,\ldots,a_n)\iff\mathcal{M}\models\phi(a_1,\ldots,a_n) [/mm].
>
> Meinst du hier Induktion über den Formelaufbau?
Ja, genau.
|
|
|
| |
|
Dann muss ich nun irgendwie die fünf Fälle:
1. $s=t$ wenn $s,t$ L-Terme sind
2. [mm] $R(t_0,\dotso, t_{n-1})$ [/mm] wenn $R$ ein n-stelliges Relationszeichen ist und [mm] $t_0,\dotso, t_{n-1}$ [/mm] L-Terme sind.
3. [mm] $(\neg\phi)$, [/mm] wenn [mm] $\phi$ [/mm] eine L-Formel ist.
4. [mm] $(\phi\wedge\psi)$ [/mm] wenn [mm] $\phi,\psi$ [/mm] L-Formeln sind.
5. [mm] $(\exists x\phi), [/mm] wenn [mm] $\phi$ [/mm] eine L-Formel ist und $x$ eine Variable.
durchgehen.
Zu 1.
Wenn [mm] $\mathcal{M}_i\models [/mm] s=t$, dann sicherlich auch [mm] $\mathcal{M}\models [/mm] s=t$, wie sieht es aber mit der Rückrichtung aus, denn wenn [mm] $\mathcal{M}\models [/mm] s=t$, dann muss dies ja nicht unbedingt in [mm] $\mathcal{M}_i$ [/mm] gelten, weil dort ja nicht die selben L-Terme vorhanden sein müssen (s und t), oder ist dies hier allgemein zu sehen so, dass es gar nicht speziell s und t sein müssen sondern irgendwelche L-Terme für die s=t gilt?
Ich fand die Induktion über den Formelaufbau bisher immer ein wenig "komisch", weil ich nie so wirklich die Induktion gesehen habe wie man sie sonst kennt, also Induktionsanfang, Induktionsvoraussetzung und der Induktionsschritt. Es werden immer nur diese fünf Fälle überprüft.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:49 So 03.05.2015 | | Autor: | tobit09 |
> Dann muss ich nun irgendwie die fünf Fälle:
>
> 1. [mm]s=t[/mm] wenn [mm]s,t[/mm] L-Terme sind
>
> 2. [mm]R(t_0,\dotso, t_{n-1})[/mm] wenn [mm]R[/mm] ein n-stelliges
> Relationszeichen ist und [mm]t_0,\dotso, t_{n-1}[/mm] L-Terme sind.
>
> 3. [mm](\neg\phi)[/mm], wenn [mm]\phi[/mm] eine L-Formel ist.
>
> 4. [mm](\phi\wedge\psi)[/mm] wenn [mm]\phi,\psi[/mm] L-Formeln sind.
>
> 5. [mm]$(\exists x\phi),[/mm] wenn [mm]$\phi$[/mm] eine L-Formel ist und $x$
> eine Variable.
>
> durchgehen.
![[ok]](/images/smileys/ok.gif "[ok]") Genau.
Wobei du bei 3., 4. und 5. jeweils annehmen darfst, dass [mm] $\phi$ [/mm] (und bei 4. auch [mm] $\psi$) [/mm] der Behauptung genügt.
> Zu 1.
>
> Wenn [mm]\mathcal{M}_i\models s=t[/mm], dann sicherlich auch
> [mm]\mathcal{M}\models s=t[/mm], wie sieht es aber mit der
> Rückrichtung aus, denn wenn [mm]\mathcal{M}\models s=t[/mm], dann
> muss dies ja nicht unbedingt in [mm]\mathcal{M}_i[/mm] gelten, weil
> dort ja nicht die selben L-Terme vorhanden sein müssen (s
> und t), oder ist dies hier allgemein zu sehen so, dass es
> gar nicht speziell s und t sein müssen sondern
> irgendwelche L-Terme für die s=t gilt?
Was ein L-Term ist, ist völlig unabhängig von irgendwelchen L-Strukturen.
Seien [mm] $\phi(x_1,\ldots,x_n)\equiv [/mm] s=t$, [mm] $i\in [/mm] I$ und [mm] $a_1,\ldots,a_n\in M_i$.
[/mm]
Dann gilt die Äquivalenz
[mm] $\mathcal{M}_i\models\phi(a_1,\ldots,a_n)\iff s^{\mathcal{M}_i}(a_1,\ldots,a_n)=t^{\mathcal{M}_i}(a_1,\ldots,a_n)$.
[/mm]
Da [mm] $\mathcal{M}_i$ [/mm] eine Teilstruktur von [mm] $\mathcal{M}$ [/mm] ist, gilt
[mm] $s^{\mathcal{M}_i}(a_1,\ldots,a_n)=s^\mathcal{M}(a_1,\ldots,a_n)$
[/mm]
und
[mm] $t^{\mathcal{M}_i}(a_1,\ldots,a_n)=t^\mathcal{M}(a_1,\ldots,a_n)$.
[/mm]
(Falls ihr dies noch nicht gezeigt habt: Der Beweis ist eine Induktion nach dem Aufbau von s (bzw. t).)
Wir haben also die Äquivalenzen
[mm] $\mathcal{M}_i\models\phi(a_1,\ldots,a_n)$
[/mm]
[mm] $\iff s^{\mathcal{M}_i}(a_1,\ldots,a_n)=t^{\mathcal{M}_i}(a_1,\ldots,a_n)$
[/mm]
[mm] $\iff s^{\mathcal{M}}(a_1,\ldots,a_n)=t^{\mathcal{M}}(a_1,\ldots,a_n)$
[/mm]
[mm] $\iff \mathcal{M}\models\phi(a_1,\ldots,a_n)$
[/mm]
> Ich fand die Induktion über den Formelaufbau bisher immer
> ein wenig "komisch", weil ich nie so wirklich die Induktion
> gesehen habe wie man sie sonst kennt, also
> Induktionsanfang, Induktionsvoraussetzung und der
> Induktionsschritt. Es werden immer nur diese fünf Fälle
> überprüft.
Ja, Induktion über den Formelaufbau ist nicht das gleiche wie gewöhnliche Induktion, auch wenn es Gemeinsamkeiten gibt.
|
|
|
| |
|
Ich habe noch einmal mein Skript durchgesehen und eine solche Aussage sollten wir nicht gezeigt haben (leider...).
Die Aussage wäre ja,
Ist [mm] $\mathcal{N}$ [/mm] eine Substruktur von [mm] $\mathcal{M}$, [/mm] so gilt
[mm] $s^{\mathcal{N}}(t_0,\dotso, t_{n-1})=s^{\mathcal{M}}(t_0,\dotso,t_{n-1})$
[/mm]
Und der Beweis funktioniert dann nach Induktion über den Termaufbau?
Die Aufgabe kommt mir irgendwie sehr umständlich vor... :(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:05 Mo 04.05.2015 | | Autor: | tobit09 |
> Die Aussage wäre ja,
>
> Ist [mm]\mathcal{N}[/mm] eine Substruktur von [mm]\mathcal{M}[/mm], so gilt
>
> [mm]s^{\mathcal{N}}(t_0,\dotso, t_{n-1})=s^{\mathcal{M}}(t_0,\dotso,t_{n-1})[/mm]
Ja, wobei [mm] $s(x_0,\ldots,x_{n-1})$ [/mm] ein L-Term sei und [mm] $t_0,\ldots,t_{n-1}\in [/mm] N$ gelte.
> Und der Beweis funktioniert dann nach Induktion über den
> Termaufbau?
Ja.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:44 So 03.05.2015 | | Autor: | hippias |
> Du meinst:
> Es gilt [mm]\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)[/mm], wobei
> [mm]\phi[/mm] die (beliebig vorgegebene) L-Formel bezeichnet, die
> hippias eingeführt hat.
>
> Genau hier finde ich kein Argument, dass tatsächlich
> [mm]\mathcal{M}_k\models\phi(b,a_0,\dotso, a_n)[/mm] gelten soll.
>
Gut, dass Du aufgepasst hast, denn das habe ich uebersehen. Fuer eventuell auftretende Existenzquantoren muesste aehnlich wie fuer $b$ argumentiert werden und anschliessend das Maximum der Indices betrachtet werden.
|
|
|
| |
|
Zu dem Beweis mit Tarski's Test hätte ich doch noch eine Frage zu dieser Bemerkung von tobit
> Ich vermute darüber hinaus, dass ein Beweis mithilfe von Tarskis Test nicht
> gelingen wird.
Vielleicht ist einfach gemeint, dass ein Beweis mit Tarskis Test sehr aufwendig und umständlich wäre, denn muss dies nicht gelingen, da Tarskis Test ja eine Äquivalenzaussage ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:01 So 03.05.2015 | | Autor: | tobit09 |
> Zu dem Beweis mit Tarski's Test hätte ich doch noch eine
> Frage zu dieser Bemerkung von tobit
>
> > Ich vermute darüber hinaus, dass ein Beweis mithilfe von
> Tarskis Test nicht
> > gelingen wird.
>
> Vielleicht ist einfach gemeint, dass ein Beweis mit Tarskis
> Test sehr aufwendig und umständlich wäre, denn muss dies
> nicht gelingen, da Tarskis Test ja eine Äquivalenzaussage
> ist?
Du hast völlig Recht.
Ich meinte, dass wir vermutlich keinen "sinnvollen" Beweis mithilfe von Tarskis Test finden werden, nicht die prinzipielle Unmöglichkeit eines Beweises damit.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:01 Mo 04.05.2015 | | Autor: | hippias |
Ich stelle mir einen Beweis in 2 Schritten vor:
1. Unter den gemachten Voraussetzungen gilt fuer eine $L$-Formel [mm] $\phi$: [/mm] Wenn [mm] $M\models \phi$, [/mm] dann gibt es ein [mm] $k\in [/mm] I$ mit [mm] $M_{k}\models \phi$.
[/mm]
Dies sollte aus einer Induktion ueber den Formelaufbau gelingen (wie von Tobias bereits angefangen).
2. Diese Hilfsaussage schliesst die Luecke in dem bereits angefangenen Beweis.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:24 Mo 04.05.2015 | | Autor: | tobit09 |
Hallo hippias!
An deiner Idee ist mir noch einiges unklar:
> Ich stelle mir einen Beweis in 2 Schritten vor:
> 1. Unter den gemachten Voraussetzungen gilt fuer eine
> [mm]L[/mm]-Formel [mm]\phi[/mm]: Wenn [mm]M\models \phi[/mm], dann gibt es ein [mm]k\in I[/mm]
> mit [mm]M_{k}\models \phi[/mm].
Was meinst du mit [mm] $M\models\phi$, [/mm] wenn [mm] $\phi$ [/mm] nicht notwendigerweise ein Satz ist, also freie Variablen enthalten kann?
Meinst du Folgendes?
(*) Für jede $L$-Formel [mm] $\phi(x_1,\ldots,x_n)$ [/mm] und alle [mm] $a_1,\ldots,a_n\in [/mm] M$ mit [mm] $M\models\phi(a_1,\ldots,a_n)$ [/mm] existiert ein [mm] $k\in [/mm] I$ mit [mm] $a_1,\ldots,a_n\in M_k$ [/mm] und [mm] $M_k\models\phi(a_1,\ldots,a_n)$.
[/mm]
> Dies sollte aus einer Induktion ueber den Formelaufbau
> gelingen (wie von Tobias bereits angefangen).
Ich sehe hier nicht, wie der Negations-Schritt bei der geplanten Induktion funktionieren soll.
> 2. Diese Hilfsaussage schliesst die Luecke in dem bereits
> angefangenen Beweis.
Bei der Formulierung von Tarskis Test, wie sie impliziteFunktion kennt, muss am Ende die Existenz eines [mm] $a\in M_i$ [/mm] mit [mm] $\mathcal{M}\models\phi(a,a_0,\ldots,a_n)$ [/mm] gezeigt sein.
In der bisherigen Argumentation haben wir aber nur ein [mm] $a\in M_i$ [/mm] mit [mm] $\mathcal{M}_\red{i}\models\phi(a,a_0,\ldots,a_n)$.
[/mm]
Diese zweite Lücke wäre auch noch zu schließen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:47 Sa 09.05.2015 | | Autor: | hippias |
Du hast recht: ich habe mich zu unkritisch auf die Idee des Eingangsposts eingelassen und das Problem nicht richtig durchdacht. Naja, wenigstens habe ich das Gefuehl etwas dazugelernt zu haben.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:18 So 03.05.2015 | | Autor: | tobit09 |
> Okay, dann habe ich das wohl falsch verstanden...
> Also das Problem wäre dann ja, dass es in [mm]I[/mm] nicht
> unbedingt ein Maximum gibt, weil ansonsten kann man den
> Tarski-Test ja "absteigend" anwenden.
Wenn es in I ein Maximum $j$ gibt, gilt für dieses $j$ die Gleichheit [mm] $\mathcal{M}_j=\mathcal{M}$ [/mm] und die Behauptung [mm] $\mathcal{M}_i\preceq \mathcal{M}$ [/mm] folgt unmittelbar aus [mm] $\mathcal{M}_i\preceq\mathcal{M}_j$, [/mm] was nach Voraussetzung gegeben ist (jeweils für alle [mm] $i\in [/mm] I$).
Dieser Spezialfall ist also nicht sonderlich spannend.
> Eigentlich kommt mir die Aussage recht intuitiv vor.
> Wenn [mm]\mathcal{M}_i[/mm] elementar äquivalent zu [mm]\mathcal{M}_j[/mm]
> ist,
Für [mm] $i,j\in [/mm] I$ mit [mm] $i\le [/mm] j$ sind [mm] $\mathcal{M}_i$ [/mm] und [mm] $\mathcal{M}_j$ [/mm] nicht nur als elementar äquivalent vorausgesetzt, sondern nach Voraussetzung ist [mm] $\mathcal{M}_i$ [/mm] sogar eine elementare Teilstruktur von [mm] $\mathcal{M}_j$.
[/mm]
(Nicht jede elementar äquivalente Teilstruktur ist eine elementare Teilstruktur!)
> für [mm]i\leq j[/mm] also es eine Substruktur von [mm]\mathcal{M}[/mm]
> gibt, in der schon die gleichen Formeln erfüllbar sind,
> wie in [mm]\mathcal{M}_i[/mm],
> dann ist es einleuchtend, dass die
> Formeln auch in [mm]\mathcal{M}[/mm] gelten, weil ich ja lediglich
> mehr zur Verfügung habe.
> Die Formeln werden also im Grunde nur immer "leichter zu
> erfüllen"...
Von dieser Vorstellung solltest du dich schnell wieder verabschieden.
Beispiel:
L sei die leere Sprache.
[mm] $\mathcal{A}$ [/mm] sei die L-Struktur mit Träger [mm] $A=\{1\}$.
[/mm]
[mm] $\mathcal{B}$ [/mm] sei die L-Struktur mit Träger [mm] $B=\{1,2\}$.
[/mm]
Die Formel
[mm] $\varphi\equiv\neg\exists x\exists [/mm] y [mm] \neg [/mm] x=y$,
die anschaulich aussagt, dass es nicht mindestens zwei verschiedene Elemente im Träger gibt (d.h. dass es höchstens ein Element im Träger gibt), erfüllt
[mm] $\mathcal{A}\models\varphi$, [/mm] aber [mm] $\mathcal{B}\not\models\varphi$,
[/mm]
obwohl nach deiner (falschen) Intuition ja in [mm] $\mathcal{B}$ [/mm] die Formeln leichter als in [mm] $\mathcal{A}$ [/mm] zu erfüllen sein müssten.
(Doch richtig ist deine Intuition im Spezialfall von sogenannten existentiellen Formeln.)
|
|
|
| |
|
Stimmt, daran hatte ich gar nicht gedacht.
Meine Intuition war etwa so:
"Wenn ich mehr zur Verfügung habe, dann kann ich auch einfacher etwas erfüllen."
Aber genau das kann mir ja einen Strick drehen...
|
|
|
|
