Exercise 2.2.3 (Basic properties of order for natural numbers)

Question

Prove Proposition 2.2.12. (Hint: you will need many of the preceding propositions, corollaries, and lemmas.)\par 

	extbf{Proposition 2.2.12} Let $a,b,c$ be natural numbers. Then
ewline
(a) (Order if reflexive) $a \geq a$.
(b) (Order is transitive) If $a \geq b$ and $b \geq c$, then $a\geq c$.
ewline
(c) (Order is anti-symmetric) If $a\geq b$ and $b\geq a$, then $a=b$.
ewline
(d) (Addition preserves order) $a \geq b$ if and only if $a+c \geq b+c$.
ewline
(e) $a < b$ if and only if $a{{+}\!{+}} \leq b$.
ewline
(f) $a < b$ if and only if $b=a+d$ for some \emph{positive} number $d$.

Issa Rice · Accepted Answer

extbf{How to think about the exercise.} Each part of the exercise is pretty straightforward. It is tiring to write down everything, but at this stage it is good for your soul.\par

extbf{Model solution.}
ewline
(a) To show that $a\leq a$ we must show that $a = a + m$ for some natural number $m$. Pick $m:=0$. Then by Lemma 2.2.2 we see that $a+m = a+0 = a$ as required.\par

(b) Suppose $a \geq b$ and $b \geq c$, thus there are natural numbers $n,m$ such that $a = b+n$ and $b=c+m$. We want to show that $a = c + r$ for some natural number $r$. Pick $r := m+n$. Then $c+r = c + (m+n) = (c+m) + n = b+n =a$ by the associativity of addition (\href{./exercise_2-2-1}{Proposition 2.2.5}).\par

(c) Suppose $a\geq b$ and $b\geq a$, thus there are natural numbers $n,m$ such that $a = b+n$ and $b = a+m$. Thus we see that $a = (a+m)+n = a + (m+n)$ by associativity of addition (\href{./exercise_2-2-1}{Proposition 2.2.5}). By the cancellation law (Proposition 2.2.6) we see that $0 = m+n$ and so by Corollary 2.2.9 we conclude that $m=0$ and $n=0$. Thus $a = b+n = b + 0 = b$ by Lemma 2.2.2.\par

(d) Suppose $a \geq b$, so that we have a natural number $n$ such that $a = b+n$. By adding $c$ to both sides, we obtain $a+c = (b+n)+c$. By associativity and commutativity of addition, we have $(b+n)+c = b + (n+c) = b+(c+n) = (b+c)+n$. Thus $a+c = (b+c) + n$, which means $a+c \geq b+c$.\par

Now suppose $a+c \geq b+c$, thus $a+c = (b+c) + n$ for some natural number $n$. We have $(b+c) + n = b+(c+n) = b+(n+c) = (b+n)+c$ by associativity and commutativity of addition. Thus $a+c = (b+n)+c$, so by cancellation we have $a = b+n$, which means $a \geq b$.\par

(e) Suppose $a<b$. Thus $a \leq b$, which means $b = a+n$ for some natural number $n$, and we also know that $a
e b$. If $n=0$, then $b=a+0=a$ which would contradict the fact that $a
e b$. Thus $n$ is positive. By \href{./exercise_2-2-2}{Lemma 2.2.10} this means that there is a natural number $m$ such that $m{{+}\!{+}} = n$. But now we have
\begin{align*}
b &= a + (m{{+}\!{+}}) \ 
&= (a+m){{+}\!{+}} \
&= (m+a){{+}\!{+}} \
&= m+(a{{+}\!{+}}) \
& = (a{{+}\!{+}}) + m
\end{align*}
by repeated applications of Lemma 2.2.3 and Proposition 2.2.4. Thus we see that $b \geq a{{+}\!{+}}$.
ewline

Now suppose $a{{+}\!{+}} \leq b$. Thus $b = (a{{+}\!{+}}) + n$ for some natural number $n$. We have $(a{{+}\!{+}}) + n = (a+n){{+}\!{+}} = a+ (n{{+}\!{+}})$ by Definition 2.2.1 and Lemma 2.2.3. Thus $b = a+ (n{{+}\!{+}})$, which means that $b \geq a$. If $b = a$, then by cancellation we would have $0 = n{{+}\!{+}}$, which contradicts Axiom 2.3. Thus $b 
e a$, which combined with $b\geq a$ means that $b > a$ as required.\par

