Considering sets in proofs

Question

In order to show that $\forall x\gt0, \ \exists n_0\in \mathbb N: \ n_0(n_0+1)\le x\lt (n_0+1)(n_0+2)$, the proof in my textbook considers the set $A=\{n\in \mathbb N :n(n+1)\le x\}$ and then goes to show that $A$ has a maximal element $n_0$, which completes the proof.

Now, I want to know what has led to this kind of argument, because I have begun to see it very frequently and even some of my classmates often use this method. But to me it doesn't seem to be very useful and I certainly wouldn't be able to tell if it's a good way to approach a certain proof.

I understand that such motivations usually can't be explained easily; in that case, I'm asking for other problems you know of that use a similar approach.

Answer 1

Everyone has their own way of proving things, and that's OK. The statement you made can be shown to be true in different ways, and what counts is that you prove it, not how you prove it. The way you learn how to prove it is that you prove many many other statements as well, and then you get used to it. Repetitio mater studiorum est.

However, if you want a path that leads to the particular proof, in this case, my thoughts would proceed as follows:

1. I look at the statement. OK, it's saying that I can squeeze any positive real $x$ between two numbers. OK, let's imagine the $x$ as some point on the positive real line.
2. Hmm, the two numbers, $n_0(n_0+1)$ and $(n_0+1)(n_0+2)$ are both integers.
3. Not only are they integers, they are two integers from a monotonically increasing sequence of integers, $a_n = n(n+1)$.
4. So... this sequence of integers, it's really a series of points on the real line. Let's imagine them as crosses. (yes, really, I do that. Don't judge) The order I draw them in is left to right.
5. So what I now have is the statement that there exist two crosses so that the previous cross is to the left of $x$, and the next one is to the right. Well... sure they do! I just need to find the last cross on the left of $x$, and the next one must be on the right of it (otherwise, the previous one wasn't the last one!).
6. OK, what I just said in point 5 can be said formally as "I need to find the maximum value of $n$ such that $a_n < x$. This can be rewritten formally as finding a maximum element from some set.

Once this train of thought concludes, I go down to really writing down the proof, and the proof "starts" with introducing the set. Sure, the proof does, but the thought process that lead me to the proof started long before.

Answer 2

For instance, let $a,b$ be natural numbers with $1\leq b\leq a$. Then consider the set $A=\{a-qb\mid a-qb\geq 0, q\geq 0\}$. Since the set of natural numbers is well-ordered, every nonempty subset $A$ of natural numbers has a least element, here $r = a-qb$ in $A$. It is then clear that $a=qb+r$ and $0\leq r<b$ is the remainder.

Answer 3

To answer your question

Now, I want to know what has lead to this kind of argument

Look at this part of the proof

and then goes to show that $A$ has a maximal element $n_0$, which completes the proof.

The way the set is build makes it trivial to show that the set is finite thus has a maximal element. This triviality is a reason why a set is used. Other proofs requiring existence of a maximal/minimal element might follow the same approach.

Of course the thinking process is going to be as outlined by 5xum.

Answer 4

This is not the only way to solve the problem, and arguably uses set theory when there is no need for it. You can prove the claim directly by an easy induction (which I am sure you can do). Also note that induction is necessary, whether or not hidden. It is logically non-trivial (and requires induction) to show that the set in your question has a maximum!