Mg Problem 19


18. Definition of $<_{\mathbb{Z}}$:

$[(a,b)] <_{\mathbb{Z}} [(c,d)] \leftrightarrow a + d <_{\mathbb{N}} b + c$

Proof that this is well-defined, i.e. if it works for one element of the equivalence class, it works for all elements of the equivalence class.

Given $(a,b) ~ (\tilde{a},\tilde{b}$ and $(c,d) ~ (\tilde{c},\tilde{d}$, we know by the definitions that $a + \tilde{b} = \tilde{a} + b$ and $c + \tilde{d} = \tilde{c} + d$. Now, we must simply show that $(a,b) <_{\mathbb{Z}} (c,d)$ proves $(\tilde{a},\tilde{b}) <_{\mathbb{Z}} (\tilde{c},\tilde{d})$.

Assume $(a,b) <_{\mathbb{Z}} (c,d)$. From the definition, we know that $a+d <_{\mathbb{N}}b+c$. From here, we may, without altering the inequality, substitute for $a$ by substituting $\tilde{a} + b$ for $a$ and adding $\tilde{b}$ to the other side to get $\tilde{a} + b + d <_{\mathbb{N}} b + c + \tilde{b}$ and using cancellation on addition to get $\tilde{a} + d <_{\mathbb{N}} c + \tilde{b}$. Next, we may substitute $c+\tilde{d}$ for $d$ and add $\tilde{c}$ to the other side. Now we have $\tilde{a} + c + \tilde{d} <_{\mathbb{N}} c + \tilde{b} + \tilde{c}$ and apply cancellation on $c$ to end up with $\tilde{a} + \tilde{d} <_{\mathbb{N}} \tilde{b} + \tilde{c}$. By our definition of $<_{\mathbb{Z}}$, we can from here say that $(\tilde{a},\tilde{b}) <_{\mathbb{Z}} (\tilde{c},\tilde{d})$. Thus, the definition is well defined. $QED$.

Finally, we must prove that this extends the linear order under $<_{\mathbb{N}}$. A number, $a$ in $\mathbb{N}$ can be written in $\mathbb{Z}$ as $[(a,0)]$. Thus, we must show that if $a <_{\mathbb{N}} b$ then $[(a,0)] <_{\mathbb{Z}} [(b,0)]$. This can be simply done by applying the definition for $<_{\mathbb{Z}}$ to $[(a,0)] <_{\mathbb{Z}} [(b,0)]$ to get $a + 0 <_{\mathbb{N}} b + 0$. By the definition of addition on the naturals, we get get $a <_{\mathbb{N}} b$. $QED$

(Prof. Simmons, 3-30-18: Good. The typesetting didn't work out entirely; use \sim (yielding $\sim$) for the equivalence of two pairs of natural numbers.)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License