Proof that addition preserves order

796 Views Asked by At

Definition: Let $a$ and $b$ be natural numbers. We say that $a \geq b$ (or $b \leq a$) iff we have $a = b + m$ for some natural number $m$.

Claim: $a \geq b$ iff $a + c \geq b + c$ for any natural number $c$.

Proof: We must show that $\forall c, (a \geq b \implies a + c \geq b + c)$ and that $\forall c (a + c \geq b + c \implies a \geq b)$

First we prove $a + c \geq b + c \implies a \geq b$. By definition, $a + c = b + c + m$ for some natural number $m$. By cancellation law, $a = b + m$ which means $a \geq b$.

Next we prove $a \geq b \implies a + c \geq b + c$. We induct on $c$. When $c=0$, we see that $a \geq b \implies a + 0 \geq b + 0$ which is true. During the inductive step we assume $a \geq b \implies a + c \geq b + c$ and need to show that $a \geq b \implies a + c + 1 \geq b + c + 1$. I'm not 100% sure where to go from here.

Edit: Maybe this: $a + c + 1 \geq b + c + 1$ means $a + c + 1 = b + c + 1 + m$ for some $m$. By cancellation law, $a = b + m$. Therefore $a \geq b \implies a + c \geq b + c = a \geq b$ which is true. I guess this also means we didn't need induction since I didn't even use the inductive hypothesis.

2

There are 2 best solutions below

6
On BEST ANSWER

If $a \ge b$ then $a= b+m$ for some $m$.

But since $a+1=a+1$ we thus have that $a+1= b+m+1 =b+1+m$, and so $a+1 \ge b+1$

3
On

Suppose that $a\geq b$, then $a=b+m$ for some natural $m$. If $c\in\mathbb{N}$, then $a+c=b+c+m$, so $a+c\geq b+c$, because $m\in\mathbb{N}$, and the definition is met. No need for induction.