Inj/Surj first-order-Sprache < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:48 Mo 29.04.2013 | | Autor: | Lu- |
| Aufgabe | | Sei [mm] \sigma [/mm] eine SIgnatur mit einem einstelligen Operationssymbol f : Geben SIe einene [mm] \sigma-Satz \phi [/mm] an, so dass gilt: Für jede [mm] \sigma [/mm] Struktur gilt M [mm] \models \phi [/mm] genau dann wenn [mm] f^M [/mm] injektiv ist. |
Die Aufgabe ansich ist ja sehr einfach, aber meine Lösung stimmt nicht mit der Musterlösung übrein.
Inj [mm] \forall [/mm] x,y gilt wenn x [mm] \not=y [/mm] -> f(x) [mm] \not= [/mm] f(y)
[mm] \neg \exists x^0 \exists x^1 \neg \neg \wedge \beg [/mm] = [mm] x^0 x^1 \neg \neg [/mm] = [mm] fx^0 fx^1
[/mm]
da
[mm] \neg \exists x^0 \exists x^1 \neg.. \forall x^0 \forall x^1
[/mm]
-> [mm] \psi \phi [/mm] ... [mm] \neg \wedge \phi \neg \psi
[/mm]
MusterLösung:
[mm] \neg \exists x^0 \exists x^1\wedge \beg [/mm] = [mm] x^0 x^1 \wedge [/mm] = f [mm] x^0 fx^1
[/mm]
Es ist mit klar, dass man meine beiden Negationszeichen jeweils kürzen kann, aber da steht ein zweites [mm] \wedge..
[/mm]
kann man auch so eine Frage stellen mit der Surjektivität?
Meine Lösung wäre dann: [mm] \neg \exists x^0 \neg \exists x^1 [/mm] = [mm] x^0 fx^1
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:10 Di 30.04.2013 | | Autor: | tobit09 |
Hallo Lu-,
> Die Aufgabe ansich ist ja sehr einfach, aber meine Lösung
> stimmt nicht mit der Musterlösung übrein.
>
> Inj [mm]\forall[/mm] x,y gilt wenn x [mm]\not=y[/mm] -> f(x) [mm]\not=[/mm] f(y)
>
> [mm]\neg \exists x^0 \exists x^1 \neg \neg \wedge \beg[/mm] = [mm]x^0 x^1 \neg \neg[/mm]
> = [mm]fx^0 fx^1[/mm]
Diese Formel [mm] $\phi$ [/mm] erfüllt für jede [mm] $\sigma$-Struktur $\underline{M}$ [/mm] genau dann [mm] $\underline{M}\models\phi$, [/mm] wenn kein [mm] $a_0\in [/mm] M$ existiert, für das ein [mm] $a_1\in [/mm] M$ existiert mit [mm] $a_0=a_1$ [/mm] und [mm] $f^{\underline{M}}(a_0)=f^{\underline{M}}(a_1)$.
[/mm]
Aber für jede Struktur [mm] $\underline{M}$ [/mm] gilt: Für JEDES [mm] $a_0\in [/mm] M$ gibt es ein [mm] $a_1\in [/mm] M$ (nämlich [mm] $a_1:=a_0$) [/mm] mit [mm] $a_0=a_1$ [/mm] und [mm] $f^{\underline{M}}(a_0)=f^{\underline{M}}(a_1)$.
[/mm]
Somit gilt [mm] $\underline{M}\models\phi$ [/mm] genau dann, wenn überhaupt kein [mm] $a_0\in [/mm] M$ existiert, also genau dann wenn [mm] $M=\emptyset$.
[/mm]
Mit Injektivität von [mm] $f^\underline{M}$ [/mm] hat das nichts zu tun.
> da
> [mm]\neg \exists x^0 \exists x^1 \neg.. \forall x^0 \forall x^1[/mm]
>
> -> [mm]\psi \phi[/mm] ... [mm]\neg \wedge \phi \neg \psi[/mm]
Sorry, das verstehe ich nicht.
> MusterLösung:
> [mm]\neg \exists x^0 \exists x^1\wedge \beg[/mm] = [mm]x^0 x^1 \wedge[/mm] =
> f [mm]x^0 fx^1[/mm]
> Es ist mit klar, dass man meine beiden
> Negationszeichen jeweils kürzen kann, aber da steht ein
> zweites [mm]\wedge..[/mm]
Und wegen dieses zweiten [mm] $\wedge$, [/mm] das nicht von zwei Formeln gefolgt wird, ist dieser Ausdruck gar keine Formel!
Lässt man das zweite [mm] $\wedge$ [/mm] weg, so erhält man wieder die Aussage, dass [mm] $M=\emptyset$.
[/mm]
Ersetzt man das zweite [mm] $\wedge$ [/mm] hingegen durch ein [mm] $\neg$, [/mm] so erhält man eine stets wahre Aussage.
Die Injektivität von [mm] $f^\underline{M}$ [/mm] wird korrekt durch
[mm] $\neg\exists x^0\exists x^1 \wedge\neg =x^0x^1=fx^0x^1$
[/mm]
wiedergegeben.
> kann man auch so eine Frage stellen mit der Surjektivität?
> Meine Lösung wäre dann: [mm]\neg \exists x^0 \neg \exists x^1[/mm]
> = [mm]x^0 fx^1[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
Viele Grüße
Tobias
|
|
|
|
