¿Cuántos órdenes de infinito hay?

Question

Definir una función de crecimiento sea una función monótona creciente $F: {\bf N} \to {\bf N}$ así, por ejemplo $n \mapsto n^2$ , $n \mapsto 2^n$ , $n \mapsto 2^{2^n}$ son ejemplos de funciones de crecimiento. Digamos que una función de crecimiento $F$ domina otro $G$ si se tiene $F(n) \geq G(n)$ para todos $n$ . (En su lugar, se podría pedir dominación final en el que se trabaja con $n$ solamente, o dominación asintótica en la que se permite una constante multiplicativa $C$ Pero parece que las respuestas a las preguntas siguientes son básicamente las mismas en ambos casos, así que me quedo con la formulación más sencilla).

Llamemos a una colección ${\mathcal F}$ de las funciones de crecimiento completa cofinal si cada función de crecimiento está dominada por al menos una función de crecimiento en ${\mathcal F}$ .

El argumento de la diagonalización de Cantor nos dice que un conjunto cofinal de funciones de crecimiento no puede ser contable. Por otra parte, el conjunto de todas las funciones de crecimiento tiene la cardinalidad del continuo. Por tanto, según la hipótesis del continuo, un conjunto cofinal de funciones de crecimiento debe tener necesariamente la cardinalidad del continuo.

Mi primera pregunta es: ¿qué ocurre sin la hipótesis del continuo? ¿Es posible tener un conjunto cofinal de funciones de crecimiento de cardinalidad intermedia?

Mi segunda pregunta es más vaga: ¿hay alguna forma más sencilla de ver el conjunto de funciones de crecimiento bajo dominación (o dominación asintótica) que facilite responder a preguntas como ésta? Idealmente me gustaría "controlar" este poset en algún sentido mediante algún otro objeto mejor comprendido (por ejemplo, el primer ordinal incontable, los números naturales no estándar o la compactificación Stone-Cech de los números naturales).

EDIT: anotación actualizada a la vista de las respuestas.

Answer 1

Para la dominación asintótica, comúnmente denominada ${\leq^*}$ y a menudo llamado dominación final Stephen Hechler ha respondido a esta pregunta, Sobre la existencia de ciertos subconjuntos cofinales de ${}^{\omega }\omega$ , MR360266 . Lo que usted llama un juego completo suele denominarse familia dominante .

Como un poset bajo dominación eventual, una familia dominante $\mathcal{F}$ debe tener las tres propiedades siguientes:

1. $\mathcal{F}$ no tiene ningún elemento maximal.
2. Todo subconjunto contable de $\mathcal{F}$ tiene un límite superior en $\mathcal{F}$ .
3. $|\mathcal{F}| \leq 2^{\aleph_0}$

Hechler demostró que para cualquier poset abstracto $(P,{\leq})$ con estas tres propiedades, existe una extensión forzosa en la que se conservan todos los cardinales y potencias cardinales, y existe una familia dominante isomorfa a $(P,{\leq})$ .

En particular, se puede tener una familia dominante bien ordenada cuya longitud sea cualquier cardinal $\delta$ con cofinalidad incontable. En este caso, la restricción $\delta \leq 2^{\aleph_0}$ no es esencial, ya que siempre se puede añadir $\delta$ Cohen reales sin afectar a las condiciones (1) y (2). Sin embargo, para posets arbitrarios, la condición (2) podría destruirse añadiendo reales.

El orden de dominación total es más complejo. Siempre se puede conseguir una familia totalmente dominante $\mathcal{F}'$ de una familia dominante $\mathcal{F}$ añadiendo $\max(f,n) \in \mathcal{F}'$ para cada $f \in \mathcal{F}$ y $n < \omega$ . Desde $\mathcal{F}$ es infinita, la familia resultante $\mathcal{F}'$ tiene el mismo tamaño que $\mathcal{F}$ . Sin embargo, no parece existir una caracterización combinatoria sencilla de las posibilidades de los posets que surgen de este modo.

Answer 2

François ha dado una excelente respuesta a esta pregunta.

Lo que se llama una colección cofinal, una familia $\cal F$ tal que toda función está dominada por una función en $\cal F$ se conoce como dominante familia. Esto es diferente, por ejemplo, del concepto similar de una sin límites familia, una familia $\cal F$ tal que ninguna función domine a todas las funciones de $\cal F$ ya que en los órdenes parciales, a diferencia de los órdenes lineales, las nociones de dominante y no limitado no son las mismas. Como aquí hay varias nociones no equivalentes pero que suenan parecido, parece que merece la pena utilizar la terminología establecida.

Como menciona Kristal, menciono en esta respuesta MO que también es una respuesta directa a esta pregunta, que el número dominante d es el tamaño de la familia de funciones dominante más pequeña, la familia de funciones más pequeña tal que toda función está dominada por algo de la familia. Como señalas, este número es siempre incontable y como mucho el continuo, pero como mencionó François, el valor particular de d puede controlarse exactamente mediante forzamiento. En particular, puede alcanzar los valores intermedios deseados, cuando falla la CH.

El similar pero en realidad no equivalente número límite b en cambio, es el tamaño de la familia no limitada más pequeña $\cal F$ una familia tal que ninguna función domina a todas las funciones de $\cal F$ . Como toda familia dominante es ilimitada, se deduce que b $\leq$ d . Sorprendentemente, sin embargo, es coherente que b $\lt$ d y esto se demuestra de nuevo forzando.

