Proof. Let $\fU \subset 2^{\natp}$ be a free ultrafilter. For each $n \in \natp$ and $1 \le i \le r$, let $A(n, i) = \bracsn{m > n| c(\bracsn{m,n}) = i}$, then $\natp = \bracsn{1, \cdots, n}\bigsqcup_{i = 1}^{r} A(n, i)$. As $\fU$ is a free ultrafilter, there exists a unique $1 \le i(n) \le r$ such that $A(n, i(n)) \in \fU$.

For each $1 \le i \le r$, let $B_{i} = \bracsn{n \in \natp|i(n) = i}$, then $\natp = \bigsqcup_{i = 1}^{r} B_{i}$. As $\fU$ is an ultrafilter, there exists a unique $1 \le i \le r$ with $B_{i} \in \fU$.

Let $n_{1} \in B_{i}$, so $i(n_{1}) = i$. Assume inductively that $\bracsn{n_j}_{1}^{N} \subset \natp$ has been defined such that:

1. (i)

   For each $1 \le j \le N - 1$, $n_{j} < n_{j+1}$.

2. (ii)

   For each $1 \le j \le N$, $i(n_{j}) = i$.

3. (iii)

   For each $1 \le j < k \le N$, $c(\bracsn{n_j, n_k}) = i$.

Let $n_{N+1}\in B_{i} \cap \bigcap_{j = 1}^{N} A(n_{j}, i)$, then:

1. (1)

   As $n_{N+1}\in A(n_{N}, i)$, $n_{N+1}> n_{N}$.

2. (2)

   Since $n_{N+1}\in B_{i}$, $i(n_{N+1}) = i$.

3. (3)

   For each $1 \le j \le N$, $n_{N+1}\in A(n_{j}, i) = A(n_{j}, i(n))$, so $c(\bracsn{n_j, n_{N+1}}) = i$.

By induction, there exists $\seq{n_j}\subset \natp$ such that $c(\bracsn{n_j, n_k}) = i$ for all $j, k \in \natp$ with $j \ne k$.$\square$