Un ejemplo que muestra que van der Waerden del teorema no es cierto para el infinito progresiones aritméticas

Question

Una de las posibles formulaciones de Van der Waerden del teorema es la siguiente:

Si $\mathbb N=A_1\cup \dots\cup A_k$ es una partición del conjunto de $\mathbb N$, entonces uno de los conjuntos de $A_1,\dots,A_k$ contiene finito progresiones aritméticas de longitud arbitraria.

En otras palabras, si tenemos en color el conjunto de todos los enteros positivos mediante un número finito de colores, no debe ser monocromática, con arbitrariamente larga finita progresiones aritméticas.

Supongo que el mismo resultado no es cierto si se requiere que uno de los conjuntos contienen una infinita progresión aritmética. (De lo contrario, este resultado sería bien conocido).

¿Cuál es un ejemplo que muestra que esta versión más fuerte del teorema anterior no es cierto? (I. e., un ejemplo de un colorante de $\mathbb N$ por un número finito de colores sin monocromática infinita progresión aritmética.)

Answer 1

El Color de los números enteros negro o blanco según si tienen un par o un número impar de dígitos.

Answer 2

Voy a añadir un ejemplo tomado del Hermoso libro de Matemáticas por Martin Erickson, página 72. Y es bastante similar a la de algunas de las respuestas que ya han sido publicados.

$$\begin{array}{cccccccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \circ & \bullet & \bullet & \circ & \circ & \circ & \bullet & \bullet & \bullet & \bullet & \circ & \circ & \circ & \circ & \circ & \bullet & \bullet & \bullet & \bullet & \bullet \end{array} $$

Empezamos por la coloración $1$ por uno de color. A continuación, hemos de color de dos números siguientes, por el otro. Siguiente segmento consiste de tres números de la primera de color, etc.

De este modo se consigue más y más largos segmentos de cada color.

Si $a+nd$ es cualquier progresión aritmética, entonces se contienen algunos de los números de ambos colores. De hecho, hay dos segmentos consecutivos de longitudes $d$$d+1$. Si esta progresión aritmética ser monocromático, tendría que "saltar" uno de esos segmentos. Pero esto no es posible, ya que la diferencia es $d$ y la longitud de cada uno de estos dos segmentos es de al menos $d$.

Answer 3

El truco es simplemente hacerlo. Basta considerar el caso de $k=2$.

Enumerar los countably muchos pares de $(d,a)\in\Bbb N^2$ y el mango de ellos, uno por uno, la adición de elementos de a $A_1$ $A_2$ en el proceso (donde ambos conjuntos son inicialmente vacía). Tenga en cuenta que en cada paso, $A_1,A_2$ son finitos y discontinuo. Así que, dado que $(d,a)$, hay una infinidad de $n\in\Bbb N$$a+nd\notin A_1\cup A_2$. Escoge dos números tales $n_1,n_2$ y añadir $a+n_1d$ $A_1$y añadir $a+n_2d$$A_2$. Después de que se proceda con el siguiente par de $(d,a)$.

Al final tenemos dos conjuntos disjuntos $A_1,A_2$ de manera tal que cada uno de ellos contiene al menos un elemento de cada infinita sucesión aritmética $(a+nd)_n$, evitando así el otro conjunto que contiene la completa secuencia infinita. En realidad obtener una partición que todavía tiene esta propiedad, los números no utilizados de $\Bbb N$ puede añadirse a cualquiera de los dos componentes.

Answer 4

Definir $$A = \{10^n + k: 1 \leq k\leq n\}=\{11, 101, 102, 1001, 1002, 1003, 10001, \ldots\}.$$ Claramente $A$ natural a la densidad de cero, y que claramente se cruza cada infinita progresión aritmética infinitamente a menudo, así que la partición $\mathbb N = A \cup A^c$ es como quería

Answer 5

Vamos a construir un ejemplo con sólo dos juegos en la partición, $A$$B$.

Enumerar el conjunto $\mathbb{N}\times\mathbb{N}^{>0}$ $\{(n_k,d_k)\mid k\in \mathbb{N}\}$ (creo que de $n$ como el punto de partida de una progresión aritmética y $d$ como la diferencia constante entre los términos). Empezamos con $A = B = \emptyset$ y asegurarse de que en cada etapa de la construcción (indexados por $k\in \mathbb{N}$), $A$ y $B$ son subconjuntos finitos de $\mathbb{N}$.

En la etapa de $k$ de la construcción, mirar a la par $(n_k,d_k)$.

Caso $1$: $n_k\in A$. Deje $m$ ser el menor número natural tal que $n_k + md_k\notin A$, y agregar$n_k+md_k$$B$.

Caso $2$: $n_k\in B$. Repita el Caso de $1$, pero con los roles de $A$ $B$ invertido.

Caso $3$: $n_k$ no es en $A$ o $B$. Agregar $n_k$ $A$y repita el Caso de $1$.

Para completar la etapa de $k$ de la construcción, si el número natural $k$ no $A$ o $B$, agregar de a $A$.

Al final del infinito de la construcción, tenemos una partición de todos los de $\mathbb{N}$ en los dos conjuntos de $A$ $B$ (ya que cada una de las $k$ fue en $A$ o en $B$ al final de la etapa $k$). Supongamos que hay una infinita progresión aritmética contenida en $A$. Comienza con $n$ y los términos constantes diferencia $d$. Ahora $(n,d) = (n_k,d_k)$ algunos $k\in \mathbb{N}$. Pero al final de la etapa $k$, nos aseguramos de que algún elemento $n+md$ de la arithemetic la progresión fue en $B$, contradicción.

El simétrica argumento muestra que no es infinita progresión aritmética contenida en $B$.