Arithmetic of Natural Numbers

Subjects: Set Theory
Links: Natural Numbers

Addition

Th: There is a unique function $+ : N \times N \to N$ such that

$+ (m, 0) = m$ for all $m \in N$
$+ (m, n + 1) = + (m, n) + 1$ for all $m, n \in N$
This can be written in the usual way as
$m + 0 = m$ for all $m \in N$
$m + (n + 1) = (m + n) + 1$

Multiplication

Th: There is a unique function $\cdot : N \times N \to N$ such that

$\cdot (m, 0) = 0$ for all $m \in N$
$\cdot (m, n + 1) = \cdot (m, n) + n$ for all $m, n \in N$
This can be written in the usual way as
$m \cdot 0 = 0$ for all $m \in N$
$m \cdot (n + 1) = (m \cdot n) + n$

Th: Addition and Multiplication are commutative, associative. Additionally, multiplication is distributive over addition.

Exponentiation

We can uniquely define exponentiation of natural numbers as

m {#0} = 1\quad \text{ for all } m\in \Bbb N $$$$ m^{n+1} = m^n \cdot m \quad \text{for all }m, n \in \Bbb N

Difference or Subtraction

Let $n, m \in N$ such that $m \leq n$ . The unique natural $r$ that satisfies $m + r = n$ , we call it the difference of $n$ and $m$ , denoted as $n - m$

Prop: Let $m, n, r, s \in N$ such that $m \leq n$ and $s \leq r$ . Then

$n - n = 0$ , and $n - 0 = n$ for all $n \in N$
$(s + m) + (n - m) = s + n$
$(n + r) - (m + s) = (n - m) + (r - s)$
If $r \leq n - m$ , then $(n - m) - r = n - (m + r)$
If $r \leq m$ , then $n - (m - r) = (n - m) + r$
$n \cdot (r - s) = n \cdot r - n \cdot s$
$(n - m) \cdot (r - s) = (n \cdot r + m \cdot s) - (n \cdot s + m \cdot r)$

Peano’s Axioms for Arithmetic

If $S (n) = S (m)$ , then $n = m$
$S (n) N e 0$
$n + 0 = n$
$n + S (m) = S (n + m)$
$n \cdot 0 = 0$
$n \cdot S (m) = n \cdot m + n$
If $n N e 0$ , then $n = S (k)$ for some $k$
The Induction Schema. Let $A$ be an arithmetic property (a property expresible in terms of $+, \cdot, S, 0$ ). If $0$ has the property $A$ and if $A (k)$ implies $A (S (k))$ for every $k$ , then has the property $A$ .

Given what we have we can check that the natural numbers constructed satisify Peano’s Axioms for arithmetic.

$Σ$ and $Π$ notation

We can define for each finite sequence $⟨ k_{i} ∣ i \in n ⟩$ of natural numbers, define $\sum ⟨ k_{i} ∣ i \in n ⟩$ so that

\sum ⟨ ⟩ = 0 $ $ $ $ \sum ⟨ k_{0} ⟩ = k_{0} $ $

\sum \langle k_0, \dots, k_n\rangle = \sum \langle k_0, \dots, k_{n-1}\rangle+k_n $$

and $\prod ⟨ k_{i} ∣ i \in n ⟩$ so that

\prod ⟨ ⟩ = 1 $ $ $ $ \prod ⟨ k_{0} ⟩ = k_{0} $ $ $ $ \prod ⟨ k_{0}, \dots, k_{n} ⟩ = \prod ⟨ k_{0}, \dots, k_{n - 1} ⟩ \cdot k_{n}