Rekursive Definition < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:11 Do 28.03.2013 | | Autor: | Labrinth |
Guten Tag,
ich würde gerne das Prinzip der rekursiven Definition rechtfertigen. Sehe ich es richtig, dass es durch folgenden Satz beschrieben wird:
Satz:Es sei $A$ eine nichtleere Menge mit [mm] $a\in [/mm] A$ und [mm] $f\colon A\longrightarrow [/mm] A$ eine Abbildung. Dann existiert eine eindeutig bestimmte Abbildung [mm] $r\colon\mathbb{N}\longrightarrow [/mm] A$ mit den Eigenschaften:
[mm] [quote]$(\alpha)$ [/mm] $r(0)=a$,
[mm] $(\beta)$ [/mm] für alle [mm] $n\in\mathbb{N}$ [/mm] gilt [mm] $r\bigl(\sigma(n)\bigr)=f\bigl(r(n)\bigr).$[/quote]
[/mm]
Falls das stimmt, würde ich den gerne beweisen, durch Induktion natürlich. Dann bräuchte ich eine Menge $N$, die Menge derjenigen [mm] $n\in\mathbb{N}$, [/mm] denen auf diese Weise ein eindeutig bestimmtes Element [mm] $r(n)\in [/mm] A$ zugeordnet wird, um die Existenz einer solchen Abbildung zu zeigen. Das sollte eigentlich einfach sein, aber ich komme im Moment nicht darauf, wie ich die Menge $N$ exakt definieren kann, sozusagen in mathematischer Zeichensprache.
Die Eindeutigkeit sollte danach wieder recht einfach sein.
Beste Grüße,
Labrinth
P.S.: [mm] $\sigma\colon\mathbb{N}\longrightarrow\mathbb{N}$ [/mm] ist meine Sukzessor-Abbildung.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:22 Do 28.03.2013 | | Autor: | fred97 |
> Guten Tag,
>
> ich würde gerne das Prinzip der rekursiven Definition
> rechtfertigen. Sehe ich es richtig, dass es durch folgenden
> Satz beschrieben wird:
>
>
> Satz:Es sei [mm]A[/mm] eine nichtleere Menge mit [mm]a\in A[/mm] und [mm]f\colon A\longrightarrow A[/mm]
> eine Abbildung. Dann existiert eine eindeutig bestimmte
> Abbildung [mm]r\colon\mathbb{N}\longrightarrow A[/mm] mit den
> Eigenschaften:
> [mm](\alpha)[/mm] [mm]r(0)=a[/mm],
> [mm](\beta)[/mm] für alle [mm]n\in\mathbb{N}[/mm] gilt
> [mm]r\bigl(\sigma(n)\bigr)=f\bigl(r(n)\bigr).[/mm]
>
> Falls das stimmt, würde ich den gerne beweisen, durch
> Induktion natürlich. Dann bräuchte ich eine Menge [mm]N[/mm], die
> Menge derjenigen [mm]n\in\mathbb{N}[/mm], denen auf diese Weise ein
> eindeutig bestimmtes Element [mm]r(n)\in A[/mm] zugeordnet wird, um
> die Existenz einer solchen Abbildung zu zeigen. Das sollte
> eigentlich einfach sein, aber ich komme im Moment nicht
> darauf, wie ich die Menge [mm]N[/mm] exakt definieren kann,
> sozusagen in mathematischer Zeichensprache.
> Die Eindeutigkeit sollte danach wieder recht einfach
> sein.
ich verstehe Dein Problem nicht.
ich sehe das so: ist [mm] f_n [/mm] die n-fache Hintereinanderausführung von f, so kommt für r nur in Frage:
[mm] r(n)=f_n(a)
[/mm]
FRED
>
>
> Beste Grüße,
> Labrinth
>
> P.S.: [mm]\sigma\colon\mathbb{N}\longrightarrow\mathbb{N}[/mm] ist
> meine Sukzessor-Abbildung.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:31 Do 28.03.2013 | | Autor: | Labrinth |
> > Guten Tag,
> >
> > ich würde gerne das Prinzip der rekursiven Definition
> > rechtfertigen. Sehe ich es richtig, dass es durch folgenden
> > Satz beschrieben wird:
> >
> >
> > Satz:Es sei [mm]A[/mm] eine nichtleere Menge mit [mm]a\in A[/mm] und [mm]f\colon A\longrightarrow A[/mm]
> > eine Abbildung. Dann existiert eine eindeutig bestimmte
> > Abbildung [mm]r\colon\mathbb{N}\longrightarrow A[/mm] mit den
> > Eigenschaften:
> > [mm](\alpha)[/mm] [mm]r(0)=a[/mm],
> > [mm](\beta)[/mm] für alle [mm]n\in\mathbb{N}[/mm] gilt
> > [mm]r\bigl(\sigma(n)\bigr)=f\bigl(r(n)\bigr).[/mm]
> >
> > Falls das stimmt, würde ich den gerne beweisen, durch
> > Induktion natürlich. Dann bräuchte ich eine Menge [mm]N[/mm], die
> > Menge derjenigen [mm]n\in\mathbb{N}[/mm], denen auf diese Weise ein
> > eindeutig bestimmtes Element [mm]r(n)\in A[/mm] zugeordnet wird, um
> > die Existenz einer solchen Abbildung zu zeigen. Das sollte
> > eigentlich einfach sein, aber ich komme im Moment nicht
> > darauf, wie ich die Menge [mm]N[/mm] exakt definieren kann,
> > sozusagen in mathematischer Zeichensprache.
> > Die Eindeutigkeit sollte danach wieder recht einfach
> > sein.
>
>
>
> ich verstehe Dein Problem nicht.
>
> ich sehe das so: ist [mm]f_n[/mm] die n-fache
> Hintereinanderausführung von f, so kommt für r nur in
> Frage:
>
> [mm]r(n)=f_n(a)[/mm]
Habe ich da nicht schon Gebrauch vom zum beweisenden Prinzip der rekursiven Definition gemacht? Bzw. Habe ich richtig verstanden: Du willst sagen:
Sei [mm] $f_n$ [/mm] für [mm] $n\ge [/mm] 1$ die $n$-fache Hintereinanderschaltung von $f$. Dann erfüllt [mm] $f_n$ [/mm] die Eigenschaften [mm] $(\alpha)$ [/mm] und [mm] $(\beta)$.
[/mm]
Natürlich kann ich explizit sagen:
Sei [mm] f_0:=r [/mm] und [mm] $f_{n+1}:=f\circ f_n$ [/mm] für [mm] $n\in\mathbb{N}$. [/mm] Aber wie beweise ich, dass diese Abbildung eindeutig definiert ist?
> FRED
> >
> >
> > Beste Grüße,
> > Labrinth
> >
> > P.S.: [mm]\sigma\colon\mathbb{N}\longrightarrow\mathbb{N}[/mm] ist
> > meine Sukzessor-Abbildung.
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:48 Do 28.03.2013 | | Autor: | tobit09 |
Hallo Labyrinth,
du sprichst ein aus meiner Sicht sehr berechtigtes Problem an, dass häufig übergangen wird, nämlich das der Rechtfertigung rekursiver Definitionen.
Gerne wird einfach gesagt, nach Induktionsprinzip sei dadurch eine eindeutig bestimmte Abbildung definiert. Aber ganz so einfach ist die Situation nicht. Lediglich die Eindeutigkeit einer Abbildung mit den gewünschten Eigenschaften lässt sich leicht mittels Induktion zeigen. Die Existenz ist schwieriger.
> > ich sehe das so: ist [mm]f_n[/mm] die n-fache
> > Hintereinanderausführung von f, so kommt für r nur in
> > Frage:
> >
> > [mm]r(n)=f_n(a)[/mm]
>
> Habe ich da nicht schon Gebrauch vom zum beweisenden
> Prinzip der rekursiven Definition gemacht?
Haargenau! Um die n-fache Hintereinanderausführung von f exakt zu definieren, benötigt man das Prinzip der rekursiven Definition.
> Natürlich kann ich explizit sagen:
>
> Sei [mm]f_0:=r[/mm] und [mm]f_{n+1}:=f\circ f_n[/mm] für [mm]n\in\mathbb{N}[/mm].
[mm] $f_0:=\operatorname{id}_A$ [/mm] meinst du sicherlich.
> Aber wie beweise ich, dass diese Abbildung eindeutig
> definiert ist?
Fraglich ist also hier die Existenz und Eindeutigkeit einer Abbildung [mm] $h\colon\IN\to\{g\colon A\to A\}$ [/mm] mit [mm] $h(0)=id_A$ [/mm] und [mm] $h(n+1)=f\circ [/mm] (h(n))$. Die Eindeutigkeit ist auch hier weniger das Problem als die Existenz. Beide folgen aus deinem Satz.
Aber beweisen wir nun deinen Satz:
> > Satz:Es sei [mm]A[/mm] eine nichtleere Menge mit [mm]a\in A[/mm] und [mm]f\colon A\longrightarrow A[/mm]
> > eine Abbildung. Dann existiert eine eindeutig bestimmte
> > Abbildung [mm]r\colon\mathbb{N}\longrightarrow A[/mm] mit den
> > Eigenschaften:
> > [mm](\alpha)[/mm] [mm]r(0)=a[/mm],
> > [mm](\beta)[/mm] für alle [mm]n\in\mathbb{N}[/mm] gilt
> > [mm]r\bigl(\sigma(n)\bigr)=f\bigl(r(n)\bigr).[/mm]
Zunächst die einfachere Eindeutigkeitsaussage:
Seien r und r' Abbildungen, die beide den Eigenschaften [mm] $(\alpha)$ [/mm] und [mm] $(\beta)$ [/mm] genügen. Zu zeigen ist r=r', d.h. $r(n)=r'(n)$. Zeige dies per Induktion nach n.
Nun zur spannenden Existenzaussage:
Sei [mm] $M:=\{(N,s)|\;N\subseteq\IN,s\colon N\to A,0\in N,s(0)=a,\forall n\in\IN(\sigma(n)\in N\Rightarrow (n\in N\wedge s(\sigma(n))=f(s(n))))\}$.
[/mm]
Zeige per Induktion nach n:
(1) Für alle [mm] $n\in\IN$ [/mm] existiert ein [mm] $(N,s)\in [/mm] M$ mit [mm] $n\in [/mm] N$.
Weitere Behauptung:
(2) Für alle [mm] $(N,s),(N',s')\in [/mm] M$ gilt $s(n)=s'(n)$ für alle [mm] $n\in N\cap [/mm] N'$.
Zeige dazu per Induktion nach n: Für alle [mm] $n\in\IN$ [/mm] gilt die Folgerung
[mm] $n\in N\cap N'\quad\Rightarrow\quad [/mm] s(n)=s'(n)$.
Sei nun
[mm] $r\colon\IN\to A,\quad n\mapsto s(n)\text{ für ein }(N,s)\in M\text{ mit }n\in [/mm] N$.
Diese Abbildung ist wohldefiniert nach (1) und (2).
Zeige nun die krönende Abschlussbehauptung:
(3) r genügt den Eigenschaften [mm] $(\alpha)$ [/mm] und [mm] $(\beta)$.
[/mm]
Übrigens lässt sich der Satz noch auf verschiedene Weisen verallgemeinern: Man könnte z.B. auch solche rekursiven Definitionen zulassen, bei denen der Funktionswert $r(n+1)$ nicht nur von $r(n)$ abhängt, sondern von allen [mm] $r(0),\ldots,r(n)$ [/mm] und zusätzlich von $n$. Auch tauchen in der Praxis häufig rekursive Konstruktionen auf, bei denen in jedem Schritt eine Wahl zu treffen ist (wobei dann natürlich nur noch die Existenz und nicht mehr die Eindeutigkeit einer solchen Abbildung gegeben ist).
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:56 Do 28.03.2013 | | Autor: | Labrinth |
> Sei [mm]M:=\{(N,s)|\;N\subseteq\IN,s\colon N\to A,0\in N,s(0)=a,\forall n\in\IN(\sigma(n)\in N\Rightarrow (n\in N\wedge s(\sigma(n))=s(n)))\}[/mm].
Das ist, wonach ich gesucht habe. Ich werde mich jetzt daran versuchen. Ich kenne übrigens ![[]](/images/popup.gif) diesen Beweis (Seite 43,44), wo aber in Schritt (b) geschickt die Menge [mm] $\{1,\dots,n\}$ [/mm] verwendet wird, die man wohl kaum anders, als durch Rekursion erhält.
Danke übrigens 
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:35 Do 28.03.2013 | | Autor: | Labrinth |
Hall nochmal,
Sehe ich es richtig, dass es heißen muss:
> Sei [mm]M:=\{(N,s)|\;N\subseteq\IN,s\colon N\to A,0\in N,s(0)=a,\forall n\in\IN(\sigma(n)\in N\Rightarrow (n\in N\wedge s(\sigma(n))=\red{f(}s(n)\red{)}))\}[/mm].
Ich bin mir eigentlich recht sicher, aber das ist schon recht kompliziert für mich, da würde ich lieber nachfragen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:57 Do 28.03.2013 | | Autor: | tobit09 |
> Sehe ich es richtig, dass es heißen muss:
>
> > Sei [mm]M:=\{(N,s)|\;N\subseteq\IN,s\colon N\to A,0\in N,s(0)=a,\forall n\in\IN(\sigma(n)\in N\Rightarrow (n\in N\wedge s(\sigma(n))=\red{f(}s(n)\red{)}))\}[/mm].
Du hast völlig recht; danke für den Hinweis! ![[ok]](/images/smileys/ok.gif "[ok]")
Ich habe es gerade korrigiert. Sorry für die Verwirrung.
|
|
|
|
