3

I'm learning the fundamentals of discrete mathematics, and I have been requested to solve this problem:

According to the set of natural numbers

$$ \mathbb{N} = {0, 1, 2, 3, ...} $$

write a definition for the less than relation.

I wrote this:

$a < b$ if $a + 1 < b + 1$

Is it correct?

InfZero
  • 875
  • 7
    No. You are using the < in its own definition! – The Chaz 2.0 Jan 19 '16 at 17:08
  • 1
    Maybe this works: $a<b$ if there is an $n\in\mathbb N$ so that $n\neq 0$ and $a+n=b$? – Asinomás Jan 19 '16 at 17:14
  • 1
    Um, no. How do you determine a + 1 < b +1? That is circular at best. – fleablood Jan 19 '16 at 17:21
  • 2
    @TheChaz that can happen in a recursive definition. – miracle173 Jan 19 '16 at 17:24
  • @miracle173 but a recursive definition requires a base definition; And this condition goes the wrong way. It defines a < b from a+1 < b+1 from which wed have to derive that from a + 2 < b + 2.... So a recursive definite requires a base case: i) 0 < b if .... something .... and then ii) a + 1 < b + 1 if ...something about a and b. – fleablood Jan 19 '16 at 17:28
  • @fleablood you are right (I posted an answer that uses this definition). But your comment and my answer also use $\lt$ in its own definition. So I think the comment of TheChaz is not well stated. – miracle173 Jan 19 '16 at 17:36
  • @miracle173 I'd modify the chaz comment to allow recursion which, if we are going to get pendantic, requires the defining case to be distinct from the defined case and also requires a base case for reference. – fleablood Jan 19 '16 at 17:56
  • I am not sure if there is a fundamental difference between your answer and my answer but at least you were able to avoid the word "finally". – miracle173 Jan 19 '16 at 18:00
  • Here's a much harder question: Let's say the base set is $\Bbb Z$, the set of integers, and you want to define $<$. Now, $\exists n:a+n=b$ is always true; just let $n$ be $b-a$. – Akiva Weinberger Jan 19 '16 at 18:09
  • 1
    Here's one answer: Lagrange's four-square theorem says that every nonnegative integer can be written as the sum of four squares. Thus, $a\le b$ is equivalent to:$$\exists m,\exists n,\exists p,\exists q:\a+m\times m+n\times n+p\times p+q\times q=b$$For $a<b$, stick a "$+1$" right before the equals sign. – Akiva Weinberger Jan 19 '16 at 18:11
  • @TheChaz2.0 Yes but recursive definitions have to bottom-out, and this one never will. – BrianO Jan 19 '16 at 23:52

5 Answers5

6

$a<b \iff \exists p \in \mathbb{N_{>0}}$: $b=a+p$.

Andres Mejia
  • 20,977
  • 2
    I voted for this answer because of its concision without loss of precision. – daOnlyBG Jan 19 '16 at 17:42
  • 1
    You might want to specify $p\ne 0$, since in this question $\mathbb N$ includes $0$. – Trevor Norton Jan 19 '16 at 17:44
  • I see you do enjoy concision by your edit, haha. In case O.P does not understand math symbols, this means: $a<b$ if and only if there exits some natural number $p$ such that $b=a+p$. – Andres Mejia Jan 19 '16 at 17:45
  • @daOnlyBG Maybe it seems to be concise because it uses not much characters. But you first have to define the + binary operator. The answer of Nephente is similar to this answer but avoids + and uses only the successor operator. – miracle173 Jan 19 '16 at 17:54
  • I do not think that following from the peano axioms really suggests pedagogical soundness. I'm do not think that in a discrete math course, anyone would really expect that. Further, $+$ is the only associative binary operation where $s(n)=n+1$, not very hard to define. – Andres Mejia Jan 19 '16 at 17:59
  • @AndresMejia nah, it was very concise before I even touched it. I reasoned that since the OP is probably taking an introductory to discrete logic course, I thought I'd throw around some quantifier symbols that he's seen in class lately. – daOnlyBG Jan 19 '16 at 18:38
  • 1
    @miracle173 That's fair. Nephente's answer is deeper and more thorough. For the level of the OP's question, though, and from what I suspect the OP's class entails, I still believe AndresMejia's response is a bit more appropriate. – daOnlyBG Jan 19 '16 at 18:40
