Axiomenäquivalenz beweisen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:53 Do 31.10.2013 | | Autor: | Catman |
| Aufgabe | | Beweisen Sie: Aus (P1) - (P3) folgt (S2). |
Schönen guten Abend,
Sitze an meinem Matheblatt und komme einfach nicht auf eine Idee wie das zu lösen ist.
Also hier mal die Axiome:
P1: [mm] \forall a\in \IN [/mm] N(a) [mm] \not= [/mm] 0
p2: [mm] \forall a,b\in\IN [/mm] N(a)=N(b) -> a=b
P3: [mm] \forall M\subseteq\IN [/mm] 0 [mm] \in [/mm] M [mm] \wedge \forall [/mm] a [mm] \in [/mm] M [mm] (a\in M->N(a)\in [/mm] M) -> [mm] M=\IN
[/mm]
s(2): [mm] \forall M\subseteq \IN M\not= \emptyset [/mm] -> [mm] \exists a\in [/mm] M [mm] \forall b\in [/mm] M N(b) [mm] \not= [/mm] a
Also zu zeigen ist also, dass aus den 3 Peano Axiomen folgt, dass jede Teilmenge von [mm] \IN [/mm] ein Element hat, dass keinen Vorgänger hat. Nur wie? Wäre sehr nett wenn mir jemand weiterhelfen würde, und vielen Dank schonmal.
Gruß
Anni
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:13 Fr 01.11.2013 | | Autor: | tobit09 |
Hallo Catman!
> Beweisen Sie: Aus (P1) - (P3) folgt (S2).
> P1: [mm]\forall a\in \IN[/mm] N(a) [mm]\not=[/mm] 0
> p2: [mm]\forall a,b\in\IN[/mm] N(a)=N(b) -> a=b
> P3: [mm]\forall M\subseteq\IN[/mm] 0 [mm]\in[/mm] M [mm]\wedge \forall[/mm] a
> [mm]\in[/mm] M [mm](a\in M->N(a)\in[/mm] M) -> [mm]M=\IN[/mm]
> s(2): [mm]\forall M\subseteq \IN M\not= \emptyset[/mm] ->
> [mm]\exists a\in[/mm] M [mm]\forall b\in[/mm] M N(b) [mm]\not=[/mm] a
> Also zu zeigen ist also, dass aus den 3 Peano Axiomen
> folgt, dass jede
nichtleere
> Teilmenge
M
> von [mm]\IN[/mm] ein Element hat, dass
> keinen Vorgänger
in M
> hat. Nur wie?
Sei [mm] $M\subseteq\IN$.
[/mm]
Um
[mm] $M\not= \emptyset\; ->\; \exists a\in [/mm] M [mm] \;\forall b\in M\; [/mm] N(b) [mm] \not= [/mm] a$
zu zeigen, zeige die Kontraposition
[mm] $\neg\exists a\in M\;\forall b\in M\; N(b)\not=a\;\rightarrow\;M=\emptyset$.
[/mm]
Gelte also
[mm] $\neg\exists a\in M\;\forall b\in M\;N(b)\not=a$,
[/mm]
d.h.
(*) [mm] $\forall a\in M\;\exists b\in M\;N(b)=a$.
[/mm]
Zu zeigen ist
[mm] $M=\emptyset$.
[/mm]
Äquivalent dazu ist
[mm] $M^c:=\IN\setminus M=\IN$.
[/mm]
Zeige nun unter Verwendung von (*), P1 und P2:
1. [mm] $0\in M^c$
[/mm]
2. [mm] $\forall a\in M^c\;N(a)\in M^c$
[/mm]
Gemäß P3 folgt dann wie gewünscht [mm] $M^c=\IN$.
[/mm]
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:30 Fr 01.11.2013 | | Autor: | Catman |
Vielen Dank für deine Hilfe.
Gruß
Anni
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:13 Fr 01.11.2013 | | Autor: | Catman |
> d.h.
>
> (*) [mm]\forall a\in M\;\exists b\in M\;N(b)=a[/mm].
>
> Zu zeigen ist
>
> [mm]M=\emptyset[/mm].
>
> Äquivalent dazu ist
>
> [mm]M^c:=\IN\setminus M=\IN[/mm].
>
> Zeige nun unter Verwendung von (*), P1 und P2:
>
> 1. [mm]0\in M^c[/mm]
> 2. [mm]\forall a\in M^c\;N(a)\in M^c[/mm]
>
> Gemäß P3 folgt dann wie gewünscht [mm]M^c=\IN[/mm].
>
>
> Viele Grüße
> Tobias
Nochmal vielen Dank für den Lösungsansatz. Also um jetzt zu zeigen, dass 0 [mm] \in M^c [/mm] ist, kann man da annehmen, dass 0 [mm] \in [/mm] M sei und das dann irgendwie mit den Axiomen zu einem Widerspruch führen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:15 Fr 01.11.2013 | | Autor: | tobit09 |
> > (*) [mm]\forall a\in M\;\exists b\in M\;N(b)=a[/mm].
> >
> > Zu zeigen ist
> >
> > [mm]M=\emptyset[/mm].
> >
> > Äquivalent dazu ist
> >
> > [mm]M^c:=\IN\setminus M=\IN[/mm].
> >
> > Zeige nun unter Verwendung von (*), P1 und P2:
> >
> > 1. [mm]0\in M^c[/mm]
> > 2. [mm]\forall a\in M^c\;N(a)\in M^c[/mm]
> >
> > Gemäß P3 folgt dann wie gewünscht [mm]M^c=\IN[/mm].
> Nochmal vielen Dank für den Lösungsansatz. Also um jetzt
> zu zeigen, dass 0 [mm]\in M^c[/mm] ist, kann man da annehmen, dass 0
> [mm]\in[/mm] M sei und das dann irgendwie mit den Axiomen zu einem
> Widerspruch führen?
![[ok]](/images/smileys/ok.gif "[ok]") Genau so würde ich das machen!
Was folgt aus [mm] $0\in [/mm] M$ gemäß (*)?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:25 Fr 01.11.2013 | | Autor: | Catman |
> > > (*) [mm]\forall a\in M\;\exists b\in M\;N(b)=a[/mm].
> > >
> > > Zu zeigen ist
> > >
> > > [mm]M=\emptyset[/mm].
> > >
> > > Äquivalent dazu ist
> > >
> > > [mm]M^c:=\IN\setminus M=\IN[/mm].
> > >
> > > Zeige nun unter Verwendung von (*), P1 und P2:
> > >
> > > 1. [mm]0\in M^c[/mm]
> > > 2. [mm]\forall a\in M^c\;N(a)\in M^c[/mm]
> >
> >
> > > Gemäß P3 folgt dann wie gewünscht [mm]M^c=\IN[/mm].
>
> > Nochmal vielen Dank für den Lösungsansatz. Also um jetzt
> > zu zeigen, dass 0 [mm]\in M^c[/mm] ist, kann man da annehmen, dass 0
> > [mm]\in[/mm] M sei und das dann irgendwie mit den Axiomen zu einem
> > Widerspruch führen?
> Genau so würde ich das machen!
>
> Was folgt aus [mm]0\in M[/mm] gemäß (*)?
Also wenn 0 [mm] \in [/mm] M ist würde folgen, dass a [mm] \not= [/mm] 0 ist, weil a ja der Nachfolger von b ist? Wobei * ja eigentlich keine Aussage darüber trifft, dass 0 nicht Nachfolger sein kann. Das würde dann zusammen mit P(1) folgen. Aber irgendwie bringt mich diese Erkenntnis nicht viel weiter, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:33 Fr 01.11.2013 | | Autor: | tobit09 |
> > > > (*) [mm]\forall a\in M\;\exists b\in M\;N(b)=a[/mm].
> > > Also um jetzt
> > > zu zeigen, dass 0 [mm]\in M^c[/mm] ist, kann man da annehmen, dass 0
> > > [mm]\in[/mm] M sei und das dann irgendwie mit den Axiomen zu einem
> > > Widerspruch führen?
> > Genau so würde ich das machen!
> >
> > Was folgt aus [mm]0\in M[/mm] gemäß (*)?
>
> Also wenn 0 [mm]\in[/mm] M ist würde folgen, dass a [mm]\not=[/mm] 0 ist,
> weil a ja der Nachfolger von b ist?
Was meinst du hier mit $a$?
> Wobei * ja eigentlich
> keine Aussage darüber trifft, dass 0 nicht Nachfolger sein
> kann. Das würde dann zusammen mit P(1) folgen. Aber
> irgendwie bringt mich diese Erkenntnis nicht viel weiter,
> oder?
Wenn [mm] $0\in [/mm] M$ ist, sagt dir (*), dass ein [mm] $b\in [/mm] M$ mit $N(b)=0$ existiert.
Gemäß P1 gilt aber [mm] $N(b)\not=0$.
[/mm]
Also gilt sowohl $N(b)=0$ als auch [mm] $N(b)\not=0$, [/mm] was natürlich einen Widerspruch darstellt.
Also muss unsere Annahme [mm] $0\in [/mm] M$ falsch gewesen sein und somit gilt wie gewünscht [mm] $0\in M^c$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:55 Fr 01.11.2013 | | Autor: | Catman |
> > > > > (*) [mm]\forall a\in M\;\exists b\in M\;N(b)=a[/mm].
>
>
> > > > Also um jetzt
> > > > zu zeigen, dass 0 [mm]\in M^c[/mm] ist, kann man da annehmen, dass 0
> > > > [mm]\in[/mm] M sei und das dann irgendwie mit den Axiomen zu einem
> > > > Widerspruch führen?
> > > Genau so würde ich das machen!
> > >
> > > Was folgt aus [mm]0\in M[/mm] gemäß (*)?
> >
> > Also wenn 0 [mm]\in[/mm] M ist würde folgen, dass a [mm]\not=[/mm] 0 ist,
> > weil a ja der Nachfolger von b ist?
> Was meinst du hier mit [mm]a[/mm]?
>
> > Wobei * ja eigentlich
> > keine Aussage darüber trifft, dass 0 nicht Nachfolger sein
> > kann. Das würde dann zusammen mit P(1) folgen. Aber
> > irgendwie bringt mich diese Erkenntnis nicht viel weiter,
> > oder?
> Wenn [mm]0\in M[/mm] ist, sagt dir (*), dass ein [mm]b\in M[/mm] mit [mm]N(b)=0[/mm]
> existiert.
>
> Gemäß P1 gilt aber [mm]N(b)\not=0[/mm].
>
> Also gilt sowohl [mm]N(b)=0[/mm] als auch [mm]N(b)\not=0[/mm], was natürlich
> einen Widerspruch darstellt.
>
> Also muss unsere Annahme [mm]0\in M[/mm] falsch gewesen sein und
> somit gilt wie gewünscht [mm]0\in M^c[/mm].
Danke. Das ist dann doch einleuchtend. Jetzt ist dementsprechend noch zu zeigen, dass für alle Elemente in [mm] M^c [/mm] auch der Nachfolger in [mm] M^c [/mm] enthalten ist. Kann man da jetzt aus (*) schließen, dass für jedes b ja ein Nachfolger (a) existiert und einfach in diesem Fall M = [mm] M^c [/mm] setzen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:02 Fr 01.11.2013 | | Autor: | tobit09 |
> Jetzt ist
> dementsprechend noch zu zeigen, dass für alle Elemente in
> [mm]M^c[/mm] auch der Nachfolger in [mm]M^c[/mm] enthalten ist.
Genau.
> Kann man da
> jetzt aus (*) schließen, dass für jedes b ja ein
> Nachfolger (a) existiert
Jede natürliche Zahl [mm] $b\in\IN$ [/mm] hat einen Nachfolger, nämlich $N(b)$. Das hat nichts mit (*) zu tun.
> und einfach in diesem Fall M = [mm]M^c[/mm]
> setzen?
Nein. Unsere Menge [mm] $M^c$ [/mm] anstelle von $M$ würde nicht (*) erfüllen.
Sei [mm] $d\in M^c$. [/mm] Zeige [mm] $N(d)\in M^c$ [/mm] per Widerspruchsbeweis mithilfe von (*) und P2.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:14 Fr 01.11.2013 | | Autor: | Catman |
> > Jetzt ist
> > dementsprechend noch zu zeigen, dass für alle Elemente in
> > [mm]M^c[/mm] auch der Nachfolger in [mm]M^c[/mm] enthalten ist.
> Genau.
>
> > Kann man da
> > jetzt aus (*) schließen, dass für jedes b ja ein
> > Nachfolger (a) existiert
> Jede natürliche Zahl [mm]b\in\IN[/mm] hat einen Nachfolger,
> nämlich [mm]N(b)[/mm]. Das hat nichts mit (*) zu tun.
>
> > und einfach in diesem Fall M = [mm]M^c[/mm]
> > setzen?
> Nein. Unsere Menge [mm]M^c[/mm] anstelle von [mm]M[/mm] würde nicht (*)
> erfüllen.
>
>
> Sei [mm]d\in M^c[/mm]. Zeige [mm]N(d)\in M^c[/mm] per Widerspruchsbeweis
> mithilfe von (*) und P2.
Das würde doch heißen, dass man annimmt d sei nicht in [mm] M^c [/mm] <-> d [mm] \in [/mm] M. Das würde mit * bedeuten, dass [mm] \forall [/mm] a [mm] \in [/mm] M [mm] \exists d\in [/mm] M mit N(d) = a. Kann man das dann einfach andersrum auch einsetzen, also [mm] \forall [/mm] d [mm] \in [/mm] M [mm] \exists b\in [/mm] M mit N(b) = d und daraus würde dann mit p(2) folgen, dass b = d ist, was ein Widerspruch wäre zu N(b) = d ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:48 Fr 01.11.2013 | | Autor: | tobit09 |
> > Sei [mm]d\in M^c[/mm]. Zeige [mm]N(d)\in M^c[/mm] per Widerspruchsbeweis
> > mithilfe von (*) und P2.
>
> Das würde doch heißen, dass man annimmt d sei nicht in
> [mm]M^c[/mm] <-> d [mm]\in[/mm] M.
Nein. Bei einem Widerspruchsbeweis nimmt man das Gegenteil der Behauptung an, nicht das Gegenteil einer Voraussetzung.
Die Behauptung ist hier [mm] $N(d)\in M^c$.
[/mm]
Nimm also [mm] $N(d)\notin M^c$ [/mm] an und führe diese Annahme unter Benutzung von [mm] $d\in M^c$ [/mm] zu einem Widerspruch.
> Das würde mit * bedeuten, dass [mm]\forall[/mm] a
> [mm]\in[/mm] M [mm]\exists d\in[/mm] M mit N(d) = a.
$d$ ist bei uns jetzt eine feste natürliche Zahl. Du kannst also im Moment nicht über $d$ quantifizieren.
> Kann man das dann
> einfach andersrum auch einsetzen, also [mm]\forall[/mm] d [mm]\in[/mm] M
> [mm]\exists b\in[/mm] M mit N(b) = d
Der gleiche Fehler (Quantifizierung über $d$).
Aber nach (*) WÜRDE in der Tat im Falle [mm] $d\in [/mm] M$ ein [mm] $b\in [/mm] M$ existieren mit $N(b)=d$.
> und daraus würde dann mit p(2)
> folgen, dass b = d ist,
Wie das?
> was ein Widerspruch wäre zu N(b) =
> d ?
Dass [mm] $N(b)\not=b$ [/mm] gilt, stimmt zwar, müsste aber bewiesen werden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:24 Fr 01.11.2013 | | Autor: | Catman |
> > > Sei [mm]d\in M^c[/mm]. Zeige [mm]N(d)\in M^c[/mm] per Widerspruchsbeweis
> > > mithilfe von (*) und P2.
> >
> > Das würde doch heißen, dass man annimmt d sei nicht in
> > [mm]M^c[/mm] <-> d [mm]\in[/mm] M.
> Nein. Bei einem Widerspruchsbeweis nimmt man das Gegenteil
> der Behauptung an, nicht das Gegenteil einer
> Voraussetzung.
>
> Die Behauptung ist hier [mm]N(d)\in M^c[/mm].
>
> Nimm also [mm]N(d)\notin M^c[/mm] an und führe diese Annahme unter
> Benutzung von [mm]d\in M^c[/mm] zu einem Widerspruch.
>
>
> > Das würde mit * bedeuten, dass [mm]\forall[/mm] a
> > [mm]\in[/mm] M [mm]\exists d\in[/mm] M mit N(d) = a.
> [mm]d[/mm] ist bei uns jetzt eine feste natürliche Zahl. Du kannst
> also im Moment nicht über [mm]d[/mm] quantifizieren.
>
> > Kann man das dann
> > einfach andersrum auch einsetzen, also [mm]\forall[/mm] d [mm]\in[/mm] M
> > [mm]\exists b\in[/mm] M mit N(b) = d
> Der gleiche Fehler (Quantifizierung über [mm]d[/mm]).
>
> Aber nach (*) WÜRDE in der Tat im Falle [mm]d\in M[/mm] ein [mm]b\in M[/mm]
> existieren mit [mm]N(b)=d[/mm].
>
> > und daraus würde dann mit p(2)
> > folgen, dass b = d ist,
> Wie das?
>
> > was ein Widerspruch wäre zu N(b) =
> > d ?
> Dass [mm]N(b)\not=b[/mm] gilt, stimmt zwar, müsste aber bewiesen
> werden.
Also heißt das dann, dass aus N(d) [mm] \not= M^c [/mm] mit d [mm] \in M^c [/mm] und * folgt: [mm] \exists [/mm] b [mm] \in [/mm] M N(b) = d, was ja ein Widerspruch wäre, weil d nicht in [mm] M^c [/mm] und M sein kann ? Hab ichs jetzt korrekt?
d kann nicht quantifiziert werden heißt dann, dass d nicht mehr wie eine allgemeine variable behandelt werden kann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:44 Fr 01.11.2013 | | Autor: | tobit09 |
> > Nimm also [mm]N(d)\notin M^c[/mm] an und führe diese Annahme unter
> > Benutzung von [mm]d\in M^c[/mm] zu einem Widerspruch.
> Also heißt das dann, dass aus N(d) [mm]\not= M^c[/mm]
[mm] $N(d)\notin M^c$ [/mm] meinst du.
> mit d [mm]\in M^c[/mm]
> und * folgt: [mm]\exists[/mm] b [mm]\in[/mm] M N(b) = d,
Nein. Wenn wir [mm] $d\in M^c$ [/mm] haben, sagt (*) nichts über $d$ aus.
Aber wir haben nach Widerspruchsannahme [mm] $N(d)\notin M^c$, [/mm] also [mm] $N(d)\in [/mm] M$.
Nach (*) existiert also ein [mm] $b\in [/mm] M$ mit $N(b)=N(d)$.
Was liefert nun P2?
Leite daraus einen Widerspruch zu [mm] $d\in M^c$ [/mm] ab.
> was ja ein
> Widerspruch wäre, weil d nicht in [mm]M^c[/mm] und M sein kann ?
Warum sollte $d$ in $M$ sein?
> d kann nicht quantifiziert werden heißt dann, dass d nicht
> mehr wie eine allgemeine variable behandelt werden kann?
Solange wir gerade von einer festen natürlichen Zahl $d$ reden, ist es wenig sinnvoll, gleichzeitig eine Aussage über alle natürlichen Zahlen $d$ oder die Existenz einer natürlichen Zahl $d$ zu machen.
Sonst würde man den Buchstaben $d$ zeitgleich in zwei verschiedenen Bedeutungen verwenden, was nur zu Konfusion führt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:46 Sa 02.11.2013 | | Autor: | Catman |
> > > Nimm also [mm]N(d)\notin M^c[/mm] an und führe diese Annahme unter
> > > Benutzung von [mm]d\in M^c[/mm] zu einem Widerspruch.
>
>
> > Also heißt das dann, dass aus N(d) [mm]\not= M^c[/mm]
> [mm]N(d)\notin M^c[/mm]
> meinst du.
> > mit d [mm]\in M^c[/mm]
> > und * folgt: [mm]\exists[/mm] b [mm]\in[/mm] M N(b) = d,
> Nein. Wenn wir [mm]d\in M^c[/mm] haben, sagt (*) nichts über [mm]d[/mm]
> aus.
>
>
> Aber wir haben nach Widerspruchsannahme [mm]N(d)\notin M^c[/mm],
> also [mm]N(d)\in M[/mm].
>
> Nach (*) existiert also ein [mm]b\in M[/mm] mit [mm]N(b)=N(d)[/mm].
>
> Was liefert nun P2?
>
> Leite daraus einen Widerspruch zu [mm]d\in M^c[/mm] ab.
>
> > was ja ein
> > Widerspruch wäre, weil d nicht in [mm]M^c[/mm] und M sein kann ?
> Warum sollte [mm]d[/mm] in [mm]M[/mm] sein?
>
>
> > d kann nicht quantifiziert werden heißt dann, dass d nicht
> > mehr wie eine allgemeine variable behandelt werden kann?
> Solange wir gerade von einer festen natürlichen Zahl [mm]d[/mm]
> reden, ist es wenig sinnvoll, gleichzeitig eine Aussage
> über alle natürlichen Zahlen [mm]d[/mm] oder die Existenz einer
> natürlichen Zahl [mm]d[/mm] zu machen.
> Sonst würde man den Buchstaben [mm]d[/mm] zeitgleich in zwei
> verschiedenen Bedeutungen verwenden, was nur zu Konfusion
> führt.
Okay, nochmal vielen Dank. Aus P2 folgt ja dann, dass b und d gleich sind. * sagt, dass ein b in M existiert, was aber im Widerspruch zu d [mm] \in M^c [/mm] steht, wenn b und d gleich sind, weil dann ja b in [mm] M^c [/mm] sein müsste. Richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:01 So 03.11.2013 | | Autor: | tobit09 |
> > > > Nimm also [mm]N(d)\notin M^c[/mm] an und führe diese Annahme unter
> > > > Benutzung von [mm]d\in M^c[/mm] zu einem Widerspruch.
> >
> >
> > > Also heißt das dann, dass aus N(d) [mm]\not= M^c[/mm]
> >
> [mm]N(d)\notin M^c[/mm]
> > meinst du.
> > > mit d [mm]\in M^c[/mm]
> > > und * folgt: [mm]\exists[/mm] b [mm]\in[/mm] M N(b) = d,
> > Nein. Wenn wir [mm]d\in M^c[/mm] haben, sagt (*) nichts über [mm]d[/mm]
> > aus.
> >
> >
> > Aber wir haben nach Widerspruchsannahme [mm]N(d)\notin M^c[/mm],
> > also [mm]N(d)\in M[/mm].
> >
> > Nach (*) existiert also ein [mm]b\in M[/mm] mit [mm]N(b)=N(d)[/mm].
> >
> > Was liefert nun P2?
> >
> > Leite daraus einen Widerspruch zu [mm]d\in M^c[/mm] ab.
> Okay, nochmal vielen Dank. Aus P2 folgt ja dann, dass b und
> d gleich sind.
> * sagt, dass ein b in M existiert,
Es müsste heißen: Nach Wahl von $b$ war [mm] $b\in [/mm] M$.
> was aber
> im Widerspruch zu d [mm]\in M^c[/mm] steht, wenn b und d gleich
> sind, weil dann ja b in [mm]M^c[/mm] sein müsste. Richtig?
|
|
|
|
