It is important for the exercises in this section that we don't assume results or knowledge that we have held as obvious for most of our lives, like $a+b = b+a$. Here we need to prove results using only the given axioms and definitions.
Let's remind ourselves of these Peano axioms.
Axiom 2.1 0 is a natural number.
Axiom 2.2 If $n$ is a natural number, then $n++$ (successor to $n$) is also a natural number.
Axiom 2.3 0 is not the successor of any natural number.
Axiom 2.4 Different natural numbers must have different successors.
Axiom 2.5 (Principle of mathematical induction). Let P(n) be any property of a natural number $n$. Suppose $P(0)$ is true. Suppose also that if $P(n)$ is true, then so is $P(n++)$. Then $P(n)$ is true for all natural numbers $n$.
Let's illustrate the use of these axioms to prove that "4 is not equal to 0". This may seem obviously true, but we need to justify it based on the axioms, and only the axioms. We can say that 4 is the successor to 3, that is $4=(3++)$. Axiom 2.3 says that 0 is not the successor if any natural number, including 3. So 0 is not 3++, that is 0 is not 4. $\square$
This may feel laborious, and it is, but it is the only way to answer really explain why "4 is not 0", in a way that can't be refuted if we agree on the minimal Peano axioms.
Addition is defined as follows.
Definition 2.2.1 (Addition of natural numbers). Let $m$ be a natural number. To add zero to $m$, we define $0 + m := m$. Now suppose inductively that we have defined how to add $n$ to $m$. Then we can add $(n++)$ to $m$ by defining $(n++) + m := (n + m)++$.
The symbol $:=$ means definition. To get a feel for how this definition works, let's ask what $2+m$ is. Using the Definition 2.2.1 we have $0 + m:=0$, then
$$1+m = (0++) + m := (0+m)++ = m++$$
We then have
$$2 + m = (1++) +m := (1 + m) ++$$
We now know $1+m=m++$ so
$$2+m = (m++)++$$
This allows us to say $3+m = ((m++)++)++$, that is, the third successor of $m$.
Let's practice using the definition of addition to show another apparently obvious statement that "$n+0=n$" for all natural numbers $n$. We might be tempted to say that this is actually in the definition, but it isn't. The definition defines $0+m$, not $m+0$. We haven't yet justified that addition is commutative.
We'll use induction to show that $n+0=n$. Following the template for inductive proofs, we define the base case for $n=0$, that is $0+0=0$. Is this true? It is the definition which says $0+m:=m$ taken with $m=0$.
Next is the inductive step. The inductive hypothesis is that the proposal $n+0=n$ is true for all natural numbers $n$. We have to use the inductive hypothesis to show that the proposal is true for $n++$, that is $(n++) + 0 = (n++)$. We use Definition 2.2.1 with $m=0$ to say $(n++) + 0:= (n+0)++$. The inductive hypothesis says $n+0=n$ so we have $(n++) + 0 = (n++)$, showing the proposal is true for $n++$. Because we've shown the proposal is true for the base case $n=0$, and also shown that if it is true for $n$ then it is also true for $n++$. By induction, Axiom 2.5, the proposal is proven for all natural numbers $n$. $\square$
This all seems laborious, and it is. But experiencing how we can build up familiar, and seemingly obvious, mathematics from a minimal set of axioms is important.
Exercise 2.2.1
Prove addition is associative. For any natural numbers $a$, $b$, $c$, we have $(a+b)+c = a + (b+c)$.
We can't use our existing knowledge to justify this. We have to prove it using only the axioms and definition of addition.
Let's use induction.
The proposal $P(a)$ says $(a+b)+c = a + (b+c)$.
The base case $P(0)$ is
$$(0+b) + c = 0 + (b+c)$$
From the definition of addition, we know that $)+m:=m$, which means
$$(b) + c = (b+c)$$
So $P(0)$ is true.
The inductive hypothesis is that $P(a)$ is true. That is
$$(a+b)+c = a + (b+c)$$
We need to show that $P(a++)$ is also true. That is,
$$((a++) + b) + c = (a++) + (b + c)$$
Let's consider the LHS, and twice apply $(n++) + m := (n + m)++$ from the definition of addition.
$$\begin{align} ((a++) + b) + c &= ((a + b)++) + c \\ &= ((a+b) + c) ++ \end{align}$$
Now let's apply the inductive hypothesis,
$$((a++) + b) + c = (a + (b+c)) ++ $$
Finally, we can use the definition again
$$\begin{align} ((a++) + b) + c &= (a + (b+c)) ++ \\ &= ((a++) + (b+c)) \end{align}$$
This the the RHS of $P(a++)$.
To summarise, we have shown:
- the base case $P(0)$ is true
- if $P(a)$ is true, then $P(a++)$ is true
So by induction (Axiom 2.5) we can say the proposal is true for all natural numbers $a$. $\square$
No comments:
Post a Comment