CheckMyProof: Pruebas con notación Big-O

Question

Este es un ejercicio de deberes de hace unas semanas y quería tu opinión sobre mis pruebas mejoradas.

Para $g: \mathbb{N} \to \mathbb{R}$ l $$o(g):= \{f:\mathbb{N} \to \mathbb{R} |\forall \alpha > 0 : \exists n_0 \in\mathbb{N} : \forall n \geq n_0 : 0 \leq f(n) \leq \alpha g(n)\}$$ Sea $g: \mathbb{N} \to \mathbb{R}$ para que $g(n)\not= 0$ para infinitas $n \in \mathbb{N}$ . Demostrar o refutar

1. $\mathcal{O}(g) \setminus \Theta(g) \subseteq o(g)$
2. $o(g) \subseteq \mathcal{O}(g) \setminus \Theta(g)$
3. $f \in o(g) \implies g \notin o(f)$

Nuestras definiciones de $\mathcal{O}$ y $\Omega$ y $\Theta$ son los siguientes $$ f \in \mathcal{O}(g) \iff \exists n_0 \in \mathbb{N} ~\exists \alpha >0 : 0 \leq f(n) \leq \alpha g(n) \forall n \geq n_0 ~\textrm{and} $$ $$ f \in \Omega(g) \iff \exists n_0 \in \mathbb{N} ~\exists \beta >0 : 0 \leq \beta g(n) \leq f(n) ~~\forall n \geq n_0 $$

$$ f \in \Theta(g) \iff f \in \Omega(g) \land f \in \mathcal{O}(g) $$

---

1. La incorrección de la afirmación se demuestra mediante un contraejemplo.

Sea $f(n) := \begin{cases} 1 & n ~\textrm{odd} \\ 0 & n ~\textrm{even} \end{cases}~~~$ y $g(n) = 1$ entonces $f \in \mathcal{O}(g) \setminus \Theta(g)$ pero $f \notin o(g)$ .

Prueba: De la definición sabemos, que $$ f \in \mathcal{O}(g) \iff \exists \hat{n_0} \in \mathbb{N} ~\exists \alpha >0 : 0 \leq f(n) \leq \alpha g(n) \forall n \geq \hat{n_0} ~\textrm{and} $$ $$ f \notin \Theta(g) \iff \exists \tilde{n_0} \in \mathbb{N} ~\nexists \beta >0 : 0 \leq \beta g(n) \leq f(n) \forall n \geq \tilde{n_0} $$ Combinando estas afirmaciones obtenemos para todos $ n \geq \tilde{n_0}, \hat{n_0} \in \mathbb{N}$ $$ 0 \leq \beta g(n) \leq f(n) \leq \alpha g(n) \iff 0 < \beta \leq f(n) \leq \alpha $$ Desde $~f(n) \in \{0,1\}$ no existe $\beta >0$ hacer $0 < \beta \leq f(n)$ cierto, porque para cada par $n$ obtenemos $0 = f(n) < \beta ~\forall \beta > 0$ . $~~\square$

(Pregunta específicamente aquí: $\beta > 0 $ pero la condición es $\beta g(n) = \beta \geq 0$ . En el último párrafo, ¿utilizo $\geq$ o $>$ ?)

---

2. La afirmación es correcta.

Sea $f \in o(g)$ es evidente que $f \in \mathcal{O}(g)$ . Ahora tenemos que demostrar que $f \notin \Theta (g)$ . Supongamos que $f \in \Theta (g)$ mientras que $f \in o(g)$ se deduce que $$ f(n) \leq \alpha g(n) ~\forall \alpha > 0 ~\textrm{and}~ n \geq n_0 \in \mathbb{N} \land \beta g(n) \leq f(n) ~\textrm{for one}~ \beta > 0 ~\forall n \geq \tilde{n_0} \in \mathbb{N} $$ Lo cual es una contradicción, porque la primera condición sólo es cierta si $f(n) = \beta g(n)$ . Entonces $\beta g(n) > \alpha \beta g(n)$ para un $\alpha <1$ por lo que la segunda condición no puede cumplirse.

