Prove that there does not exist a largest natural number

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)?

• 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. – Mark Bennet Dec 12 '16 at 22:39
• 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. – Kevin Long Dec 12 '16 at 22:39
• 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 – Peter Dec 12 '16 at 22:42
• Sometimes, a proof can be very easy! – Peter Dec 12 '16 at 22:45
• "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 – Rahul Dec 12 '16 at 22:52

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.

• Thanks, I needed all the details I could get :D – K Split X Dec 12 '16 at 23:00
• I mean, I dont really think its nessesary to show x+1 > x – K Split X Dec 12 '16 at 23:01
• 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. – Tanner Swett Dec 12 '16 at 23:15
• @TannerSwett: $x + 1 > x$, because $x + 1 - x = 1 > 0$. But why is that so? – Santiago Dec 12 '16 at 23:23

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

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

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.

• 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 – Peter Dec 12 '16 at 22:43
• I was tempted to use transfinite induction (to show that there is no greatest ordinal) but chose not to. – Hans Hüttel Dec 12 '16 at 22:47
• Good choice! We should keep in PA instead of ZFC – Peter Dec 12 '16 at 22:47
• Please note that both my proofs are intuitionistically valid. – Hans Hüttel Dec 12 '16 at 22:48

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).