2
$\begingroup$

I need a very simple proof for this.

I could say let $x$ be the largest natural number. Then $x + 1 > x$. QED.

But that doesn't really work does it? What's a very simple proof (no number theory or any sort like that)?

$\endgroup$
  • 2
    $\begingroup$ How are you defining the natural numbers? You need to have at least one property to use in a proof (every natural number has a successor, for example), and an associated definition of order within which "largest" might make sense. $\endgroup$ – Mark Bennet Dec 12 '16 at 22:39
  • 3
    $\begingroup$ What "doesn't really work" about it? If $x$ is a natural number, then $x+1$ is a natural number. By how the ordering is defined on the natural numbers, $x+1>x$, which contradicts $x$ being the largest natural number. Thus, there can be no largest natural number. $\endgroup$ – Kevin Long Dec 12 '16 at 22:39
  • 1
    $\begingroup$ Ultrafinists do not like very large numbers (I do not understand why), but , of course, there is no largest number. Your argument that $x+1$ is always larger than $x$, no matter what $x$ is, is totally valid $\endgroup$ – Peter Dec 12 '16 at 22:42
  • 1
    $\begingroup$ Sometimes, a proof can be very easy! $\endgroup$ – Peter Dec 12 '16 at 22:45
  • 1
    $\begingroup$ "It seems too simple to be a proof." "Sometimes, a proof can be very easy!" In fact we had this question recently: Deep theorems with trivial proofs $\endgroup$ – Rahul Dec 12 '16 at 22:52
3
$\begingroup$

Your proof is good. However, I see some places where you could add more detail:

  • Why are we assuming that $x$ is the largest natural number? (Answer: because we are doing a proof by contradiction.)
  • Why is the fact that $x + 1 > x$ relevant? (Answer: because it contradicts the fact that $x$ is the largest natural number.)

If we add these details in, the proof looks like this:

We will show that there is no largest natural number. In order to do this, let's assume that $x$ is the largest natural number. By the definition of "largest", there is no natural number which is greater than $x$. However, $x + 1$ is a natural number and $x + 1 > x$. This is a contradiction. QED.

There's one more question that this proof doesn't answer:

  • How do we know that $x + 1 > x$?

If you haven't already proved that $x + 1 > x$, then you should think about giving it a shot.

$\endgroup$
  • $\begingroup$ Thanks, I needed all the details I could get :D $\endgroup$ – K Split X Dec 12 '16 at 23:00
  • 1
    $\begingroup$ I mean, I dont really think its nessesary to show x+1 > x $\endgroup$ – K Split X Dec 12 '16 at 23:01
  • 1
    $\begingroup$ Yeah, I'm certainly not going to make you prove that $x + 1 > x$. But keep in mind that the statement that $x + 1 > x$ is not "too obvious to prove"; it's the sort of thing that you can prove, and the proof requires several steps. It's good to be able to prove this statement. $\endgroup$ – Tanner Swett Dec 12 '16 at 23:15
  • $\begingroup$ @TannerSwett: $x + 1 > x$, because $x + 1 - x = 1 > 0$. But why is that so? $\endgroup$ – Santiago Dec 12 '16 at 23:23
2
$\begingroup$

I am a philosophy major, not mathematics, all the same, the following will prove what you are looking for:

  1. Assume the existence of a largest natural number (p)
  2. Being the largest natural number, 'p' cannot be followed by a greater natural number. Meaning:

p + 1 ≤ p

  1. Now subtract 'p' from both sides. The result is:

1 ≤ 0

  1. This has shown that the assumption of 'p' leads to a contradiction.

  2. Therefore, it is not the case that a largest natural number exists.

QED

$\endgroup$
  • $\begingroup$ This question already had good answers, way more rigorous than this, and better formatted. $\endgroup$ – Henrik Nov 7 '17 at 14:34
  • $\begingroup$ Yeah no need to add anything $\endgroup$ – K Split X Nov 7 '17 at 21:50
1
$\begingroup$

Here is a constructive proof.

Let $P(n)$ be the property that there exists a natural number $n'$ where $n' > n$. We prove this by induction.

Base case - $n=1$: Clearly, $P(1)$, since $484000 > 1$.

Step – assume for $n$, prove for $n+1$: Assume by induction hypothesis that there exists an $n''$ such that $n'' > n$. By the precongruence properties of $>$ we easily see that $n''+484000 > n+1$. So take $n' = n'' + 484000$.

If we want to prove the statement that it is not the case that there exists an $n_0 \in \mathbb{N}$ such that $n \leq n_0$ for all $n \in \mathbb{N}$, then we assume that there exists such an $n_0$. But then we have $n_0 + 484000 \leq n_0$, which is a contradiction. Therefore $n_0$ cannot exist.

$\endgroup$
  • 1
    $\begingroup$ We do not need induction to prove that there is no largest number. This is like shooting with rockets on ants. Nevertheless, I give an upvote $\endgroup$ – Peter Dec 12 '16 at 22:43
  • $\begingroup$ I was tempted to use transfinite induction (to show that there is no greatest ordinal) but chose not to. $\endgroup$ – Hans Hüttel Dec 12 '16 at 22:47
  • 1
    $\begingroup$ Good choice! We should keep in PA instead of ZFC $\endgroup$ – Peter Dec 12 '16 at 22:47
  • $\begingroup$ Please note that both my proofs are intuitionistically valid. $\endgroup$ – Hans Hüttel Dec 12 '16 at 22:48
0
$\begingroup$

Maybe that can be shown in a million of ways, but here is one proof just for fun (which surely lacks some foundational rigor). We will use this facts:

1) $1$ is not the largest natural number

2) For every natural number $n \neq 1$ the number $n^2-n+1$ is a natural number that is not equal to $n$ (that is, we have $n^2-n+1 \neq n$)

3) $(n-1)^2>0$ for every natural $n \neq 1$.

Suppose there exists largest natural number, call it $n_L$, now form a natural number $n_L^2-n_L+1$. Because $n_L$ is the largest and because of 2) we have: $n_L>n_L^2-n_L+1$, which is equivalent to $0>(n_L-1)^2$ but this is not possible because $n_L \neq 1$ and because of 3).

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