Así que $f \notin \Theta (g)$ y, por tanto, la afirmación es cierta.

---

3. La afirmación es correcta.

Sea $f \in o(g)$ y $g \in o(f)$ . Entonces $$ \exists n_0 \in \mathbb{N} ~\forall \alpha > 0: 0 \leq f(n) \leq \alpha g(n) \forall n \geq n_0 ~\textrm{and} $$ $$ \exists \tilde{n_0} \in \mathbb{N} ~\forall \tilde{\alpha} > 0: 0 \leq g(n) \leq \tilde{\alpha} f(n) \forall n \geq \tilde{n_0} $$ Combinando ambas condiciones obtenemos $$ \exists \hat{n_0} := \max\{n_0, \tilde{n_0}\} ~\forall \alpha, \tilde{\alpha} >0 : 0 \leq f(n) \leq \alpha g(n) \leq \alpha \tilde{\alpha} f(n)\forall \hat{n_0} \geq n \in \mathbb{N} $$ Lo cual sólo es posible si $f = g = 0$ pero $g \not= 0$ para infinitas $n \in \mathbb{N}$ produciendo una contradicción, por lo que sabemos que $g \notin o(g)$ lo que demuestra que la afirmación es correcta.

También puede elegir $\alpha = 1, \tilde{\alpha} = 0.5$ para obtener $$ 0 \leq f(n) \leq g(n) \leq 0.5 f(n) \implies 2f(n) \leq f(n) \implies 2 \leq 1 $$ llegando a una contradicción. (Aquí: buscando una mejor justificación de la contradicción)

Answer 1

La prueba de la primera parte tiene algunas desviaciones que deberían revisarse. Las pruebas de las demás partes son esencialmente correctas. La segunda prueba podría reformularse un poco para mejorar la legibilidad. No obstante, todas las pruebas muestran ya un buen enfoque cualitativo.

Primera parte: $\mathcal{O}(g) \setminus \Theta(g) \subseteq o(g)$

La elección del contraejemplo mediante $f$ y $g$ está bien. También mostrando que $f\in\mathcal{O}(g)$ es correcto. La siguiente afirmación no es correcta:

\begin{align*} f \notin \Theta(g) \iff \exists \tilde{n_0} \in \mathbb{N} ~\not\exists \beta >0 : 0 \leq \beta g(n) \leq f(n) ~~\forall n \geq \tilde{n_0} \end{align*} En su lugar, podemos escribir por ejemplo: \begin{align*} f \notin \Theta(g) &\iff \neg\left(\left(f \in \mathcal{O}(g)\right)\land\left(f \in\Omega(g)\right)\right)\\ &\iff \left(f \not\in \mathcal{O}(g)\right)\lor\left(f \not \in\Omega(g)\right)\\ \end{align*} y como ya sabemos que $f\in\mathcal{O}(g)$ concluimos $f \not\in \Omega(g)$ . Obtenemos según la definición de $\Omega(g)$ : \begin{align*} f \not\in \Omega(g)&\iff\neg\left(\exists \tilde{n}_0 \in \mathbb{N}\, \exists \beta >0\,\forall n \geq \tilde{n}_0 : 0 \leq \beta g(n) \leq f(n) \right)\\ &\iff \forall\tilde{n}_0 \in \mathbb{N}\, \forall\beta >0\,\exists n \geq \tilde{n}_0:\beta g(n)>f(n)\tag{1} \end{align*} La afirmación (1) es cierta, ya que podemos tomar para cada $\tilde{n}_0\in\mathbb{N}$ y cada $\beta>0$ el valor $n=2\tilde{n}_0$ a $$\beta g(2\tilde{n}_0)=\beta>0=f(2\tilde{n}_0)$$ mostrando $f \not\in \Omega(g)$ .

Concluimos $f\in\mathcal{O}(g)\setminus\Omega(g)$ .

