Exercise 2.2.3
Prove Proposition 2.2.12. (Basic properties of order for natural numbers). Let a, b, c be natural numbers. Then
(a) (Order is reflexive) $a \geq a$.
(b) (Order is transitive) If $a \geq b$ and $b\geq c$, then $a \geq c$.
(c) (Order is antisymmetric) If $a \geq b$ and $b \geq a$, then $a=b$.
(d) (Addition preserves order) $a \geq b$ if and only if $a+c\geq b+c$.
(e) $a < b$ if and only if $a++ \leq b$.
(f) $a < b$ if and only if $b=a+d$ for some positive number $d$.
(a) Order is reflexive) $a \geq a$
We'll be using Definition 2.2.11 which defines the greater-than-or-equal $\geq$ order relation. It says that $n$ is greater than or equal to $m$, that is $n \geq m$ , iff we have $n = m + a$ for some natural number $a$.
Does this order relation hold between $a$ and itself? Let's write it down symbolically using Definition 2.2.11,
$$ a \geq a \iff a = a + k $$
where $k$ is some natural number. We know from Lemma 2.2.2 that $n+0=n$, so we can say that relation can hold if $k=0$. $\square$
(b) (Order is transitive) If $a \geq b$ and $b\geq c$, then $a \geq c$.
Again, let's write out these relations using Definition 2.2.11,
$$ \begin{align} a &= b + k_1 \\ b& = c + k_2 \end{align} $$
where $k_1$ and $k_2$ is a natural number. We can substitute for $b$,
$$ a = (c + k_2) + k_1 $$
Since addition is associative, Proposition 2.2.5, we can rearrange the brackets,
$$ a = c + (k_2 + k_1) $$
This matches Definition 2.2.11 for the order relation $\geq$ where $(k_2 + k_1)$ is a natural number, allowing us to conclude $ c \geq c$. $\square$
We've assumed $(k_2 + k_1)$ is a natural number. Interestingly the book doesn't have a lemma stating that the sum of two natural numbers is a natural number, and we could prove it from Axion 2.2 and induction.
(c) (Order is antisymmetric) If $a \geq b$ and $b \geq a$, then $a=b$.
Let write these out using Definition 2.2.11,
$$ \begin{align} a &= b + k_1 \\ b& = a + k_2 \end{align} $$
where $k_1$ and $k_2$ is a natural number. Again we can substitute for $b$,
$$ a = (a+ k_2) + k_1 $$
Since addition is associative, Proposition 2.2.5, we can rearrange the brackets,
$$ a = a + (k_2 + k_1) $$
Lemma 2.2.2 that $n+0=n$ tells us that $(k_2 + k_1)$ must be 0. Corollary 2.2.9 tells us this means both $k_2$ and $k_1$ nust be $0$. If this feels counterintuitive then remember natural numbers can't be negative, so the only way the sum of two can be $0$ is if both are $0$.
This leaves us with
$$\begin{align} a &= b + 0 \\ b& = a + 0 \end{align}$$
That is, $a=b$. $\square$.
(d) (Addition preserves order) $a \geq b$ if and only if $a+c\geq b+c$.
Here we must notice that "if and only if", or "iff", is a bidirectional implication, or biconditional.
$$ a \geq b \iff a +c \geq b + c $$
This means we need to prove this statement in both directions.
($\implies$). Let's start with the LHS and rewrite it using the order relation Definition 2.2.11.
$$ a = b + k$$
Now we increment both sides by $c$,
$$ a + c = (b + k) + c $$
Using Proposition 2.2.5 that addition is associative gives us,
$$ a + c = b + (k + c) $$
and Proposition 2.2.4 that addiiton is commutative gives us,
$$ a + c = b + (c + k) $$
Using Proposition 2.2.5 that addition is associative one more time gives us,
$$ (a + c) = (b + c) + k$$
This is the RHS, $a+c \geq b+c$.
($\impliedby$). Now we start from the RHS, and rewrite it using Definition 2.2.11,
$$ (a + c) = (b + c) + j $$
Using commutativity we get
$$ (c + a) = (c + b) + j$$
Using associativity we get
$$ c + a = c + (b + j) $$
Now we can use the cancellation law of Proposition 2.2.6
$$ a = b + j$$
This matches the Definition 2.2.11 for order relations, giving us the LHS
$$ a \geq b $$
Since we have proved the implication in both directions, the proof is complete. $\square$
It is worth commenting that most people would have demonstrated the validity of the statement in 2 lines, but our objective is to prove the statement using only the basic axioms and the few lemmas that have been proven at this point. That is the challenge, not showing the truth of the statement in a way that would convince most people.
(e) $a <b$ if and only if $a++ \leq b$
Here we must be careful of the direction of the order relation, and also note the bidirectional implication.
As usual, let's write this out using Definitition 2.2.11, with $j$ and $k$ natural numbers,
$$b = a + j \iff b = (a++) + k$$
where $b \neq a$ because $b > a$ by Definition 2.2.11 again.
($\implies$). Let's start with the LHS.
$$b = a + j $$
By definition, $b \neq a$. Lemma 2.2.2 says $n + 0 = n$. This means $j \neq 0$. If we set $h$ such that $h++ = j$, then $h$ can be any natural number, including $0$.
$$b = a + (h++)$$
Using commutativity, Proposition 2.2.4, we have
$$b = (h++) + a$$
Using the Definition 2.2.1 of addition, $(n++) + m := (n +m)++$, we have,
$$b = (h + a)++$$
And again by commutativity,
$$b = (a + h)++$$
And finally Definition 2.2.1 again,
$$b = (a++) + h$$
This is the RHS, $b \geq a++$.
($\impliedby$). Now let's consider the RHS, and write it using Definition 2.2.11,
$$b = (a++) + k$$
where $k$ is a natural number.
Using the same process as above, we shift the increment from $a$ to $k$,
$$b = a + (k++)$$
Now consider a positive number $q$ such that $k++ = q$.
$$b = a + q$$
Because $q \neq 0$, that means $b \neq a$, which matches the definition of the order relation $>$. That is $b > a$, the LHS.
Having proven the implication in both directions, the proof is complete. $square$
(f) $a < b$ if and only if $b=a+d$ for some positive number $d$.
Again, we note the bidirectional implication, and take care of the direction of the order relation.
($\implies$). Let's start with the LHS, and write it using the Definition 2.2.11,
$$ b = a + d$$
where $b \neq a$, and so $d \neq 0$ as argued above in (e). That means $d$ is a positive number.
($\impliedby$). Now let's consider the RHS
$$ b = a + d$$
where $d$ is a positive number. Since $d \neq 0$, that means $b \neq a$ and so by definition 2.2.11, we have a strict order relation, the RHS.
$$ b > a$$
Since we have proved the statement in both directions, the proof is complete. $\square$
No comments:
Post a Comment