Beweis O-Klassen sind präfixabgeschlossen

Question

Aufgabe:

Wir nehmen im Folgenden an, dass Funktionen vom Typ \( \mathbb{N} \longrightarrow \mathbb{R}_{\geq 0} \) sind. Beweisen oder widerlegen Sie: \( \mathcal{O}- \) Klassen sind präfixabgeschlossen, d.h. für jede Funktion \( g \) gilt:
\( \forall h \in \mathcal{O}(g) \quad \forall \text { Funktionen } f: \quad f \in \mathcal{O}(h) \Longrightarrow f \in \mathcal{O}(g) . \)

Problem/Ansatz:

ich würde vermuten, dass die Aussage stimmt, da die Transitivität bei O-Klassen gilt. Aber ich würde dennoch gerne einen Tipp von euch kriegen.

Answer 1

\( \forall h \in \mathcal{O}(g) \quad \forall \text { Funktionen } f: \quad f \in \mathcal{O}(h) \Longrightarrow f \in \mathcal{O}(g) . \)

Etwas formaler ausgedrückt lautet die Aussage

        \(\forall g\ \forall h\ \forall f:\ (h\in O(g)\implies (f\in O(h)\implies f\in O(g)))\).

Transitivität besagt aber

        \(\forall g\ \forall h\ \forall f:\ ((f\in O(h)\wedge h\in O(g))\implies f\in O(g))\).

Mit einem einfachen Hinweis auf Transitivität ist es deshalb nicht getan.