Sind rekursive Folgen und Funktionen sauber definiert?

30/03/2008 - 11:42 von Ernst Baumann | Report spam
Hallo allerseits,
Gebilde wie Terme und Formeln _muss_ man als induktive Mengen (mit
Hilfe einer Regelmenge) bilden, wenn man dies korrekt machen will.
Siehe (Kapitel über induktive Definitionen)
http://wwwcs.upb.de/cs/kindler/Lehr...pitel4.pdf


Beispiel einer induktiv definierten Menge

{}

3

{}

5

r, s sind natürliche Zahlen (>=1) mit r!=s
{r ; s}

r + s

D0 := {3 ; 5}
D1 := {3 ; 5 ; 8}
D2 =: {3 ; 5 ; 8 ; 11 , 13}
...

Damit hat man eine sauber definierte Menge I(R)
I(R) = D0 u D1 u D2 u ...
I(R) = {3 ; 5 ; 8 ; 11 , 13, ...}


1)
Frage:
Sind dann _rekursiv definierte Folgen_ (n ist eine _ganze_ Zahl) wie
z.B:
a(0) = 4
a(n) = a(n-5) * 2
überhaupt sauber definiert, oder braucht man dazu auch eine induktiv
definierte Menge?

2)
Sind _rekursiv definierte Funktionen_ (siehe Beispiel unten) sauber
definiert oder braucht man dazu auch eine induktiv definierte Menge?

Beispiel:
Sei W eine Teilmenge der natürlichen Zahlen.
Ein Vorgànger V von W sei eine Teilmenge der natürlichen Zahlen, so
dass für jedes w Element von W gilt:

a) Vorgànger von 3 ist {}
b) Vorgànger von 5 ist {}
c) Es existieren natürliche Zahlen (>=1) n und m und n != m mit
w = n + m

z.B:
W = {13 , 17}
V1 = {8, 5 ; 10 , 7} ist ein Vorgànger von W
V2 = {9, 4 ; 11 , 6} ist ein Vorgànger von W

Definiere folgende _rekursive Funktion_
D1) t({}) = 1
D2) t(W) = 0, wenn kein Vorgànger existiert.
D3) t(W) = max {t(V)} mit V Vorgànger von W

Ist diese Definition korrekt?


mfg
Ernst
 

Lesen sie die antworten

#1 Jannick Asmus
28/04/2008 - 07:48 | Warnen spam
On 30.03.2008 11:42, Ernst Baumann wrote:
Hallo allerseits,
Gebilde wie Terme und Formeln _muss_ man als induktive Mengen (mit
Hilfe einer Regelmenge) bilden, wenn man dies korrekt machen will.
Siehe (Kapitel über induktive Definitionen)
http://wwwcs.upb.de/cs/kindler/Lehr...pitel4.pdf


Beispiel einer induktiv definierten Menge

{}

3



Leider ist mir diese Symbolik nicht klar. :-(

{}

5

r, s sind natürliche Zahlen (>=1) mit r!=s
{r ; s}

r + s

D0 := {3 ; 5}
D1 := {3 ; 5 ; 8}
D2 =: {3 ; 5 ; 8 ; 11 , 13}



Mal Semikolon, mal Komma. Ich nehme an, dass dies in der üblichen
Notation immer als Komma gemeint ist.

...



Ich denke dass es gerade hierum geht, nàmlich um diese Pünktchen, die
man schnell so hinschreibt.

Bei der vollstàndigen Induktion wird die *Existenz* einer Funktion mit
dem Definitionsbereich N und einem vorher vorgegebenen Wertebereich WW
mit vorgegebener Selbstabbildung f_WW: WW -> WW gesichert, die die
entsprechenden Eigenschaften (Induktionsanfang und Induktionsschluss)
hat. Die Eindeutigkeit einer solchen Funktion ist aber ein kleineres
(mengentheoretisches) Problem.

Damit hat man eine sauber definierte Menge I(R)
I(R) = D0 u D1 u D2 u ...
I(R) = {3 ; 5 ; 8 ; 11 , 13, ...}


1)
Frage:
Sind dann _rekursiv definierte Folgen_ (n ist eine _ganze_ Zahl) wie
z.B:
a(0) = 4
a(n) = a(n-5) * 2
überhaupt sauber definiert, oder braucht man dazu auch eine induktiv
definierte Menge?