(f) Suppose $a<b$. In the first part of the proof of part (e), we already showed that $b = a+n$ for positive $n$.
ewline

Now suppose $b=a+d$ for some positive number $d$. Since $d$ is a natural number, we have $b \geq a$. It remains to show that $a
e b$. Suppose for contradiction that $a=b$. Then by cancellation we have $0=d$, which means $d$ is not positive, a contradiction. Thus $a
e b$ as required.\par

Source: \href{https://issarice.com/}{Issa Rice's blog}.

Khagan Gulusoy · Answer

\begin{proof} \begin{enumerate}[label=(\alph*)] \item extit{(order is reflexive)} By extit{Definition 2.2.11}, $a\geq a$ iff there exists a natural number $b$ such that $a = a+ b$. Since $a = a + 0$ by extit{Definition 2.2.11}, the assertion $a \geq a$ follows by setting $b:=0$. \item (order is transitive) By Definition 2.2.11, we have to show that there exists a natural number $n$ such that $a = c + n$. By extit{Definition 2.2.11}, since $a \geq b,$ then $a = b + m,$ where $m$ is some natural number. By extit{Definition 2.2.11} again, since $b \geq c,$ $b = c + l$, where $l$ is some natural number. Thus, we get: $$a = b + m = (c + l) + m.$$ Setting $n := l + m$, we obtain the desired result. \item (order is anti-symmetric) extit{Definition 2.2.11}, we have: $$a = b + m, ext{ for some natural number }m.$$ $$b = a + n, ext{ for some natural number }n.$$ Substituting $a$ into the equation for $b$, we get $$b = (b + m) + n.$$ By the cancellation law ( extit{Proposition 2.2.6}), from $b + 0 = b + (m+n)$, we deduce $$0 = m + n.$$ By the extit{Corrolary 2.2.9}, we must have $m=0$ and $n=0$. In other words, $a = b$. \item extit{(addition preserves order)} We demonstrate both implications. \begin{description} \item[$\implies$] \begin{remark} Note that the other direction for the cancellation law holds also. To see why, assume that $b = c$. Then it is true from the axioms of equality that $b + a = b + a.$ By substituting $b=c$ into that equation, we trivially get $b + a = c + a.$ Thus, we can add a natural number from both sides of an equation. \end{remark} By extit{Definition 2.2.11}, we have: $$a = b + m, ext{ for some natural number $m$.}$$ By the remark, the following statement $$a + c = b + m + c$$ is true for all natural numbers $c.$ Thus, $$a + c \geq b + c,$$ as desired. \item[$\impliedby$] By extit{Definition 2.2.11}, we get: $$a + c = b + c + x, ext{ where }x ext{ is some natural number.}$$ By the cancellation law, $$a = b + x,$$ which means by extit{Definition 2.2.11}, that $a\geq b.$ \end{description} \item[(f)] We first demonstrate that part (f) holds, since it is easier to prove part (e) using part (f). \begin{description} \item[$\implies$] By Definition 2.2.11, $a < b$ means that $b = a + d$ for some natural number $d$ and that $b eq a$. Assume for the sake of contradiction that $d$ is not positive. Since $d$ is natural, it must be zero by definition. Therefore $b = a + 0$. By Definition 2.2.1, $b = a$ - a contradiction. \item[$\impliedby$] Now suppose that $b = a + d$ for some positive number $d$. To prove that $b > a$ we must additionally demonstrate that $b eq a$. Suppose for the sake of contradiction that $b = a$. Then, $a = a + d$, or $a + 0 = a + d$. By the cancellation law (Proposition 2.2.6), $0 = d$ - a contradiction. \end{description} \item[(e)] \begin{description} \item[$\implies$] The statement we should prove in this case is: $$aa$ by the part (f) of this theorem. This proves the assertion. \end{description} \end{enumerate} \end{proof}

Exercise 2.2.3 (Basic properties of order for natural numbers)

Answers

Comments

Comments

Exercise 2.2.3 (Basic properties of order for natural numbers)

Answers

Comments

Comments

Add answer