Aufgabe:
Betrachten Sie die Funktion
f : N+ → N+, x →
x/2 , falls x gerade
3x + 1, falls x ungerade
Für n ∈ N definieren wir die n-te Iteration
f^n : N+ → N+ von f folgendermaßen:
(f0)(x) := x, , (f^2)(x) := f(f(x)), f^3(x) := f(f(f(x))) usw. für alle x ∈ N+
(c) Zeigen Sie, dass
C := {(x, y) ∈ N2x | ∃n ∈ N : y = fn(x)} ⊆ N2x
eine reflexive und transitive Relation mit der Eigenschaft Γf ⊆ C ist.
Hinweis: Sie dürfen ohne Beweis verwenden, dass fn(fm(x))=fn+m(x) für alle, m ∈ N und alle x ∈ N+ gilt.
