Proposition 10.2.19. Denote by \(E\colon \N\times \N \to \Prop\) the observational equality of natural numbers, defined by induction via \begin{equation} E(0,0) \coloneq *, \quad E(0,n+1) \coloneq \emptyset, \quad E(n+1,0) \coloneq \emptyset \quad E(n+1,m+1)\coloneq E(n,m). \tag{10.1}\end{equation} Then for each \(n,m \in N\) we have \begin{equation} (n=m) = E(n,m). \tag{10.2}\end{equation}

Proof

Each \(E(n,m)\) is a proposition by definition, and each \((n=m)\) is a proposition by Corollary 10.2.18. Moreover, the two propositions can be shown to be logically equivalent by induction. The base case is \begin{equation} ! \colon (0=0) \leftrightarrow * : \id_0 \tag{10.3}\end{equation} and the successor steps follow by using Lemma 10.2.12 and Lemma 10.2.16.

From Section 10.2, The natural numbers.