Im Grundsatz ja,denn eine Funktion a: N -> N _ist_ eine Teilmenge von N
x N mit gewissen Eigenschaften. Das "Prinzip der vollstàndigen
Induktion" sichert - wie oben schon gesagt - die Existenz einer solchen
Menge. Und zwar eine Funktion mit Definitionsbereich *N* - und nicht
kleiner! Das kann man durch endlich viele Konstruktionsschritte nicht
gewàhrleisten.

Der /Umweg/, dass man eine Funktion als Teilmenge des Kreuzproduktes
auffasst, wird aber in dem Beweis des "Prinzip der vollstàndigen
Induktion" so durchgeführt. (Natürlich ist dies über die Definition
einer Funktion in der Mengentheorie.). Danach kann man es so salopp wie
in der Schule halten, sofern man natürlich die Voraussetzungen überprüft
hat.

2)
Sind _rekursiv definierte Funktionen_ (siehe Beispiel unten) sauber
definiert oder braucht man dazu auch eine induktiv definierte Menge?

Beispiel:
Sei W eine Teilmenge der natürlichen Zahlen.
Ein Vorgànger V von W sei eine Teilmenge der natürlichen Zahlen, so
dass für jedes w Element von W gilt:

a) Vorgànger von 3 ist {}
b) Vorgànger von 5 ist {}
c) Es existieren natürliche Zahlen (>=1) n und m und n != m mit
w = n + m



Ok, dies soll dann eine Relation auf der Menge der Potenzmengen von N sein.

Dabei ist (c) àquivalent damit, dass w>2 ist. Oder sollen m,n vielleicht
in V enthalten sein? Aber ich lese einfach mal weiter und nehme an, dass
(c) so gemeint ist wie es da steht.

Außerdem nehme ich an, dass Du N als kleinste Menge auffasst, die (1)
die leere Menge 0={} enthàlt und (2) die mit jedem Element n auch der
Nachfolger n+:=n u {n} in N enthàlt. (Die Existenz mindestens _einer_
solchen Menge wird von der Mengentheorie gefordert, daher gibt es dann
auch eine kleinste - nàmlich den Schnitt über all diese.) Das Ganze
mache ich, damit ich die Bedingungen (a) und (b) interpretieren kann.

z.B:
W = {13 , 17}
V1 = {8, 5 ; 10 , 7} ist ein Vorgànger von W
V2 = {9, 4 ; 11 , 6} ist ein Vorgànger von W



... wenn ich das so lese, könnte man auch denken, dass Du unter
Bedingung (c) doch sagen möchtest:

(c') Es existieren verschiedene natürliche Zahlen (>=1) n und m in V mit
w=m+n.

... und über das "Interpunktionsproblem" habe ich ja schon oben etwas
geschrieben. ;)

Definiere folgende _rekursive Funktion_



Folgende Fragen - bevor ich weiterlese (ich habe noch nicht nach unten
gescrollt):

- Definitionsbereich der Funktion?
- Wertebereich der Funktion?
- Selbstabbildung auf dem Wertebereich?

D1) t({}) = 1
D2) t(W) = 0, wenn kein Vorgànger existiert.
D3) t(W) = max {t(V)} mit V Vorgànger von W

Ist diese Definition korrekt?



Hmm, ich warte mal Deine Antworten auf meine drei Fragen oben ab. ;)

mfg
Ernst



Ich hoffe, dass dies hilfreich sein kann. Ich bin auf Deine Antwort
gespannt. :-)

Best wishes,
J.

Ähnliche fragen