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
StartseiteMatheForenLogikelementar äquivalente Sprachen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Logik" - elementar äquivalente Sprachen
elementar äquivalente Sprachen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

elementar äquivalente Sprachen: Beispiel
Status: (Frage) beantwortet Status 
Datum: 13:46 So 19.04.2015
Autor: impliziteFunktion

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

        
Bezug
elementar äquivalente Sprachen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
elementar äquivalente Sprachen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:42 Mo 20.04.2015
Autor: impliziteFunktion


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

Bezug
                        
Bezug
elementar äquivalente Sprachen: Antwort
Status: (Antwort) fertig Status 
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.

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


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