Together, the formal system that includes Propositional Logic, Predicate Logic, and Equality will be simply called Logic. We can now extend the Logic mathematical system by adding the definition of the natural numbers.
It is possible to define the Natural Numbers and addition, multiplication, and $<$ for those numbers from scratch. One famous way of doing that is with the following axioms which were developed by Giuseppe Peano at the end of the $19^\text{th}$ century. We extend our language by defining two constants, $0$ and $\sigma$.
Peano Axioms
| Name | Rule |
|---|---|
| N0 (existence of $0$) | $0$ is a natural number (a constant declaration) |
| N1 (existence of successors) | if $n$ is a natural number then $\sigma(n)$ is also a natural number |
| N2 (uniqueness of predecessor) | $\sigma(m)=\sigma(n) \implies m=n$ |
| N3 (zero is first) | $0\neq\sigma(n)$ |
| N4 (induction) | $\mc{P}\left(0\right)\xand\left(\forall k.\mc{P}\left(k\right)\implies \mc{P}\left(\sigma(k)\right)\right)\implies\forall n.\mc{P}\left(n\right)$ |
| A0 (additive identity) | $n+0=n$ |
| A1 (successor addition) | $m+\sigma(n)=\sigma(m+n)$ |
| M0 (multiplication by zero) | $n\cdot 0=0$ |
| M1 (successor multiplication) | $m\cdot \sigma(n)=m+m\cdot n$ |
| I (order) | $m\leq n \iff \exists k.m+k=n$ |
Peano Axioms
Declare $0, \sigma, +, \cdot$ to be constants.
Axiom N0 $0$ is a natural number.
Axiom N1 For all natural numbers $n$, the
successor of $n$ is a natural number.
The set $\NN$
Axiom N2 (successor is injective). If $\sigma(m)=\sigma(n)$ then $m=n$.
Axiom N3 (zero is first). $0\neq \sigma(n)$.
Axioms N4 (induction)
Given
$\mc{P}(0)$ (base case)
Let $k$ be such that $\mc{P}(k)$
(inductive hypothesis)
$\mc{P}(\sigma(k))$
Conclude $\forall n.\mc{P}(n)$
Addition
Axiom A0 (base case for addition). $n+0=n$.
Axiom A1 (recursion for addition). $m+\sigma(n) = \sigma(m+n)$.
Multiplication
Axiom M0 (base case for multiplication). $n\cdot 0=0$.
Axiom M1 (recursion for multiplication). $m\cdot\sigma(n) = m+m\cdot n$.
Order
Axiom I (less than or equal to). $m \leq n \equiv \exists k.m+k=n$
While not absolutely necessary, the following definitions are convenient.
Definition . We define the usual base ten representation of natural numbers as illustrated in the following table.
| base-ten | definition | equivalently |
|---|---|---|
| 1 | $\sigma(0)$ | $\sigma(0)$ |
| 2 | $\sigma(1)$ | $\sigma(\sigma(0))$ |
| 3 | $\sigma(2)$ | $\sigma(\sigma(\sigma(0)))$ |
| 4 | $\sigma(3)$ | $\sigma(\sigma(\sigma(\sigma(0))))$ |
| 5 | $\sigma(4)$ | $\sigma(\sigma(\sigma(\sigma(\sigma(0)))))$ |
| : | : | : |
So each natural number is defined by the number of $\sigma$'s applied to zero, and the successor of each natural number is the next counting number in order.
Once we have determined the basic properties that follow from our definitions, we can move on to deeper theorems that provide us with important non-obvious insights into the nature of the natural numbers. The study of such theorems is called Number Theory. We begin with some additional definitions. All variables are arbitrary natural numbers. \newline
Number Theory Definitions
| Name | Rule |
|---|---|
| less than | $m<n ~\iff~ m\leq n \xand m\neq n$ |
| positive | $n$ is positive $~\iff~ 1\leq n$ |
| divides | $m\mid n ~\iff~ \exists k. n=k\cdot m$ |
| even | $n$ is even $~\iff~ 2\mid n$ |
| odd | $n$ is odd $~\iff~ n$ is not even |
| composite | $n$ is composite $~\iff~ \exists k. 1<k<n \xand k\mid n$ |
| prime | $n$ is prime $~\iff~ 1<n \xand n$ is not composite |
As usual, we can derive useful rules from these succinct definitions.
Number Theory Definitions
Declare $\lt$, is, positive, $\mid$, even, odd, composite, prime to be constants.
less than $m \lt n$ $~\equiv~$ $m\leq n$, $m\neq n$
positive $n$ is positive $~\equiv~$ $1\leq n$
divides If $m \mid n$ then $n=k\cdot m$ for some $k$
divides If $n=k\cdot m$ then $m \mid n$
even $n$ is even $~\equiv~$ $2\mid n$
odd $n$ is odd $~\equiv~$ $n$ is not even
composite
If $n$ is composite then
$1<k$, $k<n$, and
$k|n$ for some $k$
composite
If $1<k$, $k<n$, and
$k|n$ then
$n$ is composite
prime
$n$ is prime $~\equiv~$ $1<n$ and
$n$ is not composite
The natural numbers have two very different but very useful applications in mathematics (and outside of mathematics in general).
On the one hand, they are useful for counting. For that we use natural numbers to indicate how many items are in some collection. Natural numbers used in this way are examples of cardinal numbers, which are used to measure the relative sizes, or cardinality of collections of items. The branch of mathematics that studies cardinality and counting is called combinatorics. We will discuss that in detail later in the course.
On the other hand, natural numbers are useful for numbering items to put them in some order, a first item, second item, and so on. Natural numbers used in this way are examples of ordinal numbers and are used to indicate the relative positions of items in an ordered list of items. Such ordered lists are called sequences, which we study next.
The following theorems can be proved in the order shown. Therefore, you can use an earlier theorem as a rule of inference in the proof of a later theorem but not vice versa. These should be proved with a semiformal proof using the shortcuts described in Chapter 6.
Properties of the successor function
Nonzero implies successor$\forall n. n\neq 0\implies \exists m. n=\sigma(m)$
No number is its own successor$\forall n. n\neq\sigma(n)$
Properties of addition
Alternate definition of $\sigma$$\forall m. \sigma(m) = m+1$
Associativity of addition$\forall m.\forall n.\forall p. m+(n+p)=(m+n)+p$
Additive Identity$\forall m. 0+m=m=m+0$
Commutativity of Adding 1$\forall m. 1+m=m+1$
Commutativity of addition$\forall m.\forall n.m+n=n+m$
Zero sums$\forall m.\forall n. m+n=0 \implies m=n=0$
Cancellation Law of addition$\forall m.\forall n.\forall p. m+p=n+p \implies m=n$
Properties of multiplication
Left multiplication by 0$\forall m. 0\cdot m=0$
Multiplicative identity$\forall m. 1\cdot m=m=m\cdot 1$
Left Distributive Law$\forall m.\forall n.\forall p. p\cdot(m+n)=p\cdot m+p\cdot n$
Right Distributive Law$\forall m. \forall n.\forall p. (m+n)\cdot p=m\cdot p+n\cdot p$
Commutativity of multiplication$\forall m.\forall n. m\cdot n = n\cdot m$
Associativity of multiplication$\forall m.\forall n. \forall p. (m\cdot n)\cdot p = m\cdot(n\cdot p)$
Zero divisors$\forall m.\forall n. m\neq 0 \xand m\cdot n=0 \implies n=0$
Cancellation Law of multiplication$\forall p.p\neq 0\implies \forall m.\forall n. p\cdot m=p\cdot n \implies m=n$
Properties of order
Nonzero is positive$\forall n. 0\leq n \xand (0<n \xiff n\neq 0)$
Successors are bigger$\forall n.n<\sigma(n)$.
Alternate definition of $<$$\forall m.\forall n. m<n \xiff \exists k. k\neq 0\xand m+k=n$
Minimum difference$\forall m.\forall n. m<n \xiff \sigma(m)\leq n$
Reflexivity of $\leq$$\forall n. n\leq n$
Antisymmetry of $\leq$$\forall m.\forall n.m\leq n \xand n\leq m \implies m=n$
Transitivity of $\leq$$\forall m.\forall n.\forall p.m\leq n \xand n\leq p \implies m\leq p$
Irreflexivity of $<$$\forall n. \neg(n<n)$
Transitivity of $<$$\forall m.\forall n.\forall p.m<n \xand n<p \implies m<p$
Trichotomy$\forall m.\forall n.m<n \xor m=n \xor n<m$
Translation$\forall m.\forall n.\forall p. m<n \iff m+p<n+p$ This also holds if $<$ is replaced by $\leq$ or if $m+p<n+p$ is replaced by $p+m<p+n$.
Scaling$\forall m.\forall n.\forall p. p\neq 0 \implies (m<n \iff p\cdot m < p\cdot n$ This also holds if $<$ is replaced by $\leq$ or if $p\cdot m<p\cdot n$ is replaced by $$m\cdot p<n\cdot p$$
Some Number Theory
Divisibility of differences$\forall b.b\neq 0\implies \forall m.\forall n.\forall r. b\cdot m=b\cdot n+r \implies \exists p. r=b\cdot p$.
Division Algorithm - existence$\forall b.b\neq 0\implies \forall a.\exists q.\exists r. a=b\cdot q+r \xand 0\leq r < b$
Note that technically we do not need to state that $0\leq r$ since every natural number is greater than or equal to zero, but we include it here because the theorem also holds for the set of integers.
Division Algorithm - UniquenessFor all $b\neq 0$ and all $a,q,r,s,t$, if $$\begin{align*} &\text{(a) }a=bq+r \text{ and } 0\leq r < b \\ &\text{(b) }a=bs+t \xand 0\leq t<b \end{align*} $$ then $q=s$ and $r=t$.
Everything divides zero$\forall m. m\mid 0$
Every number divides itself$\forall m. 1\mid m \xand m\mid m$
Divisors are smaller$\forall m.\forall n.n\neq 0 \xand m\mid n \implies m\leq n$
Divisors divide products$\forall m.\forall n.\forall p. m\mid n \implies m\mid n\cdot p$
Common divisors divide sums$\forall m.\forall n.\forall p.p\mid m \xand p\mid n\implies p\mid (m+n)$
Common divisors divide differences$\forall m.\forall n.\forall p.p\mid m \xand p\mid m+n\implies p\mid n$
Divisibility is transitive$\forall m.\forall n.\forall p.m\mid n \xand n\mid p\implies m\mid p$
Mutual divisors are equal$\forall m.\forall n.m\mid n \xand n\mid m\iff m=n$
Miscellaneous Exercises
$\forall m. \forall n. m^2\mid n\implies m\mid n$
$2$ is prime.
As we did with logic, once we have proven major results about the natural numbers and number theory, we can add those theorems to our list of rules to justify statements in our proofs. Here are some of the major results we can add to our context as we move on to other topics or explore number theory more deeply.
The following variant of induction is called strong induction.
Theorem (strong induction). Let $\mc{P}(n)$ be any statement about a natural number variable $n$. Then $$ \mc{P}(0) \xand \Big(\forall k.\big(\forall j.j\leq k\implies \mc{P}(j)\big) \implies \mc{P}(\sigma(k)) \Big) \implies \forall n.\mc{P}\left( n\right) \text{.} $$
As usual, we can derive a more useful rule from this theorem.
Strong Induction
Given
$\mc{P}(0)$
Let $k$ be such that $\forall j.j\leq k \implies
\mc{P}(j)$
$\mc{P}(\sigma(k))$
Conclude $\forall n.\mc{P}(n)$
It can be shown that Strong Induction and ordinary Induction are logically equivalent. Namely, we can prove Strong Induction as a theorem in the axiom system defined above, and also if we replace the induction axiom with strong induction, we can prove ordinary induction holds as a theorem.
Problem
Prove that the original statement of the principle of induction is equivalent to strong induction.
The following rules are derived from the corresponding problems above.
Number Theory Theorems
Theorem (alternate definition of $\sigma$) $$\sigma(n)=n+1$$
Theorem (commutativity of addition) $$m+n=n+m$$
Theorem (associativity of addition) $$(m+n)+p=m+(n+p)$$
Theorem (addition of zero on the left) $$0+n=n$$
Theorem (multiplication by zero on the left) $$0\cdot n=0$$
Theorem (identity of multiplication)
$1\cdot n=n$ and $n\cdot 1=n$
Theorem (commutativity of multiplication) $$m\cdot n=n\cdot m$$
Theorem (associativity of multiplication) $$(m\cdot n)\cdot p=m\cdot (n\cdot p)$$
Theorem (distributive property of $\cdot$ over $+$) $$m\cdot (n+p)=m\cdot n+m\cdot p$$ $$(n+p)\cdot m=n\cdot m+p\cdot m$$
