elementar äquivalente Sprachen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Hallo,
diesem Thread liegt keine explizite Aufgabenstellung zugrunde.
Ich versuche gerade nur ein Beispiel für eine endliche Sprache L und zwei endliche L-Strukturen [mm] \mathcal{M},\mathcal{N}, [/mm] welche elementar Äquivalent sind, also
[mm] $\mathcal{M}\models\phi\Leftrightarrow\mathcal{N}\models{\phi}$
[/mm]
wobei das Beispiel nicht trivial sein soll. Denn mir fällt leider keins ein.
Gibt es überhaupt welche?
Wenn ich zum Beispiel die Sprache
[mm] $L=\{0,+,\cdot,\leq\}$ [/mm] habe mit den L-Strukturen
[mm] $\mathcal{M}=\{\mathbb{Z},0,+,\cdot,\leq\}$ [/mm] und
[mm] $\mathcal{N}=\{\mathbb{N},0,+,\cdot,\leq\}$ [/mm] dann wären diese Sprachen ja nicht elementar äquivalent, weil es Aussagen gibt die in [mm] $\mathcal{M}$ [/mm] gelten, aber nicht in [mm] $\mathcal{N}$, [/mm] zum Beispiel das die Summe zweier Zahlen größergleich Null ist.
Dazu eine allgemeine Frage.
Wenn ich eine Sprache L gegeben habe, und mehrere L-Strukturen, dann taucht in jeder dieser L-Struktur die selben Konstanten, Funktionen und Relationzeichen auf, die in L vorhanden sind. (Wie im obigen Beispiel).
Man könnte nicht eines weglassen und schon gar nicht hinzufügen. Dann wäre es keine L-Struktur mehr.
Gibt es denn eine nicht-triviale, elementar äquivalente L-Struktur zu [mm] $\mathcal{N}$? [/mm] Wobei ich mit "nicht-trival" meine, dass die andere L-Struktur nicht die selbe Trägermenge hat, in dem Fall die natürlichen Zahlen.
Vielen Dank.
(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:10 Mo 20.04.2015 | | Autor: | tobit09 |
Hallo impliziteFunktion!
> diesem Thread liegt keine explizite Aufgabenstellung
> zugrunde.
> Ich versuche gerade nur ein Beispiel für eine endliche
> Sprache L und zwei endliche L-Strukturen
> [mm]\mathcal{M},\mathcal{N},[/mm] welche elementar Äquivalent sind,
> also
>
> [mm]\mathcal{M}\models\phi\Leftrightarrow\mathcal{N}\models{\phi}[/mm]
>
> wobei das Beispiel nicht trivial sein soll. Denn mir fällt
> leider keins ein.
> Gibt es überhaupt welche?
Ich nehme mal an mit "nicht trivial" meinst du, dass [mm] $\mathcal{M}$ [/mm] und [mm] $\mathcal{N}$ [/mm] nicht isomorph sind.
Man kann folgendes zeigen:
Sind zwei ENDLICHE L-Strukturen elementar äquivalent, so sind sie schon isomorph.
Daher gibt es kein nicht triviales Beispiel zweier ENDLICHER elementar äquivalenter L-Strukturen.
Interessant wird der Begriff der elementaren Äquivalenz hingegen bei unendlichen L-Strukturen.
> Wenn ich zum Beispiel die Sprache
>
> [mm]L=\{0,+,\cdot,\leq\}[/mm] habe mit den L-Strukturen
>
> [mm]\mathcal{M}=\{\mathbb{Z},0,+,\cdot,\leq\}[/mm] und
> [mm]\mathcal{N}=\{\mathbb{N},0,+,\cdot,\leq\}[/mm]
Diese L-Strukturen sind gar nicht endlich.
> dann wären
> diese Sprachen ja nicht elementar äquivalent,
Du meinst "diese Strukturen" statt "diese Sprachen".
> weil es
> Aussagen gibt die in [mm]\mathcal{M}[/mm] gelten, aber nicht in
> [mm]\mathcal{N}[/mm], zum Beispiel das die Summe zweier Zahlen
> größergleich Null ist.
Ja.
> Dazu eine allgemeine Frage.
> Wenn ich eine Sprache L gegeben habe, und mehrere
> L-Strukturen, dann taucht in jeder dieser L-Struktur die
> selben Konstanten, Funktionen und Relationzeichen auf, die
> in L vorhanden sind. (Wie im obigen Beispiel).
> Man könnte nicht eines weglassen und schon gar nicht
> hinzufügen. Dann wäre es keine L-Struktur mehr.
Ja.
> Gibt es denn eine nicht-triviale, elementar äquivalente
> L-Struktur zu [mm]\mathcal{N}[/mm]? Wobei ich mit "nicht-trival"
> meine, dass die andere L-Struktur nicht die selbe
> Trägermenge hat, in dem Fall die natürlichen Zahlen.
Meinst du wirklich diesen Begriff von "nicht-trivial"?
Eine zu [mm] $\mathcal{N}$ [/mm] elementar äquivalente L-Struktur mit anderer Trägermenge bekommst du am einfachsten, indem du eine geeignete isomorphe Kopie von [mm] $\mathcal{N}$ [/mm] betrachtest.
Vermutlich meinst du aber eher mit "nicht-trivial", dass [mm] $\mathcal{N}$ [/mm] und die neue Struktur nicht isomorph sind.
Mit einem Kompaktheitssatz-Argument lässt sich tatsächlich die Existenz zu [mm] $\mathcal{N}$ [/mm] elementar äquivalenter, aber nicht zu [mm] $\mathcal{N}$ [/mm] isomorpher L-Strukturen zeigen.
Diese Strukturen enthalten neben einer isomorphen Kopie der natürlichen Zahlen sogenannte Nichtstandardzahlen, die größer als alle natürlichen Zahlen (bzw. deren Kopien) sind.
Viele Grüße
Tobias
|
|
|
| |
|
> Sind zwei ENDLICHE L-Strukturen elementar äquivalent, so sind sie schon
> isomorph.
Ist der Beweis dazu schwer?
Also das was ich mit "nicht-trivial" meine ist, dass ich nicht einfach zweimal die selbe endliche L-Struktur angebe.
Irgendwie hatte ich bisher glaube ich dennoch immer unendliche Trägermengen im Sinn... Ich weiß auch nicht warum.
Wenn ich nun etwa eine Sprache L und die Mengen [mm] $A=\{0,1\}$ [/mm] und [mm] $B=\{2,3\}$ [/mm] betrachte mit der jeweiligen L-Struktur, wären diese dann elementar äquivalent, weil ich etwa die 0 aus A mit der 2 aus B identifizieren könnte, bzw. die 1 mit der 3, oder auch umgekehrt.
Ja, ich glaube mir wird gerade ein Denkfehler klar.
Etwa hätte ich vorher gedacht, dass ich nun zum Beispiel in
[mm] $\mathcal{B}=(B, [/mm] ...)$ eine Formel formulieren kann wie
[mm] $\exists x\exists [/mm] y (x+y=5)$
Das ist aber nur möglich, wenn ich das Symbol der 5 in der Sprache L gegeben hätte. Dann wäre die Aussage aber auch in [mm] $\mathcal{A}=(A, [/mm] ...)$ erfüllbar.
Sehe ich das richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:34 Di 21.04.2015 | | Autor: | tobit09 |
> > Sind zwei ENDLICHE L-Strukturen elementar äquivalent, so
> sind sie schon
> > isomorph.
>
> Ist der Beweis dazu schwer?
Ich würde sagen: Der Beweis ist weder trivial noch ultra-schwer.
Er besteht aus zwei Schritten:
1. Nachweis für endliche Sprachen L
2. Verallgemeinerung auf beliebige Sprachen L
Die Idee zu 1.:
Seien [mm] $\mathcal{A}$ [/mm] und [mm] $\mathcal{B}$ [/mm] endliche elementar äquivalente L-Strukturen für eine endliche Sprache L.
Nun lässt sich der "Isomorphietyp" von [mm] $\mathcal{A}$ [/mm] vollständig durch einen einzigen L-Satz [mm] $\varphi$ [/mm] ausdrücken.
Wegen [mm] $\mathcal{A}\models\varphi$ [/mm] folgt aus der elementaren Äquivalenz auch [mm] $\mathcal{B}\models\varphi$ [/mm] und damit die Isomorphie von [mm] $\mathcal{A}$ [/mm] und [mm] $\mathcal{B}$.
[/mm]
> Also das was ich mit "nicht-trivial" meine ist, dass ich
> nicht einfach zweimal die selbe endliche L-Struktur
> angebe.
Dann kannst du als "nicht-triviale" Beispiele für elementar äquivalente L-Strukturen auch einfach jede beliebige L-Struktur mit einer isomorphen Kopie nehmen.
> Wenn ich nun etwa eine Sprache L und die Mengen [mm]A=\{0,1\}[/mm]
> und [mm]B=\{2,3\}[/mm] betrachte mit der jeweiligen L-Struktur,
Was ist L?
Was sind die Interpretationen der Zeichen aus L in den beiden L-Strukturen?
Oder soll L einfach die leere Sprache sein?
> wären diese dann elementar äquivalent, weil ich etwa die
> 0 aus A mit der 2 aus B identifizieren könnte, bzw. die 1
> mit der 3, oder auch umgekehrt.
Das hängt von der Beantwortung meiner obigen Fragen ab.
> Ja, ich glaube mir wird gerade ein Denkfehler klar.
> Etwa hätte ich vorher gedacht, dass ich nun zum Beispiel
> in
>
> [mm]\mathcal{B}=(B, ...)[/mm] eine Formel formulieren kann wie
>
> [mm]\exists x\exists y (x+y=5)[/mm]
>
> Das ist aber nur möglich, wenn ich das Symbol der 5 in der
> Sprache L gegeben hätte.
Das ist nur dann eine L-Formel, wenn L ein zweistelliges Funktions-Zeichen + und ein Konstanten-Zeichen 5 enthält.
> Dann wäre die Aussage aber auch
> in [mm]\mathcal{A}=(A, ...)[/mm] erfüllbar.
>
> Sehe ich das richtig?
Mir ist nicht klar, was du hier mit erfüllbar meinst.
Der von dir genannte Satz [mm] $\psi$ [/mm] ist in [mm] $\mathcal{A}$ [/mm] entweder gültig (d.h. [mm] $\mathcal{A}\models\psi$) [/mm] oder nicht.
Ob [mm] $\mathcal{A}\models\psi$ [/mm] auf der einen Seite und [mm] $\mathcal{B}\models\psi$ [/mm] auf der anderen Seite gelten, hängt von der Interpretation der Zeichen $+$ und $5$ in den Strukturen ab.
|
|
|
|
