Proposition 10.2.17. The anima \(\N\) of natural numbers has decidable equality.

Proof

We need to show that for all \(n,m : \N\) we have \(n=m\) or \(n\neq m\). By double induction on \(n\) and \(m\) it suffices to observe the following:

  • • We have \(\id_0 : 0=0\).

  • • We have \(0 \neq \succ m\) and \(\succ n \neq 0\) by Lemma 10.2.12.

  • • If we assume that \(n=m\) then we also have \(\succ n = \succ m\), and similarly \(n\neq m\) implies \(\succ n \neq \succ m\); both by Lemma 10.2.16.

From Section 10.2, The natural numbers.