自然数
自然数の加法は再帰的に、以下のように定義できる。
すべての自然数 a に対して、a + 0 = a
すべての自然数 a, b に対して、a + suc(b) = suc(a + b)
1 := suc(0) と定義するならば、suc(b) = suc(b + 0) = b + suc(0) = b + 1 となり、b の後者とは単に b + 1 のことである。
加法が定義されたならば、自然数の乗法は再帰的に、以下のように定義できる。
すべての自然数 a に対して a × 0 = 0
すべての自然数 a, b に対して a × suc(b) = (a × b) + a
加法、乗法とも (i) 0 に対する演算結果を定義し、(ii) ある自然数 b に対する演算結果を用いてその次の自然数 suc(b) に対する演算結果を定義する、と言う形式になっている。