 Almost all number theoretic functions and relations encountered in ordinary mathematics can be shown to be primitive recursive. In order to illustrate the extent of this class, we will present here a standard sequence of definitions which can be traced historically to Skolem (1923). This can be used to show that the sequence coding \(\langle \ldots \rangle\) and decoding \((\cdot)_i\) operations defined below are primitive recursive.  This is in turn required for Gödel’s arithmetization of syntax (see  Section 1.3)  as well as results like the Normal Form Theorem  (2.3)  which will be discussed below.