How to prove this result for a sequence of sequences?

Question

There are n infinite sequences of positive integers,
$A_1 = a_{11}, a_{12}, a_{13}…,$
$A_2 = a_{21}, a_{22}, a_{23}…,$
$A_3 = a_{31}, a_{32}, a_{33}…,$
$A_n = a_{n1}, a_{n2}, a_{n3}…,$
Show that there must exist i and j such that a $a_{ki}\leq a_{kj}$ for all 1<=k<=n. It seems very much intuitively true, but cannot figure a rigrous proof.

Answer 1

A sequence of positive integers necessarily has a non-decreasing subsequence $(*)$.

First choose a non-decreasing subsequence $(a_{1, f_1(l))})_l$ of $(a_{1, l})_l$.

Next, choose a non-decreasing subsequence $(a_{2, f_2(l))})_l$ of $(a_{2, f_1(l))})_l$. Then $(a_{1, f_2(l))})_l$ is non-decreasing as well.

Repeat the process until you have a non-decreasing subsequence $(a_{n, f_n(l))})_l$ of $(a_{n, f_{n-1}(l))})_l$. Then $(a_{k, f_n(l))})_l$ is non-decreasing for $1 \le k \le n$.

If $l_1 < l_2$ then $i = f_n(l_1)$, $j = f_n(l_2)$ satisfy $$ a_{k,i} \le a_{k, j} \quad \text{for } 1 \le k \le n $$ so there are infinitely many pairs $(i, j)$ with the desired property.

---

Proof of $(*)$: Let $(x_n)_n$ be a sequence of positive integers. The set $\{ x_n \mid n \in \Bbb N \}$ has a minimum, and the set of integers $n$ where the $x_n$ is equal to the minimum has a minimum as well. Therefore we can define $$ n_1 = \min \{ n \mid x_{n_1} = \min_j x_j \} $$ If $n_1, \ldots, n_k$ are defined, define $$ n_{k+1} = \min \{ n > n_k \mid x_{n_k} = \min_{j> n_k} x_j \} $$

Then $n_1 < n_2 < \ldots$ and $x_{n_1} \le x_{n_2} \le \ldots$.