www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

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
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenPrädikatenlogikBelegung von Termen,
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Prädikatenlogik" - Belegung von Termen,
Belegung von Termen, < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Prädikatenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Belegung von Termen,: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:10 Mi 17.04.2013
Autor: Lu-

Aufgabe
Definiton: Zwei [mm] \sigma-Terme [/mm] u und u' sind äquivalent, falls für jede
Struktur M der Signatur [mm] \sigma [/mm] und jede Belegung [mm] \beta [/mm] in M gilt: [mm] \beta^-(u)= \beta^-(u'). [/mm]
Zeigen Sie,
dass zwei [mm] \sigma-Terme [/mm] genau dann gleich sind, wenn sie identisch sind.
Hinweis Termalgebra

Hallo,
Lemma was ich wahrscheinlich brauche:
Jeder [mm] \sigma [/mm] Term ist entweder eine Variable (von der Form: [mm] x^0) [/mm] oder lässt sich in der Form [mm] ft_1 [/mm] ... [mm] t_k [/mm]  schreiben, wobei f [mm] \in \sigma^{op} [/mm]  ein k stelliges Operationssymbol ist und [mm] t_1 [/mm] ,.., [mm] t_k [/mm] sind [mm] \sigma [/mm] - Terme
Im zweiten Fall sind sind k, f, [mm] t_1 [/mm] ,.., [mm] t_k [/mm] eindeutig bestimmt.

Und Definition der Belegung:
Eine Belegung der Variablen in einer Struktur M ist eine
Abbildung [mm] \beta [/mm] : [mm] X=\{x^0,x^1,..\} [/mm] -> [mm] \underline{M} [/mm] (grundmenge zur Struktur). Wenn [mm] \sigma [/mm] die Signatur von M ist, setzen wir eine Belegung [mm] \beta [/mm] in M wie folgt rekursiv zu einer Abbildung [mm] \beta^- [/mm] : {t : t ist [mm] \sigma-Term} [/mm] -> M fort:
-) [mm] \beta^- ((x_0))= \beta(x_0), \beta^- ((x_1)) [/mm] = [mm] \beta(x_1),..,usw. [/mm]
-) [mm] \beta^- (ft_1 [/mm] .. [mm] t_k) [/mm] = [mm] f^M (\beta^- ((t_1)),.., \beta^- ((t_k))) [/mm]

Edit: Wenn sich wer damit beschäftigen will, gebe ich euch per privat Nachricht das Skript.
Oder Buchausschnitt: [mm] http://link.springer.com/content/pdf/10.1007%2F978-3-0346-0652-3_2 [/mm]

u äquiv zu u' nach Def in Angabe<=> u= u'

<= u=u'
Zuzeigen für beliebe Forsetzungen der Belegung gilt [mm] \beta^- [/mm] (u) = [mm] \beta^- [/mm] (u')
Wenn u eine Variable ist, ist klar dass [mm] \beta^- [/mm] (u) = [mm] \beta [/mm] (u) [mm] =\beta(u')= \beta^-(u') [/mm]
Wenn u die andere Form hat folgt das zuzeigende  aus der Eindeutigkeit der Darstellung.

=> Beliebige Struktur M mit Signatur [mm] \sigma [/mm] und beliebige Belegung mit [mm] \beta^- [/mm] (u) = [mm] \beta^- [/mm] (u')
ZZ.: u=u'

3Fälle (die ich alle nicht zu beweisen weiß)
1)Sei u eine Variable also von der gestalt z.B.: [mm] x^0 [/mm]
nach Definition [mm] \beta^- (x^0) [/mm] = [mm] \beta(x_0) [/mm]
u' ebenfalls Variable also von gestalt [mm] x^1 [/mm] : [mm] \beta^-(x^1) [/mm] = [mm] \beta( x^1) [/mm]

2) u eine Variable und u'=f [mm] s_1 ..s_k [/mm]  dann nach definition
[mm] \beta^-(u') [/mm] = [mm] f^M [/mm] ( [mm] \beta^- (s_1),.., \beta^- (s_k)) [/mm]

3) u und u' keine variablen also von der gestalt
u= g [mm] u_1 [/mm] .. [mm] u_l [/mm]
u' = f [mm] s_1 ..s_k [/mm]

