Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Ist der Beweis korrekt?
13 views
Skip to first unread message
Ernst Baumann
Feb 5, 2012, 3:15:11 AM2/5/12
to
Hallo allerseits,
Bei Amann/Escher wurde Seite 43 der Satz 5.11 bewiesen.
Ich habe den Beweis nicht verstanden und deshalb _selbst_ einen Beweis
produziert. Mein Problem ist:
Ist dieser Beweis auch korrekt?
Ich wuerde mich auf feebback freuen
Der komplette Satz mit meinem Beweis befindet sich unter:
http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
mfg
Ernst
Bei Amann/Escher wurde Seite 43 der Satz 5.11 bewiesen.
Ich habe den Beweis nicht verstanden und deshalb _selbst_ einen Beweis
produziert. Mein Problem ist:
Ist dieser Beweis auch korrekt?
Ich wuerde mich auf feebback freuen
Der komplette Satz mit meinem Beweis befindet sich unter:
http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
mfg
Ernst
Carsten Schultz
Feb 5, 2012, 6:30:01 AM2/5/12
to
Am 05.02.12 09:15, schrieb Ernst Baumann:
Ich habe nur kurz geschaut, aber in II) 1) scheinst Du Abbildungen f_n
rekursiv zu definieren. Dass rekursive Definitionen möglich sind, ist
aber gerade, was Du zeigen möchtest.
Gruß
Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
rekursiv zu definieren. Dass rekursive Definitionen möglich sind, ist
aber gerade, was Du zeigen möchtest.
Gruß
Carsten
--
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
Ernst Baumann
Feb 5, 2012, 2:43:16 PM2/5/12
to
>> Hallo allerseits,
>> Bei Amann/Escher wurde Seite 43 der Satz 5.11 bewiesen.
>> Ich habe den Beweis nicht verstanden und deshalb _selbst_ einen Beweis
>> produziert. Mein Problem ist:=20
>> Bei Amann/Escher wurde Seite 43 der Satz 5.11 bewiesen.
>> Ich habe den Beweis nicht verstanden und deshalb _selbst_ einen Beweis
>> Ist dieser Beweis auch korrekt?
>> Ich wuerde mich auf feebback freuen
>>=20
>> Ich wuerde mich auf feebback freuen
>> Der komplette Satz mit meinem Beweis befindet sich unter:
>>=20
>> http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
>>=20
>
>Ich habe nur kurz geschaut, aber in II) 1) scheinst Du Abbildungen f_n
>rekursiv zu definieren. Dass rekursive Definitionen m=C3=B6glich sind, i=
>Ich habe nur kurz geschaut, aber in II) 1) scheinst Du Abbildungen f_n
>st
>aber gerade, was Du zeigen m=C3=B6chtest.
>
>
1)
In der Behauptung des Satzes kommt links des Gleichheitszeichens und
rechts des Gleichheitszeichens dieselbe Abbildung vor:
f(n+1) = ... f(0), ..., f(n) ...
Man muss also zeigen, dass es so eine Abbildung f gibt.
Das mache ich mit Hilfe von 2) (siehe gleich).
2)
Bei meinem Beweis werden Abbildungen (Eine Folge von Abbildungen)
f_0, f_1, ..., f_n konstruiert.
Bei meinem Beweis kommt links des Gleichheitszeichens und rechts des
Gleichheitszeichens nicht dieselbe Abbildung vor (im Gegensatz zu1)
siehe oben)
Es kommt nur so etwas vor wie:
f_i+1 = ... f_0, f_1, .... f_i ...
Allerdings wird f_i+1 rekursiv dargestellt.
D.h. Die Abbildung f_i+1 wird durch _andere_ Abbildungen dargestellt
(gebastelt).
Warum ich allerdings diese Rekursion so ohne weiteres verwenden darf,
ist mir allerdings auch unklar.
3)
Was mich jetzt vollends verwirrt ist folgendes:
f(n+1) := V_n+1( f(0), ..., f(n) ) (*)
ist nicht ohne Weiteres erlaubt, weil ja eine Rekursion vorkommt.
Aber man koennte ja folgendes definieren:
f(0) := a_0
f(1) := a_1
f(2) := a_2
...
f(i) := a_i
und
a_n+1 := V_n+1( a_0, ..., a_n )
Jetzt hat man also Folgendglieder (also Rekursion erlaubt)
Wegen der Gleichheit muesste dann folgen:
f(n+1) := V_n+1( f(0), ..., f(n) )
im Widerspruch zu (*)
4)
In dem Orginalbeweis (des Rekursionssatzes)
www.kapitalismus-modell.de/Div/diverses.html
wird aber die Definition der folgenden Rekursion einfach so erlaubt,
ohne dies weiter rechtzufertigen
f_n+1(k) := V_n+1( f_n(0), ..., f_n(n) )
Warum geht das (weil das Folgen sind) ?
mit total verwirrten Gruessen
Ernst
Carsten Schultz
Feb 5, 2012, 4:08:56 PM2/5/12
to
Am 05.02.12 20:43, schrieb Ernst Baumann:
Darfst Du ja auch nicht. Eine Folge (f_i) ist ja das selbe wie eine
Funktion, deren Definitionsbereich die natürlichen Zahlen sind, und die
i auf f_i abbildet. Du benutzt hier also eine rekursive Definition wie
in der Behauptung, nur mit komplizierterem X.
> 3)
> Was mich jetzt vollends verwirrt ist folgendes:
> f(n+1) := V_n+1( f(0), ..., f(n) ) (*)
> ist nicht ohne Weiteres erlaubt, weil ja eine Rekursion vorkommt.
> Aber man koennte ja folgendes definieren:
> f(0) := a_0
> f(1) := a_1
> f(2) := a_2
> ...
> f(i) := a_i
> und
> a_n+1 := V_n+1( a_0, ..., a_n )
>
> Jetzt hat man also Folgendglieder (also Rekursion erlaubt)
> Wegen der Gleichheit muesste dann folgen:
> f(n+1) := V_n+1( f(0), ..., f(n) )
> im Widerspruch zu (*)
>
Du hast richtig gesehen, dass es hier keinen Unterschied gibt. Was Dir
anscheinend noch nicht klar ist, ist, dass es hier darum geht, zu
beweisen, dass Folgen rekursiv definiert werden können.
Der Link im Link funktioniert nicht.
> wird aber die Definition der folgenden Rekursion einfach so erlaubt,
> ohne dies weiter rechtzufertigen
> f_n+1(k) := V_n+1( f_n(0), ..., f_n(n) )
>
> Warum geht das (weil das Folgen sind) ?
>
Ich nehme an, dass da das n fest ist und man sich gerade in einem
Induktionsbeweis befindet. Das wäre dann gar keine Rekursion, denn man
definiert ja nur eine Funktion f_{n+1}, wobei die Funktion f_n bereits
gegeben ist.
Funktion, deren Definitionsbereich die natürlichen Zahlen sind, und die
i auf f_i abbildet. Du benutzt hier also eine rekursive Definition wie
in der Behauptung, nur mit komplizierterem X.
> 3)
> Was mich jetzt vollends verwirrt ist folgendes:
> f(n+1) := V_n+1( f(0), ..., f(n) ) (*)
> ist nicht ohne Weiteres erlaubt, weil ja eine Rekursion vorkommt.
> Aber man koennte ja folgendes definieren:
> f(0) := a_0
> f(1) := a_1
> f(2) := a_2
> ...
> f(i) := a_i
> und
> a_n+1 := V_n+1( a_0, ..., a_n )
>
> Jetzt hat man also Folgendglieder (also Rekursion erlaubt)
> Wegen der Gleichheit muesste dann folgen:
> f(n+1) := V_n+1( f(0), ..., f(n) )
> im Widerspruch zu (*)
>
anscheinend noch nicht klar ist, ist, dass es hier darum geht, zu
beweisen, dass Folgen rekursiv definiert werden können.
Der Link im Link funktioniert nicht.
> wird aber die Definition der folgenden Rekursion einfach so erlaubt,
> ohne dies weiter rechtzufertigen
> f_n+1(k) := V_n+1( f_n(0), ..., f_n(n) )
>
> Warum geht das (weil das Folgen sind) ?
>
Induktionsbeweis befindet. Das wäre dann gar keine Rekursion, denn man
definiert ja nur eine Funktion f_{n+1}, wobei die Funktion f_n bereits
gegeben ist.
Ernst Baumann
Feb 6, 2012, 3:03:16 PM2/6/12
to
>> 4)
>> In dem Orginalbeweis (des Rekursionssatzes)=20
Probier mal den:
http://www.kapitalismus-modell.de/Div/diverses.html
>>=20
http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
>Das w=C3=A4re dann gar keine Rekursion, denn man
Meiner Meinung nach ist das schon eine Rekursion, ungeachtet dessen,
dass du in deinen anderen Kritikpunkten ueberall recht hast.
mfg
Ernst
>> In dem Orginalbeweis (des Rekursionssatzes)=20
Probier mal den:
http://www.kapitalismus-modell.de/Div/diverses.html
>
>
>> wird aber die Definition der folgenden Rekursion einfach so erlaubt,
>> ohne dies weiter rechtzufertigen
>> f_n+1(k) :=3D V_n+1( f_n(0), ..., f_n(n) )=20
>
>> wird aber die Definition der folgenden Rekursion einfach so erlaubt,
>> ohne dies weiter rechtzufertigen
>>=20
>> Warum geht das (weil das Folgen sind) ?
>>=20
>
>Ich nehme an, dass da das n fest ist und man sich gerade in einem
>Induktionsbeweis befindet.
>
Ok, dann mache ich in meinem Beweis auch einen Induktionsbeweis:
>Ich nehme an, dass da das n fest ist und man sich gerade in einem
>Induktionsbeweis befindet.
>
http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
>Das w=C3=A4re dann gar keine Rekursion, denn man
>definiert ja nur eine Funktion f_{n+1}, wobei die Funktion f_n bereits
>gegeben ist.
>
Wie willst du das dann nennen, wenn dies keine Rekursion sein soll.
>gegeben ist.
>
Meiner Meinung nach ist das schon eine Rekursion, ungeachtet dessen,
dass du in deinen anderen Kritikpunkten ueberall recht hast.
mfg
Ernst
Carsten Schultz
Feb 6, 2012, 3:49:47 PM2/6/12
to
Am 06.02.12 21:03, schrieb Ernst Baumann:
>>
>>
>>> wird aber die Definition der folgenden Rekursion einfach so erlaubt,
>>> ohne dies weiter rechtzufertigen
>>> f_n+1(k) :=3D V_n+1( f_n(0), ..., f_n(n) )=20
>>> =20
>>> Warum geht das (weil das Folgen sind) ?
>>> =20
>>
>> Ich nehme an, dass da das n fest ist und man sich gerade in einem
>> Induktionsbeweis befindet.
>>
> Ok, dann mache ich in meinem Beweis auch einen Induktionsbeweis:
>
> http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
>
>
„ist ein wohlgeformtes mathematisches Objekt“ ist keine Aussage, die
exakt genug wäre, um sie zu beweisen. Es hat schon seine Gründe, dass
das im Buch so gemacht wird, wie es dort gemacht wird. (Ich vertraue
dem Buch einfach mal, ohne es gelesen zu haben.) Es wäre daher besser,
wenn Du noch einmal versuchen würdest, den Beweis dort zu verstehen.
Im übrigen beziehen wir uns hier auf ein im Wandel befindliches Dokument
auf Deiner Website, so dass die Diskussion hier im Nachhinein für
niemanden nachvollziehbar ist. Das ist eigentlich nicht Sinn der Sache.
>> Das w=C3=A4re dann gar keine Rekursion, denn man
>> definiert ja nur eine Funktion f_{n+1}, wobei die Funktion f_n bereits
>> gegeben ist.
>>
> Wie willst du das dann nennen, wenn dies keine Rekursion sein soll.
> Meiner Meinung nach ist das schon eine Rekursion, ungeachtet dessen,
> dass du in deinen anderen Kritikpunkten ueberall recht hast.
Wie gesagt wäre es wichtig, den Kontext zu verstehen.
>>> 4)
>>> In dem Orginalbeweis (des Rekursionssatzes)=20
>>> www.kapitalismus-modell.de/Div/diverses.html
>>
>> Der Link im Link funktioniert nicht.
>>
> Probier mal den:
> http://www.kapitalismus-modell.de/Div/diverses.html
Das konnte ich herunterladen, es ist aber kein mir bekanntes Dateiformat.
>>> In dem Orginalbeweis (des Rekursionssatzes)=20
>>> www.kapitalismus-modell.de/Div/diverses.html
>>
>> Der Link im Link funktioniert nicht.
>>
> Probier mal den:
> http://www.kapitalismus-modell.de/Div/diverses.html
>>
>>
>>> wird aber die Definition der folgenden Rekursion einfach so erlaubt,
>>> ohne dies weiter rechtzufertigen
>>> f_n+1(k) :=3D V_n+1( f_n(0), ..., f_n(n) )=20
>>> =20
>>> Warum geht das (weil das Folgen sind) ?
>>> =20
>>
>> Ich nehme an, dass da das n fest ist und man sich gerade in einem
>> Induktionsbeweis befindet.
>>
> Ok, dann mache ich in meinem Beweis auch einen Induktionsbeweis:
>
> http://www.kapitalismus-modell.de/Div/rekursionssatz.pdf
>
>
exakt genug wäre, um sie zu beweisen. Es hat schon seine Gründe, dass
das im Buch so gemacht wird, wie es dort gemacht wird. (Ich vertraue
dem Buch einfach mal, ohne es gelesen zu haben.) Es wäre daher besser,
wenn Du noch einmal versuchen würdest, den Beweis dort zu verstehen.
Im übrigen beziehen wir uns hier auf ein im Wandel befindliches Dokument
auf Deiner Website, so dass die Diskussion hier im Nachhinein für
niemanden nachvollziehbar ist. Das ist eigentlich nicht Sinn der Sache.
>> Das w=C3=A4re dann gar keine Rekursion, denn man
>> definiert ja nur eine Funktion f_{n+1}, wobei die Funktion f_n bereits
>> gegeben ist.
>>
> Wie willst du das dann nennen, wenn dies keine Rekursion sein soll.
> Meiner Meinung nach ist das schon eine Rekursion, ungeachtet dessen,
> dass du in deinen anderen Kritikpunkten ueberall recht hast.
Ernst Baumann
Feb 7, 2012, 12:07:52 PM2/7/12
to
>Das konnte ich herunterladen, es ist aber kein mir bekanntes Dateiformat.=
>
Ich habe die Datei in eine pdf-Datei umgewandelt.
Du kannst sie jetzt anschauen:
www.kapitalismus-modell.de/Div/diverses.html
>
>
>=E2=80=9Eist ein wohlgeformtes mathematisches Objekt=E2=80=9C ist keine A=
>ussage, die
>exakt genug w=C3=A4re, um sie zu beweisen.
>
Du hast recht.
Siehe unten den veraenderten Beweis.
>
>
>Es hat schon seine Gr=C3=BCnd=
>er,
>wenn Du noch einmal versuchen w=C3=BCrdest, den Beweis dort zu verstehen.=
>
Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
(siehe unten).
>
>Im =C3=BCbrigen beziehen wir uns hier auf ein im Wandel befindliches Doku=
>ment
>auf Deiner Website, so dass die Diskussion hier im Nachhinein f=C3=BCr
-----------------------------------------------------------------------------------------------
REKURSIONSSATZ
Voraussetzung:
X != {} und a aus X und N := {0;1;2, ...}
Fuer alle n aus N gilt V_n : X^n --> X ist eine Abbildung.
Behauptung:
Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
f(0) = a und
f(n+1) = V_{n+1}(f(0), ..., f(n)) fuer n aus N
Beweisidee:
Man konstruiert die Abbildung f dadurch, daß man ihren
Definitionsbereich schrittweise immer groeßer werden laeßt:
Man konstruiert f erst auf 0, dann f auf 1, dann f auf 2, usw.
diese Abbildungen werden dann alle zusammengefuegt zur Abbildung f auf
allen natuerlichen
Zahlen.
Beweis:
I) Eindeutigkeit:
g sei eine Abbildung, die o.g. Eigenschaften hat. Zeige g = f
B(n) :<==> g(n) = f(n)
D.h: Zeige B(n) fuer alle n aus N
Dies geschieht mit Hilfe der vollstaendigen Induktion:
1) Induktionsanfang B(0):
Nach Voraussetzung muss gelten: g(0) = a = f(0), also g(0) = f(0)
2) Induktionsvoraussetzung: B(0) und ... und B(n)
Es sei f(0)=g(0) und ... und f(n) = g(n)
also:
f(n+1) = V_{n+1}(f(0), ..., f(n)) = V_{n+1}(g(0), ..., g(n)) = g(n+1)
also wurde B(n+1) gezeigt.
II) Existenz
Bemerkung:
Im nachfolgenden Beweis wird hauptsaechlich verwendet: Eine Abbildung
ist eine rechtseindeutige Relation.
1) Unterbehauptung1:
Durch die 2 folgenden Gleichungen
f_0 : = {(0,a)}
f_n : = {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )} fuer n>0
werden fuer alle n aus N Abbildungen definiert, d.h. wohlgeformte
mathematische Objekte f_n erzeugt.
Beweis:
B(n) : <==> f_n ist eine Abbildung, d.h.ein wohlgeformtes
mathematisches Objekt.
Beweis durch Induktion:
a) Induktionsanfang: B(0)
Zeige f_0 : = {(0,a)} ist eine Abbildung, d.h. ein wohlgeformtes
mathematisches Objekt.
Da a eindeutig vorgegeben ist, gilt diese Behauptung.
b) Induktionsvoraussetzung: Es gelte fuer alle i<=n B(i) Zeige: B(n+1)
Voraussetzung:
Fuer alle i<=n gilt f_i ist eine Abbildung, d.h. ein wohlgeformtes
mathematisches Objekt.
Also sind f_0(0), f_1(1), ... ,f_n(n) alles Funktionswerte, d.h.
wohlgeformte mathematische Objekte.
Da außerdem fuer alle n aus N V_n eine Abbildung ist, ist
V_{n+1}(f_0(0), f_1(1), ... ,f_n(n)) ein Funktionswert,
d.h. ein wohlgeformtes mathematisches Objekt.
Nach Definition von f_n gilt:
f_{n+1} : = ( n , V_{n+1} (f_0(0), f_1(1), ... ,f_n(n)) )
Also ist auch f_{n+1} eine Abbildung, d.h. ein wohlgeformtes
mathematisches Objekt.
2)Definition:
f := f_0 U f_1 U f_2 U f_3 U ...
3)
Unterbehauptung2: fuer alle n aus N f_n(n) = f(n)
Beweis Unterbehauptung2:
a)
aus f : = f_0 U f_1 U f_2 U f_3 U ...
folgt fuer ein beliebiges n: f_n Teilmenge von f
b) n aus N\{0} ==> (n,V_n(f_0(0), f_1(1), ... ,f_{n-1} (i-1))) Element
f_n
Setze (um Schreibarbeit zu verringern):
x : = V_n(f_0(0), f_1(1), ... ,f_{n-1}(i-1)). Dann gilt: (n,x) Element
f_n
Da f_n Teilmenge f folgt (n,x) Element f. Also:
(n,x) aus f_n ==> f_n(n) = x
(n,x) aus f ==> f(n) = x
Damit:
f_n(n) = f(n)
c)
(0,a) aus f_0 Da f_0 Teilmenge f folgt (0,a) aus f. Also:
(0,a) Element f_0 ==> f_0(0) = x
(0,a) aus f ==> f(0) = a
Damit:
f_0(0) = f(0)
Aus b) und c) folgt die Unterbehauptung2
4)
Es gilt laut Definition fuer ein beliebiges n aus N
f_{n+1}(n+1) = V_{n+1}(f_0(0), f_1(1), ... ,f_n(n))
Da laut Unterbehauptung2 gilt: fuer alle i aus N f_i(i) = f(i) folgt:
f(n+1) = f_{n+1}(n+1) = V_{n+1}(f_0(0), ... , f_n(n)) =
V_{n+1}(f(0), ... , f(n)) , also:
f(n+1) = V_{n+1}(f(0), ... , f(n))
mfg
Ernst
>
Ich habe die Datei in eine pdf-Datei umgewandelt.
Du kannst sie jetzt anschauen:
www.kapitalismus-modell.de/Div/diverses.html
>
>
>=E2=80=9Eist ein wohlgeformtes mathematisches Objekt=E2=80=9C ist keine A=
>ussage, die
>exakt genug w=C3=A4re, um sie zu beweisen.
>
Du hast recht.
Siehe unten den veraenderten Beweis.
>
>
>Es hat schon seine Gr=C3=BCnd=
>e, dass
>das im Buch so gemacht wird, wie es dort gemacht wird. (Ich vertraue
>dem Buch einfach mal, ohne es gelesen zu haben.) Es w=C3=A4re daher bess=
>das im Buch so gemacht wird, wie es dort gemacht wird. (Ich vertraue
>er,
>wenn Du noch einmal versuchen w=C3=BCrdest, den Beweis dort zu verstehen.=
>
Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
(siehe unten).
>
>Im =C3=BCbrigen beziehen wir uns hier auf ein im Wandel befindliches Doku=
>ment
>auf Deiner Website, so dass die Diskussion hier im Nachhinein f=C3=BCr
>niemanden nachvollziehbar ist. Das ist eigentlich nicht Sinn der Sache.
>
Deshalb poste ich ab jetzt alles hier und nicht ueber den Link.
>
-----------------------------------------------------------------------------------------------
REKURSIONSSATZ
Voraussetzung:
X != {} und a aus X und N := {0;1;2, ...}
Fuer alle n aus N gilt V_n : X^n --> X ist eine Abbildung.
Behauptung:
Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
f(0) = a und
f(n+1) = V_{n+1}(f(0), ..., f(n)) fuer n aus N
Beweisidee:
Man konstruiert die Abbildung f dadurch, daß man ihren
Definitionsbereich schrittweise immer groeßer werden laeßt:
Man konstruiert f erst auf 0, dann f auf 1, dann f auf 2, usw.
diese Abbildungen werden dann alle zusammengefuegt zur Abbildung f auf
allen natuerlichen
Zahlen.
Beweis:
I) Eindeutigkeit:
g sei eine Abbildung, die o.g. Eigenschaften hat. Zeige g = f
B(n) :<==> g(n) = f(n)
D.h: Zeige B(n) fuer alle n aus N
Dies geschieht mit Hilfe der vollstaendigen Induktion:
1) Induktionsanfang B(0):
Nach Voraussetzung muss gelten: g(0) = a = f(0), also g(0) = f(0)
2) Induktionsvoraussetzung: B(0) und ... und B(n)
Es sei f(0)=g(0) und ... und f(n) = g(n)
also:
f(n+1) = V_{n+1}(f(0), ..., f(n)) = V_{n+1}(g(0), ..., g(n)) = g(n+1)
also wurde B(n+1) gezeigt.
II) Existenz
Bemerkung:
Im nachfolgenden Beweis wird hauptsaechlich verwendet: Eine Abbildung
ist eine rechtseindeutige Relation.
1) Unterbehauptung1:
Durch die 2 folgenden Gleichungen
f_0 : = {(0,a)}
f_n : = {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )} fuer n>0
werden fuer alle n aus N Abbildungen definiert, d.h. wohlgeformte
mathematische Objekte f_n erzeugt.
Beweis:
B(n) : <==> f_n ist eine Abbildung, d.h.ein wohlgeformtes
mathematisches Objekt.
Beweis durch Induktion:
a) Induktionsanfang: B(0)
Zeige f_0 : = {(0,a)} ist eine Abbildung, d.h. ein wohlgeformtes
mathematisches Objekt.
Da a eindeutig vorgegeben ist, gilt diese Behauptung.
b) Induktionsvoraussetzung: Es gelte fuer alle i<=n B(i) Zeige: B(n+1)
Voraussetzung:
Fuer alle i<=n gilt f_i ist eine Abbildung, d.h. ein wohlgeformtes
mathematisches Objekt.
Also sind f_0(0), f_1(1), ... ,f_n(n) alles Funktionswerte, d.h.
wohlgeformte mathematische Objekte.
Da außerdem fuer alle n aus N V_n eine Abbildung ist, ist
V_{n+1}(f_0(0), f_1(1), ... ,f_n(n)) ein Funktionswert,
d.h. ein wohlgeformtes mathematisches Objekt.
Nach Definition von f_n gilt:
f_{n+1} : = ( n , V_{n+1} (f_0(0), f_1(1), ... ,f_n(n)) )
Also ist auch f_{n+1} eine Abbildung, d.h. ein wohlgeformtes
mathematisches Objekt.
2)Definition:
f := f_0 U f_1 U f_2 U f_3 U ...
3)
Unterbehauptung2: fuer alle n aus N f_n(n) = f(n)
Beweis Unterbehauptung2:
a)
aus f : = f_0 U f_1 U f_2 U f_3 U ...
folgt fuer ein beliebiges n: f_n Teilmenge von f
b) n aus N\{0} ==> (n,V_n(f_0(0), f_1(1), ... ,f_{n-1} (i-1))) Element
f_n
Setze (um Schreibarbeit zu verringern):
x : = V_n(f_0(0), f_1(1), ... ,f_{n-1}(i-1)). Dann gilt: (n,x) Element
f_n
Da f_n Teilmenge f folgt (n,x) Element f. Also:
(n,x) aus f_n ==> f_n(n) = x
(n,x) aus f ==> f(n) = x
Damit:
f_n(n) = f(n)
c)
(0,a) aus f_0 Da f_0 Teilmenge f folgt (0,a) aus f. Also:
(0,a) Element f_0 ==> f_0(0) = x
(0,a) aus f ==> f(0) = a
Damit:
f_0(0) = f(0)
Aus b) und c) folgt die Unterbehauptung2
4)
Es gilt laut Definition fuer ein beliebiges n aus N
f_{n+1}(n+1) = V_{n+1}(f_0(0), f_1(1), ... ,f_n(n))
Da laut Unterbehauptung2 gilt: fuer alle i aus N f_i(i) = f(i) folgt:
f(n+1) = f_{n+1}(n+1) = V_{n+1}(f_0(0), ... , f_n(n)) =
V_{n+1}(f(0), ... , f(n)) , also:
f(n+1) = V_{n+1}(f(0), ... , f(n))
mfg
Ernst
Carsten Schultz
Feb 7, 2012, 1:58:27 PM2/7/12
to
Am 07.02.12 18:07, schrieb Ernst Baumann:
in Deinem nicht siehst. Ich erkläre das demnächst, habe aber momentan
keine Zeit. Vielleicht findest Du ja auch irgendwo einen Beweis, der
Dir mehr einleuchtet.
>>
>>
>> =E2=80=9Eist ein wohlgeformtes mathematisches Objekt=E2=80=9C ist keine A=
>> ussage, die
>> exakt genug w=C3=A4re, um sie zu beweisen.
>>
> Du hast recht.
> Siehe unten den veraenderten Beweis.
>>
>>
>> Es hat schon seine Gr=C3=BCnd=
>> e, dass
>> das im Buch so gemacht wird, wie es dort gemacht wird. (Ich vertraue
>> dem Buch einfach mal, ohne es gelesen zu haben.) Es w=C3=A4re daher bess=
>> er,
>> wenn Du noch einmal versuchen w=C3=BCrdest, den Beweis dort zu verstehen.=
>>
> Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
> (siehe unten).
>>
[...]
>>> Probier mal den:
>>> http://www.kapitalismus-modell.de/Div/diverses.html
>>
>> Das konnte ich herunterladen, es ist aber kein mir bekanntes Dateiformat.=
>>
> Ich habe die Datei in eine pdf-Datei umgewandelt.
> Du kannst sie jetzt anschauen:
> www.kapitalismus-modell.de/Div/diverses.html
Ok, der Beweis ist auch jetzt, jetzt ist mir klar, warum Du das Problem
>>> http://www.kapitalismus-modell.de/Div/diverses.html
>>
>> Das konnte ich herunterladen, es ist aber kein mir bekanntes Dateiformat.=
>>
> Ich habe die Datei in eine pdf-Datei umgewandelt.
> Du kannst sie jetzt anschauen:
> www.kapitalismus-modell.de/Div/diverses.html
in Deinem nicht siehst. Ich erkläre das demnächst, habe aber momentan
keine Zeit. Vielleicht findest Du ja auch irgendwo einen Beweis, der
Dir mehr einleuchtet.
>>
>>
>> =E2=80=9Eist ein wohlgeformtes mathematisches Objekt=E2=80=9C ist keine A=
>> ussage, die
>> exakt genug w=C3=A4re, um sie zu beweisen.
>>
> Du hast recht.
> Siehe unten den veraenderten Beweis.
>>
>>
>> Es hat schon seine Gr=C3=BCnd=
>> e, dass
>> das im Buch so gemacht wird, wie es dort gemacht wird. (Ich vertraue
>> dem Buch einfach mal, ohne es gelesen zu haben.) Es w=C3=A4re daher bess=
>> er,
>> wenn Du noch einmal versuchen w=C3=BCrdest, den Beweis dort zu verstehen.=
>>
> Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
> (siehe unten).
>>
> 1) Unterbehauptung1:
> Durch die 2 folgenden Gleichungen
> f_0 : = {(0,a)}
> f_n : = {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )} fuer n>0
> werden fuer alle n aus N Abbildungen definiert, d.h. wohlgeformte
> mathematische Objekte f_n erzeugt.
Das ist noch nicht besser.
> Durch die 2 folgenden Gleichungen
> f_0 : = {(0,a)}
> f_n : = {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )} fuer n>0
> werden fuer alle n aus N Abbildungen definiert, d.h. wohlgeformte
> mathematische Objekte f_n erzeugt.
Carsten Schultz
Feb 7, 2012, 2:05:54 PM2/7/12
to
Korrektur:
Am 07.02.12 19:58, schrieb Carsten Schultz:
> Am 07.02.12 18:07, schrieb Ernst Baumann:
>>>> Probier mal den:
>>>> http://www.kapitalismus-modell.de/Div/diverses.html
>>>
>>> Das konnte ich herunterladen, es ist aber kein mir bekanntes Dateiformat.=
>>>
>> Ich habe die Datei in eine pdf-Datei umgewandelt.
>> Du kannst sie jetzt anschauen:
>> www.kapitalismus-modell.de/Div/diverses.html
>
> Ok, der Beweis ist auch jetzt,
Ok, der Beweis ist auch schlecht,
>>>> Probier mal den:
>>>> http://www.kapitalismus-modell.de/Div/diverses.html
>>>
>>> Das konnte ich herunterladen, es ist aber kein mir bekanntes Dateiformat.=
>>>
>> Ich habe die Datei in eine pdf-Datei umgewandelt.
>> Du kannst sie jetzt anschauen:
>> www.kapitalismus-modell.de/Div/diverses.html
>
> Ok, der Beweis ist auch jetzt,
Ernst Baumann
Feb 7, 2012, 2:43:41 PM2/7/12
to
>> Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
>> (siehe unten).
>>>
>[...]
>> 1) Unterbehauptung1:
>> Durch die 2 folgenden Gleichungen=20
>> (siehe unten).
>>>
>[...]
>> 1) Unterbehauptung1:
>> f_0 : =3D {(0,a)}
>> f_n : =3D {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )} fuer n>0
>> werden fuer alle n aus N Abbildungen definiert, d.h. wohlgeformte
>> mathematische Objekte f_n erzeugt.=20
>
>Das ist noch nicht besser.
>
und wenn ich ueberall die Redewendung "wohlgeformte
>Das ist noch nicht besser.
>
mathematische Objekte" weglasse ?
mfg
Ernst
Ernst Baumann
Feb 7, 2012, 3:18:28 PM2/7/12
to
>>>
>> Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
>> (siehe unten).
>>>
>[...]
>> 1) Unterbehauptung1:
>> Mich wuerde interesieren, ob ich meinem Beweis einen Denkfehler habe
>> (siehe unten).
>>>
>[...]
>> 1) Unterbehauptung1:
>> Durch die 2 folgenden Gleichungen=20
>> f_0 : =3D {(0,a)}
>> f_n : =3D {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )} fuer n>0
>> f_0 : =3D {(0,a)}
>> werden fuer alle n aus N Abbildungen definiert, d.h. wohlgeformte
>> mathematische Objekte f_n erzeugt.=20
>
>Das ist noch nicht besser.
>
Du hast zwar wenig Zeit, aber nur eine Frage:
>Das ist noch nicht besser.
>
Zusatz:
Ich lasse in meinem Beweis ueberall die Redewendung "wohlgeformte
mathematische Objekte" weg.
Kannst du mir in meinem Beweis dann einen Denkfehler nennen?
mfg
Ernst
Carsten Schultz
Feb 8, 2012, 4:33:51 AM2/8/12
to
Am 07.02.12 18:07, schrieb Ernst Baumann:
ein f_n mit dieser Eigenschaft gibt. Das Problem ist dann, dass da aber
auch die Rede von f_k für k<n ist. Was also genau ist die Aussage B(n)?
Hier ist auch der Beweis im Buch zweifelhaft.
Carsten Schultz
Feb 8, 2012, 4:50:18 AM2/8/12
to
Am 07.02.12 18:07, schrieb Ernst Baumann:
[...]
>
> -----------------------------------------------------------------------------------------------
> REKURSIONSSATZ
> Voraussetzung:
> X != {} und a aus X und N := {0;1;2, ...}
> Fuer alle n aus N gilt V_n : X^n --> X ist eine Abbildung.
>
> Behauptung:
> Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
> f(0) = a und
> f(n+1) = V_{n+1}(f(0), ..., f(n)) fuer n aus N
>
Einen ordentlichen Beweis (nicht, dass ich ihn gelesen hätte ;) eines
> -----------------------------------------------------------------------------------------------
> REKURSIONSSATZ
> Voraussetzung:
> X != {} und a aus X und N := {0;1;2, ...}
> Fuer alle n aus N gilt V_n : X^n --> X ist eine Abbildung.
>
> Behauptung:
> Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
> f(0) = a und
> f(n+1) = V_{n+1}(f(0), ..., f(n)) fuer n aus N
>
allgemeineren Satzes findest Du zum Beispiel bei Geschke, Satz 7.3. Ich
sage nur einmal, wie sich die Situation hier in die Situation dort
übersetzt.
Setze dort X = N und
g(f) = V_{n+1} (f(0),...,f(n)),
wenn f eine Funktion {0,...n} -> X ist,
g(f) = a, wenn f die Funktion {} -> X ist.
g(f) beliebig (zum Beipiel {}), sonst.
Das V dort ist übrigens die Allklasse. Hilft das? Verstehst Du den
Beweis dort?
Ernst Baumann
Feb 8, 2012, 3:30:50 PM2/8/12
to
>> Beweis:
>> B(n) : <--> f_n ist eine Abbildung, d.h.ein wohlgeformtes
>(n)?
>
Ich bin daran interessiert, wo ich meine mathematische
"Sorgfaelltigkeitspflicht" verletzt habe.
Deswegen nochmals:
B(n) : <-->
Warum ist dies _nicht_ praezise ?
Weil links des Gleichheitszeichens f_n und rechts des
Gleichheitszeichens f_0 bis f_{n-1} vorkommen.
Hast du das gemeinst?
mfg
Ernst
>> B(n) : <--> f_n ist eine Abbildung, d.h.ein wohlgeformtes
>> mathematisches Objekt.
>>
>
>Du musst hier genauer sein. Du willst vielleicht sagen, dass es genau
>ein f_n mit dieser Eigenschaft gibt. Das Problem ist dann, dass da aber
>auch die Rede von f_k f=C3=BCr k<n ist. Was also genau ist die Aussage B=
>>
>
>Du musst hier genauer sein. Du willst vielleicht sagen, dass es genau
>ein f_n mit dieser Eigenschaft gibt. Das Problem ist dann, dass da aber
>(n)?
>
>Du musst hier genauer sein. Du willst vielleicht sagen,
>dass es genau ein f_n mit dieser Eigenschaft gibt.
>Das Problem ist dann, dass da aber auch die Rede von
>f_k fuer k<n ist. Was also genau ist die Aussage B(n)?
>Du musst hier genauer sein. Du willst vielleicht sagen,
>dass es genau ein f_n mit dieser Eigenschaft gibt.
>Das Problem ist dann, dass da aber auch die Rede von
>
Ich bin daran interessiert, wo ich meine mathematische
"Sorgfaelltigkeitspflicht" verletzt habe.
Deswegen nochmals:
B(n) : <-->
f_n : = {( n,V_n(f_0(0), f_1(1), ... ,f_{n-1}(n-1)) )}
ist eine Abbildung.
Warum ist dies _nicht_ praezise ?
Weil links des Gleichheitszeichens f_n und rechts des
Gleichheitszeichens f_0 bis f_{n-1} vorkommen.
Hast du das gemeinst?
mfg
Ernst
Ernst Baumann
Feb 8, 2012, 3:30:51 PM2/8/12
to
>
>Einen ordentlichen Beweis (nicht, dass ich ihn gelesen haette ;)
habe.
Deswegen:
Braucht man diese fuer meine Version des Rekursionssatzes oder geht es
"billiiger" (d.h. mit weniger Kenntnissen der Mengenlehre)?
mfg
Ernst
>Einen ordentlichen Beweis (nicht, dass ich ihn gelesen haette ;)
>eines allgemeineren Satzes findest Du zum Beispiel bei
>Geschke, Satz 7.3. Ich sage nur einmal, wie sich die Situation
>hier in die Situation dort uebersetzt.
>Geschke, Satz 7.3. Ich sage nur einmal, wie sich die Situation
>
>Setze dort X = N und
> g(f) = V_{n+1} (f(0),...,f(n)),
> wenn f eine Funktion {0,...n} -> X ist,
> g(f) = a, wenn f die Funktion {} -> X ist.
> g(f) beliebig (zum Beipiel {}), sonst.
>
>Das V dort ist uebrigens die Allklasse. Hilft das?
>Setze dort X = N und
> g(f) = V_{n+1} (f(0),...,f(n)),
> wenn f eine Funktion {0,...n} -> X ist,
> g(f) = a, wenn f die Funktion {} -> X ist.
> g(f) beliebig (zum Beipiel {}), sonst.
>
>Verstehst Du den Beweis dort?
>
Leider nein, da ich nicht diese tieferen Kenntnisse der Mengenlehre
>
habe.
Deswegen:
Braucht man diese fuer meine Version des Rekursionssatzes oder geht es
"billiiger" (d.h. mit weniger Kenntnissen der Mengenlehre)?
mfg
Ernst
Ernst Baumann
Feb 8, 2012, 3:30:53 PM2/8/12
to
>
>Einen ordentlichen Beweis (nicht, dass ich ihn gelesen h=C3=A4tte ;) eine=
>
I)
Bemerkung:
Beim Programmieren von Rekursionen hat man _nicht_ immer den Fall
gegeben, dass
f(0) = a und
f(n+1) = Vn+1(f(0), ..., f(n)) fuer n aus N
d.h. es kann beim Programmieren vorkommen, dass rechts des
Gleichheitszeichnes nicht alle Vorgaenger von n+1 stehen.
II)
Deswegen habe ich eine Variante des Rekursionssatzes ausfgestellt:
Satz (Variante des Rekursionssatzes)
Voraussetzung:
X !={} und a aus X.
Fuer alle n aus N V_n : X_n --> X ist eine Abbildung.
Fuer alle n aus N ist
H: N--> P(N) = Menge aller Teilmengen von N
eine Abbildung mit
H(n+1) = { j1 , ..., jk} ist Teilmenge von N fuer n aus N und
H(n) != {} fuer n>0 und
j1 < j2 <...< jk < n+1
Behauptung:
Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
f(0) = a und
f(n+1) = V_{n+1}( f_j1), ..., f_jk) )
Ist dieser Satz korrekt ?
III)
1)
Als Beweisidee dieses Satzes wuerde ich das Konzept einer induktiv
definierten Menge benutzen:
http://www2.cs.uni-paderborn.de/cs/kindler/Lehre/WS04/Semantik/PDF/Kapitel4.pdf
"..., dass in der Informatik fast ueberall nur mit Wasser gekocht
wird, wobei das Wasser die Konzepte des induktiven Definierens und
Beweisens sind." (Prof . Kindler)
2)
Vermutlich ist dir das bekannt.
Dewegen nur ein kurzes Beispiel fuer das Konzept des induktiven
Definierens:
Regeln fuer den Rekursionssatz, den wir bisher diskutiert haben:
Regeln:
{}
----------
(0, f(0))
(0 , x_0), ...,(n , x_n)
----------------------------
(n+1, V_{n+1}(x_0, ..., x_n)
D_0 := {}
D_i={x aus X | es existiert Y Teilmengee aus D_{i-1} mit (Y,x) ist
eine Regel }
D = D_0 U D_1 U D_2 U . . .
Das setzt vermutlich den Rekursionssatz voraus.
Ich akkzeptiere dies und hoffe dann mit Hilfe dieses Konzeptes "meine
Variante" des Rekursionssatzes zu beweisen.
Was meinst du dazu?
mfg
Ernst
>Einen ordentlichen Beweis (nicht, dass ich ihn gelesen h=C3=A4tte ;) eine=
>s
>allgemeineren Satzes findest Du zum Beispiel bei Geschke, Satz 7.3. Ich
>sage nur einmal, wie sich die Situation hier in die Situation dort
>=C3=BCbersetzt.
>allgemeineren Satzes findest Du zum Beispiel bei Geschke, Satz 7.3. Ich
>sage nur einmal, wie sich die Situation hier in die Situation dort
>
I)
Bemerkung:
Beim Programmieren von Rekursionen hat man _nicht_ immer den Fall
gegeben, dass
f(0) = a und
f(n+1) = Vn+1(f(0), ..., f(n)) fuer n aus N
d.h. es kann beim Programmieren vorkommen, dass rechts des
Gleichheitszeichnes nicht alle Vorgaenger von n+1 stehen.
II)
Deswegen habe ich eine Variante des Rekursionssatzes ausfgestellt:
Satz (Variante des Rekursionssatzes)
Voraussetzung:
X !={} und a aus X.
Fuer alle n aus N V_n : X_n --> X ist eine Abbildung.
Fuer alle n aus N ist
H: N--> P(N) = Menge aller Teilmengen von N
eine Abbildung mit
H(n+1) = { j1 , ..., jk} ist Teilmenge von N fuer n aus N und
H(n) != {} fuer n>0 und
j1 < j2 <...< jk < n+1
Behauptung:
Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
f(0) = a und
Ist dieser Satz korrekt ?
III)
1)
Als Beweisidee dieses Satzes wuerde ich das Konzept einer induktiv
definierten Menge benutzen:
http://www2.cs.uni-paderborn.de/cs/kindler/Lehre/WS04/Semantik/PDF/Kapitel4.pdf
"..., dass in der Informatik fast ueberall nur mit Wasser gekocht
wird, wobei das Wasser die Konzepte des induktiven Definierens und
Beweisens sind." (Prof . Kindler)
2)
Vermutlich ist dir das bekannt.
Dewegen nur ein kurzes Beispiel fuer das Konzept des induktiven
Definierens:
Regeln fuer den Rekursionssatz, den wir bisher diskutiert haben:
Regeln:
{}
----------
(0, f(0))
(0 , x_0), ...,(n , x_n)
----------------------------
(n+1, V_{n+1}(x_0, ..., x_n)
D_0 := {}
D_i={x aus X | es existiert Y Teilmengee aus D_{i-1} mit (Y,x) ist
eine Regel }
D = D_0 U D_1 U D_2 U . . .
Das setzt vermutlich den Rekursionssatz voraus.
Ich akkzeptiere dies und hoffe dann mit Hilfe dieses Konzeptes "meine
Variante" des Rekursionssatzes zu beweisen.
Was meinst du dazu?
mfg
Ernst
Ernst Baumann
Feb 9, 2012, 1:30:52 AM2/9/12
to
Korrektur:
>
>II)
>Deswegen habe ich eine Variante des Rekursionssatzes ausfgestellt:
>
>Satz (Variante des Rekursionssatzes)
>Voraussetzung:
>X !={} und a aus X.
>Fuer alle n aus N V_n : X_n --> X ist eine Abbildung.
>Fuer alle n aus N ist
>H: N--> P(N) = Menge aller Teilmengen von N
>eine Abbildung mit
>H(n+1) = { j1 , ..., jk} ist Teilmenge von N fuer n aus N und
>H(n) != {} fuer n>0 und
>j1 < j2 <...< jk < n+1
>
>Behauptung:
>Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
>f(0) = a und
>f(n+1) = V_{n+1}( f( j1 ), ..., f( jk ) ) <-- Korrektur
>Deswegen habe ich eine Variante des Rekursionssatzes ausfgestellt:
>
>Satz (Variante des Rekursionssatzes)
>Voraussetzung:
>X !={} und a aus X.
>Fuer alle n aus N V_n : X_n --> X ist eine Abbildung.
>Fuer alle n aus N ist
>H: N--> P(N) = Menge aller Teilmengen von N
>eine Abbildung mit
>H(n+1) = { j1 , ..., jk} ist Teilmenge von N fuer n aus N und
>H(n) != {} fuer n>0 und
>j1 < j2 <...< jk < n+1
>
>Behauptung:
>Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
>f(0) = a und
>
Carsten Schultz
Feb 9, 2012, 4:32:05 AM2/9/12
to
Am 08.02.12 21:30, schrieb Ernst Baumann:
Das ist das Problem, Du sagst nicht, was das für Objekte sein sollen.
Die Aussage B(n), die Du per Induktion beweisen willst, muss Sinn
ergeben, wenn ich sie für ein festes n betrachte, ohne dass irgendetwas
aus den B(k) für andere k vorkäme.
> Hast du das gemeinst?
>
> mfg
> Ernst
>
>
>
Die Aussage B(n), die Du per Induktion beweisen willst, muss Sinn
ergeben, wenn ich sie für ein festes n betrachte, ohne dass irgendetwas
aus den B(k) für andere k vorkäme.
> Hast du das gemeinst?
>
> mfg
> Ernst
>
>
>
Carsten Schultz
Feb 9, 2012, 4:33:10 AM2/9/12
to
Am 08.02.12 21:30, schrieb Ernst Baumann:
>>
>>
spezialisiert, benötigt er auch keine tieferen Kenntnisse der Mengenlehre.
Carsten Schultz
Feb 9, 2012, 4:35:26 AM2/9/12
to
Am 08.02.12 21:30, schrieb Ernst Baumann:
>>
>>
>> Einen ordentlichen Beweis (nicht, dass ich ihn gelesen h=C3=A4tte ;) eine=
>> s
>> allgemeineren Satzes findest Du zum Beispiel bei Geschke, Satz 7.3. Ich
>> sage nur einmal, wie sich die Situation hier in die Situation dort
>> =C3=BCbersetzt.
>>
> I)
> Bemerkung:
> Beim Programmieren von Rekursionen hat man _nicht_ immer den Fall
> gegeben, dass
> f(0) = a und
> f(n+1) = Vn+1(f(0), ..., f(n)) fuer n aus N
> d.h. es kann beim Programmieren vorkommen, dass rechts des
> Gleichheitszeichnes nicht alle Vorgaenger von n+1 stehen.
>
Die Funktion V_{n+1} muss ja nicht von allen diesen Parametern echt
>> s
>> allgemeineren Satzes findest Du zum Beispiel bei Geschke, Satz 7.3. Ich
>> sage nur einmal, wie sich die Situation hier in die Situation dort
>> =C3=BCbersetzt.
>>
> I)
> Bemerkung:
> Beim Programmieren von Rekursionen hat man _nicht_ immer den Fall
> gegeben, dass
> f(0) = a und
> f(n+1) = Vn+1(f(0), ..., f(n)) fuer n aus N
> d.h. es kann beim Programmieren vorkommen, dass rechts des
> Gleichheitszeichnes nicht alle Vorgaenger von n+1 stehen.
>
abhängen.
Übung: Welche Funktionen V_{n+1} entsprechen der rekusiven Definition
der Fibonacci-Zahlen?
Carsten Schultz
Feb 9, 2012, 4:42:51 AM2/9/12
to
Am 09.02.12 10:32, schrieb Carsten Schultz:
Eine hilfreiche und sinnvolle Hilfsbehauptung wäre hingegen:
C(n):
Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
f_n(0) = a und
f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) für alle 0 <= k < n.
Siehst Du den Unterschied, und kannst Du diese Behauptung per Induktion
beweisen?
C(n):
Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
f_n(0) = a und
f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) für alle 0 <= k < n.
Siehst Du den Unterschied, und kannst Du diese Behauptung per Induktion
beweisen?
Ernst Baumann
Feb 9, 2012, 3:17:39 PM2/9/12
to
Hallo Carsten,
I)
>Eine hilfreiche und sinnvolle Hilfsbehauptung waere hingegen:
Ich habe versucht, in einer _Definition_ links und rechts
des Gleichheitszeichens (also im Definiens und im Definiendum)
dieselbe Funktion zu verwenden.
Das ist verboten.
Du hingegen hast eine _Behauptung_ aufgestellt (keine Definition).
In einer Behauptung kann links und rechts des Gleichheitszeichens
alles Moegliche stehen, auch dieselbe Funktion.
Habe ich das richtig erfasst?
II)
Um den folgenden Satz mit Hilfe der vollstaendigen Induktion zu
beweisen
------------------
-------------------
braeuchte man eine Konstruktion, die einem aus den Funktionen
f_0, ..., f_n die Funktion f_{n+1} basteln laesst.
Leider gibt die Gleichung
f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) fuer alle 0 <= k < n.
auch keinen Hinweis darauf, da links und rechts des
Gleichheitszeichens nur f_{n+1} vorkommt.
Deshalb habe ich in der Not die folgenden Rechnungen gemacht:
--------------
n=0:
f_0(0) = a
-------------
n=1:
f_1(0) = a
f_1(1) = V_1(f_1(0)) = V_1(a)
----------------------------
n=2:
f_2(0) = a
f_2(1) = V_1(f_2(0)) = V_1(a) = f_1(1)
f_2(2) = V_2(f_2(0), f_2(1) ) = V_2(f_1(0), f_1(1) )
-----------------------------------------------------
n=3:
f_3(0) = a
f_3(1) = V_1(f_3(0)) = V_1(a) = f_2(1)
f_3(2) = V_2(f_3(0), f_3(1)) = V_2(f_2(0), f_2(1)) = f_2(2)
f_3(3) = V_3(f_3(0), f_3(1), f_3(2)) = V_3(f_2(0), f_2(1), f_2(2) )
---------------------------------------------------------------------
Dies laesst Folgendes Vermuten:
f_{n+1}(k) = f_n(k) fuer k<= n
f_{n+1}(n+1) = V_{n+1}(f_n(0), ... , f_n(n))
Diese Vermutung gibt mir einen _Hinweis_ darauf, wie ich aus den
Funktionen f_0, ..., f_n die Funktion f_{n+1} basteln kann.
Beweis des Satzes:
Zeige Existenz:
1) Induktionsvoraussetzung C(0)
f_n = {(0,a)} ist eine Funktion mit der gewuenschten Eigenschaft
2) Induktionsvoraussetzung C(n)
Zeige C(n+1)
Laut Induktionsvoraussetzung existieren f_0, ..., f_n:
Jetzt wird daraus wie folgt die Funktion f_{n+1} gebastelt:
f_{n+1}(k) : = f_n(k) fuer k<= n
f_{n+1}(n+1) : = V_{n+1}(f_n(0), ... , f_n(n))
--------------
_Zwischenfrage:_
Ist f_{n+1} jetzt ein wohlgeformtes mathematisches Objekt?
Vermutlich nicht, weil links des Gleichheitszeichens
f_{n+1} und rechts f_n vorkommt.
Leider habe ich keine andere Idee, wie
der Beweis korrekt verlaufen sollte.
---------
Zeige:
f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
fuer alle 0 <= k < n+1.
Fall1: k<n
f_{n+1}(k) := f_n(k)
also:
f_{n+1}(k+1) = V_{k+1}(f_n(0),...,f_n(k)) =
V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
also:
f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
Fall2: k=n
f_{n+1}(n+1) := V_{n+1}(f_n(0), ... , f_n(n)) = V_{n+1}(f_{n+1}(0),
.. , f_{n+1}(n))
also:
f_{n+1}(n+1) = V_{n+1}(f_{n+1}(0), ... , f_{n+1}(n))
mfg
Ernst
I)
>Eine hilfreiche und sinnvolle Hilfsbehauptung waere hingegen:
>
>C(n):
>Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
>f_n(0) = a und
>f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) für alle 0 <= k < n.
>
>Siehst Du den Unterschied, und kannst Du
>diese Behauptung per Induktion beweisen?
>
Der Unterschied ist Folgender:
>C(n):
>Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
>f_n(0) = a und
>f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) für alle 0 <= k < n.
>
>Siehst Du den Unterschied, und kannst Du
>diese Behauptung per Induktion beweisen?
>
Ich habe versucht, in einer _Definition_ links und rechts
des Gleichheitszeichens (also im Definiens und im Definiendum)
dieselbe Funktion zu verwenden.
Das ist verboten.
Du hingegen hast eine _Behauptung_ aufgestellt (keine Definition).
In einer Behauptung kann links und rechts des Gleichheitszeichens
alles Moegliche stehen, auch dieselbe Funktion.
Habe ich das richtig erfasst?
II)
Um den folgenden Satz mit Hilfe der vollstaendigen Induktion zu
beweisen
------------------
C(n):
Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
f_n(0) = a und
f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) fuer alle 0 <= k < n.
Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
f_n(0) = a und
-------------------
braeuchte man eine Konstruktion, die einem aus den Funktionen
f_0, ..., f_n die Funktion f_{n+1} basteln laesst.
Leider gibt die Gleichung
f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) fuer alle 0 <= k < n.
auch keinen Hinweis darauf, da links und rechts des
Gleichheitszeichens nur f_{n+1} vorkommt.
Deshalb habe ich in der Not die folgenden Rechnungen gemacht:
--------------
n=0:
f_0(0) = a
-------------
n=1:
f_1(0) = a
f_1(1) = V_1(f_1(0)) = V_1(a)
----------------------------
n=2:
f_2(0) = a
f_2(1) = V_1(f_2(0)) = V_1(a) = f_1(1)
f_2(2) = V_2(f_2(0), f_2(1) ) = V_2(f_1(0), f_1(1) )
-----------------------------------------------------
n=3:
f_3(0) = a
f_3(1) = V_1(f_3(0)) = V_1(a) = f_2(1)
f_3(2) = V_2(f_3(0), f_3(1)) = V_2(f_2(0), f_2(1)) = f_2(2)
f_3(3) = V_3(f_3(0), f_3(1), f_3(2)) = V_3(f_2(0), f_2(1), f_2(2) )
---------------------------------------------------------------------
Dies laesst Folgendes Vermuten:
f_{n+1}(k) = f_n(k) fuer k<= n
f_{n+1}(n+1) = V_{n+1}(f_n(0), ... , f_n(n))
Diese Vermutung gibt mir einen _Hinweis_ darauf, wie ich aus den
Funktionen f_0, ..., f_n die Funktion f_{n+1} basteln kann.
Beweis des Satzes:
Zeige Existenz:
1) Induktionsvoraussetzung C(0)
f_n = {(0,a)} ist eine Funktion mit der gewuenschten Eigenschaft
2) Induktionsvoraussetzung C(n)
Zeige C(n+1)
Laut Induktionsvoraussetzung existieren f_0, ..., f_n:
Jetzt wird daraus wie folgt die Funktion f_{n+1} gebastelt:
f_{n+1}(k) : = f_n(k) fuer k<= n
f_{n+1}(n+1) : = V_{n+1}(f_n(0), ... , f_n(n))
--------------
_Zwischenfrage:_
Ist f_{n+1} jetzt ein wohlgeformtes mathematisches Objekt?
Vermutlich nicht, weil links des Gleichheitszeichens
f_{n+1} und rechts f_n vorkommt.
Leider habe ich keine andere Idee, wie
der Beweis korrekt verlaufen sollte.
---------
Zeige:
f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
fuer alle 0 <= k < n+1.
Fall1: k<n
f_{n+1}(k) := f_n(k)
also:
f_{n+1}(k+1) = V_{k+1}(f_n(0),...,f_n(k)) =
V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
also:
f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
Fall2: k=n
f_{n+1}(n+1) := V_{n+1}(f_n(0), ... , f_n(n)) = V_{n+1}(f_{n+1}(0),
.. , f_{n+1}(n))
also:
f_{n+1}(n+1) = V_{n+1}(f_{n+1}(0), ... , f_{n+1}(n))
mfg
Ernst
Ernst Baumann
Feb 9, 2012, 3:31:09 PM2/9/12
to
>
>Die Funktion V_{n+1} muss ja nicht von allen diesen Parametern echt
>abhaengen.
>Die Funktion V_{n+1} muss ja nicht von allen diesen Parametern echt
>
>Uebung: Welche Funktionen V_{n+1} entsprechen der rekusiven
>Definition der Fibonacci-Zahlen?
>
Das wuerde noch mit dem Rekursionssatz darstellbar sein.
Aber schau mal das Folgende von mir konstruierte Beispiel an:
Beispiel:
(N,<) ist die (wohlgeordnete) Menge der natürlichen Zahlen und Y = N
f : MxY U MxYxY U MxYxYxY U ... --> Y mit
f(m1, ..., mk) : = m1-m2+m3-m4+ ... mk
H(m) = {i1, ..., ik} = Menge aller Primzahlen, die kleiner m sind
vereinigt der Zahl m/2 (falls m gerade ist)
für alle m>10 gilt: g(m) = f(m, g(i1), ... ,g(ik) ) , wobei
i1<i2<...<ik
und für 2<=i<=10 gilt g(i) : = i
Also kann man wie folgt berechnen:
g(11) = f( 11, g(2), g(3), g(5), g(7) ) =
11 - g(2) + g(3) - g(5) + g(7) = 11- 2 +3 - 5 + 7 = 14
g(12) = f( 12, g(2), g(3), g(5), g(6), g(7), g(11) ) =
12 - g(2) + g(3) - g(5) + g(6) - g(7) + g(11) =
12 - 2 + 3 - 5 + 6 - 7 +14 = 21
g(13) = f( 13, g(2), g(3), g(5), g(7), g(11) ) =
13 - g(2) + g(3) - g(5) + g(7) - g(11) =
13 - 2 + 3 - 5 + 7 - 14 = 2
g(14) = f( 14, g(2), g(3), g(5), g(7), g(11), g(13) ) =
14 - g(2) + g(3) - g(5) + g(7) - g(11) +g(13) =
14 - 2 + 3 - 5 + 7 - 14 + 2 = 5
...
mfg
Ernst
Carsten Schultz
Feb 10, 2012, 9:54:07 AM2/10/12
to
Am 09.02.12 21:17, schrieb Ernst Baumann:
Definition war keine, und die Behauptung daher keine sinnvolle Aussage.
>
> Du hingegen hast eine _Behauptung_ aufgestellt (keine Definition).
> In einer Behauptung kann links und rechts des Gleichheitszeichens
> alles Moegliche stehen, auch dieselbe Funktion.
>
> Habe ich das richtig erfasst?
Ja, diese Behauptung ist eine klare Aussage.
>
> II)
> Um den folgenden Satz mit Hilfe der vollstaendigen Induktion zu
> beweisen
> ------------------
> C(n):
> Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
> f_n(0) = a und
> f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) fuer alle 0 <= k < n.
> -------------------
[...]
schreiben sollen, damit man nicht das Gefühl hat, die Behauptung würde
nebenbei gleich etwas definieren.
>
> 2) Induktionsvoraussetzung C(n)
> Zeige C(n+1)
>
> Laut Induktionsvoraussetzung existieren f_0, ..., f_n:
... mit (hier die Eigenschaft hinschreiben)
> Jetzt wird daraus wie folgt die Funktion f_{n+1} gebastelt:
> f_{n+1}(k) : = f_n(k) fuer k<= n
> f_{n+1}(n+1) : = V_{n+1}(f_n(0), ... , f_n(n))
>
> --------------
> _Zwischenfrage:_
> Ist f_{n+1} jetzt ein wohlgeformtes mathematisches Objekt?
> Vermutlich nicht, weil links des Gleichheitszeichens
> f_{n+1} und rechts f_n vorkommt.
Das ist doch genau das, was Du willst. Nach IV existiert (genau) eine
Funktion f_n mit ... Diese nehmen wir und setzen nun f_{n+1} wie Du es
tust. Nun muss man nur noch kurz bemerken, dass f_{n+1} die geforderten
Eigenschaften hat. Ah, das tust Du hier:
> Leider habe ich keine andere Idee, wie
> der Beweis korrekt verlaufen sollte.
> ---------
>
> Zeige:
> f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
> fuer alle 0 <= k < n+1.
>
> Fall1: k<n
> f_{n+1}(k) := f_n(k)
> also:
> f_{n+1}(k+1) =
= f_n(k+1) =
> V_{k+1}(f_n(0),...,f_n(k)) =
> V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
> also:
> f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
>
> Fall2: k=n
> f_{n+1}(n+1) := V_{n+1}(f_n(0), ... , f_n(n)) = V_{n+1}(f_{n+1}(0),
> .. , f_{n+1}(n))
> also:
> f_{n+1}(n+1) = V_{n+1}(f_{n+1}(0), ... , f_{n+1}(n))
>
>
Genau. Jetzt musst Du nur noch einen Kommentar zur Eindeutigkeit machen.
Gruß
Carsten
> Hallo Carsten,
> I)
>> Eine hilfreiche und sinnvolle Hilfsbehauptung waere hingegen:
>>
>> C(n):
>> Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
>> f_n(0) = a und
>> f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) fÃŒr alle 0 <= k < n.
> I)
>> Eine hilfreiche und sinnvolle Hilfsbehauptung waere hingegen:
>>
>> C(n):
>> Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
>> f_n(0) = a und
>>
>> Siehst Du den Unterschied, und kannst Du
>> diese Behauptung per Induktion beweisen?
>>
> Der Unterschied ist Folgender:
> Ich habe versucht, in einer _Definition_ links und rechts
> des Gleichheitszeichens (also im Definiens und im Definiendum)
> dieselbe Funktion zu verwenden.
> Das ist verboten.
Es war eher so, dass rechts etwas nicht definiertes stand, aber ja, die
>> Siehst Du den Unterschied, und kannst Du
>> diese Behauptung per Induktion beweisen?
>>
> Der Unterschied ist Folgender:
> Ich habe versucht, in einer _Definition_ links und rechts
> des Gleichheitszeichens (also im Definiens und im Definiendum)
> dieselbe Funktion zu verwenden.
> Das ist verboten.
Definition war keine, und die Behauptung daher keine sinnvolle Aussage.
>
> Du hingegen hast eine _Behauptung_ aufgestellt (keine Definition).
> In einer Behauptung kann links und rechts des Gleichheitszeichens
> alles Moegliche stehen, auch dieselbe Funktion.
>
> Habe ich das richtig erfasst?
>
> II)
> Um den folgenden Satz mit Hilfe der vollstaendigen Induktion zu
> beweisen
> ------------------
> C(n):
> Es gibt genau eine Funktion f_n: {0,...,n} -> X mit
> f_n(0) = a und
> f_n(k+1) = V_{k+1}(f_n(0),...,f_n(k)) fuer alle 0 <= k < n.
> -------------------
>
> Beweis des Satzes:
> Zeige Existenz:
> 1) Induktionsvoraussetzung C(0)
> f_n = {(0,a)} ist eine Funktion mit der gewuenschten Eigenschaft
f_0. Aber wahrscheinlich hätte ich ohnehin nicht f_n sondern g
> Beweis des Satzes:
> Zeige Existenz:
> 1) Induktionsvoraussetzung C(0)
> f_n = {(0,a)} ist eine Funktion mit der gewuenschten Eigenschaft
schreiben sollen, damit man nicht das Gefühl hat, die Behauptung würde
nebenbei gleich etwas definieren.
>
> 2) Induktionsvoraussetzung C(n)
> Zeige C(n+1)
>
> Laut Induktionsvoraussetzung existieren f_0, ..., f_n:
> Jetzt wird daraus wie folgt die Funktion f_{n+1} gebastelt:
> f_{n+1}(k) : = f_n(k) fuer k<= n
> f_{n+1}(n+1) : = V_{n+1}(f_n(0), ... , f_n(n))
>
> --------------
> _Zwischenfrage:_
> Ist f_{n+1} jetzt ein wohlgeformtes mathematisches Objekt?
> Vermutlich nicht, weil links des Gleichheitszeichens
> f_{n+1} und rechts f_n vorkommt.
Funktion f_n mit ... Diese nehmen wir und setzen nun f_{n+1} wie Du es
tust. Nun muss man nur noch kurz bemerken, dass f_{n+1} die geforderten
Eigenschaften hat. Ah, das tust Du hier:
> Leider habe ich keine andere Idee, wie
> der Beweis korrekt verlaufen sollte.
> ---------
>
> Zeige:
> f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
> fuer alle 0 <= k < n+1.
>
> Fall1: k<n
> f_{n+1}(k) := f_n(k)
> also:
> f_{n+1}(k+1) =
> V_{k+1}(f_n(0),...,f_n(k)) =
> V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
> also:
> f_{n+1}(k+1) = V_{k+1}(f_{n+1}(0),...,f_{n+1}(k))
>
> Fall2: k=n
> f_{n+1}(n+1) := V_{n+1}(f_n(0), ... , f_n(n)) = V_{n+1}(f_{n+1}(0),
> .. , f_{n+1}(n))
> also:
> f_{n+1}(n+1) = V_{n+1}(f_{n+1}(0), ... , f_{n+1}(n))
>
>
Gruß
Carsten
Carsten Schultz
Feb 10, 2012, 10:03:32 AM2/10/12
to
Am 09.02.12 21:31, schrieb Ernst Baumann:
Das geht doch mit
V_n(x_0,...,x_{n-1}) = n - x_{p_1} + x_{p+2} - ... +- x_{p_r},
wobei p_1 < ... < p_r die Primzahlen kleiner als n sind.
Gruß
Carsten
V_n(x_0,...,x_{n-1}) = n - x_{p_1} + x_{p+2} - ... +- x_{p_r},
wobei p_1 < ... < p_r die Primzahlen kleiner als n sind.
Gruß
Carsten
Ernst Baumann
Feb 10, 2012, 12:03:06 PM2/10/12
to
>>> Siehst Du den Unterschied, und kannst Du=20
>> f_{n+1}(n+1) : =3D V_{n+1}(f_n(0), ... , f_n(n))
Du schreibst:
"Nach Voraussetzung existiert genau eine mathematische Funkton f_n".
Das n dient zur Nummerierung.
Aber dieser Ausdruck f_n ist doch eine Abkuerzung fuer f(n)
Und
f_{n+1}(k)
ist eine Abkuerzung fuer
(f(n+1)) (n)
f ist also eine Funktion:
f : N --> M
wobei M die Menge aller Funktionen von N nach X ist.
Betrachte jetzt die Definition
(f(n+1)) (k) := (f(n)) (k)
Dies ist aber keine Definition, da das was links steht (naemlich f)
durch etwas definiert wird (naemlich f), was noch nicht definiert
wurde und rechts steht.
Ich weiss nicht, ob ich mich praezise genug ausgedrueckt habe.
Aber ich habe da meine mathematischen Bedenken....
mfg
Ernst
>>> diese Behauptung per Induktion beweisen?
>>>
>> Der Unterschied ist Folgender:
>> Ich habe versucht, in einer _Definition_ links und rechts=20
>>>
>> Der Unterschied ist Folgender:
>> des Gleichheitszeichens (also im Definiens und im Definiendum)
>> dieselbe Funktion zu verwenden.
>> Das ist verboten.
>
>Es war eher so, dass rechts etwas nicht definiertes stand, aber ja, die
>Definition war keine, und die Behauptung daher keine sinnvolle Aussage.
>
....
>> dieselbe Funktion zu verwenden.
>> Das ist verboten.
>
>Es war eher so, dass rechts etwas nicht definiertes stand, aber ja, die
>Definition war keine, und die Behauptung daher keine sinnvolle Aussage.
>
>> Jetzt wird daraus wie folgt die Funktion f_{n+1} gebastelt:
>> f_{n+1}(k) : =3D f_n(k) fuer k<=3D n
>> f_{n+1}(n+1) : =3D V_{n+1}(f_n(0), ... , f_n(n))
>>
>> --------------
>> _Zwischenfrage:_
>> Ist f_{n+1} jetzt ein wohlgeformtes mathematisches Objekt?
>> Vermutlich nicht, weil links des Gleichheitszeichens=20
>> --------------
>> _Zwischenfrage:_
>> Ist f_{n+1} jetzt ein wohlgeformtes mathematisches Objekt?
>> f_{n+1} und rechts f_n vorkommt.
>
>Das ist doch genau das, was Du willst. Nach IV existiert (genau) eine
>Funktion f_n mit ... Diese nehmen wir und setzen nun f_{n+1} wie Du es
>tust. Nun muss man nur noch kurz bemerken, dass f_{n+1} die geforderten
>Eigenschaften hat. Ah, das tust Du hier:
>
Bei mir tauchen folgende mathematische "Skrupel" auf:
>
>Das ist doch genau das, was Du willst. Nach IV existiert (genau) eine
>Funktion f_n mit ... Diese nehmen wir und setzen nun f_{n+1} wie Du es
>tust. Nun muss man nur noch kurz bemerken, dass f_{n+1} die geforderten
>Eigenschaften hat. Ah, das tust Du hier:
>
Du schreibst:
"Nach Voraussetzung existiert genau eine mathematische Funkton f_n".
Das n dient zur Nummerierung.
Aber dieser Ausdruck f_n ist doch eine Abkuerzung fuer f(n)
Und
f_{n+1}(k)
ist eine Abkuerzung fuer
(f(n+1)) (n)
f ist also eine Funktion:
f : N --> M
wobei M die Menge aller Funktionen von N nach X ist.
Betrachte jetzt die Definition
f_{n+1}(k) : = f_n(k)
Dies ist eine Abkuerzung fuer:
(f(n+1)) (k) := (f(n)) (k)
Dies ist aber keine Definition, da das was links steht (naemlich f)
durch etwas definiert wird (naemlich f), was noch nicht definiert
wurde und rechts steht.
Ich weiss nicht, ob ich mich praezise genug ausgedrueckt habe.
Aber ich habe da meine mathematischen Bedenken....
mfg
Ernst
Carsten Schultz
Feb 10, 2012, 1:37:41 PM2/10/12
to
Am 10.02.12 18:03, schrieb Ernst Baumann:
Ja, wie ich geschrieben habe, war es ungünstig, die Funktion mit f_n zu
bezeichnen, ich hätte g schreiben sollen. Dann heißt es hier
Nach IV existiert h: {0,...,n} -> X mit ...
Wir definieren nun g: {0,...,n+1} -> X durch ...
Also g statt f_{n+1}, h statt f_n.
bezeichnen, ich hätte g schreiben sollen. Dann heißt es hier
Nach IV existiert h: {0,...,n} -> X mit ...
Wir definieren nun g: {0,...,n+1} -> X durch ...
Also g statt f_{n+1}, h statt f_n.
Carsten Schultz
Feb 10, 2012, 1:39:08 PM2/10/12
to
Am 10.02.12 19:37, schrieb Carsten Schultz:
Nachtrag: Nachdem wir C(n) für alle n bewiesen haben, sind wir
natürlich auch noch nicht fertig.
natürlich auch noch nicht fertig.
Ernst Baumann
Feb 11, 2012, 4:46:17 PM2/11/12
to
>Dann hei=C3=9Ft es hier=
>
>Nachtrag: Nachdem wir C(n) fuer alle n bewiesen haben, sind wir
>natuerlich auch noch nicht fertig.
>
Was fehlt noch?
Was muss ich noch beweisen?
mfg
Ernst
>
>>
>> Nach IV existiert h: {0,...,n} -> X mit ...
>> Wir definieren nun g: {0,...,n+1} -> X durch ...
>>=20
>>
>> Nach IV existiert h: {0,...,n} -> X mit ...
>> Wir definieren nun g: {0,...,n+1} -> X durch ...
>> Also g statt f_{n+1}, h statt f_n.
>>=20
>
>Nachtrag: Nachdem wir C(n) fuer alle n bewiesen haben, sind wir
>natuerlich auch noch nicht fertig.
>
Was fehlt noch?
Was muss ich noch beweisen?
mfg
Ernst
Ernst Baumann
Feb 11, 2012, 4:46:15 PM2/11/12
to
>>>
>> Bei mir tauchen folgende mathematische "Skrupel" auf:
>> Du schreibst:
>> "Nach Voraussetzung existiert genau eine mathematische Funkton f_n".
>> Das n dient zur Nummerierung.
>> Aber dieser Ausdruck f_n ist doch eine Abkuerzung fuer f(n)
>
>Ja, wie ich geschrieben habe, war es ung=C3=BCnstig, die Funktion mit f_n=
>> Bei mir tauchen folgende mathematische "Skrupel" auf:
>> Du schreibst:
>> "Nach Voraussetzung existiert genau eine mathematische Funkton f_n".
>> Das n dient zur Nummerierung.
>> Aber dieser Ausdruck f_n ist doch eine Abkuerzung fuer f(n)
>
> zu
>bezeichnen, ich h=C3=A4tte g schreiben sollen. Dann hei=C3=9Ft es hier
>
> Nach IV existiert h: {0,...,n} -> X mit ...
> Wir definieren nun g: {0,...,n+1} -> X durch ...
>
>Also g statt f_{n+1}, h statt f_n.
>
Hallo Carsten,
> Nach IV existiert h: {0,...,n} -> X mit ...
> Wir definieren nun g: {0,...,n+1} -> X durch ...
>
>Also g statt f_{n+1}, h statt f_n.
>
Das mit f_{k+1} usw. (es soll ja erst gezeigt werden, dass f eine
Funktion ist) hat mich ziemlich verwirrt.
Deswegen war der Hinweis auf g und h sehr wertvoll fuer mich.
Trotzdem hat es Zeit gebraucht, bis mir klaren Gedanken in den Kopf
kamen.
Deswegen nochmals ein neuer Versuch mit der Bitte, mir meine
Denkfehler
zu benennen.
§1)
Definition
C(n):<==>
Es gibt genau eine Funktion f: {0,...,n} -> X mit
der folgenden Eigenschaft (E):
f(0) = a und
f(k+1) = V_{k+1}(f(0),...,f(k)) fuer alle 0 <= k < n.
Bemerkung:
Aus der Definition folgt, dass f von n abhaengt.
Satz:
Fuer alle n aus N gilt C(n)
Beweis des Satzes:
I) Eindeutigkeit
Beweis mit vollstaendiger Induktion.
1) Induktionsvoraussetzung C(0)
Annahme:
Es gilt: f1(0) = a und f2(0) = a
also f1(0) = f2(0)
2) Induktionsvoraussetzung C(n)
Zeige C(n+1)
Es gelte
f1(k+1) = V_{k+1}(f1(0),...,f1(k)) fuer alle 0 <= k < n+1
und
f2(k+1) = V_{k+1}(f2(0),...,f2(k)) fuer alle 0 <= k < n+1
Da nach der Induktionsvoraussetzung C(n) gilt:
f1(0) = f2(0) und ... und f1(n)=f2(n), folgt:
f1(k+1)=f2(k+1)
also:
f1(k)=f2(k) fuer 0<=k<=n+1
also: f1 = f2
II) Existenz:
Zeige Existenz:
1) Induktionsvoraussetzung C(0)
f = {(0,a)} ist eine Funktion mit der gewuenschten Eigenschaft
1) Induktionsvoraussetzung C(0)
2) Induktionsvoraussetzung C(n)
Zeige C(n+1)
h : {0, ..., n} --> X mit
h(0) = a und
h(k+1) = V_{k+1}(h(0),...,h(k)) fuer alle 0 <= k < n.
Nun definiere ich eine Funktion
g : {0, ..., n+1} --> X wie folgt:
g(k) := h(k) fuer k<=n
g(n+1) := V_{n+1}(h(0),...,h(n))
Diese hat folgende Eigenschaften:
a)
g(0) = h(0) = a, also g(0)=a
b)
Fall1: k<n
g(k+1) := h(k+1) = V_{k+1}(h(0),...,h(k)) = V_{n+1}(g(0),...,g(k))
also;
g(k+1) = V_{n+1}(g(0),...,g(k))
Fall2: k=n
g(k+1) := V_{n+1}(h(0),...,h(k)) = V_{n+1}(g(0),...,g(k))
also:
g(k+1) = V_{n+1}(g(0),...,g(k))
Fall1 und Fall2 zusammenfasst gilt:
g(k+1) = V_{n+1}(g(0),...,g(k))
Also gibt es eine Funktion (naemlich g)
g: {0,...,n+1} --> X mit der Eigenschaft E
§2)
Aus obiger Definition von C(n) und dem
Satz:
Fuer alle n aus N gilt C(n)
und der Definition von M
M = Vereinigung aller {0,....n} mit n aus N
folgt:
F : N--> [ Menge aller Abbildungen von M - >X ]
ist eine Abbildung mit Vorbereich von F(n) = {0,...,n}
und jedes F(n) hat die Eigenschaft (E)
(siehe oben).
mfg
Ernst
Carsten Schultz
Feb 12, 2012, 7:04:35 AM2/12/12
to
Am 11.02.12 22:46, schrieb Ernst Baumann:
Sieht alles gut aus.
> §2)
> Aus obiger Definition von C(n) und dem
> Satz:
> Fuer alle n aus N gilt C(n)
> und der Definition von M
> M = Vereinigung aller {0,....n} mit n aus N
>
> folgt:
> F : N--> [ Menge aller Abbildungen von M - >X ]
> ist eine Abbildung mit Vorbereich von F(n) = {0,...,n}
> und jedes F(n) hat die Eigenschaft (E)
> (siehe oben).
Irgendwo scheine ich die Definition von F verpasst zu haben. Das ist
aber vielleicht auch nicht so wichtig. Wichtig ist, jetzt ein
f: N -> X zu definieren, von dem wir zeigen können, dass es die
Eigenschaften aus dem Satz hat.
> §2)
> Aus obiger Definition von C(n) und dem
> Satz:
> Fuer alle n aus N gilt C(n)
> und der Definition von M
> M = Vereinigung aller {0,....n} mit n aus N
>
> folgt:
> F : N--> [ Menge aller Abbildungen von M - >X ]
> ist eine Abbildung mit Vorbereich von F(n) = {0,...,n}
> und jedes F(n) hat die Eigenschaft (E)
> (siehe oben).
aber vielleicht auch nicht so wichtig. Wichtig ist, jetzt ein
f: N -> X zu definieren, von dem wir zeigen können, dass es die
Eigenschaften aus dem Satz hat.
Ernst Baumann
Feb 12, 2012, 1:18:01 PM2/12/12
to
>
>> =C2=A72)
>> Aus obiger Definition von C(n) und dem=20
Ich aendere den von dir aufgestellten Satz etwas ab
(so dass sich das metasprachlich Symbol C(n) nicht
mehr in der Formulierung befindet).
Stimmt das alles, bzw. wo sind meine Denkfehler?
I) Satz (neue Formulierung):
Fuer alle n aus N gibt es genau eine Funktion
Es existiert genau eine Abbildung
Definiere:
H := U F(n) := Vereinigung aller F(n), wobei alle n aus N
Unterbehauptung1:
H : N --> X
ist eine Abbildung.
Beweis:
Es sei
(k,x1) aus H und (k,x2) aus H
Zeige x1=x2
Es sei
(k,x1) aus H ==> (k,x1) aus U F(n) ==>
(k,x1) aus F(k) oder
(k,x1) aus F(k+1) oder
(k,x1) aus F(k+2) oder
...
also
F(k)(k)=x1 oder
F(k+1)(k)=x1 oder
F(k+2)(k)=x1 oder
...
Da aber gilt:
F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x1
folgt:
F(k)(k)=x1 (G1)
Es sei
(k,x2) aus H ==> (k,x2) aus U F(n) ==>
(k,x2) aus F(k) oder
(k,x2) aus F(k+1) oder
(k,x2) aus F(k+2) oder
...
also
F(k)(k)=x2 oder
F(k+1)(k)=x2 oder
F(k+2)(k)=x2 oder
...
Da aber gilt:
F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x2
folgt:
F(k)(k)=x2 (G2)
Aus (G1) und (G2) folgt
x1=x2
Unterbehauptung2
n aus N ==> F(n)(n) = H(n)
Beweis:
Damit der Term F(n)(n) = H(n) ein wohlgeformtes
mathematisches Objekt ist, muss es ein
x aus X geben mit
F(n)(n)=x
also
(n,x) Element F(n)
Da F(n) Teilmenge H ist, gilt:
(n,x) Element H
also
x = H(n)
Damit:
F(n)(n)=x=H(n)
also
F(n)(n) = H(n)
Unterbehauptung3:
H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
Beweis:
H(n+1) = F(n+1)(n+1) = V_{n+1}(F(n)(0),...,F(n)(n))
Da gilt:
F(n)(0) = F(n-1)(0) = ... = F(0)(0) = H(0)
F(n)(1) = F(n-1)(1) = ... = F(1)(1) = H(1)
...
F(n)(n-1) = F(n-1)(n-1) = H(n-1)
F(n)(n) = H(n)
gilt:
H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
qed
mfg
Ernst
>> =C2=A72)
>> Aus obiger Definition von C(n) und dem=20
>> Satz:
>> Fuer alle n aus N gilt C(n)
>> und der Definition von M
>> Fuer alle n aus N gilt C(n)
>> und der Definition von M
>> = Vereinigung aller {0,....n} mit n aus N
>>
>> folgt:
>> F : N--> [ Menge aller Abbildungen von M - >X ]
>> ist eine Abbildung mit Vorbereich von F(n) =3D {0,...,n}
>>
>> folgt:
>> F : N--> [ Menge aller Abbildungen von M - >X ]
>> und jedes F(n) hat die Eigenschaft (E)
>> (siehe oben).
>
>Irgendwo scheine ich die Definition von F verpasst zu haben.
>
>Das ist
>aber vielleicht auch nicht so wichtig. Wichtig ist, jetzt ein
>f: N -> X zu definieren, von dem wir zeigen k=C3=B6nnen, dass es die
>> (siehe oben).
>
>Irgendwo scheine ich die Definition von F verpasst zu haben.
>
>Das ist
>aber vielleicht auch nicht so wichtig. Wichtig ist, jetzt ein
>Eigenschaften aus dem Satz hat.
>
Ich habe F nicht sauber definiert (wird gleich nachgeliefert):
>
Ich aendere den von dir aufgestellten Satz etwas ab
(so dass sich das metasprachlich Symbol C(n) nicht
mehr in der Formulierung befindet).
Stimmt das alles, bzw. wo sind meine Denkfehler?
I) Satz (neue Formulierung):
Fuer alle n aus N gibt es genau eine Funktion
f: {0,...,n} -> X mit
der folgenden Eigenschaft (E):
f(0) = a und
f(k+1) = V_{k+1}(f(0),...,f(k)) fuer alle 0 <= k < n.
Definition:
der folgenden Eigenschaft (E):
f(0) = a und
f(k+1) = V_{k+1}(f(0),...,f(k)) fuer alle 0 <= k < n.
M = Vereinigung aller {0,....n} mit n aus N
II) Folgerung:
Es existiert genau eine Abbildung
F : N--> [ Menge aller Abbildungen von M - > X ]
mit Vorbereich von F(n) = {0,...,n}
und jedes F(n) hat die Eigenschaft (E)
(siehe oben).
III) Rekursionssatz
und jedes F(n) hat die Eigenschaft (E)
(siehe oben).
Voraussetzung:
X != {} und a aus X und N := {0;1;2, ...}
Fuer alle n aus N gilt V_n : X^n --> X ist eine Abbildung.
Behauptung:
Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
f(0) = a und
f(n+1) = V_{n+1}(f(0), ..., f(n)) fuer n aus N
Beweis:
X != {} und a aus X und N := {0;1;2, ...}
Fuer alle n aus N gilt V_n : X^n --> X ist eine Abbildung.
Behauptung:
Es existiert eine eindeutig bestimmte Abbildung f: N --> X mit:
f(0) = a und
f(n+1) = V_{n+1}(f(0), ..., f(n)) fuer n aus N
Definiere:
H := U F(n) := Vereinigung aller F(n), wobei alle n aus N
Unterbehauptung1:
H : N --> X
ist eine Abbildung.
Beweis:
Es sei
(k,x1) aus H und (k,x2) aus H
Zeige x1=x2
Es sei
(k,x1) aus H ==> (k,x1) aus U F(n) ==>
(k,x1) aus F(k) oder
(k,x1) aus F(k+1) oder
(k,x1) aus F(k+2) oder
...
also
F(k)(k)=x1 oder
F(k+1)(k)=x1 oder
F(k+2)(k)=x1 oder
...
Da aber gilt:
F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x1
folgt:
F(k)(k)=x1 (G1)
Es sei
(k,x2) aus H ==> (k,x2) aus U F(n) ==>
(k,x2) aus F(k) oder
(k,x2) aus F(k+1) oder
(k,x2) aus F(k+2) oder
...
also
F(k)(k)=x2 oder
F(k+1)(k)=x2 oder
F(k+2)(k)=x2 oder
...
Da aber gilt:
F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x2
folgt:
F(k)(k)=x2 (G2)
Aus (G1) und (G2) folgt
x1=x2
Unterbehauptung2
n aus N ==> F(n)(n) = H(n)
Beweis:
Damit der Term F(n)(n) = H(n) ein wohlgeformtes
mathematisches Objekt ist, muss es ein
x aus X geben mit
F(n)(n)=x
also
(n,x) Element F(n)
Da F(n) Teilmenge H ist, gilt:
(n,x) Element H
also
x = H(n)
Damit:
F(n)(n)=x=H(n)
also
F(n)(n) = H(n)
Unterbehauptung3:
H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
Beweis:
H(n+1) = F(n+1)(n+1) = V_{n+1}(F(n)(0),...,F(n)(n))
Da gilt:
F(n)(0) = F(n-1)(0) = ... = F(0)(0) = H(0)
F(n)(1) = F(n-1)(1) = ... = F(1)(1) = H(1)
...
F(n)(n-1) = F(n-1)(n-1) = H(n-1)
F(n)(n) = H(n)
gilt:
H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
qed
mfg
Ernst
Carsten Schultz
Feb 13, 2012, 4:16:37 AM2/13/12
to
Am 12.02.12 19:18, schrieb Ernst Baumann:
Du meinst wahrscheinlich „Menge aller“, nicht „Vereinigung aller“.
Ein Pünktchenbeweis ist hier nicht so angebracht, da wir ja gerade an
Grundlagen arbeiten. Besser wohl: Es existiert l1 >= k mit
x1=F(l1)(k).
> also
> F(k)(k)=x1 oder
> F(k+1)(k)=x1 oder
> F(k+2)(k)=x1 oder
> ...
> Da aber gilt:
> F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x1
Hierfür sollten wir uns auf die Eindeutigkeit in der Hilfsbehauptung
beziehen.
> folgt:
> F(k)(k)=x1 (G1)
>
> Es sei
> (k,x2) aus H ==> (k,x2) aus U F(n) ==>
> (k,x2) aus F(k) oder
> (k,x2) aus F(k+1) oder
> (k,x2) aus F(k+2) oder
> ...
> also
> F(k)(k)=x2 oder
> F(k+1)(k)=x2 oder
> F(k+2)(k)=x2 oder
> ...
> Da aber gilt:
> F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x2
> folgt:
> F(k)(k)=x2 (G2)
> Aus (G1) und (G2) folgt
> x1=x2
>
>
Ebenso existiert l2 >= k mit x2=F(l2)(k). Nun erfüllt aber die
Einschränkung von F(l1) bzw. F(l2) auf {0,...,k} auch die Bedingung E
ist also aufgrund der Eindeutigkeit gleich F(k). Also
x1 = F(l1)(k) = F(k)(k) = F(l2)(k) = x2.
Das sollte wieder mit Verweis auf die Eindeutigkeit begründet werden.
Daher solltest Du noch einmal nachschauen, ob Du daran gedacht hattest,
diese auch wirklich zu beweisen. Es ist möglich, dass Du das vergessen
hattest, weil Dir die Relevanz noch nicht klar war.
> gilt:
> H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
> qed
>
Im Grunde alles gut. Statt der Details finde ich wichtiger: Du
verstehst jetzt wahrscheinlich auch den Beweis bei Geschke. Wichtiger:
Du verstehst, wie man formal ausdrückt, dass sich Funktionen mit
Definitionsbereich N rekursiv definieren lassen. Deine ursprüngliche
Frage war ja, wie sich das verallgemeinert. Eine mögliche Antwort ist,
dass sich das gleich von N auf andere wohlgeordnete Mengen
verallgemeinert. Noch allgemeiner wären wohlfundierte Relationen,
http://en.wikipedia.org/wiki/Well-founded_relation Vielleicht kommen
die bei Geschke auch noch weiter hinten, ich habe nicht geschaut.
Grundlagen arbeiten. Besser wohl: Es existiert l1 >= k mit
x1=F(l1)(k).
> also
> F(k)(k)=x1 oder
> F(k+1)(k)=x1 oder
> F(k+2)(k)=x1 oder
> ...
> Da aber gilt:
> F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x1
beziehen.
> folgt:
> F(k)(k)=x1 (G1)
>
> Es sei
> (k,x2) aus H ==> (k,x2) aus U F(n) ==>
> (k,x2) aus F(k) oder
> (k,x2) aus F(k+1) oder
> (k,x2) aus F(k+2) oder
> ...
> also
> F(k)(k)=x2 oder
> F(k+1)(k)=x2 oder
> F(k+2)(k)=x2 oder
> ...
> Da aber gilt:
> F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x2
> folgt:
> F(k)(k)=x2 (G2)
> Aus (G1) und (G2) folgt
> x1=x2
>
>
Einschränkung von F(l1) bzw. F(l2) auf {0,...,k} auch die Bedingung E
ist also aufgrund der Eindeutigkeit gleich F(k). Also
x1 = F(l1)(k) = F(k)(k) = F(l2)(k) = x2.
Daher solltest Du noch einmal nachschauen, ob Du daran gedacht hattest,
diese auch wirklich zu beweisen. Es ist möglich, dass Du das vergessen
hattest, weil Dir die Relevanz noch nicht klar war.
> gilt:
> H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
> qed
>
verstehst jetzt wahrscheinlich auch den Beweis bei Geschke. Wichtiger:
Du verstehst, wie man formal ausdrückt, dass sich Funktionen mit
Definitionsbereich N rekursiv definieren lassen. Deine ursprüngliche
Frage war ja, wie sich das verallgemeinert. Eine mögliche Antwort ist,
dass sich das gleich von N auf andere wohlgeordnete Mengen
verallgemeinert. Noch allgemeiner wären wohlfundierte Relationen,
http://en.wikipedia.org/wiki/Well-founded_relation Vielleicht kommen
die bei Geschke auch noch weiter hinten, ich habe nicht geschaut.
Ernst Baumann
Feb 14, 2012, 1:39:11 PM2/14/12
to
I)
V_n nicht _echt_ von allen folgenden Parametern
x_0,...,x_{n-1}
abhaengen muss?
Meine Idee:
Voraussetzungen:
Fuer alle n aus N gilt G_n : X^n --> X ist eine Abbildung.
und es sei {i(0), i(1), i(2), ... , i(k(n)) }
mit k(n)<=n-1 eine Teilmenge von {0, ..., n-1}
wobei i(0), i(1), ..., i(k(n)) alle
jeweis verschieden sind.
Damit ist
{ x_{i(0)}, x_{i(1)}, ..., x_{i(k(n))} } eine Teilmenge von
{ x_0,...,x_{n-1} }
Mein Vorschlag:
V_n(x_0,...,x_{n-1}) :=
G_{k(n)+1}( x_{i(0)}, x_{i(1)}, ..., x_{i(k(n))} )
kann man
V_n(x_0,...,x_{n-1})
nicht von _allen_ diesen Parametern
x_0,...,x_{n-1}}
abhaengen lassen.
Ist mein Vorschlag korrekt?
II)
Wenn man einen mathematischen Satz formuliert,
folgt daraus, dass die darin enthaltenen Objekte
wohlgeformte, mathematische Objekte sind.
1.Beispiel:
Es genuegt den folgenden Satz zu formulieren:
x/y = (2x)/(2y)
Es ist nicht noetig Folgendes zu formulieren:
y != 0 ==> x/y = (2x)/(2y)
2.Beispiel:
Es genuegt den folgenden Satz zu formulieren:
Satz (Eindeutigkeitslemma):
n aus N und m aus N und k aus N ==>
F(n)(k) = F(k)(K)
Es ist nicht noetig Folgendes zu formulieren:
n aus N und m aus N und k aus N und k<=n und k<=m ==>
F(n)(k) = F(k)(K)
Stimmen diese Ansichten von mir ?
mfg
Ernst
>
>Das geht doch mit
>V_n(x_0,...,x_{n-1}) = n - x_{p_1} + x_{p+2} - ... +- x_{p_r},
>
>wobei p_1 < ... < p_r die Primzahlen kleiner als n sind.
>
Wie kann man ganz _allgemein_ erreichen, dass die Funktion
>Das geht doch mit
>V_n(x_0,...,x_{n-1}) = n - x_{p_1} + x_{p+2} - ... +- x_{p_r},
>
>wobei p_1 < ... < p_r die Primzahlen kleiner als n sind.
>
V_n nicht _echt_ von allen folgenden Parametern
x_0,...,x_{n-1}
abhaengen muss?
Meine Idee:
Voraussetzungen:
Fuer alle n aus N gilt G_n : X^n --> X ist eine Abbildung.
und es sei {i(0), i(1), i(2), ... , i(k(n)) }
mit k(n)<=n-1 eine Teilmenge von {0, ..., n-1}
wobei i(0), i(1), ..., i(k(n)) alle
jeweis verschieden sind.
Damit ist
{ x_{i(0)}, x_{i(1)}, ..., x_{i(k(n))} } eine Teilmenge von
{ x_0,...,x_{n-1} }
Mein Vorschlag:
V_n(x_0,...,x_{n-1}) :=
G_{k(n)+1}( x_{i(0)}, x_{i(1)}, ..., x_{i(k(n))} )
kann man
V_n(x_0,...,x_{n-1})
nicht von _allen_ diesen Parametern
x_0,...,x_{n-1}}
abhaengen lassen.
Ist mein Vorschlag korrekt?
II)
Wenn man einen mathematischen Satz formuliert,
folgt daraus, dass die darin enthaltenen Objekte
wohlgeformte, mathematische Objekte sind.
1.Beispiel:
Es genuegt den folgenden Satz zu formulieren:
x/y = (2x)/(2y)
Es ist nicht noetig Folgendes zu formulieren:
y != 0 ==> x/y = (2x)/(2y)
2.Beispiel:
Es genuegt den folgenden Satz zu formulieren:
Satz (Eindeutigkeitslemma):
n aus N und m aus N und k aus N ==>
F(n)(k) = F(k)(K)
Es ist nicht noetig Folgendes zu formulieren:
n aus N und m aus N und k aus N und k<=n und k<=m ==>
F(n)(k) = F(k)(K)
Stimmen diese Ansichten von mir ?
mfg
Ernst
Ernst Baumann
Feb 14, 2012, 1:39:13 PM2/14/12
to
>> Stimmt das alles, bzw. wo sind meine Denkfehler?
>>
>> I) Satz (neue Formulierung):
>> Fuer alle n aus N gibt es genau eine Funktion
>> f: {0,...,n} -> X mit
>> der folgenden Eigenschaft (E):
>> f(0) = a und
>> f(k+1) = V_{k+1}(f(0),...,f(k)) fuer alle 0 <= k < n.
>>
Deine Kritikpunkte habe ich in diesem Posting verarbeitet
>>
>> I) Satz (neue Formulierung):
>> Fuer alle n aus N gibt es genau eine Funktion
>> f: {0,...,n} -> X mit
>> der folgenden Eigenschaft (E):
>> f(0) = a und
>> f(k+1) = V_{k+1}(f(0),...,f(k)) fuer alle 0 <= k < n.
>>
und gehe im Folgenden auf jeden der Punkte ein.
>
>> Definition:
>> M = Vereinigung aller {0,....n} mit n aus N
>
>Du meinst wahrscheinlich „Menge aller“, nicht „Vereinigung aller“.
>
M : = { {0,...,n} | n ist Element von N}
>da wir ja gerade an Grundlagen arbeiten.
>Besser wohl:
>Es existiert l1 >= k mit
>x1=F(l1)(k).
>
Du hast recht.
>Besser wohl:
>Es existiert l1 >= k mit
>x1=F(l1)(k).
>
Da du nachher noch das Fehlen des Arguments der
Eindeutigkeit kritisierst, bringe ich hier noch eine
weitere Unterbehauptung:
Satz (Eindeutigkeitslemma):
n aus N und m aus N und k aus N ==>
Beweis:
a) n=0 klar
b) sonst:
Es gilt:
F(n)(k) = V_k(F(n)(0), ..., F(n)(k-1)) fuer k<=n
und
F(m)(k) = V_k(F(m)(0), ..., F(m)(k-1)) fuer k<=m
Es sei obdA: m <= n
also gilt auch:
F(n)(k) = V_k(F(n)(0), ..., F(n)(k-1)) fuer k<=m
Da es laut der Hilfsbehauptung eine eindeutige Funktion
f auf {0, ..., m} gibt mit der folgenden Eigenschaft (E) :
f(k) = V_k(f(0), ..., f(k-1)) fuer k<=m
muss gelten:
f = F(n) = F(m) auf {0, ..., m}
da F(N) und F(m) auch die Eigenschaft (E) haben.
also gilt:
F(n)(k) = F(m)(k) fuer k<=m
w�hle m=k, dann gilt:
F(n)(k) = F(k)(k)
>>
>> also
>> F(k)(k)=x1 oder
>> F(k+1)(k)=x1 oder
>> F(k+2)(k)=x1 oder
>> ...
>> Da aber gilt:
>> F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x1
>>
>
>in der Hilfsbehauptung beziehen.
>
also so:
Es gilt einmal
x1=F(l1)(k)
und nach dem Eindeutigkeitslemma:
F(l1)(k) = F(k)(k), also:
x1 = F(l1)(k) = F(k)(k), also:
x1 = F(k)(k)
>>
>> folgt:
>> F(k)(k)=x1 (G1)
>>
>> Es sei
>> (k,x2) aus H ==> (k,x2) aus U F(n) ==>
>> (k,x2) aus F(k) oder
>> (k,x2) aus F(k+1) oder
>> (k,x2) aus F(k+2) oder
>> ...
>> also
>> F(k)(k)=x2 oder
>> F(k+1)(k)=x2 oder
>> F(k+2)(k)=x2 oder
>> ...
>> Da aber gilt:
>> F(k)(k)=F(k+1)(k)=F(k+2)(k)=...=x2
>> folgt:
>> F(k)(k)=x2 (G2)
>> Aus (G1) und (G2) folgt
>> x1=x2
>>
>>
>
>Ebenso existiert l2 >= k mit x2=F(l2)(k).
>bzw. F(l2) auf {0,...,k} auch die Bedingung E
>ist also aufgrund der Eindeutigkeit gleich F(k).
>Also
>x1 = F(l1)(k) = F(k)(k) = F(l2)(k) = x2.
>
Ich wuerde es analog wie oben machen:
>ist also aufgrund der Eindeutigkeit gleich F(k).
>Also
>x1 = F(l1)(k) = F(k)(k) = F(l2)(k) = x2.
>
Es existiert l2 >= k mit
x2=F(l2)(k)
Nach dem Eindeutigkeitslemma gilt aber auch:
F(l2)(k) = F(k)(k), also:
x2 = F(l2)(k) = F(k)(k), also:
x2 = F(k)(k)
Damit:
x2 = F(k)(k) = x1, also:
x2=x1
>nachschauen, ob Du daran gedacht hattest,
>diese auch wirklich zu beweisen. Es ist moeglich,
>dass Du das vergessen
>hattest, weil Dir die Relevanz noch nicht klar war.
>
Ich gehe davon aus, dass du die in deiner Hilfsbehauptung
>hattest, weil Dir die Relevanz noch nicht klar war.
>
verwendete Eindeutigkeit meinst.
Ich hatte diese Eindeutigkeit bewiesen, aber
leider nicht in dem Beweis hier verwendet.
Das will ich nachholen, indem ich das
Eindeutigkeitslemma verwende:
Unterbehauptung3:
H(n+1) = V_{n+1}(H(0), ..., H(n)) fuer n aus N
Beweis:
Aus dem Eindeutigkeitslemma folgt:
V_{n+1}(F(n+1)(0),...,F(n+1)(n)) =
V_{n+1}(F(0)(0),...,F(n)(n))
Mit Hilfe der Unterbehauptung2 folgt:
V_{n+1}(F(0)(0),...,F(n)(n)) =
V_{n+1}(H(0),...,H(n))
also insgesamt:
H(n+1) = V_{n+1}(H(0),...,H(n))
>
>Im Grunde alles gut. Statt der Details finde ich wichtiger:
>Du verstehst jetzt wahrscheinlich auch den Beweis bei Geschke.
>sich Funktionen mit Definitionsbereich N rekursiv definieren
>lassen. Deine urspruengliche Frage war ja, wie sich das
>verallgemeinert. Eine moegliche Antwort ist,
>dass sich das gleich von N auf andere wohlgeordnete Mengen
>verallgemeinert. Noch allgemeiner wären wohlfundierte Relationen,
>http://en.wikipedia.org/wiki/Well-founded_relation Vielleicht kommen
>die bei Geschke auch noch weiter hinten, ich habe nicht geschaut.
>
Den Rekursionssatz brauche ich, um beim Programmieren die Rekursion
>verallgemeinert. Noch allgemeiner wären wohlfundierte Relationen,
>http://en.wikipedia.org/wiki/Well-founded_relation Vielleicht kommen
>die bei Geschke auch noch weiter hinten, ich habe nicht geschaut.
>
zu rechtfertigen.
Dazu wird es wohl ausreichen, wohlgeordnete Mengen M zu verwenden,
fuer die jedes Element von M endlich viele Vorgaenger hat.
Ich vermute, dass so eine Menge M isomorph N (=Menge der natuerlichen
Zahlen) ist.
Stimmt das?
Nachttrag:
Aufgrund deiner Bemerkungen ist mir noch aufgefallen, dass
ich - im Gegensatz zum Eindeutigkeitsbeweis der Hilfsbehauptung - die
Eindeutigkeit des Rekursionssatzes noch nicht bewiesen habe.
Ich hole dies hier nach:
Es sei
f1: N -->X und
f1(0) = a
f1(n+1) = V_{n+1}(f1(0), ..., f1(n))
und
f2: N -->X und
f2(0) = a
f2(n+1) = V_{n+1}(f2(0), ..., f2(n))
Zeige: f1 = f2
d.h. Zeige
f1(n) = f2(n) fuer alle n aus N
Beweis:
Induktionsanfang:
aus f1(0)= a und f2(0)=a folgt:
f1(0)=f2(0)
Ind.Voraussetzung:
Es sei f1(i)=f2(i) fuer alle i<=n
Zeige: f1(n+1) = f2(n+1)
Es gilt:
f1(n+1)=V_{n+1}(f1(0), ..., f1(n))
und
f2(n+1)=V_{n+1}(f2(0), ..., f2(n))
Mit Hilfe der Ind. Vor. folgt daraus:
f1(n+1) = f2(n+1)
mfg
Ernst
0 new messages