We define M as :={|:→ℝ+} M := { f | f : n → R + } for ,∈ f , g ∈ M we say ≈, iff ∈Θ() f ∈ Θ ( g ) . Since ≈ is an equivalence relation (I have proved this part) we define the equivalence class []≈:={∈|≈}
Further we define ⊳ as a order relation between the classes and say: []≈⊳[]≈
iff ∈()
1) Prove or disprove whether ⊳ is a strict partial order? For ⊳ to be a partial order, irreflexivity and transitivity have to fulfilled. []≈⊳[]≈
must NOT hold. However []≈⊳[]≈
equals ∈() which is fulfilled due to the symmetry of Big
.
So it can not be a strict partial order, right? How can I show that ⊳ is a partial order? Reflexivity and transitivity are clear but how can I show antisymmetry?
Assuming you use the same notations as explained in the Wikipedia, then $f\in \theta(g)$ means
$$0 < \lim_{n\to\infty} \inf \left\lvert \frac{f(n)}{g(n)}\right\rvert \le \lim_{n\to\infty} \sup \left\lvert \frac{f(n)}{g(n)}\right\rvert < \infty.$$
and $f\in O(g)$ means
$$\lim_{n\to\infty} \sup \left\lvert \frac{f(n)}{g(n)}\right\rvert < \infty.$$
Now assume $[f] \rhd [g]$ and $[g] \rhd [f]$ (I've removed the $\approx$, because we are only dealing with one equivalence relation and using the "$[]$" brackets indicates that we are talking about the equivalence class of the function inside).
First, since all elements of $M$ are functions with co-domain $\mathbb R_+$, we can ignore the absolute values in the definitions above. So $[f] \rhd [g]$ and $[g] \rhd [f]$ mean
$$\lim_{n\to\infty} \sup \frac{f(n)}{g(n)} < \infty \text{ and } \lim_{n\to\infty} \sup \frac{g(n)}{f(n)} < \infty. \tag{1} \label{eq1}$$
Considering the second inequality, we have
$$\frac{g(n)}{f(n)} = \frac1{\frac{f(n)}{g(n)}}$$
and since $h(x)=\frac1x, h:\mathbb R_+ \to \mathbb R_+$ is a monotonically decreasing continuous function, we have
$$\lim_{n\to\infty} \sup \frac{g(n)}{f(n)} = \frac1{\lim_{n\to\infty} \inf \frac{f(n)}{g(n)}}.$$
The "decreasing" means we need to change from $\lim \sup$ to $\lim \inf$, and the "continuity" means those limits are the same. The right part of \eqref{eq1} says that the $\lim \sup$ on the left hand side above is finite (not $\infty$), so we know the $\lim \inf$ on the right hand side isn't $0$. Since $\frac{f(n)}{g(n)} > 0, \forall n$, that means
$$ \lim_{n\to\infty} \inf \frac{f(n)}{g(n)} > 0. \tag{2}\label{eq2}$$
Now combining the left part of $\eqref{eq1}$ with $\eqref{eq2}$ we get
$$0 < \lim_{n\to\infty} \inf \frac{f(n)}{g(n)} \le \lim_{n\to\infty} \sup \frac{f(n)}{g(n)} < \infty.$$
where the middle "$\le$" is true for any sequence. This is however the definition of $f\in\theta(g)$ from the start of this answer, with the absolute values removed (as explained above).
So we have $f\in\theta(g)$ and hence $[f]=[g]$. That proves the antisymmetry of the partial order $\rhd$.