Bei 3)
Vor..: [mm] \beta^-(u)= \beta^-(u') [/mm]
<=>  [mm] f^M (\beta^- (u_1),.., \beta^- (u_k))= g^M (\beta^- (s_1),.., \beta^- (s_l)) [/mm]

Idee war in dem Zusammenhang noch Induktion nach der Länge von u. Da Belegung rekursiv defeniert ist.
O.b.d.A l [mm] \le [/mm] k
Jeweils Teilzeichenkete [mm] u_1 [/mm] und [mm] s_1 [/mm] von u und u' um jeweils 1 Symbol kürzer als u (da ja die Funktionsoperation vorne steht)
Induktionsvoraussetzung sagt: [mm] \beta^- (u_1) [/mm] = [mm] \beta^- (s_1) [/mm] => [mm] u_1 =s_1 [/mm]
usw.
Problem: l [mm] \le [/mm] k und Funktionssymbole müssen nicht gleich sein, wenn länge nicht gleich ist.

        
Bezug
Belegung von Termen,: dein Lösungsansatz
Status: (Antwort) fertig Status 
Datum: 07:29 Do 18.04.2013
Autor: tobit09

Hallo Lu-,


> Definiton: Zwei [mm]\sigma-Terme[/mm] u und u' sind äquivalent,
> falls für jede
>  Struktur M der Signatur [mm]\sigma[/mm] und jede Belegung [mm]\beta[/mm] in
> M gilt: [mm]\beta^-(u)= \beta^-(u').[/mm]
>  Zeigen Sie,
>  dass zwei [mm]\sigma-Terme[/mm] genau dann gleich sind, wenn sie
> identisch sind.

Gemeint ist wohl: Zeigen Sie, dass zwei [mm] $\sigma$-Terme [/mm] genau dann ÄQUIVALENT sind, wenn sie identisch sind.

> Hinweis Termalgebra

Eurem Skript entnehme ich, dass der vollständige Hinweis wie folgt lautet:

"Es gibt sogar für jede Signatur [mm] $\sigma$ [/mm] eine einzige [mm] $\sigma$-Struktur [/mm] $M$, so dass für alle Belegungen [mm] $\beta$ [/mm] in $M$ und alle [mm] $\sigma$-Terme [/mm] $t,t'$ gilt: [mm] $\overline{\beta}(t)=\overline{\beta}(t')\gdw [/mm] t=t'$. Diese Struktur heißt Termalgebra, weil sie aus Termen besteht."

Bitte gib beim nächsten Mal solche Hinweise vollständig an!


Zu zeigen:

> u äquiv zu u' nach Def in Angabe<=> u= u'
>  
> <= u=u'
>  Zuzeigen für beliebe Forsetzungen der Belegung gilt
> [mm]\beta^-[/mm] (u) = [mm]\beta^-[/mm] (u')
>  Wenn u eine Variable ist, ist klar dass [mm]\beta^-[/mm] (u) =
> [mm]\beta[/mm] (u) [mm]=\beta(u')= \beta^-(u')[/mm]
>  Wenn u die andere Form
> hat folgt das zuzeigende  aus der Eindeutigkeit der
> Darstellung.

Wenn $u=u'$ ist, gilt trivialerweise [mm] $\overline{\beta}(u)=\overline{\beta}(u')$. [/mm] Für diese Richtung ist also nichts weiter zu tun.


> => Beliebige Struktur M mit Signatur [mm]\sigma[/mm] und beliebige
> Belegung mit [mm]\beta^-[/mm] (u) = [mm]\beta^-[/mm] (u')

Möglicherweise hast du etwas missverstanden: Falls $u$ und $u'$ äquivalent sind, haben wir nicht nur irgendeine Struktur $M$ und eine Belegung [mm] $\beta$ [/mm] in $M$, für die [mm] $\overline{\beta}(u)=\overline{\beta}(u')$ [/mm] gilt. Vielmehr gilt im Falle $u$ und $u'$ äquivalent [mm] $\overline{\beta}(u)=\overline{\beta}(u')$ [/mm] für ALLE Strukturen $M$ mit Signatur [mm] $\sigma$ [/mm] und ALLE Belegungen [mm] $\beta$ [/mm] in $M$.

Um diese Voraussetzung auszunutzen, wirst du auf jeden Fall eine oder mehrere einzelne Strukturen $M$ mit Belegung(en) [mm] $\beta$ [/mm] in $M$ konstruieren müssen, auf die du die Voraussetzung anwendest.


>  ZZ.: u=u'
>  
> 3Fälle (die ich alle nicht zu beweisen weiß)
>  1)Sei u eine Variable also von der gestalt z.B.: [mm]x^0[/mm]
>  nach Definition [mm]\beta^- (x^0)[/mm] = [mm]\beta(x_0)[/mm]
>  u' ebenfalls Variable also von gestalt [mm]x^1[/mm] : [mm]\beta^-(x^1)[/mm]
> = [mm]\beta( x^1)[/mm]

Besser: [mm] $u=x^i$ [/mm] und [mm] $u'=x^j$ [/mm] für gewisse [mm] $i,j\in\IN_0$. [/mm]

Angenommen nun [mm] $u\not=u'$ [/mm] und somit [mm] $i\not=j$. [/mm]

Bastele nun eine Struktur $M$ mit Signatur [mm] $\sigma$ [/mm] und eine Belegung [mm] $\beta$ [/mm] in $M$, so dass [mm] $\overline{\beta}(u)\not=\overline{\beta}(u')$. [/mm] (Vorschlag: [mm] $\underline{M}:=\{0,1\}$) [/mm]

Das ist der gewünschte Widerspruch.


> 2) u eine Variable und u'=f [mm]s_1 ..s_k[/mm]  dann nach definition
> [mm]\beta^-(u')[/mm] = [mm]f^M[/mm] ( [mm]\beta^- (s_1),.., \beta^- (s_k))[/mm]

Dieser Fall ist zum Widerspruch zu führen.

Bastele wieder eine Struktur $M$ mit Signatur [mm] $\sigma$ [/mm] und eine Belegung [mm] $\beta$ [/mm] in $M$, so dass [mm] $\overline{\beta}(u)\not=\overline{\beta}(u')$. [/mm] (Vorschlag: erneut [mm] $\underline{M}:=\{0,1\}$) [/mm]


> 3) u und u' keine variablen also von der gestalt
>  u= g [mm]u_1[/mm] .. [mm]u_l[/mm]
>  u' = f [mm]s_1 ..s_k[/mm]
>  
> Bei 3)
>  Vor..: [mm]\beta^-(u)= \beta^-(u')[/mm]
>  <=>  [mm]f^M (\beta^- (u_1),.., \beta^- (u_k))= g^M (\beta^- (s_1),.., \beta^- (s_l))[/mm]
>  
> Idee war in dem Zusammenhang noch Induktion nach der Länge
> von u. Da Belegung rekursiv defeniert ist.
>  O.b.d.A l [mm]\le[/mm] k
>  Jeweils Teilzeichenkete [mm]u_1[/mm] und [mm]s_1[/mm] von u und u' um
> jeweils 1 Symbol kürzer als u (da ja die
> Funktionsoperation vorne steht)

Die Idee habe ich auch versucht. Leider führt sie wohl nicht zum Erfolg.

>  Induktionsvoraussetzung sagt: [mm]\beta^- (u_1)[/mm] = [mm]\beta^- (s_1)[/mm]
> => [mm]u_1 =s_1[/mm]
> usw.

Nein.

>  Problem: l [mm]\le[/mm] k und Funktionssymbole müssen nicht gleich
> sein, wenn länge nicht gleich ist.

Den Fall [mm] $f\not=g$ [/mm] kann man wieder wie oben zum Widerspruch führen.

Bliebe der Fall $f=g$ (und somit $l=k$) zu behandeln. Dieser lässt sich anscheinend nicht so elementar wie die anderen Fälle behandeln.


Daher: Fangen wir nochmal neu an und folgen dem Hinweis! Ich schreibe gleich dazu eine weitere Antwort.


Viele Grüße
Tobias

Bezug
                
Bezug
Belegung von Termen,: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:10 Do 18.04.2013
Autor: Lu-


>  Zuzeigen für beliebe Forsetzungen der Belegung gilt
> $ [mm] \beta^- [/mm] $ (u) = $ [mm] \beta^- [/mm] $ (u')
>  Wenn u eine Variable ist, ist klar dass $ [mm] \beta^- [/mm] $ (u) =
> $ [mm] \beta [/mm] $ (u) $ [mm] =\beta(u')= \beta^-(u') [/mm] $
>  Wenn u die andere Form
> hat folgt das zuzeigende  aus der Eindeutigkeit der
> Darstellung.

> Wenn $ u=u' $ ist, gilt trivialerweise $ [mm] \overline{\beta}(u)=\overline{\beta}(u') [/mm] $. Für diese Richtung ist also nichts weiter zu tun.

Ich würde die eindeutigkeit der Darstellung schon dazusagen.
weil wenn u=u' ist könnte man ja bei nicht Variablen ohne Eindeutigkeit der Lesbarkeit u und u' verschieden schreiben und dann wäre keine gleichheit der belegungen gegeben.

Bezug
                        
Bezug
Belegung von Termen,: Antwort
Status: (Antwort) fertig Status 
Datum: 08:27 Do 18.04.2013
Autor: tobit09


> >  Zuzeigen für beliebe Forsetzungen der Belegung gilt

>  > [mm]\beta^-[/mm] (u) = [mm]\beta^-[/mm] (u')

>  >  Wenn u eine Variable ist, ist klar dass [mm]\beta^-[/mm] (u) =
>  > [mm]\beta[/mm] (u) [mm]=\beta(u')= \beta^-(u')[/mm]

>  >  Wenn u die andere
> Form
>  > hat folgt das zuzeigende  aus der Eindeutigkeit der

>  > Darstellung.

>  
> > Wenn [mm]u=u'[/mm] ist, gilt trivialerweise
> [mm]\overline{\beta}(u)=\overline{\beta}(u') [/mm]. Für diese
> Richtung ist also nichts weiter zu tun.
>  
> Ich würde die eindeutigkeit der Darstellung schon
> dazusagen.
>  weil wenn u=u' ist könnte man ja bei nicht Variablen ohne
> Eindeutigkeit der Lesbarkeit u und u' verschieden schreiben
> und dann wäre keine gleichheit der belegungen gegeben.  

Wäre die Eindeutigkeit der Lesbarkeit von $u=u'$ nicht gegeben, wäre die Wohldefiniertheit von [mm] $\overline{\beta}$ [/mm] fraglich.

Aus der Vorlesung ist jedoch offenbar bekannt, dass [mm] $\overline{\beta}$ [/mm] eine wohldefinierte Abbildung von der Menge der [mm] $\sigma$-Terme [/mm] nach [mm] $\underline{M}$ [/mm] ist (sonst wäre es unsinnig, in der Aufgabenstellung überhaupt von [mm] $\overline{\beta}$ [/mm] zu sprechen).

Und handelt es sich bei [mm] $\overline{\beta}$ [/mm] um eine wohldefinierte Abbildung, so folgt aus $u=u'$ trivialerweise [mm] $\overline{\beta}(u)=\overline{\beta}(u')$. [/mm]

Bezug
        
Bezug
Belegung von Termen,: Lösung mithilfe Hinweis
Status: (Antwort) fertig Status 
Datum: 08:04 Do 18.04.2013
Autor: tobit09

Hier nochmal der Hinweis:

"Es gibt sogar für jede Signatur [mm] $\sigma$ [/mm] eine einzige [mm] $\sigma$-Struktur [/mm] $M$, so dass für alle Belegungen [mm] $\beta$ [/mm] in $M$ und alle [mm] $\sigma$-Terme [/mm] $t,t'$ gilt: [mm] $\overline{\beta}(t)=\overline{\beta}(t')\gdw [/mm] t=t'$. Diese Struktur heißt Termalgebra, weil sie aus Termen besteht."


Wie ich gerade festgestellt habe, ist der Hinweis fehlerhaft. Die einzige Struktur $M$, die der Bedingung aus dem Hinweis genügen kann, ist die (im Falle ihrer Existenz eindeutig bestimmte) [mm] $\sigma$-Struktur [/mm] $M$ mit [mm] $\underline{M}=\emptyset$. [/mm] Sie existiert sowieso nur dann, wenn [mm] $\sigma$ [/mm] keine Konstanten enthält. Und selbst dann hilft sie uns nicht weiter: Es gibt dann gar keine Belegung [mm] $\beta$ [/mm] in $M$.

Korrekt muss der Hinweis wie folgt lauten:

"Es gibt sogar für jede Signatur [mm] $\sigma$ [/mm] eine einzige [mm] $\sigma$-Struktur [/mm] $M$ und eine Belegung [mm] $\beta$ [/mm] in $M$ mit der Eigenschaft:

(*) Für alle [mm] $\sigma$-Terme [/mm] $t,t'$ gilt: [mm] $\overline{\beta}(t)=\overline{\beta}(t')\gdw [/mm] t=t'$.

Diese Struktur heißt Termalgebra, weil sie aus Termen besteht."


Ist dir klar, dass der Beweis der Behauptung aus dem (korrigierten) Hinweis für den Beweis unserer noch fehlenden Hin-Richtung genügt?


Basteln wir also nun $M$ und [mm] $\beta$ [/mm] mit der Eigenschaft (*):

Wie der letzte Satz des Hinweises andeutet, ist

     [mm] $\underline{M}:=\{t\;|\;t\text{ ist }\sigma\text{-Term}\}$ [/mm]

ein guter Anfang.

Sei nun $f$ ein $k$-stelliges Operationssymbol von [mm] $\sigma$. [/mm] Gesucht ist nun eine "sinnvolle" Wahl von [mm] $f^M\colon \underline{M}^k\to\underline{M}$: [/mm]

Wie kann man [mm] $f^M(t_1,\ldots,t_k)\in\underline{M}$ [/mm] für [mm] $t_1,\ldots,t_k\in\underline{M}$ [/mm] wohl sinnvoll festlegen?

Wir haben also [mm] $\sigma$-Terme $t_1,\ldots,t_k$ [/mm] und suchen einen [mm] $\sigma$-Term [/mm] für [mm] $f^M(t_1,\ldots,t_k)$. [/mm]

Als nächstes benötigen wir eine "sinnvolle" Belegung [mm] $\beta$ [/mm] in $M$, also eine Abbildung [mm] $\{x^0,x^1,x^2,\ldots\}\to\underline{M}$: [/mm]

Welches Element von [mm] $\underline{M}$ [/mm] könnten wir "sinnvollerweise" [mm] $x^i$ ($i\in\IN_0$) [/mm] zuordnen?


Wenn nun $M$ und [mm] $\beta$ [/mm] stehen, ist (*) zu zeigen.

Finde dazu eine naheliegende Vermutung, wie [mm] $\overline\beta(s)\in\underline{M}$ [/mm] für [mm] $\sigma$-Terme [/mm] $s$ aussehen könnte.

Beweise sie per Induktion nach dem Aufbau oder der Länge von $s$.

Folgere dann (*).


Viel Erfolg!

Bezug
                
Bezug
Belegung von Termen,: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:42 Do 18.04.2013
Autor: Lu-

Hallo
Ich hab noch paar Fragen dazu:

>  Die einzige Struktur $ M $, die der Bedingung aus dem Hinweis genügen kann, ist die (im Falle ihrer Existenz eindeutig bestimmte) $ [mm] \sigma [/mm] $-Struktur $ M $ mit $ [mm] \underline{M}=\emptyset [/mm] $. Sie existiert sowieso nur dann, wenn $ [mm] \sigma [/mm] $ keine Konstanten enthält. Und selbst dann hilft sie uns nicht weiter

Wir kommst du darauf, dass es außer [mm] \underline{M}=\emptyset [/mm] dann keine geben kann?

> Ist dir klar, dass der Beweis der Behauptung aus dem (korrigierten) Hinweis für den Beweis unserer noch fehlenden Hin-Richtung genügt?

Ist der Hinweis dann nicht eine Abschwächung von der Angabe?
Oder meint man: Es gibt sowie nur eine Belegung also gilt es natürlich für JEDE Belegung. ABer das es nur eine einzige gibt müsste man doch dann auch beweisen?


> Sei nun $ f $ ein $ k $-stelliges Operationssymbol von $ [mm] \sigma [/mm] $. Gesucht ist nun eine "sinnvolle" Wahl von $ [mm] f^M\colon \underline{M}^k\to\underline{M} [/mm] $:

> Wie kann man $ [mm] f^M(t_1,\ldots,t_k)\in\underline{M} [/mm] $ für $ [mm] t_1,\ldots,t_k\in\underline{M} [/mm] $ wohl sinnvoll festlegen?

> Wir haben also $ [mm] \sigma [/mm] $-Terme $ [mm] t_1,\ldots,t_k [/mm] $ und suchen einen $ [mm] \sigma [/mm] $-Term für $ [mm] f^M(t_1,\ldots,t_k) [/mm] $.

Der Ausdruck der Form: [mm] f^M(t_1,\ldots,t_k) [/mm] ist doch sowieso ein sigma term nach der Definition dieser.
(Wenn f [mm] \in \sigma^{op} [/mm] und k=ar(f) gilt und [mm] t_1 [/mm] ,.., [mm] t_k \sigma- [/mm] Terme sind, dann ist auch f [mm] t_1 [/mm] .. [mm] t_k [/mm] ein [mm] \sigma- [/mm] Term)

> Als nächstes benötigen wir eine "sinnvolle" Belegung $ [mm] \beta [/mm] $ in $ M $, also eine Abbildung $ [mm] \{x^0,x^1,x^2,\ldots\}\to\underline{M} [/mm] $:

> Welches Element von $ [mm] \underline{M} [/mm] $ könnten wir "sinnvollerweise" $ [mm] x^i [/mm] $ ($ [mm] i\in\IN_0 [/mm] $) zuordnen?

[mm] \beta (x^i [/mm] )= [mm] x^i [/mm]
Da jede Variable selbst ein Sigma-Term ist.

> Finde dazu eine naheliegende Vermutung, wie $ [mm] \overline\beta(s)\in\underline{M} [/mm] $ für $ [mm] \sigma [/mm] $-Terme $ s $ aussehen könnte.

Wie soll ich das anders als wie in der Definition von Belegungen vermuten?
Klar ist [mm] \overline{\beta } (x^i)= \beta(x^i)=x^i [/mm] , [mm] \overline{\beta} [/mm] (f [mm] t_1 ..t_k)= f^M (\overline{\beta}(t_1),..,\overline{\beta}(t_k)) [/mm] wie in der definition der belegung.
Iterativ:
[mm] \overline{\beta} [/mm] (f [mm] t_1 ..t_k)= f^M (\overline{\beta}(t_1),..,\overline{\beta}(t_k)) [/mm] = [mm] f^M [f^M (\overline{\beta}(t_1_1),..,\overline{\beta} (t_1_k)),..,f^M (\overline{\beta} (t_k_1),..,\overline{\beta} (t_k_k)] [/mm]

Bezug
                        
Bezug
Belegung von Termen,: Antwort
Status: (Antwort) fertig Status 
Datum: 09:18 Do 18.04.2013
Autor: tobit09


>  >  Die einzige Struktur [mm]M [/mm], die der Bedingung aus dem
> Hinweis genügen kann, ist die (im Falle ihrer Existenz
> eindeutig bestimmte) [mm]\sigma [/mm]-Struktur [mm]M[/mm] mit
> [mm]\underline{M}=\emptyset [/mm]. Sie existiert sowieso nur dann,
> wenn [mm]\sigma[/mm] keine Konstanten enthält. Und selbst dann
> hilft sie uns nicht weiter
>  Wir kommst du darauf, dass es außer
> [mm]\underline{M}=\emptyset[/mm] dann keine geben kann?

Angenommen es gibt ein [mm] $a\in\underline{M}$. [/mm] Dann können wir die konstante Belegung [mm] $\beta$ [/mm] definiert durch

     [mm] $\beta(x_i):=a$ [/mm]     für alle [mm] $i\in\IN_0$ [/mm]

betrachten. Mit [mm] $t:=x^0$ [/mm] und [mm] $t':=x_1$ [/mm] gilt dann

     [mm] $\overline\beta(t)=\beta(x^0)=a=\beta(x^1)=\overline{\beta}(t')$, [/mm]

aber nicht $t=t'$.


>  > Ist dir klar, dass der Beweis der Behauptung aus dem

> (korrigierten) Hinweis für den Beweis unserer noch
> fehlenden Hin-Richtung genügt?
> Ist der Hinweis dann nicht eine Abschwächung von der
> Angabe?

Ich habe das "für jede Belegung" durch "existiert eine Belegung" ersetzt.

Das klingt ersteinmal schwächer. Irgendwie musste ich ja auch die ursprüngliche i.A. falsche Behauptung des Hinweises abschwächen, um zu einer richtigen Behauptung zu gelangen.

Aber meine Version des Hinweises ist auch in einer Hinsicht stärker als der ursprüngliche: Es wird gefordert, dass es überhaupt eine Belegung in $M$ gibt (was genau dann der Fall ist, wenn [mm] $\underline{M}\not=\emptyset$). [/mm]

Und genau das benötigen wir! Bei der Hin-Richtung wissen wir, dass (*) für ALLE [mm] $\sigma$-Strukturen [/mm] $M$ und ALLE Belegungen [mm] $\beta$ [/mm] gilt. Das hilft uns weiter, wenn wir eine konkrete [mm] $\sigma$-Struktur [/mm] $M$ und eine konkrete Belegung [mm] $\beta$ [/mm] basteln und auf diese (*) anwenden.

>  Oder meint man: Es gibt sowie nur eine Belegung also gilt
> es natürlich für JEDE Belegung.

Nein.

> ABer das es nur eine
> einzige gibt müsste man doch dann auch beweisen?

Nein, wir behaupten keine Eindeutigkeit von [mm] $\beta$. [/mm]


> > Sei nun [mm]f[/mm] ein [mm]k [/mm]-stelliges Operationssymbol von [mm]\sigma [/mm].
> Gesucht ist nun eine "sinnvolle" Wahl von [mm]f^M\colon \underline{M}^k\to\underline{M} [/mm]:
>  
> > Wie kann man [mm]f^M(t_1,\ldots,t_k)\in\underline{M}[/mm] für
> [mm]t_1,\ldots,t_k\in\underline{M}[/mm] wohl sinnvoll festlegen?
>  
> > Wir haben also [mm]\sigma [/mm]-Terme [mm]t_1,\ldots,t_k[/mm] und suchen
> einen [mm]\sigma [/mm]-Term für [mm]f^M(t_1,\ldots,t_k) [/mm].
> Der Ausdruck der Form: [mm]f^M(t_1,\ldots,t_k)[/mm] ist doch sowieso
> ein sigma term nach der Definition dieser.

Nicht ganz. In [mm] $\sigma$-Termen [/mm] kommen nach eurem Skript (i.A.) nicht das Zeichen [mm] $f^M$ [/mm] und keine Klammern vor, aber möglicherweise das Zeichen $f$.

>  (Wenn f [mm]\in \sigma^{op}[/mm] und k=ar(f) gilt und [mm]t_1[/mm] ,.., [mm]t_k \sigma-[/mm]
> Terme sind, dann ist auch f [mm]t_1[/mm] .. [mm]t_k[/mm] ein [mm]\sigma-[/mm] Term)

Genau. Setze

     [mm] $f^M(t_1,\ldots,t_k):=ft_1\ldots t_k$. [/mm]

> > Als nächstes benötigen wir eine "sinnvolle" Belegung
> [mm]\beta[/mm] in [mm]M [/mm], also eine Abbildung
> [mm]\{x^0,x^1,x^2,\ldots\}\to\underline{M} [/mm]:
>  
> > Welches Element von [mm]\underline{M}[/mm] könnten wir
> "sinnvollerweise" [mm]x^i[/mm] ([mm] i\in\IN_0 [/mm]) zuordnen?
> [mm]\beta (x^i[/mm] )= [mm]x^i[/mm]
>  Da jede Variable selbst ein Sigma-Term ist.

[ok]


> > Finde dazu eine naheliegende Vermutung, wie
> [mm]\overline\beta(s)\in\underline{M}[/mm] für [mm]\sigma [/mm]-Terme [mm]s[/mm]
> aussehen könnte.
> Wie soll ich das anders als wie in der Definition von
> Belegungen vermuten?
>  Klar ist [mm]\overline{\beta } (x^i)= \beta(x^i)=x^i[/mm] ,
> [mm]\overline{\beta}[/mm] (f [mm]t_1 ..t_k)= f^M (\overline{\beta}(t_1),..,\overline{\beta}(t_k))[/mm]
> wie in der definition der belegung.

Ja. Also nach unserer Definition von [mm] $f^M$: [/mm]

     [mm] $\overline{\beta}(ft_1\ldots t_k)=f\overline\beta(t_1)\ldots\overline{\beta}(t_k)$. [/mm]

>  Iterativ:
>  [mm]\overline{\beta}[/mm] (f [mm]t_1 ..t_k)= f^M (\overline{\beta}(t_1),..,\overline{\beta}(t_k))[/mm]
> = [mm]f^M [f^M (\overline{\beta}(t_1_1),..,\overline{\beta} (t_1_k)),..,f^M (\overline{\beta} (t_k_1),..,\overline{\beta} (t_k_k)][/mm]

Das zweite Gleichheitszeichen ist Quatsch. Warum sollte z.B. [mm] $t_1$ [/mm] die Gestalt [mm] $t_1=ft_1_1\ldots t_1_k$ [/mm] haben? [mm] $t_1$ [/mm] könnte auch eine Variable oder von der Form [mm] $t_1=gt_1_1\ldots t_1_l$ [/mm] für irgendein $l$-stelliges Funktionssymbol $g$ von [mm] $\sigma$ [/mm] sein.


Zeige per Induktion:

     [mm] $\overline{\beta}(s)=s$ [/mm]

für alle [mm] $\sigma$-Terme [/mm] $s$.

Folgere dann (*).

Bezug
                                
Bezug
Belegung von Termen,: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:50 Do 18.04.2013
Autor: Lu-

Hallo
Ah also:

> Folgere dann (*)

Wenn wir den Hinweis gezeigt haben. Folgt aus dem Hinweis und der Vorausetzung, dass für alle $ [mm] \sigma [/mm] $-Strukturen $ M $ und alle Belegungen $ [mm] \beta [/mm] $  die Eigenschaft (*) gilt. Was ja zuzeigen war.

> Zeige per Induktion:

     $ [mm] \overline{\beta}(s)=s [/mm] $

> für alle $ [mm] \sigma [/mm] $-Terme $ s $.

Den Induktionsanfang für s der Länge 1 ist oben für Variablen gezeigt.
Was ist hier nun wenn wir es mit einer 0 stelleigen Funktion zu tun haben (konstante). [mm] \overline{\beta} [/mm] (f) =f (konstanten werden auf kostanten abgebildet ist klar)

Es gelte nach Induktionsvorrausetzung für alle [mm] \sigma [/mm] Terme der Länge n
I.Schritt für Länge n+1
[mm] \overline{\beta} (ft_1 [/mm] .. [mm] t_n [/mm] )= f [mm] \overline{\beta} (t_1) [/mm] .. [mm] \overline{\beta} (t_n) [/mm]
nach Induktionsvor.:
= f [mm] t_1 ..t_n [/mm]
qed.

Bezug
                                        
Bezug
Belegung von Termen,: Antwort
Status: (Antwort) fertig Status 
Datum: 10:12 Do 18.04.2013
Autor: tobit09


>  > Folgere dann (*)

>  Wenn wir den Hinweis gezeigt haben.

[haee]

(*) ist ein Teil des Hinweises: Wir behaupten, dass unser [mm] $\beta$ [/mm] der Bedingung

     (*) Für alle [mm] $\sigma$-Terme [/mm] $t,t'$ gilt: [mm] $\overline{\beta}(t)=\overline{\beta}(t')\gdw [/mm] t=t'$.

genügt.

Wegen [mm] $\overline\beta(t)=t$ [/mm] und [mm] $\overline\beta(t')=t'$ [/mm] (s.u.) ist das trivial.

Damit ist der Hinweis gezeigt.


> Folgt aus dem Hinweis
> und der Vorausetzung, dass für alle [mm]\sigma [/mm]-Strukturen [mm]M[/mm]
> und alle Belegungen [mm]\beta[/mm]  die Eigenschaft (*) gilt. Was ja
> zuzeigen war.

Nein. Unsere Voraussetzung sagt, dass u und u' äquivalent sind, also dass [mm] $\overline\beta(u)=\overline\beta(u')$ [/mm] für alle [mm] $\beta$ [/mm] gilt.

Insbesondere gilt dies also für unser [mm] $\beta$. [/mm]

Unser [mm] $\beta$ [/mm] (und nicht jedes [mm] $\beta$!) [/mm] genügt darüber hinaus (*).

Also ($t:=u$, $t':=u'$):

     $u=u'$.

Was zu zeigen war.


> > Zeige per Induktion:
>  
> [mm]\overline{\beta}(s)=s[/mm]
>  
> > für alle [mm]\sigma [/mm]-Terme [mm]s [/mm].

Zwei Möglichkeiten: Induktion nach dem Aufbau von $s$ (falls ihr dieses Verfahren kennt) oder Induktion nach der Länge von $s$.

Du hast dich offenbar für letzteres entschieden.

> Den Induktionsanfang für s der Länge 1 ist oben für
> Variablen gezeigt.

Ja.

>  Was ist hier nun wenn wir es mit einer 0 stelleigen
> Funktion zu tun haben (konstante). [mm]\overline{\beta}[/mm] (f) =f
> (konstanten werden auf kostanten abgebildet ist klar)

Ja, denn für Konstanten $f$ gilt

     [mm] $\overline\beta(f)=f^M(())=f$ [/mm]

nach Definition von [mm] $\overline\beta$ [/mm] und [mm] $f^M$. [/mm]

> Es gelte nach Induktionsvorrausetzung für alle [mm]\sigma[/mm]
> Terme der Länge n
>  I.Schritt für Länge n+1
>  [mm]\overline{\beta} (ft_1[/mm] .. [mm]t_n[/mm] )= f [mm]\overline{\beta} (t_1)[/mm]
> .. [mm]\overline{\beta} (t_n)[/mm]
> nach Induktionsvor.:
>  = f [mm]t_1 ..t_n[/mm]

Abgesehen davon, dass du die Indizes n und k verwechselt hast: [ok]

Bezug
                                                
Bezug
Belegung von Termen,: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:30 Do 18.04.2013
Autor: Lu-

Vielen dank.
Aber mir ist noch immer eine Sache unklar, die du schon erklärt hast.

Wir haben ja nun den Hinweis bewiesen: Für jede Signatur [mm] \sigma [/mm] GIBT ES EINE ....und eine Belegung ... mit Eig (*)

ZuZeigen ist:
Das für jede Struktir M der SIgnatur [mm] \sigma [/mm] und JEDE Belegug [mm] \beta [/mm] in M (*) gilt.


> Ich habe das "für jede Belegung" durch "existiert eine Belegung" ersetzt.

> Das klingt ersteinmal schwächer. Irgendwie musste ich ja auch die ursprüngliche i.A. falsche Behauptung des Hinweises abschwächen, um zu einer richtigen Behauptung zu gelangen.

ja

> Aber meine Version des Hinweises ist auch in einer Hinsicht stärker als der ursprüngliche: Es wird gefordert, dass es überhaupt eine Belegung in $ M $ gibt (was genau dann der Fall ist, wenn $ [mm] \underline{M}\not=\emptyset [/mm] $).

Ja aber es ist doch zuzeigen  für ALLE Belegungen. Wir haben es aber nur für eine gezeigt, dafür aber gibt es immer solch eine.

Sry, dass ich da nochmals nachfrage. ABer es ist für mich nach paar mal lesen nicht klar geworden-

Bezug
                                                        
Bezug
Belegung von Termen,: Antwort
Status: (Antwort) fertig Status 
Datum: 11:06 Do 18.04.2013
Autor: tobit09


>  Aber mir ist noch immer eine Sache unklar, die du schon
> erklärt hast.
>  
> Wir haben ja nun den Hinweis bewiesen: Für jede Signatur
> [mm]\sigma[/mm] GIBT ES EINE ....und eine Belegung ... mit Eig (*)
>  
> ZuZeigen ist:
>  Das für jede Struktir M der SIgnatur [mm]\sigma[/mm] und JEDE
> Belegug [mm]\beta[/mm] in M (*) gilt.

Nein, das ist nicht zu zeigen, das wäre auch falsch.

> > Aber meine Version des Hinweises ist auch in einer Hinsicht
> stärker als der ursprüngliche: Es wird gefordert, dass es
> überhaupt eine Belegung in [mm]M[/mm] gibt (was genau dann der Fall
> ist, wenn [mm]\underline{M}\not=\emptyset [/mm]).
>  Ja aber es ist
> doch zuzeigen  für ALLE Belegungen.

Nein.

> Wir haben es aber nur
> für eine gezeigt, dafür aber gibt es immer solch eine.
>  
> Sry, dass ich da nochmals nachfrage. ABer es ist für mich
> nach paar mal lesen nicht klar geworden-

Gut, dass du nachfragst! Dafür ist das Forum ja da!


Wir wollen ja nicht die Behauptung des ursprünglichen Hinweises (die i.A. falsch ist!) zeigen, sondern die Behauptung aus der Aufgabe:

     $u$ ist äquivalent zu $u'$     [mm] $\gdw$ [/mm]     $u=u'$.

Die Rück-Richtung haben wir ganz zu Beginn abgehandelt, da gab es nicht viel zu tun.

Zuletzt waren wir bei der deutlich schwierigeren Hin-Richtung.

Dafür durften wir VORAUSSETZEN, dass $u$ äquivalent zu $u'$ ist, d.h. dass für ALLE Belegungen [mm] $\beta$ [/mm] in allen Strukturen

(**)     [mm] $\overline\beta(u)=\overline\beta(u')$ [/mm]

gilt.

Wir mussten "nur" $u=u'$ zeigen.


Dazu haben wir eine bestimmte Belegung [mm] $\beta$ [/mm] in einer bestimmten Struktur $M$ gebastelt, die die besondere Eigenschaft (*) hat:

(*) Für alle [mm] $\sigma$-Terme [/mm] $t,t'$ gilt: [mm] $\overline{\beta}(t)=\overline{\beta}(t')\gdw [/mm] t=t'$.

Insbesondere gilt für unser [mm] $\beta$ [/mm] die Äquivalenz ($t:=u$, $t':=u'$)

(***)     [mm] $\overline\beta(u)=\overline{\beta}(u')\gdw [/mm] u=u'$.

Unser [mm] $\beta$ [/mm] erfüllt (wie alle anderen [mm] $\beta$) [/mm] auch die Bedingung (**).

Zusammen mit (***) folgt $u=u'$.

Genau das war bei der Hin-Richtung zu zeigen.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Prädikatenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]