Cómo muchas de las Grandes $O$ clases de equivalencia hay?

Question

Estoy hablando de la teoría de conjuntos definición de $O(f(n))$, que es el conjunto de todas las funciones $g$ tal que $O(f(n))=O(g(n))$.

¿Cuál es la cardinalidad de a $\{O(f(n)):f\in\mathbb{R}^\mathbb{R}\}$?

Podemos denotar esta cardinalidad $\kappa$. Sabemos que $\kappa\geq\mathfrak{c}$ (debido a que para cada número real $x$, $O(x^n)$ es distinto).

También sabemos que $\kappa\leq\mathfrak{c}^\mathfrak{c}=2^\mathfrak{c}$, porque el conjunto es la cardinalidad de inyección en $\{f:f\in\mathbb{R}^\mathbb{R}\}=\mathbb{R}^\mathbb{R}$.

Así, tenemos los límites superior e inferior. Suponiendo GCH tiene por $\aleph_0$ $\aleph_1$ ( $\mathfrak{c}=\aleph_1$ $2^\mathfrak{c}=\aleph_2$ ), a continuación, se muestra que el $\aleph_1\leq\kappa\leq\aleph_2$, lo que significa que es $\mathfrak{c}$ o $2^\mathfrak{c}$.

Sin embargo, si ZFC puede demostrar que $\mathfrak{c}<\kappa<2^\mathfrak{c}$, que inmediatamente refutar GCH. Suponiendo que ZFC es consistente y $\mathfrak{c}<\kappa<2^\mathfrak{c}$, entonces ZFC no puede probar que esto es cierto, y claramente no puedo dar una exacta cardinalidad de a $\kappa$.

Así, me gustaría animar a aquellos que la solución de este problema para intentar demostrar o bien $\kappa=\mathfrak{c}$ o $\kappa=2^\mathfrak{c}$, o su no va a llegar muy lejos.

Answer 1

Para $A\subseteq\mathbb{R}$, vamos a $f_A(x)=0$ si $0\not\in A$ $x^2$ si $x\in A$. A continuación, tenemos las siguientes:

Supongamos que hay arbitrariamente grandes elementos de $A\setminus B$. A continuación,$f_A\not\in O(f_B)$.

A partir de aquí no es difícil mostrar que $\kappa=2^{\mathfrak{c}}$, como sigue. Dado $C\subseteq [0, 1)$, vamos a $\hat{C}$ se define de la siguiente manera:

• Para $x\in [2k, 2k+1)$, $x\in\hat{C}$ iff $x-2k\in C$.

• Para $x\in [2k+1, 2k+2)$, $x\in\hat{C}$ iff $x-2k-1\in C$.

Si $C_0\not=C_1$, $\hat{C_0}$ contiene arbitrariamente grande de reales no en $\hat{C_1}$; por lo que el conjunto de $$\{f_{\hat{C}}: C\subseteq [0,1)\}$$ is a big-O antichain and has size $2^\mathfrak{c}$.

---

Mientras tanto, si nos restringimos a la atención continua de las funciones sólo, obtenemos $\mathfrak{c}$, ya que sólo hay continuum-muchas funciones continuas en el primer lugar.