Zeigen Sie, dass R = {(f,g) ∈ Abb(ℕ,ℝ)2 | f(n) = θ(g(n))} eine Äquivalenzrelation auf Abb(ℕ,ℝ) ist.

Question

Aufgabe:

Sei Abb(ℕ,ℝ) die Menge aller Funktionen von ℕ nach ℝ. Zeigen Sie, dass

R = {(f,g) ∈ Abb(ℕ,ℝ)² | f(n) = θ(g(n))}

eine Äquivalenzrelation auf Abb(ℕ,ℝ) ist.

Problem/Ansatz:

Kann mir da bitte jemand helfen?

Comments

Wie habt Ihr genau \(\theta\) definiert?

---

Sei \( g: \mathbb{N} \rightarrow \mathbb{R} . \) Dann definieren wir:
\( \Theta(g(n))=\left\{f(n) \mid \exists C_{1}, C_{2}>0\right. \) und \( n_{0} \in \mathbb{N} \), so dass \( C_{1}|g(n)| \leq|f(n)| \leq C_{2}|g(n)| \) für alle \( \left.n \geq n_{0}\right\} . \)


a) \( \Theta(g(n)) \) ist die Menge aller Funktionen \( f(n) \), welche asymptotisch sowohl von unten als auch von oben durch ein Vielfaches von \( g(n) \) beschränkt sind.

Answer 1

Mit dieser Definition ( ich schreibe c statt \(C_1\) und d statt \(C_2\))

1. \(f =\theta(f)\): Klar mit c=d=1.

2. Symmetrie es sei: \(f = \theta(g)\) also ex m, so dass für \(n \geq m\) gilt

$$c|g(n)| \leq |f(n) \leq d |g(n)| \Rightarrow\frac{1}{d}|f(n)| \leq |g(n)| \leq \frac{1}{c}|f(n)|$$

Also gilt auch \(g=\theta(f)\).

3. Transitivität: Es sei \(f = \theta(g)\) und \(g = \theta(h)\), d.h.

$$c|g(n)| \leq |f(n)| \leq d |g(n)| \text{ für } n \geq m$$

$$c'|h(n)| \leq |g(n)| \leq d' |h(n)| \text{ für } n \geq m'$$

DAnn gilt für \(n \geq \max\{m,m'\}\):

$$cc'|h(n)| \leq c|g(n)| \leq |f(n)| \leq d|g(n)| \leq dd'|h(n)|$$

Also ist auch \(f=\theta(h)\).

Gruß Mathhilf

Comments

Wow super danke. Würde gerne die beste Antwort auszeichnen, aber leider bin ich nicht der Fragesteller ^^

---

Kein Problem. Gut, wenn es hilfreich war - für wen auch immer

---

Könntest Du mir dann eventuell bei dieser Aufgabe auch behilflich sein?

https://www.mathelounge.de/891269/theta-und-konsorten-beweis