Lemma des linear beschränkten Längenwachstum

Lemma des Linear beschränkten Längenwachstum

Def. Lemma des Linear beschränkten Längenwachstum

Ist $f:A^*\rightarrow B^*$ eine Sequenzielle Funktion, dann existiert eine Konstante $c\in\mathbb{N}$ so, dass

$$|f(x)|\leq c(|x|+1)$$

für alle $x\in\text{dom}(f)$, also für alle $x$ für die $f$ definiert ist.

Beweis durch Induktion über $|x|$.