, 2021

We denote $(R', C') \le (R, C)$ to mean $R' \subseteq R$ and $C' \subseteq C$, and we denote $(R', C') < (R, C)$ to mean that at least one of these two inclusions is not an equality. Furthermore, we denote $(r, c) \in (R, C)$ to mean $r \in R$ and $c \in C$.
Consider two good pairs $(R_1, C_1)$ and $(R_2, C_2)$, where $|R_1| > |R_2|$. We shall prove that we can find $(R', C') \le (R_1, C_1)$ satisfying $|R'| \le |R_2|$. Note that this immediately implies the original claim.

Step One: First we construct maps $\rho : R_1 \to R_1$ and $\sigma : C_1 \to C_1$, such that $|\rho(R_1)| \le |R_2|$ and $a(\rho(r_1), c_1) \le a(r_1, \sigma(c_1))$ holds for all $r_1 \in R_1, c_1 \in C_1$.
The construction is as follows: since $(R_1, C_1)$ is good, for every $r_2 \in R_2$, there exists $r_1 \in R_1$ such that $a(r_1, c_1) \ge a(r_2, c_1)$ holds for all $c_1 \in C_1$; denote one such $r_1$ by $\rho_1(r_2)$. Similarly, we define the following four functions:
$$\rho_1 : R_2 \to R_1 \text{ s.t. } a(\rho_1(r_2), c_1) \ge a(r_2, c_1) \text{ for all } r_2 \in R_2, c_1 \in C_1;$$
$$\rho_2 : R_1 \to R_2 \text{ s.t. } a(\rho_2(r_1), c_2) \ge a(r_1, c_2) \text{ for all } r_1 \in R_1, c_2 \in C_2;$$
$$\sigma_1 : C_2 \to C_1 \text{ s.t. } a(r_1, \sigma(c_2)) \le a(r_1, c_2) \text{ for all } r_1 \in R_1, c_2 \in C_2;$$
$$\sigma_2 : C_1 \to C_2 \text{ s.t. } a(r_2, \sigma(c_1)) \le a(r_2, c_1) \text{ for all } r_2 \in R_2, c_1 \in C_1.$$
Now, let $\rho = \rho_1 \circ \rho_2 : R_1 \to R_1$ and $\sigma = \sigma_1 \circ \sigma_2 : C_1 \to C_1$. Then we have
$$|\rho(R_1)| = |\rho_1(\rho_2(R_1))| \le |\rho_1(R_2)| \le |R_2|.$$

Moreover, for all $r_1 \in R_1, c_1 \in C_1$, we have
$$\begin{aligned} a(\rho(r_1), c_1) &= a(\rho_1(\rho_2(r_1)), c_1) \ge a(\rho_2(r_1), c_1) \ge a(\rho_2(r_1), \sigma_2(c_1)) \\ &\ge a(r_1, \sigma_2(c_1)) \ge a(r_1, \sigma_1(\sigma_2(c_1))) = a(r_1, \sigma(c_1)). \end{aligned}$$
Thus the construction is established.

Step Two: Given the good pair $(R, C)$, the maps $\rho$ and $\sigma$, we construct a good pair $(R', C') < (R_1, C_1)$.
The construction is as follows. Note that the properties of $\rho$ and $\sigma$ guarantee that
$$a(\rho^i(r_1), c_1) \ge a(\rho^{i-1}(r_1), \sigma(c_1)) \ge \cdots \ge a(r_1, \rho^i(c_1)),$$
holds for all positive integers $i$ and $r_1 \in R_1, c_1 \in C_1$. Let $R^i = \rho^i(R_1)$ and $C^i = \sigma^i(C_1)$, then we have $R_1 = R^0 \supseteq R^1 \supseteq R^2 \supseteq \cdots$ and $C_1 = C^0 \supseteq C^1 \supseteq C^2 \supseteq \cdots$. But since the number of columns and rows is finite, there must exist $n \in \mathbb{N}$ such that $R^n = R^{n+1} = \cdots$ and $C^n = C^{n+1} = \cdots$. This means $\rho^n(R^n) = R^{2n} = R^n$, that is, $\rho^n$ is a bijection from $R^n$ to $R^n$. Similarly, $\sigma^n$ is a bijection from $C^n$ to $C^n$. Since the elements of $R^n$ and $C^n$ are both finite, there exists a positive integer $k$ such that $\rho^{nk}(r) = r$ and $\sigma^{nk}(c) = c$ hold for all $r \in R^n, c \in C^n$.

Now, let us prove that $(R^n, C^n)$ is exactly the good pair we wish to construct, and that it satisfies $|R^n| \le |R^1| = |\rho(R_1)| \le |R_2|$, from which the original claim follows. To prove that it is a good pair, consider any row $r'$. Since $(R_1, C_1)$ is a good pair, there exists $r_1 \in R_1$ such that $a(r_1, c_1) \ge a(r', c_1)$ holds for all $c_1 \in C_1$. Let $r^* = \rho^{nk}(r_1) \in R^n$, then for any $c \in C^n$, we have $c = \sigma^{nk}(c)$, and thus
$$a(r^*, c) = a(\rho^{nk}(r_1), c) \ge a(r_1, \sigma^{nk}(c)) = a(r_1, c) \ge a(r', c)$$
hence condition 1. holds. Similarly, condition 2. holds, so $(R^n, C^n)$ is a good pair. $\blacksquare$