Elementare Definierbarkeit < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:06 Do 24.04.2014 | | Autor: | ac1989 |
| Aufgabe | Sei [mm] \mathcal{A} [/mm] eine Struktur mit [mm] \mathcal{A} [/mm] = [mm] (\{0,1\}^{*}, [/mm] <, E, P ).
wobei < sei die Präfix-Relation: v < w gdw. w = vz für ein z [mm] \in \{0,1\}^{*}
[/mm]
und E die Relation: (v,w) [mm] \in [/mm] E gdw. |v| = |w|.
Nun ist folgende Relation gegeben:
[mm] R=\{w \in \{0,1\}^{*} : |w| \ge 3\}
[/mm]
Frage: Ist R nun elementar definierbar in der Struktur [mm] \mathcal{A}? [/mm] |
Nun, dazu habe ich folgende Lösung gesehen:
[mm] \phi [/mm] (x) = [mm] \exists x_{1} \exists x_{2} \exists x_{3} \exists x_{4} \bigwedge_{i \not= j} \exists x_{i} \not=j \exists x_{j} \wedge \bigwedge_{i} \exists x_{i} [/mm] < x
meine Lösung war allerdings fast dasselbe:
[mm] \phi [/mm] (x) = [mm] \exists x_{1} \exists x_{2} \exists x_{3} \bigwedge_{i \not= j} \exists x_{i} \not=j \exists x_{j} \wedge \bigwedge_{i} \exists x_{i} [/mm] < x
Idee war halt: Ich nehme 3 Elemente, die alle unterschiedlich sind und alle
alle 3 sind Präfixe von x. Um das Präfix auszudrücken habe ich das < aus der Struktur genommen.
Aber:
wie Ihr sehen könnt hab ich ein Element weniger. Meine Frage lautet:
Wieso wurde in deren Lösung 4 Elemente genommen. Hat das irgendeine Bedeutung in der Prädikatenlogik ? Eigtl. müssten es doch 3 Elemente sein, da in der vorgegebenen Relation von mindestens 3 die Rede ist.
Ich hoffe jmd. kann mir da weiterhelfen....xD
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:42 Do 24.04.2014 | | Autor: | tobit09 |
Hallo ac1989!
> Sei [mm]\mathcal{A}[/mm] eine Struktur mit [mm]\mathcal{A}[/mm] =
> [mm](\{0,1\}^{*},[/mm] <, E, P ).
> wobei < sei die Präfix-Relation: v < w gdw. w = vz für
> ein z [mm]\in \{0,1\}^{*}[/mm]
> und E die Relation: (v,w) [mm]\in[/mm] E gdw.
> |v| = |w|.
>
> Nun ist folgende Relation gegeben:
> [mm]R=\{w \in \{0,1\}^{*} : |w| \ge 3\}[/mm]
>
> Frage: Ist R nun elementar definierbar in der Struktur
> [mm]\mathcal{A}?[/mm]
> Nun, dazu habe ich folgende Lösung gesehen:
>
> [mm]\phi[/mm] (x) = [mm]\exists x_{1} \exists x_{2} \exists x_{3} \exists x_{4} \bigwedge_{i \not= j} \exists x_{i} \not=j \exists x_{j} \wedge \bigwedge_{i} \exists x_{i}[/mm]
> < x
>
> meine Lösung war allerdings fast dasselbe:
>
> [mm]\phi[/mm] (x) = [mm]\exists x_{1} \exists x_{2} \exists x_{3} \bigwedge_{i \not= j} \exists x_{i} \not=j \exists x_{j} \wedge \bigwedge_{i} \exists x_{i}[/mm]
> < x
>
> Idee war halt: Ich nehme 3 Elemente, die alle
> unterschiedlich sind und alle
> alle 3 sind Präfixe von x. Um das Präfix auszudrücken
> habe ich das < aus der Struktur genommen.
>
> Aber:
> wie Ihr sehen könnt hab ich ein Element weniger. Meine
> Frage lautet:
> Wieso wurde in deren Lösung 4 Elemente genommen. Hat das
> irgendeine Bedeutung in der Prädikatenlogik ? Eigtl.
> müssten es doch 3 Elemente sein, da in der vorgegebenen
> Relation von mindestens 3 die Rede ist.
Anscheinend übersiehst du ein Wort als mögliches Präfix.
Etwa das Wort $w:=00$ gehört nicht zu $R$, aber es hat drei verschiedene Präfixe: Das leere Wort, das Wort $0$ und $w$ selbst.
Also gilt für dein [mm] $\phi$
[/mm]
[mm] $\mathcal{A}\models\phi[w]$
[/mm]
obwohl [mm] $w\notin [/mm] R$.
Viele Grüße
Tobias
|
|
|
|
