Rechner-Arithmetik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Hier ist die fragestellung
http://www.informatik.uni-trier.de/~mueller/Lehre/2005-arith/arith-2004-folien-05-02-17.pdf
folie 49 da steht man kann das per induktion zeigen aber ich schnall das nicht.
Jedes ( · ) r ist surjektiv, dazu induktiver Beweis von
2.4 Lemma.
Für alle r > 1 und k ∈ N gilt:
{ (w) r | w ∈ Σ k
r } = { 0, . . . , r ^k − 1 } |
Hi , Ich weiss leider nicht genau wie ich das schreieben soll!
also ich bin gerade am lernen für ne mündliche prüfung und ich stelle fest das ich nicht ma den beweis vom anfang hin bekommen würde.
Kann mir da wer auf die sprünge helfen oder mir sagen wie ich da an die sache dran gehe?
Danke schon mal vorher
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:56 So 18.04.2010 | | Autor: | felixf |
Hallo!
> Hier ist die fragestellung
> http://www.informatik.uni-trier.de/~mueller/Lehre/2005-arith/arith-2004-folien-05-02-17.pdf
>
> folie 49 da steht man kann das per induktion zeigen aber
> ich schnall das nicht.
>
> Jedes ( · ) r ist surjektiv, dazu induktiver Beweis von
> 2.4 Lemma.
> Für alle r > 1 und k ∈ N gilt:
> { (w) r | w ∈ Σ k
> r } = { 0, . . . , r ^k − 1 }
Das ist nicht sehr leserlich. Du haettest auch wenigstens dabeischreiben koennen, das die einzelnden Objekte bedeuten sollen.
> also ich bin gerade am lernen für ne mündliche prüfung
> und ich stelle fest das ich nicht ma den beweis vom anfang
> hin bekommen würde.
>
> Kann mir da wer auf die sprünge helfen oder mir sagen wie
> ich da an die sache dran gehe?
Du machst vollstaendige Induktion nach $k$.
Im Induktionsschritt machst du eine Division mit Rest, indem du ein Element $x$ aus [mm] $\{ 0, \dots, r^{k+1} - 1 \}$ [/mm] durch $r$ teilst: dann bekommst du Zahlen $a, b [mm] \in \IN$ [/mm] mit $x = a r + b$ und $0 [mm] \le [/mm] b < r$. Jetzt muss $0 [mm] \le [/mm] a [mm] \le r^k [/mm] - 1$ sein (warum?). Wende auf $a$ die Induktionsvoraussetzung an.
LG Felix
|
|
|
|
