Recursion and Induction: Peano Arithmetic

Recall that the integers are being treated as atomic objects in this
document. But we can explore elementary arithmetic by thinking of a list of
*n* `nil`s as a representation for the natural number *n*. We will call
such a list a “nat.” Thus, `(nil nil nil)` is a nat, but `3` is a
natural number.

**Problem 65. ** Define

**Problem 66. ** Define

**Problem 67. ** Define

**Problem 68. ** Define

**Problem 69. ** Define

**Problem 70. ** Define

**Problem 71. ** Prove

(implies (nat i) (equal (plus i nil) i))

**Problem 72. ** Prove

(equal (plus (plus i j) k) (plus i (plus j k)))

**Problem 73. ** Prove

(equal (plus i j) (plus j i))

**Problem 74. ** Prove

(equal (times (times i j) k) (times i (times j k)))

**Problem 75. ** Prove

(equal (times i j) (times j i))

**Problem 76. ** Prove

(equal (power b (plus i j)) (times (power b i) (power b j)))

**Problem 77. ** Prove

(equal (power (power b i) j) (power b (times i j)))

**Problem 78. ** Prove

(lesseqp i i)

**Problem 79. ** Prove

(implies (and (lesseqp i j) (lesseqp j k)) (lesseqp i k))

**Problem 80. ** Prove

(equal (lesseqp (plus i j) (plus i k)) (lesseqp j k))

**Problem 81. ** Prove

(implies (and (evennat i) (evennat j)) (evennat (plus i j)))

Next: