Track / Stage 7 / 125 of 300 #1525 of 1964

Problem 1525

National olympiad second round; IMO P1/P4

Number theory Difficulty 7.2 Prove it

Theorem 3 (Principle of the Greatest Natural Number) Let $M$ be a non-empty subset of the set of natural numbers $\mathbb{N}$ . If $M$ has an upper bound, i.e., there exists $a \in \mathbb{N}$ , such that for any $m \in M$ , we have $m \leqslant a$ , then there must exist $m_{0} \in M$ , such that for any $m \in M$ , we have $m \leqslant m_{0}$ , i.e., $m_{0}$ is the greatest natural number in $M$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Consider the set $T$ consisting of all natural numbers $t$ such that for any $m \in M$ , we have $m \leqslant t$ . By the condition, $a \in T$ , so $T$ is non-empty. By Theorem 2, there exists a smallest natural number in $T$ , denoted as $t_{0}$ . We will prove that $t_{0} \in M$ . If not, for any $m \in M$ , we must have $m < t_{0}$ . From this and property (2), we know $t_{0} \neq e$ , and thus by Theorem 2 in §1, there exists $t_{1} \in N$ such that $t_{0} = t_{1}^{+}$ . By property (5), for any $m \in M$ , we have $m^{+} \leqslant t_{0}$ , so $m^{+} \leqslant t_{1}^{+}$ . This implies $m \leqslant t_{1}$ (why). This shows that $t_{1} \in T$ . But $t_{1} < t_{0}$ , which contradicts the minimality of $t_{0}$ . Taking $m_{0} = t_{0}$ completes the proof of the theorem.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.