3
$\begingroup$

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?

$\endgroup$
11
  • 7
    $\begingroup$ No. You are using the < in its own definition! $\endgroup$ Jan 19, 2016 at 17:08
  • 1
    $\begingroup$ Maybe this works: $a<b$ if there is an $n\in\mathbb N$ so that $n\neq 0$ and $a+n=b$? $\endgroup$
    – Asinomás
    Jan 19, 2016 at 17:14
  • 1
    $\begingroup$ Um, no. How do you determine a + 1 < b +1? That is circular at best. $\endgroup$
    – fleablood
    Jan 19, 2016 at 17:21
  • 2
    $\begingroup$ @TheChaz that can happen in a recursive definition. $\endgroup$
    – miracle173
    Jan 19, 2016 at 17:24
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 19, 2016 at 18:11

5 Answers 5

6
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ I voted for this answer because of its concision without loss of precision. $\endgroup$
    – daOnlyBG
    Jan 19, 2016 at 17:42
  • 1
    $\begingroup$ You might want to specify $p\ne 0$, since in this question $\mathbb N$ includes $0$. $\endgroup$ Jan 19, 2016 at 17:44
  • $\begingroup$ 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$. $\endgroup$ Jan 19, 2016 at 17:45
  • $\begingroup$ @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. $\endgroup$
    – miracle173
    Jan 19, 2016 at 17:54
  • 1
    $\begingroup$ @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. $\endgroup$
    – daOnlyBG
    Jan 19, 2016 at 18:40
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ "finally" - ??? $\endgroup$ Jan 19, 2016 at 17:36
  • 1
    $\begingroup$ @TheChaz2.0: Maybe it seemed that way when miracle173 was typing. :-P $\endgroup$
    – Brian Tung
    Jan 19, 2016 at 17:42
  • $\begingroup$ @TheChaz: what is wrong with finally? Is it not possible to use this word here? $\endgroup$
    – miracle173
    Jan 19, 2016 at 17:43
  • 1
    $\begingroup$ @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. $\endgroup$
    – Brian Tung
    Jan 19, 2016 at 17:58
  • $\begingroup$ 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. $\endgroup$ Jan 20, 2016 at 4:29
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .