Belegung von Termen, < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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]](/images/smileys/ok.gif "[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 (*).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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-
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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.
|
|
|
|
![[haee]](/images/smileys/haee.gif "[haee]"){kind=small}
