4.3 Arithmetic[0NN]

We will define the addition operation between natural numbers, formally

\[ ⋅+⋅ : ℕ×ℕ→ℕ \quad ,\quad (h,k)↦ h+k \quad . \]

Definition 137

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

  • \( h+0=h\) ,

  • \(∀ n∈ ℕ, 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\) ,

  • \(∀ n∈ ℕ, 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 138

[27N](Solved on 2022-11-03) \(∀ n,h∈ ℕ, 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)≐ ∀ h∈ ℕ, f_{S(h)}(n)=S(f_ h(n))\quad ; \]

\(P(0)\) is the clause

\[ ∀ h∈ ℕ, 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{eqnarray*} f_{S(h)}(S(n)) \stackrel{(1)}{=} S(f_{S(h)}(n)) \stackrel{(2)}{=}\\ SS(f_ h(n)) \stackrel{(3)}{=} S(f_{h}(S(n)) \end{eqnarray*}

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 \(∀ h∈ ℕ,\ldots \)).

Proposition 139

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

Proof ▼

By the lemma we can write

\begin{equation} S(h) + n = S(h+n)= h + S(n)\label{eq:Shn_ hSN} \end{equation}
140

intuitively the formula is symmetric and therefore also the definition of addition must have a symmetry. Precisely, let \(\tilde f_ n(h){\stackrel{.}{=}}f_ h(n)\) then \(\tilde f_ n(0)=n\) (as already noted) and for the lemma 138 \(\tilde f_ n(S(h))=S\Big(\tilde f_ n(h)\Big)\) 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 141

[27Q]Addition is associative.

Proof ▼

Consider

\[ P(h)≐ ∀ n,m∈ ℕ, (n+m)+h = n+ (m+h)\quad ; \]

Obviously \(P(0)\) is true, moreover \(P(Sh)\) is proven (omitting ”\(∀ n,m∈ ℕ\)”) like this

\begin{align*} (n+m)+Sh = S(n+m)+h = (Sn + m) + h \stackrel{P(n)}{=}\\ = Sn + (m + h) = n+ S (m+h)= n+ (m+Sh)\quad \qedhere \end{align*}

Multiplication is similarly defined.

Definition 142

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

  • \( m× 0=0\)

  • \(∀ n∈ ℕ, m× (n+1)=m× n + m\);

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

E142

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

E142

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

E142

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

Hidden solution: [UNACCESSIBLE UUID ’286’]

E142

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

E142

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

E142

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

\[ \forall m,n∈ ℕ , (m+1)\times n=m\times n + n\quad , \]

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

E142

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

\[ ∀ m,n,h∈ ℕ,~ m× (n+h)=m× n + m× h\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’28Y’]

E142

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

\[ ∀ m,n,h ∈ ℕ, (m× n)× h =m× (n× h)\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’28X’]

E142

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

Hidden solution: [UNACCESSIBLE UUID ’2DG’]

In the following we will simply write \(nm\) instead of \(n× m\).