5
$\begingroup$

Hi everyone I wonder to myself if the next proof is correct. I would appreciate any suggestion.

Proposition: There is not a sequence of natural numbers which is infinite descent.

Proof: Suppose for contradiction that there exists a sequence of natural numbers which is infinite descent. Let $(a_n)$ be such sequence, i.e., $a_n>a_{n+1}$ for all natural numbers n.

We claim that if the sequence exists, then $a_n\ge k$ for all $k, n \in N$.

We induct on $k$. Clearly the base case holds, since each $a_n$ is a natural number and then $a_n \ge 0$ for all $n$. Now suppose inductively that the claim holds for $k\ge 0$, i.e., $a_n\ge k$ for all $n \in N$; we wish to show that also holds for $k+1$ and thus close the induction. Furthermore, we get a contradiction since $a_n \ge k$ for all $k, n \in N$, implies that the natural numbers are bounded.

$a_n>a_{n+1}$ since $(a_n)$ is an infinite descent. By the inductive hypothesis we know that $a_{n+1}\ge k$, so we have $a_n>k$ and then $a_n\ge k+1$.

To conclude we have to show that the claim holds for every $n$. Suppose there is some $n_0$ such that $a_{n_0}<k+1$ so, $\,a_{n_0}\le k$. Then either $\,a_{n_0} = k$ or $\,a_{n_0} < k$ but both cases contradicts our hypothesis. Thus $a_n\ge k+1$ for all $n$, which close the induction.

Thanks :)

$\endgroup$
10
$\begingroup$

I would argue a different way.

By assumption, for all $n$, $a_n > a_{n+1}$, or $a_n \ge a_{n+1}+1$.

Therefore, since $a_{n+1} \ge a_{n+2}+1$, $a_n \ge a_{n+2}+2$.

Proceeding by induction, for any $k$, $a_n \ge a_{n+k}+k$.

But, set $k = a_n+1$. We get $a_n \ge a_{n+a_n+1}+a_n+1 > a_n$.

This is the desired contradiction.

This can be stated in this form: We can only go down as far as we are up.

Note: This sort of reminds me of some of the fixed point theorems in recursive function theory.

$\endgroup$
  • 1
    $\begingroup$ I think it should be $a_{n+1} \ge a_{n+2}+1$ instead of $a_{n+1} \ge a_{n+2}-1$ doesn't it? $\endgroup$ – Jose Antonio Oct 11 '13 at 20:17
  • $\begingroup$ Aha! I see what you meant. You are correct. Thanks, fixed, upvoted. $\endgroup$ – marty cohen Oct 16 '13 at 1:10
  • 1
    $\begingroup$ I think this proof is not correct. You can only say that $a_{n+a_n} \ge 0$, and therefore, $a_n \ge a_{n+a_n}+a_n \ge a_n$, which does not have a contradiction. $\endgroup$ – winston Nov 17 '18 at 14:11
  • $\begingroup$ Then set $k=a_n+1$. I'll edit the answer. Thanks. $\endgroup$ – marty cohen Aug 26 at 16:41
2
$\begingroup$

Your argument does seem to work. Note that the last paragraph, however, is unnecessary. In the second last paragraph you have shown that $a_n \ge k + 1$ for every $n$ ($n$ was arbitrary here).

Also, your argument seems to be unneccesarily complicated. Here is how I would argue:

Fix any sequence of natural numbers $\left\{a_n\right\}$. Then by definition of natural numbers there are only finitely many $m \le a_0$, therefore we cannot choose infinitely many distinct numbers below $a_0$ and $\left\{a_n\right\}$ does not have infinite descent.

$\endgroup$
  • 2
    $\begingroup$ Doesn't "... by definition of natural numbers there are only finitely many $m \leq a_{0}$..." require proof? $\endgroup$ – Maxis Jaisi Mar 4 '17 at 7:06
0
$\begingroup$

THEOREM : There are only finite no. of positive integers less than any given positive integer.

The above theorem is also known as Principle of Infinite Descent.

PROOF : Let us assume that there are infinite positive integers less than any given positive integer. So there can't be any minimal or maximal element.

Consider, "a"$\in$Z such that a>0.

Let "S" be the set of positive integers less than "a"

Here,S≠∅ ( because of our assumption)

But, By WOP( Well Ordering Principle).. There must be a minimal element.

CONTRADICTION!!!

Hence our theorem is true

Hope it helps 😋

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.