matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLogikTarski's chain-lemma
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Logik" - Tarski's chain-lemma
Tarski's chain-lemma < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Tarski's chain-lemma: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:45 Sa 02.05.2015
Autor: impliziteFunktion

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

        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Tarski's chain-lemma: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:40 So 03.05.2015
Autor: impliziteFunktion


> 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. :)

Bezug
                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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.


Bezug
                                
Bezug
Tarski's chain-lemma: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:59 So 03.05.2015
Autor: impliziteFunktion

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? ...

:)

Bezug
                                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                
Bezug
Tarski's chain-lemma: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:48 So 03.05.2015
Autor: impliziteFunktion

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?


Bezug
                                                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                                
Bezug
Tarski's chain-lemma: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:27 So 03.05.2015
Autor: impliziteFunktion

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.

Bezug
                                                                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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] 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.

Bezug
                                                                                
Bezug
Tarski's chain-lemma: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:19 So 03.05.2015
Autor: impliziteFunktion

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... :(

Bezug
                                                                                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                        
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:52 So 03.05.2015
Autor: impliziteFunktion

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?

Bezug
                                                                
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                                
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                                        
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                                                
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Tarski's chain-lemma: Antwort
Status: (Antwort) fertig Status 
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.)


Bezug
                                
Bezug
Tarski's chain-lemma: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:50 So 03.05.2015
Autor: impliziteFunktion

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...

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]