Äquivalenz zweier Formeln < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
[mm] \forall [/mm] x [mm] \exists [/mm] y (P(Y) [mm] \to [/mm] Q(x)) [mm] \equiv \exists [/mm] y [mm] \forall [/mm] x (P(Y) [mm] \to [/mm] Q(x))
Ich verstehe nicht ganz wie ich die obrige gleichung umformen muss um auf das ergebnis zu kommen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hiho,
> [mm]\forall[/mm] x [mm]\exists[/mm] y (P(Y) [mm]\to[/mm] Q(x)) [mm]\equiv \exists[/mm] y
> [mm]\forall[/mm] x (P(Y) [mm]\to[/mm] Q(x))
>
> Ich verstehe nicht ganz wie ich die obrige gleichung umformen muss um auf das ergebnis zu kommen.
Auf welches Ergebnis?
Wenn du wissen willst, ob [mm]\forall\,x \;\exists\, y\; (P(Y)\to Q(x))[/mm] äquivalent ist zu [mm]\exists\, y\;\forall\,x\; (P(Y)\to Q(x))[/mm], dann lautet die Antwort im Allgemeinen "Nein."
Gruß,
Gono.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:10 Mo 16.12.2013 | | Autor: | tobit09 |
Hallo zusammen,
> Wenn du wissen willst, ob [mm]\forall\,x \;\exists\, y\; (P(Y)\to Q(x))[/mm]
> äquivalent ist zu [mm]\exists\, y\;\forall\,x\; (P(Y)\to Q(x))[/mm],
> dann lautet die Antwort im Allgemeinen "Nein."
Doch, diese beiden Sätze sind elementar äquivalent.
Korrekt ist, dass Sätze der Form
[mm] $\forall x\exists [/mm] y F(x,y)$
und
[mm] $\exists [/mm] y [mm] \forall [/mm] x F(x,y)$
im Allgemeinen nicht elementar äquivalent sind.
Genauer gesagt impliziert der zweite Satz den ersten, jedoch im Allgemeinen nicht umgekehrt.
Im gegebenen Spezialfall
[mm] $F(x,y)=(P(y)\to [/mm] Q(x))$
gilt jedoch unter Beachtung der Konvention, dass Träger von Strukturen der Prädikatenlogik nicht leer sind, sehr wohl auch die zweite Implikation.
Sei also [mm] $\mathfrak{A}$ [/mm] eine Struktur der vorliegenden Sprache mit
(*) [mm] $\mathfrak{A}\models \forall x\exists [/mm] y [mm] (P(y)\to [/mm] Q(x))$.
Zu zeigen ist
(**) [mm] $\mathfrak{A}\models \exists y\forall [/mm] x [mm] (P(y)\to [/mm] Q(x))$.
Falls (1. Fall)
[mm] $\mathfrak{A}\models\forall [/mm] x Q(x)$,
gilt für jedes beliebige [mm] $b\in [/mm] A$
[mm] $\mathfrak{A}\models \forall [/mm] x [mm] (P(b)\to [/mm] Q(x))$.
Da ein [mm] $b\in [/mm] A$ nach oben genannter Konvention existiert, bezeugt dieses $b$ wie gewünscht (**).
Falls (2. Fall)
[mm] $\mathfrak{A}\not\models \forall [/mm] x Q(x)$,
gibt es ein [mm] $a\in [/mm] A$ mit
(***) [mm] $\mathfrak{A}\models \neg [/mm] Q(a)$.
Nach (*) existiert dazu ein [mm] $b\in [/mm] A$ mit
[mm] $\mathfrak{A}\models (P(b)\to [/mm] Q(a))$.
Nach (***) folgt
[mm] $\mathfrak{A}\models \neg [/mm] P(b)$
und damit
[mm] $\mathfrak{A}\models P(b)\to [/mm] P(c)$
für alle [mm] $c\in [/mm] A$.
Somit bezeugt $b$ wie gewünscht (**).
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:55 Mo 16.12.2013 | | Autor: | Gonozal_IX |
Hallo tobi,
danke für die Korrektur (kannst du nächste Mal auch deutlicher machen).
Die Sache funktioniert hier aber nur, weil P und Q unabhängig voneinander sind, d.h. Q selbst nicht mehr von x abhängt (oder umgekehrt).
Da war ich etwas vorschnell.
Gruß,
Gono.
|
|
|
|
