: Arithmetic<a class="btn btn-sm" href="/UUID/EDB/0NN/?lang=eng"><span class="ttfamily"><small class="scriptsize">[0NN]</small></span></a>

3.3 Arithmetic[0NN]

We will define the addition operation between natural numbers, formally

\cdot + \cdot : ℕ \times ℕ \to ℕ, (h, k) \mapsto h + k .

Definition 136

[292]Having fixed the parameter $h \in ℕ$ , we define the operation $h + \cdot$ , which will be a function $f_{h} : ℕ \to ℕ$ given by $f_{h} (n) = h + n$ , using a recursive definition: we wish to express the rules

$h + 0 = h$ ,
$\forall n \in ℕ, h + S (n) = S (h + n)$ .

To this end, set $A = ℕ$ , and $g (n, a) = S (a)$ , we rewrite the above as recursive rules for $f_{h}$

$f_{h} (0) = h$ ,
$\forall n \in ℕ, f_{h} (S (n)) = g (n, f_{h} (n)) = S (f_{h} (n))$ .

This defines recursively $f_{h}$ . Considering then the parameter $h$ as a variable, we have constructed the addition operation, and we define the operation ”+” between natural numbers as $h + n = f_{h} (n)$ .

This operation is commutative and associative, as shown below.

Note that $h + 0 = f_{h} (0) = h$ (basis of recursion); also $0 + n = f_{0} (n) = n$ (shows easily by induction).

To prove that it is commutative, we first show that

Lemma 137

[27N](Solved on 2022-11-03) $\forall n, h \in ℕ, f_{S (h)} (n) = S (f_{h} (n))$

Proof ▼

Recall that $S (f_{h} (n)) = f_{h} (S (n))$ by recursive definition; Consider

P (n) ≐ \forall h \in ℕ, f_{S (h)} (n) = S (f_{h} (n));

$P (0)$ is the clause

\forall h \in ℕ, f_{S (h)} (0) = S (f_{h} (0)) = S (h)

which is true because it is the initial value of the recursive definition $f_{S (h)}$ and $f_{h}$ . For the inductive step we assume that $P (n)$ is true and we study $P (S (n))$ , within which we can say

\begin{array}{r} f_{S (h)} (S (n)) \overset{(1)}{=} S (f_{S (h)} (n)) \overset{(2)}{=} \\ S S (f_{h} (n)) \overset{(3)}{=} S (f_{h} (S (n)) \end{array}

where in (1) we used the recursive definition of $f_{h}$ with $S (h)$ instead $h$ , in (2) we used the inductive hypothesis, and in (3) we used the recursive definition of $f_{h}$ . This completes the inductive step.

(Note, in the first step, how important it is that in the definition of $P (n)$ there is $\forall h \in ℕ, \dots$ ).

Proposition 138

[27P](Replaces 27Y) Addition is commutative.

Proof ▼

By the lemma we can write

S (h) + n = S (h + n) = h + S (n)

139

intuitively the formula is symmetric and therefore also the definition of addition must have a symmetry. Precisely, let ${\tilde{f}}_{n} (h) \dot{=} f_{h} (n)$ then ${\tilde{f}}_{n} (0) = n$ (as already noted) and for the lemma 137 ${\tilde{f}}_{n} (S (h)) = S ({\tilde{f}}_{n} (h))$ but then $\tilde{f}$ satisfies the same recursive relation as $f$ and therefore they are identical, so $f_{h} (n) = f_{n} (h)$ . (The idea is that if we had defined addition. recursively starting from left instead of right, we would have achieved the same result).

At this point we can give a name to $1 = S (0)$ and notice that $S (n) = n + 1$ . So from now on we could do without the symbol $S$ .

With similar procedures we show that addition is associative.

Proposition 140

[27Q]Addition is associative.

Proof ▼

Consider

P (h) ≐ \forall n, m \in ℕ, (n + m) + h = n + (m + h);

Obviously $P (0)$ is true, moreover $P (S h)$ is proven (omitting ” $\forall n, m \in ℕ$ ”) like this □

\begin{array}{r} (n + m) + S h = S (n + m) + h = (S n + m) + h \overset{P (n)}{=} \\ = S n + (m + h) = n + S (m + h) = n + (m + S h) \qedhere \end{array}

Multiplication is similarly defined.

Definition 141

[28V](Solved on 2022-11-03) We fix the parameter $m$ , and we define recursively $(m \times \cdot)$ through

$m \times 0 = 0$
$\forall n \in ℕ, m \times (n + 1) = m \times n + m$ ;

then we can prove the known properties (commutativity, associativity, distributivity).

E141

[27R]Rewrite some notions seen above, such as the principle of induction, and the definition of addition, using $n + 1$ instead of $S (n)$ .

E141

[27S] (Solved on 2022-11-03) Show that the function $f_{h} (n) = (h + n)$ is injective. Hidden solution: [UNACCESSIBLE UUID ’27T’]

E141

[27V] Prove the cancellation property: if $n + h = m + h$ then $n = m$ .

Hidden solution: [UNACCESSIBLE UUID ’286’]

E141

[27W] (Solved on 2022-11-03) We have $n + m = 0$ if and only if $n = 0 \land m = 0$ . Hidden solution: [UNACCESSIBLE UUID ’285’]

E141

[27X] (Solved on 2022-11-03) You have $n \times m = 0$ if and only if $n = 0 \lor m = 0$ . Hidden solution: [UNACCESSIBLE UUID ’284’]

E141

[28T]Prove that multiplication is commutative. Hint prove by induction in $n$

\forall m, n \in ℕ, (m + 1) \times n = m \times n + n,

then reason as in Prop. 138. Hidden solution: [UNACCESSIBLE UUID ’28W’]

E141

[281]Show that addition distributes over multiplication. Hint prove by induction in $h$

\forall m, n, h \in ℕ, m \times (n + h) = m \times n + m \times h .

Hidden solution: [UNACCESSIBLE UUID ’28Y’]

E141

[27Z]Prerequisites:7.Show that multiplication is associative. Hint prove by induction in $h$

\forall m, n, h \in ℕ, (m \times n) \times h = m \times (n \times h) .

Hidden solution: [UNACCESSIBLE UUID ’28X’]

E141

[280] Fix $n \neq 0$ and $h \in ℕ$ , write a recursive definition of exponentiation $n^{h}$ . Then prove that $n^{h + k} = n^{n} n^{k}$ and $(n^{h})^{k} = n^{(h k)}$ .

Hidden solution: [UNACCESSIBLE UUID ’2DG’]

In the following we will simply write $n m$ instead of $n \times m$ .