La prueba del Lema de Dickson

Question

Una forma de Dickson Lema estados: Para cada conjunto infinito de $n$-tuplas de números naturales, no existen dos tuplas $(a_1,\ldots,a_n),(b_1,\ldots,b_n)$ tal que $a_i\leq b_i$ todos los $i$.

He tratado de demostrar por inducción sobre $n$. El caso de $n=1$ es clara. Asumir el resultado de $n-1$.

Supongamos que existe $x$ de manera tal que el $n$-ésima coordenada es igual a $x$ infinitamente muchas tuplas. A continuación, la hipótesis inductiva se aplica.

Así, supongamos que para cualquier $x$, hay sólo un número finito de tuplas con el último coordinar $x$. De manera que podamos elegir de una lista infinita $(a_{1,1},\ldots,a_{1,n}), (a_{2,1},\ldots,a_{2,n}),\ldots$ tal que $a_{1,n}<a_{2,n}<\cdots$.

Si podemos encontrar la $i<j$ tal que $a_{i,k}\leq a_{j,k}$$k=1,\ldots,n-1$, lo vamos a hacer. ¿Cómo podemos encontrar?

Answer 1

Usted está casi allí, sólo tiene que repetir este paso para todas las coordenadas (tenga en cuenta que esto produciría un error si su tuplas eran de tamaño infinito).

Como usted ha observado, cualquier secuencia infinita de números naturales $(a_n)_{n \in \mathbb N} \subseteq \mathbb{N}$ contiene un infinito no decreciente larga, en particular, hay un elemento $k \in \mathbb{N}$ que ocurre infinidad de veces, o hay un infinito aumento de la larga.

Deje $F$ ser cualquier función de $F : \mathbb{N}^\mathbb{N} \to \mathbb{N}^\mathbb{N}$ que los extractos de los índices de algunas larga con la propiedad mencionada, es decir,

$$F\Big((a_k)_{k \in \mathbb{N}}\Big) \en \Big\{ (i_k)_{k \in \mathbb{N}} \subseteq \mathbb{N} \ \Big|\ i_k \text{ es creciente en }k \de la tierra a_{i_k} \text{ es no decreciente en }k \Big\}.$$

Que se establezca, vamos a hacer su conjunto infinito $S \subseteq \mathbb{N}^n$ de tuplas en una secuencia infinita $S^0$ de tuplas y, a continuación, deje $S^i$ ser un subsequence de $S^{i-1}$ de manera tal que su $i$-ésima coordenada es no decreciente

$$S^{i}_k = S^{i-1}_{F(\pi_i \circ S^{i-1})_k}.$$

Por último, cualquiera de los dos tuplas de $S^n$ le dan lo que quiere.

Espero que esto ayude a $\ddot\smile$