Echemos un vistazo más de cerca:

• Desde $f(n) \in \{0,1\}$ no existe $\beta >0$ hacer $0 < \beta \leq f(n)$ cierto, porque para cada par $n$ obtenemos $0 = f(n) < \beta ~\forall \beta > 0$ .

El objetivo de este apartado no está claramente establecido. Parece que esta es la parte que muestra que $f\not \in o(g)$ . Pero el argumento no es sólido.

La formulación debe mejorarse ya que no es $f(n)\in\{0,1\}$ que es la esencia, sino la propiedad que $f(n)$ es uno para impar $n$ . También es útil exponer claramente lo que significa que $f\not\in o(g)$ .

Por ejemplo:

Mostramos $f\not\in o(g)$ . Esto significa, según la definición de $o(g)$ : \begin{align*} f\not \in o(g)&\iff \neg\left(\forall \alpha > 0 \, \exists n_0 \in\mathbb{N} \, \forall n \geq n_0 : 0 \leq f(n) \leq \alpha g(n)\right)\\ &\iff \exists\alpha>0\,\forall n_0\in\mathbb{N}\,\exists n\geq n_0: f(n)>\alpha g(n) \end{align*} Tomamos $\alpha=\frac{1}{2}$ y para $n_0\in\mathbb{N}$ tomamos $n=2n_0+1$ : f \begin{align*} f(n)=f(2n_0+1)=1>\frac{1}{2}=\alpha g(n) \end{align*} demuestra que $f\not\in o(g)$ .

Aquí también utilizamos específico ajustes para $\alpha$ y $n$ que es más fácil de seguir que los argumentos con el no existente $\beta>0$ arriba.

Segunda parte: $o(g)\subseteq \mathcal{O}(g) \setminus \Theta(g)$

La segunda parte es esencialmente correcta. Podría estructurarse algo más claramente para mejorar la legibilidad.

La declaración Supongamos que $f\in\Theta(g)$ inicia un argumento indirecto. Podría ser más fácil seguirla enunciándola explícitamente y argumentar de nuevo basándose en la definición.

Por ejemplo:

Asumimos indirectamente $f\in\Theta(g)$ . Como ya sabemos que $f\in\mathcal{O}(g)$ tenemos que demostrar $f\in\Omega(g)$ . Esto significa per definiti \begin{align*} f\in \Omega(g)&\iff\exists n_0\in\mathbb{N}\,\exists\beta>0\,\forall n\geq n_0: 0\leq \beta g(n)\leq f(n)\tag{2} \end{align*} por otra parte, ya que $f\in o(g)$ w \begin{align*} f\in o(g)&\iff \forall \alpha>0\, \exists\tilde{n}_0\in\mathbb{N}\,0\leq f(n)\leq \alpha g(n)\tag{3} \end{align*} Como sabemos por (2) que existe un $\beta>0$ cumpliendo (2) podemos tomar en (3) $\alpha=\frac{\beta}{2}$ w \begin{align*} 0\leq f(n)\leq \frac{\beta}{2} g(n)\leq\frac{1}{2} f(n)\qquad\forall n\geq \max\{n_0,\tilde{n}_0\} \end{align*} Esto implica $f\equiv 0\equiv g$ para todos $n\geq \max\{n_0,\tilde{n}_0\}$ mostrando la contradicción ya que por definición $g(n)\not =0$ para infinitas $n$ que prueba la afirmación.

Tercera parte: $f \in o(g) \implies g \notin o(f)$

La prueba es correcta. Desde mi punto de vista, los ajustes explícitos de variables para $\alpha ,\tilde{\alpha}$ mejora la legibilidad. El último párrafo podría formularse

Elegimos $\alpha = 1, \tilde{\alpha} = 0.5$ para obtener $$ 0 \leq f(n) \leq g(n) \leq 0.5 f(n) $$ llegando a una contradicción para $n$ con $f(n)\neq 0$ . Este es el caso para infinitos $n\in\mathbb{N}$ según la definición de $g$ .