54 2 Verfugbarkeit von Aussagen
Definition 2-6. Passende Folgen naturlicher Zahlen fur Teilmengen von Sequenzen
g ist eine passende Folge naturlicher Zahlen fur a
gdw
Es gibt ein A ∈ SEQ, so dass a ⊆ A und g eine streng monoton wachsende Folge naturlicher
Zahlen mit Ran(g) = Dom(a) ist.
Zweck der Definition ist es zunachst, die Elemente (des Definitionsbereichs) einer Teil-
menge einer Sequenz unter Wahrung der naturlichen Ordnung aufzahlen zu konnen. So-
dann konnen passende Folgen dazu verwendet werden, um aus Abschnitten von Sequen-
zen Sequenzen zu machen, indem man den Abschnitt mit einer zu ihm passenden Folge
naturlicher Zahlen verknupft. In gewisser Weise handelt es sich also um eine Umkehrope-
ration zur Folgenverkettung.
Theorem 2-10. Existenz passender Folgen naturlicher Zahlen
Wenn A ∈ SEQ und a ⊆ A, dann gibt es ein g, so dass g eine passende Folge naturlicher Zah-
len fur a ist.
Beweis: Sei A ∈ SEQ und a ⊆ A. Der Beweis wird induktiv uber die Machtigkeit von a
gefuhrt. Sei ∣a∣ = 0. Sei g = 0. Dann ist g trivialerweise eine streng monoton wachsende
Folge naturlicher Zahlen mit Ran(g) = Dom(a). Sei nun ∣a∣ = k+1. Dann ist k = 0 oder k
> 0. Im ersten Fall ist {(0, max(Dom(a)))} eine passende Folge naturlicher Zahlen fur a.
Sei nun k > 0. Da a eine endliche Funktion ist, ist ∣a∖{(max(Dom(a)), amax(Dom(a)))}∣ = k.
Auβerdem ist a∖{(max(Dom(a)), amax(Dom(a)))} ⊆ A. Also gibt es nach I.V. ein g, so dass
g eine passende Folge naturlicher Zahlen fur a∖{(max(Dom(a)), amax(Dom(a)))} ist. Sei
nun g' = g ∪ {(Dom(g), max(Dom(a)))}. Offenbar ist Ran(g') = Dom(a). Wegen
g(max(Dom(g))) = max(Ran(g)) = max(Dom(a∖{(max(Dom(a)), aιmaχ(Dom(a)))}))
< max(Dom(a)) = max(Ran(g')) = g'(Dom(g)) = g'(max(Dom(g')))
ubertragt sich die strenge Monotonie von g auf g'. Also ist g' eine passende Folge naturli-
cher Zahlen fur a. ■