◀ ▲ ▶Branches / Number-systems-arithmetics / Proof

Proof

(related to Proposition: Well-Ordering Principle of Natural Numbers)

We will prove the proposition for the poset $(\mathbb N,\le).$ An analogous proof is possible for the strictly-ordered set $(\mathbb N, < ),$ in which we have to replace the order relation "$\le$" by the order relation "$<$" and the word minimum by the word minimal element.

• Let \(M\) be a non-empty subset of natural numbers \(M\subseteq\mathbb N.\)
• Since $M$ is non-empty, let \(n_0\in M\) be its element.
• We will construct a minimum as follows:
  • If there is no smaller element \(m \le n_0\) then we set \(m_0:=n_0\), since it is the minimum we were looking for.
  • Otherwise there exists an $n_1\in M$ with \(n_1 < n_0.\)
  • We ask again if there is no smaller element \(m \le n_1\).
  • If so, then we set \(m_0:=n_1\), otherwise we find an $n_2\in M$ with \(n_2 < n_1.\) and repeat the same search again.
  • Our searching process will be repeated at most \(n_0 - m_0+1\) times until we finally find the smallest element of \(M\).
• This shows that $M$ contains a minimum, which is by construction unique.
• We have shown that $(\mathbb N,\le)$ is a well-ordered set.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Kramer Jürg, von Pippich, Anna-Maria: "Von den natürlichen Zahlen zu den Quaternionen", Springer-Spektrum, 2013