5

Regarding to this particular set, you can define $<$ as $a < b$ if $b - a \in \mathbb{N}$ and $b - a \neq 0$.

Zhanxiong
  • 14,040
3

How can you decide if $3<5$ using your definition? You can say $3<5$ if $4<6$ if $5<7$ and so on, but this sequence will never end.

It works the other way round:

  • if $b \ne 0$: $0 \lt b$
  • if $a \lt b$: $a+1 \lt b+1 $

$2 \ne 0$ , so $0 \lt 2$, therefore $1 \lt 3$, therefore $ 2 \lt 4$ , and finally $3 \lt 5$

miracle173
  • 11,049
  • "finally" - ??? – The Chaz 2.0 Jan 19 '16 at 17:36
  • 1
    @TheChaz2.0: Maybe it seemed that way when miracle173 was typing. :-P – Brian Tung Jan 19 '16 at 17:42
  • @TheChaz: what is wrong with finally? Is it not possible to use this word here? – miracle173 Jan 19 '16 at 17:43
  • 1
    @miracle173: I think it was fine; I don't know that the question was that serious. It is a little funny because there's really only three steps (it's not as though you had to show $77 < 79$), but it didn't throw me at all when reading it. – Brian Tung Jan 19 '16 at 17:58
  • There's nothing terribly wrong with the word - it just seemed funny that a word with such finality would be used to demonstrate $3 < 5$, a fact almost irrelevant to the task at hand. – The Chaz 2.0 Jan 20 '16 at 04:29
2

A way to think about the natural numbers is in terms of the Peano Axioms. There exists a "successor" map

$$ S: \mathbb{N}\rightarrow \mathbb{N} $$ such that in particular

  • $S(0) = 1 $
  • $0\notin S(\mathbb{N}) $

The action of $S$ is usually written as $S(n) =: n+1$ The ordering of $\mathbb{N}$ may then be defined as

$$ a\leq b :\Longleftrightarrow \exists k\in\mathbb{N}: S^k(a) = b$$

where the $k$-th power is understood as $k$ fold application of $S$.

This is essentially the same answer already given by Solitary.

Nephente
  • 271
1

You can either have a direct definition or a recursive definition. If you have a recursive definition you need a base case from which all cases arrive.

Your function appears to be recursive but it has no base case.

a < b if a + 1< b + 1 which raises the question what is the definition of a + 1 < b + 1 to which a + 1 < b+a if a + 2 < b +2, and final verification is pushed further and further away.

So if you are going to do recursion, you need a base case involving 0

  1. $0 < b$ if $b \ne 0$

Now your definition $a < b$ if $a + 1 < b + 1$ ... isn't good because it is taking you away from the base case. We need a definition that either a) takes you from the base case to $a < b$ or b) takes you from $a < b$ to the base case.

Either

2a. $a < b $ if $a - 1 < b -1$ (allows the user to start at $a<b$ and work down to $0 < b'$)

Or

2b. if $a < b$ then $a + 1 < b + 1$ (allows the user to start at $0<b'$ annd work up to $a < b$)

will do. Which one you like is a matter of taste.

====

Then there is a direct definition. This is less obvious to see but more "powerful" and ,ahem, direct to use. When is $a < b$ true? It's true when $0 < b- a$ which, as these are natural numbers rather than integers, is true whenever $b - a \ne 0$ and $b - a$ is a legitimate natural number.

So

  • $a < b$ if $b - a \ne 0$ and $b - a \in \mathbb N$.
fleablood
  • 124,253