Tautologie beweisen < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:47 So 23.02.2014 | | Autor: | ne1 |
| Aufgabe | | Beweise [mm] $\neg (\forall [/mm] x) [mm] \varphi(x) \Leftrightarrow (\exists [/mm] x) [mm] \neg \varphi(x)$. [/mm] |
Hallo,
den Beweis dieser Aufgabe habe ich im Buch, leider verstehe ich ihn nicht.
Sei $X$ eine nicht leere Menge.
Ich habe folgende Definitionen
[mm] $(\forall [/mm] x [mm] \in [/mm] X) [mm] \varphi(x) [/mm] wahr [mm] \Leftrightarrow \{x \in X: \varphi(x)\} [/mm] = X$
[mm] $(\exists [/mm] x [mm] \in [/mm] X) [mm] \varphi(x) [/mm] wahr [mm] \Leftrightarrow \{x \in X: \varphi(x)\} \not [/mm] = [mm] \emptyset$
[/mm]
und sei [mm] D_{\varphi} [/mm] = [mm] \{x \in X : \varphi(x)\}.
[/mm]
Außerdem habe ich folgendes Lemma, das ich bereits bewiesen habe:
[mm] $D_{\varphi \vee \psi} [/mm] = [mm] D_{\varphi} \cup D_{\psi}$
[/mm]
[mm] $D_{\varphi \wedge \psi} [/mm] = [mm] D_{\varphi} \cap D_{\psi}$
[/mm]
[mm] $D_{\neg \varphi} [/mm] = [mm] D^c_{\varphi}$.
[/mm]
Der Beweis in meinem Buch lautet:
[mm] $\neg (\forall [/mm] x) [mm] \varphi(x) \Leftrightarrow \neg (D_{\varphi} [/mm] = X) [mm] \Leftrightarrow D_{\varphi} \not [/mm] = X [mm] \Leftrightarrow D_{\varphi}^C \not [/mm] = [mm] \emptyset \Leftrightarrow D_{\neg \varphi} \not [/mm] = [mm] \emptyset \Leftrightarrow (\exists [/mm] x) [mm] \neg \varphi(x)$.
[/mm]
Ich verstehe alles bis auf diese Umformung: [mm] $D_{\varphi} \not [/mm] = X [mm] \Leftrightarrow D_{\varphi}^C \not [/mm] = [mm] \emptyset$. [/mm] Anschaulich ist diese Umformung für mich selbstverständlich, aber diese Anschaulichkeit kommt, meiner Meinung nach, aus den Tautologien die ich gerade beweisen will und das macht keinen Sinn. Ich beweise etwas und nutze dabei, das was ich gerade beweisen will.
Anders gesprochen, ich versuche zu beweisen, dass diese Äquivalenz tatsächlich stimmt [mm] $D_{\varphi} \not [/mm] = X [mm] \Leftrightarrow D_{\varphi}^C \not [/mm] = [mm] \emptyset$. [/mm] Ich weiss, dass [mm] $D_{\varphi}$ [/mm] aus Elementen von $X$ besteht also [mm] $D_{\varphi} \subseteq [/mm] X$ und ich schreibe für [mm] $D_{\varphi}$, [/mm] $A$. Ich muss also beweisen $A [mm] \subseteq [/mm] X [mm] \wedge [/mm] A [mm] \not [/mm] = X [mm] \Leftrightarrow X\setminus [/mm] A [mm] \not [/mm] = [mm] \emptyset$. [/mm] $X [mm] \setminus [/mm] A [mm] \not [/mm] = [mm] \emptyset$ [/mm] bedeutet laut meiner obigen Definitiono [mm] $(\exists [/mm] x [mm] \in [/mm] X) (x [mm] \in [/mm] X [mm] \wedge [/mm] x [mm] \not \in [/mm] A)$.
Beweis:
$A [mm] \subseteq [/mm] X [mm] \wedge [/mm] A [mm] \not [/mm] = X [mm] \Leftrightarrow$ [/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge \neg [/mm] (A [mm] \subseteq [/mm] X [mm] \wedge [/mm] X [mm] \subseteq [/mm] A) [mm] \Leftrightarrow$ [/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge [/mm] (A [mm] \not \subseteq [/mm] X [mm] \vee [/mm] X [mm] \not \subseteq [/mm] A) [mm] \Leftrightarrow$ [/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge [/mm] X [mm] \not \subseteq [/mm] A [mm] \Leftrightarrow$ [/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge \neg [/mm] (X [mm] \subseteq [/mm] A) [mm] \Leftrightarrow$
[/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge \neg \forall [/mm] x (x [mm] \in [/mm] X [mm] \Rightarrow [/mm] x [mm] \in [/mm] A) [mm] \Leftrightarrow$ [/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge \neg \forall [/mm] x (x [mm] \not \in [/mm] X [mm] \vee [/mm] x [mm] \in [/mm] A) [mm] \Leftrightarrow$ [/mm]
$A [mm] \subseteq [/mm] X [mm] \wedge (\exists [/mm] x [mm] \in [/mm] X)(x [mm] \in [/mm] X [mm] \wedge [/mm] x [mm] \not \in [/mm] A) [mm] \Leftrightarrow$
[/mm]
[mm] $(\exists [/mm] x [mm] \in [/mm] X)(x [mm] \in [/mm] X [mm] \wedge [/mm] x [mm] \not \in [/mm] A)$.
Ich habe es bewiesen, aber dabei nutze ich eine Tautologie der Prädikatenlogik, die ich gerade beweise. Welchen Sinn hat das bzw. was muss man bei dem Beweis tun oder wo ist mein Denkfehler?
Danke im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:07 Mo 24.02.2014 | | Autor: | tobit09 |
Hallo ne1!
Freut mich, dass du nicht kritiklos alles akzeptiert! 
> Beweise [mm]\neg (\forall x) \varphi(x) \Leftrightarrow (\exists x) \neg \varphi(x)[/mm].
> Der Beweis in meinem Buch lautet:
> [mm]\neg (\forall x) \varphi(x) \Leftrightarrow \neg (D_{\varphi} = X) \Leftrightarrow D_{\varphi} \not = X \Leftrightarrow D_{\varphi}^C \not = \emptyset \Leftrightarrow D_{\neg \varphi} \not = \emptyset \Leftrightarrow (\exists x) \neg \varphi(x)[/mm].
>
> Ich verstehe alles bis auf diese Umformung: [mm]D_{\varphi} \not = X \Leftrightarrow D_{\varphi}^C \not = \emptyset[/mm].
> Anschaulich ist diese Umformung für mich
> selbstverständlich, aber diese Anschaulichkeit kommt,
> meiner Meinung nach, aus den Tautologien die ich gerade
> beweisen will und das macht keinen Sinn. Ich beweise etwas
> und nutze dabei, das was ich gerade beweisen will.
>
> Anders gesprochen, ich versuche zu beweisen, dass diese
> Äquivalenz tatsächlich stimmt [mm]D_{\varphi} \not = X \Leftrightarrow D_{\varphi}^C \not = \emptyset[/mm].
> Ich weiss, dass [mm]D_{\varphi}[/mm] aus Elementen von [mm]X[/mm] besteht
> also [mm]D_{\varphi} \subseteq X[/mm] und ich schreibe für
> [mm]D_{\varphi}[/mm], [mm]A[/mm]. Ich muss also beweisen [mm]A \subseteq X \wedge A \not = X \Leftrightarrow X\setminus A \not = \emptyset[/mm].
Nein, das stimmt auch im Allgemeinen nicht.
Zu zeigen ist für eine beliebige Teilmenge [mm] $A\subseteq [/mm] X$ die Äquivalenz
[mm] $A\not=X\iff X\setminus A\not=\emptyset$.
[/mm]
> Beweis:
> [mm]A \subseteq X \wedge A \not = X \Leftrightarrow[/mm]
> [mm]A \subseteq X \wedge \neg (A \subseteq X \wedge X \subseteq A) \Leftrightarrow[/mm]
> [mm]A \subseteq X \wedge (A \not \subseteq X \vee X \not \subseteq A) \Leftrightarrow[/mm]
> [mm]A \subseteq X \wedge X \not \subseteq A \Leftrightarrow[/mm]
> [mm]A \subseteq X \wedge \neg (X \subseteq A) \Leftrightarrow[/mm]
>
> [mm]A \subseteq X \wedge \neg \forall x (x \in X \Rightarrow x \in A) \Leftrightarrow[/mm]
> [mm]A \subseteq X \wedge \neg \forall x (x \not \in X \vee x \in A) \Leftrightarrow[/mm]
> [mm]A \subseteq X \wedge (\exists x \in X)(x \in X \wedge x \not \in A) \Leftrightarrow[/mm]
>
> [mm](\exists x \in X)(x \in X \wedge x \not \in A)[/mm].
(Die Rückrichtung der letzten Äquivalenz stimmt nicht.)
> Ich habe es bewiesen, aber dabei nutze ich eine Tautologie
> der Prädikatenlogik, die ich gerade beweise. Welchen Sinn
> hat das
Möglicherweise versucht das Buch gar keinen lückenlosen Aufbau der gesamten Mathematik. Möglicherweise wird zwischen den "umgangssprachlichen" und den formal definierten Quantoren unterschieden. Häufig werden in der mathematischen Logik die formal definierten Quantoren mithilfe der "umgangssprachlichen" definiert. Es kann durchaus sein, dass die "umgangssprachliche" Äquivalenz
"$E(x)$ gilt nicht für alle x genau dann wenn $E(x)$ gilt für ein $x$ nicht"
bereits vorausgesetzt wird und nun lediglich in die formal definierte Äquivalenz
"[mm]\neg (\forall x) \varphi(x) \Leftrightarrow (\exists x) \neg \varphi(x)[/mm]"
"übersetzt" werden soll. Aber da ich das Buch nicht kenne, ist das Spekulation.
Auf alle Fälle scheint das Buch ja irgendeine (naive?) Mengenlehre zugrunde zu legen, in der
[mm] $A=X\iff A\subseteq X\wedge X\subseteq [/mm] A$
und
[mm] $A\subseteq X\iff$ [/mm] für alle [mm] $x\in [/mm] A$ gilt [mm] $x\in [/mm] X$
gilt. Es wird also auf der Ebene der Mengenlehre bereits der (umgangssprachliche) "für alle"-Quantor benutzt. Dies erscheint mir nur sinnvoll, wenn man auch damit in irgendeiner "gewöhnlichen" Weise umgehen darf, wie ich es im Folgenden tun werde.
> bzw. was muss man bei dem Beweis tun
Es ist deutlich einfacher statt
[mm] $A\not=X\iff X\setminus A\not=\emptyset$
[/mm]
die äquivalente Aussage
[mm] $A=X\iff X\setminus A=\emptyset$
[/mm]
zu zeigen.
Wenn $A=X$ gilt, folgt wie gewünscht
[mm] $X\setminus A=X\setminus X=\emptyset$.
[/mm]
Gelte nun umgekehrt [mm] $X\setminus A=\emptyset$. [/mm] Wir zeigen [mm] $X\subseteq [/mm] A$. Dann folgt zusammen mit [mm] $A\subseteq [/mm] X$ wie gewünscht $A=X$.
Sei also [mm] $x\in [/mm] X$. Zu zeigen ist [mm] $x\in [/mm] A$.
Angenommen [mm] $x\notin [/mm] A$. Dann folgt
[mm] $x\in X\setminus A=\emptyset$, [/mm] Widerspruch.
Wenn du möchtest, kann ich zusätzlich noch angeben, wie man
[mm]\neg (\forall x\in X) \varphi(x) \Leftrightarrow (\exists x\in X) \neg \varphi(x)[/mm]
beweisen kann, wenn die Quantoren nicht wie im Buch formal definiert sind, sondern man "gewöhnlich" mit ihnen umgeht.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:12 Do 27.02.2014 | | Autor: | ne1 |
Vielen Dank für Deine Antwort.
> Hallo ne1!
>
>
> Freut mich, dass du nicht kritiklos alles akzeptiert!
>
>
> > Beweise [mm]\neg (\forall x) \varphi(x) \Leftrightarrow (\exists x) \neg \varphi(x)[/mm].
>
>
> > Der Beweis in meinem Buch lautet:
> > [mm]\neg (\forall x) \varphi(x) \Leftrightarrow \neg (D_{\varphi} = X) \Leftrightarrow D_{\varphi} \not = X \Leftrightarrow D_{\varphi}^C \not = \emptyset \Leftrightarrow D_{\neg \varphi} \not = \emptyset \Leftrightarrow (\exists x) \neg \varphi(x)[/mm].
>
> >
> > Ich verstehe alles bis auf diese Umformung: [mm]D_{\varphi} \not = X \Leftrightarrow D_{\varphi}^C \not = \emptyset[/mm].
> > Anschaulich ist diese Umformung für mich
> > selbstverständlich, aber diese Anschaulichkeit kommt,
> > meiner Meinung nach, aus den Tautologien die ich gerade
> > beweisen will und das macht keinen Sinn. Ich beweise etwas
> > und nutze dabei, das was ich gerade beweisen will.
> >
> > Anders gesprochen, ich versuche zu beweisen, dass diese
> > Äquivalenz tatsächlich stimmt [mm]D_{\varphi} \not = X \Leftrightarrow D_{\varphi}^C \not = \emptyset[/mm].
> > Ich weiss, dass [mm]D_{\varphi}[/mm] aus Elementen von [mm]X[/mm] besteht
> > also [mm]D_{\varphi} \subseteq X[/mm] und ich schreibe für
> > [mm]D_{\varphi}[/mm], [mm]A[/mm]. Ich muss also beweisen [mm]A \subseteq X \wedge A \not = X \Leftrightarrow X\setminus A \not = \emptyset[/mm].
>
> Nein, das stimmt auch im Allgemeinen nicht.
>
> Zu zeigen ist für eine beliebige Teilmenge [mm]A\subseteq X[/mm]
> die Äquivalenz
>
> [mm]A\not=X\iff X\setminus A\not=\emptyset[/mm].
>
Ja, das ist mir jetzt schon klar :).
>
> Auf alle Fälle scheint das Buch ja irgendeine (naive?)
> Mengenlehre zugrunde zu legen, in der
>
> [mm]A=X\iff A\subseteq X\wedge X\subseteq A[/mm]
>
> und
>
> [mm]A\subseteq X\iff[/mm] für alle [mm]x\in A[/mm] gilt [mm]x\in X[/mm]
>
> gilt. Es wird also auf der Ebene der Mengenlehre bereits
> der (umgangssprachliche) "für alle"-Quantor benutzt. Dies
> erscheint mir nur sinnvoll, wenn man auch damit in
> irgendeiner "gewöhnlichen" Weise umgehen darf, wie ich es
> im Folgenden tun werde.
>
Ja, naive Lehre wurde vor der Prädikatenlogik behandelt, da wurde "für alle" als etwas selbstverständliches behandelt bzw. die Beweise würde so durchgeführt wie Du unten es gemacht hast, d.h. ohne irgendwelche Quantoren anzuwenden.
> > bzw. was muss man bei dem Beweis tun
> Es ist deutlich einfacher statt
>
> [mm]A\not=X\iff X\setminus A\not=\emptyset[/mm]
>
> die äquivalente Aussage
>
> [mm]A=X\iff X\setminus A=\emptyset[/mm]
>
> zu zeigen.
>
> Wenn [mm]A=X[/mm] gilt, folgt wie gewünscht
>
> [mm]X\setminus A=X\setminus X=\emptyset[/mm].
>
> Gelte nun umgekehrt [mm]X\setminus A=\emptyset[/mm]. Wir zeigen
> [mm]X\subseteq A[/mm]. Dann folgt zusammen mit [mm]A\subseteq X[/mm] wie
> gewünscht [mm]A=X[/mm].
>
> Sei also [mm]x\in X[/mm]. Zu zeigen ist [mm]x\in A[/mm].
>
> Angenommen [mm]x\notin A[/mm]. Dann folgt
>
> [mm]x\in X\setminus A=\emptyset[/mm], Widerspruch.
>
Mit dieser Lösung bin ich jetzt sehr zufrieden, da sie das erwünschte Ergebnis auf Basis der naiven Mengenlehre liefert.
>
> Wenn du möchtest, kann ich zusätzlich noch angeben, wie
> man
>
> [mm]\neg (\forall x\in X) \varphi(x) \Leftrightarrow (\exists x\in X) \neg \varphi(x)[/mm]
>
> beweisen kann, wenn die Quantoren nicht wie im Buch formal
> definiert sind, sondern man "gewöhnlich" mit ihnen
> umgeht.
>
Ja, bitte.
> Viele Grüße
> Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 04:45 Do 27.02.2014 | | Autor: | tobit09 |
> > Wenn du möchtest, kann ich zusätzlich noch angeben, wie
> > man
> >
> > [mm]\neg (\forall x\in X) \varphi(x) \Leftrightarrow (\exists x\in X) \neg \varphi(x)[/mm]
>
> >
> > beweisen kann, wenn die Quantoren nicht wie im Buch formal
> > definiert sind, sondern man "gewöhnlich" mit ihnen
> > umgeht.
> >
> Ja, bitte.
Fangen wir mit der leichteren Rück-Richtung an:
Es existiere also ein [mm] $x_0\in [/mm] X$ mit [mm] $\neg\varphi(x_0)$.
[/mm]
Zu zeigen ist [mm] $\neg \forall x\in [/mm] X [mm] \varphi(x)$.
[/mm]
Angenommen [mm] $\forall x\in X\varphi(x)$.
[/mm]
Dann gilt insbesondere [mm] $\varphi(x_0)$.
[/mm]
Dies widerspricht jedoch [mm] $\neg\varphi(x_0)$.
[/mm]
Zur Hin-Richtung:
Gelte [mm] $\neg \forall x\in [/mm] X [mm] \varphi(x)$.
[/mm]
Zu zeigen ist [mm] $\exists x\in [/mm] X [mm] \neg \varphi(x)$.
[/mm]
Angenommen [mm] $\neg\exists x\in [/mm] X [mm] \neg \varphi(x)$.
[/mm]
Wir werden [mm] $\forall x\in [/mm] X [mm] \varphi(x)$ [/mm] zeigen.
Das liefert dann den gewünschten Widerspruch zu [mm] $\neg \forall x\in [/mm] X [mm] \varphi(x)$.
[/mm]
Um [mm] $\forall x\in [/mm] X [mm] \varphi(x)$ [/mm] zu zeigen sei [mm] $x_0\in [/mm] X$.
Zu zeigen ist [mm] $\varphi(x_0)$.
[/mm]
Angenommen [mm] $\neg\varphi(x_0)$.
[/mm]
Dann gilt [mm] $\exists x\in X\neg\varphi(x)$.
[/mm]
Dies widerspricht unserer Annahme [mm] $\neg\exists x\in [/mm] X [mm] \neg \varphi(x)$.
[/mm]
|
|
|
|
