How to prove this result for a sequence of sequences? 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. 
 A: 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$.