Hay docenas de otras características cardinales similares del continuo, algunas de las cuales menciono en esta respuesta MO . A modo de ejemplo, los investigadores consideran la aditividad de la medida de Lebesgue, la aditividad del ideal magro, la cofinalidad del grupo simétrico $S_\omega$ (el menor número de subgrupos propios que forman una cadena cuya unión es el grupo entero), el número de cobertura (el menor número de conjuntos de medida cero que cubren los reales) y variaciones, etc. Los investigadores en este campo clasifican y separan estos diferentes cardinales en jerarquías, y algunas relaciones destacadas se expresan mediante Diagrama de Cichon . A menudo se desea particularmente controlar algunas de las características cardinales forzando, mientras se dejan fijas otras, y algunos de los resultados más valiosos aquí son teoremas generales que llegan a tal conclusión. Andreas Blass , ahora aquí en MO, es uno de los expertos mundiales en esta área.

Answer 3

François Dorais citó el artículo de Stephen Hechler que responde (más que) completamente a la primera parte de la pregunta. En cuanto a la segunda parte, relativa a otras formas de ver $\mathfrak d$ , otros dos artículos de Hechler son relevantes; aquí están las citas de MathSciNet:

MR0369078 (51 #5314) Hechler, Stephen H., Una docena de pequeños cardinales incontables. TOPO 72---general topology and its applications (Proc. Second Pittsburgh Internat. Conf., Pittsburgh, Pa., 1972; dedicado a la memoria de Johannes H. de Groot), pp. 207--218. Lecture Notes in Math. Lecture Notes in Math, Vol. 378, Springer, Berlín, 1974.

MR0380705 (52 #1602) Hechler, Stephen H., Sobre un cardinal ubicuo. Proc. Amer. Math. Soc. 52 (1975), 348--352.

Cuatro (si no recuerdo mal) de los 12 cardenales del primer documento resultan ser iguales a $\mathfrak d$ que es también el "cardinal ubicuo" del segundo artículo.

Permítanme mencionar también que, si uno sólo quiere responder a la primera parte de la pregunta, no necesita la información tan detallada que da el teorema de Hechler. Para obtener un modelo de teoría de conjuntos con valores prescritos para $\mathfrak d$ y para la cardinalidad $\mathfrak c$ del continuo (sujeto a las restricciones necesarias de que ambos tengan cofinalidad incontable y que $\mathfrak d\leq\mathfrak c$ ), basta con partir de un modelo de la hipótesis del continuo generalizado (por ejemplo, el universo construible de G\"odel), adosar tantos reales de Cohen como el cardinal que se desea que sea $\mathfrak d$ y luego adjuntar suficientes reales aleatorios para traer $\mathfrak c$ hasta el valor deseado.

El método de forzamiento introducido por Hechler en el artículo que citó François se ha convertido en una de las herramientas estándar en el estudio de las características cardinales del continuo. Para un ejemplo, véase

MR0780528 (86i:03064) Baumgartner, James E.; Dordal, Peter, Funciones dominantes adyacentes. J. Symbolic Logic 50 (1985), no. 1, 94--101.

Por último, permítanme un poco de autopromoción. En la página de teoría de conjuntos de mi sitio web,

http://www.math.lsa.umich.edu/~ablass/set.html ,

los dos primeros documentos tratan de las características cardinales del continuo. El primero es una breve introducción (6 páginas) para el público en general (basada en una charla en una conferencia con motivo del 70 cumpleaños de Ryll-Nardzewski), y el segundo es un largo capítulo que (contrariamente al "to appear" de la página web) ya ha aparecido en el Handbook of Set Theory.

Answer 4

Sí, es posible, si se define el orden como dominante con un número finito de excepciones. Entonces f < g si el conjunto de n con f(n) > g(n) es finito. Lo que llamas un sistema completo de funciones de crecimiento se llama un subconjunto dominante de $\omega^\omega$ (y una escala si está bien ordenada). Véase el artículo de van Douwen "The integers and topology" en el Handbook of Set Theoretic Topology. La cardinalidad mínima de una familia dominante de este tipo se denomina $\mathfrak{d}$ en la literatura teórica de conjuntos y es uno de los llamados invariantes cardinales del continuo. Lo que se sabe es que su cofinalidad es al menos $\mathfrak{b}$ donde este último es el tamaño mínimo de un conjunto no limitado en $\omega^\omega$ en el orden parcial de dominación eventual. También, $\mathfrak{d}$ es igual al tamaño mínimo de un subconjunto cofinal de $\omega^\omega$ en el orden de dominancia total que definió. Así que, efectivamente, el problema es el mismo para ambos órdenes, y ambos tienen tamaño mínimo $\mathfrak{d}$ . Sin embargo, la dominancia eventual se utiliza más comúnmente, y así es como la conocí al principio.

Este cardinal puede asumir casi cualquier valor (bajo dicha restricción sobre la cofinalidad al menos) y se han realizado muchos estudios sobre este y otros invariantes cardinales similares y sus interrelaciones. Podemos tener $\omega_1 = \mathfrak{d} < \mathfrak{c}$ , $\omega_1 < \mathfrak{d} < \mathfrak{c}$ y $\omega_1 < \mathfrak{d} = \mathfrak{c}$ en diferentes modelos de ZFC.

Answer 5

Si en lugar de mirar todas las funciones sólo se miran las computables, entonces en cierto sentido se puede encontrar un subconjunto cofinal correspondiente a grandes axiomas cardinales. La idea es, a grandes rasgos, que si se tiene un axioma cardinal grande se puede definir una función de crecimiento rápido computable f como sigue. Tomemos todas las máquinas de Turing de tamaño como máximo n tales que ZFC con el axioma cardinal grande pueda demostrar en menos de n símbolos que la máquina de Turing finalmente se detiene. Entonces f(n) es el número máximo de pasos que tarda cualquiera de estas máquinas en detenerse.