Big Omg(f1) subs of Big Omg(f2) iff f1 element BigOmg(f2)

[zzmanzz]

Homework Statement

I usually struggle with proofs and would appreciate some help with the following problem:

Prove the following fact:

$$\Omega(f_1) \subseteq \Omega(f_2)$$ iff $$f_1 \in \Omega(f_2)$$

Homework Equations

$$\Omega(f_1)$$ is the set of functions g s.t.
$$g(n) \geq c f_1(n)$$ where $$n_1 \geq n_o$$

The Attempt at a Solution

[/B]
1. $$\Omega(f_1) = g_1 (n_1) \geq c f_1(n_1)$$
$$\Omega(f_2) = g_2 (n_1) \geq c f_2(n_2)$$

2. $$f_1 \in \Omega(f_2) = f_2(n) \geq c f_1(n)$$

2. implies that
$$g_2(n) \geq f_2(n) \geq c f_1(n)$$

which shows that $$\Omega(f_1) \subseteq \Omega(f_2)$$ from 1.

Is this on the right track? Thanks

 

[mfb]

$\Omega(f_1) = g_1 (n_1) \geq c f_1(n_1)$

You can't set a set of functions equal to a single function.

$g_2(n) \geq f_2(n) \geq c f_1(n)$

Where would the first inequality come from?

Also be careful that you don't reuse "c" for different things.

 

[zzmanzz]

You can't set a set of functions equal to a single function.
Where would the first inequality come from?

Also be careful that you don't reuse "c" for different things.

Thank you for the response. I think I may have made a mistake in the notation so I went back to the textbook to make sure that everything is accurate for this Big Omega which provides an asymptotic lower bound for functions.

1.

$$\Omega(f_1) = \{ g_1(n) :\exists c_1, \exists n_0 , c_1 > 0, s.t. 0 \leq c_1 f_1 (n_1) \leq g_1 (n_1) \quad n_1 \geq n_0 \}$$ $$\Omega(f_2) = \{ g_2(n) :\exists c_2, \exists n_0 , c_2 > 0, s.t. 0 \leq c_2 f_2 (n_2) \leq g_2 (n_2) \quad n_2 \geq n_0 \}$$

2.

$$f_1 \in \Omega(f_2) = \quad \exists c_3, \exists n_0 , c_3 > 0 \quad f_2(n_3) \leq c_3 f_1(n_3) \quad n_3 \geq n_0$$

Maybe here I can use a proof by contradiction and state that :

$$f_1 \notin \Omega(f_2)$$

implies 3.

$$\quad \exists c_3, \exists n_0 , c_3 > 0 \quad f_2(n_3) \geq c_3 f_1(n_3) \quad n_3 \geq n_0$$

but in order to have:

$$\Omega(f_1) \subseteq \Omega(f_2)$$

3 can't be true because this fould imply that $$f_2$$ is not a lower bound on $$f_1$$

 

[mfb]

Maybe here I can use a proof by contradiction and state that :

$$f_1 \notin \Omega(f_2)$$

implies 3.

$$\quad \exists c_3, \exists n_0 , c_3 > 0 \quad f_2(n_3) \geq c_3 f_1(n_3) \quad n_3 \geq n_0$$

It doesn't imply that. As an example, $f_1(x)=x^2 |\sin(\pi x/2)| \notin \Omega(x)$ but there is no $c_3, n_0$ where $x \geq c_3 f_1(n_3) \quad \forall n_3 \geq n_0$.

$\notin$ needs a bit more thought what it means.

 

[zzmanzz]

Thanks for the example - very helpful.

I think that
$$f_1 \notin \Omega(f_2)$$

means that f1 is not in the set of functions asymptotically bounded below by f2and implies

$$\forall c_1 > 0 ,n_0, \exists n > n_0 \quad c_1 f_2(n) > f_1(n)$$In this adjustment of the formula, we say that some n exists where this is not true. I think earlier I made the mistake of giving an asymptotic upper bound definition for the contradiction.

For your example:

$$f_1(x)=x^2 |\sin(\pi x/2)| \notin \Omega(x)$$

we would have:

$$c_1 x > x^2 |\sin(\pi x/2)|$$

which is true whenever the sin part is negative.

However, I think that this contradiction still works for the proof because we just showed that

$$f_1 \notin \Omega(f_2)$$
$$\forall c_1 > 0 ,n_0, \exists n > n_0 \quad c_1 f_2(n) > f_1(n)$$
can't have
$$\Omega(f_1) \subseteq \Omega(f_2)$$
where
$$f_2(n) > f_1(n)$$

 

[mfb]

That is good.

which is true whenever the sin part is negative.

The sine part has to be zero (note the absolute value of it - I wanted to avoid negative numbers), but the key point here is the existence of some n where the right side is small.

You'll have to show $f_1 \in \Omega(f_1)$ to complete that direction.
If $f_1 \notin \Omega(f_2)$ and $f_1 \in \Omega(f_1)$ then $\Omega(f_1)$ cannot be a subset of $\Omega(f_2)$.