Definability of the $<$ order relation on the natural numbers using addition.

Question

Show that the usual order relation $<$ on the natural numbers is definable in the structure $(\mathbb{N}, +)$ with only addition.

My teacher has clarified this for me and quantifiers can be used. My teacher has explained that we can define $a < b$ iff there exists a $c$ such that $(a+c=b)$ and $c$ cannot equal zero. He also explained it is enough to write not$(a=b)$ since this would only hold if we had the less than or equal to order relation, but here we have just the $<$ order relation. I was just wondering if someone can clarify this answer for me. Does this hold for any $a$, $b$ and $c$ in the natural numbers (besides $c=0$ of course)? Possibly can someone clarify this using an example with actual natural numbers. Thank you!

Answer 1

Following the suggestion of your teacher, you can use the property that $a < b$ if and only if there exists a $c \not= 0$ such that $(a+c=b)$. Now, in order to translate this property into a first order formula, you first need to express the condition $c \not= 0$. But for this part, you can use another trick: $c \not= 0$ iff $c + c \not= c$. In summary, the following formula expresses the property that $a < b$: $$ \exists c\ \bigl(\neg(c + c = c) \wedge (a+c = b)\bigr) $$

Answer 2

I see two ways of interpreting this question. Because I do not know what class you are taking and how material has been presented or what the goals of your class are, I do not know which one is applicable.

1) You have an intuitive "magical" idea of what "<" means but, if you stop and think about it, it has never been defined except circularly "a < b" means "b is a bigger number than a".

The objective is to show that defining "a < b" as "there exist a positive natural number c, such that a + c = b" is a definition.

If we assume that whatever "being a bigger number" means, that "a < b" means "a $\pm$ x < b $\pm$ x" because "adding or subtracting the same thing from smaller and bigger numbers maintains the relationship" then:

$a < b \implies$

$a - a < b - a \implies$

$0 < b-a$

Let $c := b-a$. Then $c$ is a positive natural number so that $a + c = a + b -a = b$.

That's half the proof.

If $c$ is positive and $a + c = b$ then

Then $0 < c$ (that's what positive means)

So $0 + a < c + a$

So $a < c + a = b$.

That's the other half.

2) If this is a more advanced abstract class then although we were originally taught that "<" means "is a smaller number than", in actuality "<" is an abstract concept called an "order". A total order is defined as a relationship where:

i) given elements a and b: exactly one and only one of the following apply: a < b; b< a; or a = b.

ii) a < b and b < c then a < c.

An abstract example: if S = {baboons, elephants, giraffes, lions} and

baboons < elephants, baboons < giraffes, baboons < lions, elephants < giraffes, elephants < lions, giraffes < lions

Then "<" is a total order.

So if we define "a < b" as "there exists a positive natural c such that a + c = b" show that "<" is a total order.

i) Show that one and only one of the follow are true.

a + c = b; b + c' = a; a = b

If a + c = b and b + c' = a then a + c + c' = a implies c + c' = 0 so two positive numbers add to 0 which is impossible. So only one of a +c = b and b + c' = b are possible.

If a = b then a + c = b implies c = b - a = 0 and b + c' =a implies c' = a - b = 0.

So only one of the three are possible.

Suppose none of them are true then $a \ne b$ so $a - b \ne 0$ so either $a - b$ is positive or $a - b$ is negative. If $a - b$ is positive then $b + (a-b) = a$ and if we let $c' = a - b$ the second is true. If $a - b$ is negative then $b-a$ is positive and $a + (b-a) = b$ so if we let $c = b-a$ then the first is true.

So at least one is true and at most one is true so exactly one is true.

ii) Show if $a + c = b$ and $b + c' = d$ then there is a positive $\overline{c}$ such that $a + \overline{c} = d$.

Let $\overline{c} = c + c'$. As $c$ and $c'$ are positive natural numbers their sum is too.

$a + \overline{c} = a + (c + c') = (a + c) + c' = b + c' = d$.

So both conditions hold. "there existing a positive natural c so that a + c = b" is a total order.