35
$\begingroup$

I remember reading a simple proof that natural numbers are infinite which goes like the following:

  1. Let $ℕ$ be the set of natural numbers.
  2. Assume that $ℕ$ is finite. Now consider an arbitrary number $K$, where $K$ is the largest number in $ℕ$.
  3. $K+1$ is also a natural number such that $K+1 > K$.
  4. Therefore, $ℕ$ cannot be finite.

Is this a valid proof? And if so, how can the 3rd step be valid when we assumed in the 2nd step that $K$ is the largest number in $ℕ$?

I understand this is a proof by contradiction (wrong?), but if we initially assume $K$ to be the largest number, then we cannot simply assume that there is such a number as $K+1$ later!

$\endgroup$
  • 16
    $\begingroup$ First you need to decide on exactly what "infinite" means to you, in particular which kind of proof that anything is "infinite" you're going to accept. Once you do that, you may well find that what "the natural numbers is infinite" means "there is no largest natural number" to you -- and then it's a perfectly good proof to say that nothing can be the largest natural number because you can always add 1 to it. $\endgroup$ – Henning Makholm Jan 11 '18 at 23:56
  • 1
    $\begingroup$ Welcome! Here is the MathJax tutorial $\endgroup$ – Chase Ryan Taylor Jan 12 '18 at 0:13
  • 21
    $\begingroup$ Regarding the title: The natural numbers are not infinite, they are finite (each and every one of them). But they are infinitely many. And the set of all natural numbers is infinite. $\endgroup$ – Hans Lundmark Jan 12 '18 at 5:44
  • 5
    $\begingroup$ What if I define a set N = { 0, 1 }, and an operator + such that 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 0 and 1 + 1 = 0. Now we run your proof. We have our set N, we assume it is finite, we take K to be 1, K + 1 is 0, but it is smaller than K, so the third step of your proof does not hold. How do we know that the natural numbers and the received + operator do not have the same characteristics of my N and my +? $\endgroup$ – Eric Lippert Jan 12 '18 at 14:46
  • $\begingroup$ How do we know that the natural numbers $\endgroup$ – Att Righ Jan 14 '18 at 3:06

12 Answers 12

39
$\begingroup$

The key here is what we mean by the word "natural number" - without a definition, of course our proof is unclear!

One way to define natural numbers is this:

  1. Zero is a natural number.

  2. If $k$ is a natural number, then $k + 1$ exists and is also a natural number.

  3. No other things are natural numbers.

(There are lots of weird things that can happen with this definition, but it's good enough for now.)

Now, your step (3) should make a lot more sense - we aren't assuming that $K + 1$ exists, we're using the fact that $K$ is a "natural number" and that - by definition - a natural number is followed by another natural number.

$\endgroup$
  • 13
    $\begingroup$ Just out of curiosity, what are the weird things that can happen with your nature numbers definition? $\endgroup$ – dwarandae Jan 12 '18 at 4:17
  • 38
    $\begingroup$ @groov but are they? I could declare the "natural numbers" to be the set {0,1}, with addition defined as 0+1=1 and 1+1=0. This satisfies all three of Reese's rules. The OP's proof depends on the existence of a "greater than" relation with certain properties that are not automatically implied by "k+1 exists and is also a natural number". $\endgroup$ – Geoffrey Brent Jan 12 '18 at 4:34
  • 3
    $\begingroup$ @Deepakms - In all fields, there are times when a set of integers starting with $1$ is useful and times when a set of integers starting with $0$ is useful. And people seem to prefer to describe both by "natural numbers". When counting, having $0$ is necessary, since it is the count of the empty set. And since counting is how numbers are defined, of late the version with $0$ has been winning this war - so much so that some people forget the question is only about nomenclature, not something fundamental. $\endgroup$ – Paul Sinclair Jan 12 '18 at 14:15
  • 3
    $\begingroup$ @dwarandae Among the weird things that can happen is the idea of a nonstandard model of arithmetic - basically, add an "infinite" natural number. Now, according to the definition, it has to have an immediate predecessor to "justify" it and an immediate successor, so throw those in too; and so on. Now you have a collection of things called "natural numbers" that don't really look like what we mean by "natural number". $\endgroup$ – Reese Jan 13 '18 at 17:18
  • 3
    $\begingroup$ If you would add "$k+1\ne 0$ (for all $k$)" and "$j+1=k+1$ if and only if $j=k$" to your definition, then the above criticisms wouldn't be valid, and you would essentially have the Peano axioms. $\endgroup$ – Nathaniel Jan 14 '18 at 4:41
22
$\begingroup$

We do not "assume that there is such a number as $K+1$ later", we assume it earlier. It is one of the fundamental axioms about natural numbers.

$\endgroup$
  • 14
    $\begingroup$ ...or to be more precise, we assume that there is a successor $s(K)$, we define addition, we define $1$ and we prove that $s(K)=K+1$. $\endgroup$ – David Jan 12 '18 at 0:10
14
$\begingroup$

That’s correct using the standard definitions. It’s very similar to the structure of Euclid’s theorem that there are infinitely many primes. I think that the biggest quibble most mathematicians would have with it is that it doesn’t clearly specify its axioms.

We might, for example, object, “Step 3 only says that n+1 > n. But why must it be different from 0, 1, 2 and so on up to n-1? Couldn’t it be equal to some other natural number?” If we say, well, we define greater-than as transitive and implying not-equal, “Then how do we know a function like that exists on the natural numbers? Plenty of functions we can talk about don’t, like square root.”

To answer that, we’d need to define our axioms more clearly. The first real formalization of the natural numbers that’s still taught today was Peano arithmetic. A slightly-modernized version of his axioms would be:

  1. Zero is a number.

  2. If a is a number, the successor of a is a number.

  3. Zero is not equal to the successor of any number.

  4. Two numbers of which the successors are equal are themselves equal.

  5. If a set S of numbers contains zero and also the successor of every number in S, then every natural number is in S.

Translating your notation to Peano’s, n+1 means the successor of n. If we use this theory, axiom 2 tells us that n+1 exists, axiom 3 tells us that n+1 is not 0 and axiom 4 tells us that n+1 is not 0+1, 1+1, 2+1 or any other number up to (n-1)+1. Therefore, it’s a new number different from any in our list. We can make step 3 of your proof sound by defining a>b iff a=b+1 or a>b+1 and then showing that, if a>b, a is not equal to any number from 0 to b. Under these axioms, though, we don’t need to take that extra step.

The axioms most mathematicians use today as the foundation of standard mathematics are Zermelo-Fraenkel set theory. That theory includes a model of Peano arithmetic where numbers are sets, zero is the empty set, the successor of a set s is s∪{s}, and two sets are equal if both contain every element of the other. In this theory, we have to add an axiom that the set that contains the empty set and is closed under succession exists, the Axiom of Infinity. If we assumed instead that there were no infinite set, we could still get a consistent set theory, but we couldn’t use it to do Peano arithmetic without getting a contradiction.

There are other constructions you’ll sometimes see in which either “infinite” or “number” have a different formal meaning. Theoretical computer science sometimes uses the Church numerals, for example. Another common definition of “infinite” is Dedekind infinity, where a set is infinite if it can be put into one-to-one correspondence with a proper subset of itself, like multiplying by 2 puts the natural numbers into one-to-one correspondence with the even numbers. There are even some mathematicians who say that the only mathematical objects that “exist” are those that can be constructed in a finite number of steps, so if you say something is “infinite,“ it must not be the kind of thing their theory of mathematics is talking about. So they would agree with you up until you start saying that “the natural numbers” is itself a well-defined entity that can have properties like “infinite.”

$\endgroup$
7
$\begingroup$

The trouble is that we need a definition of both terms, "natural numbers" and "infinite". In Zermelo-Fraenkel set theory we have the axiom of infinity, one version of which states:

$\exists_S (\emptyset \in S \land (\forall_x (x \in S \rightarrow x \cup \{x\} \in S)))$

Since this question is tagged with set theory, let's take this as an example of an "infinite" set. Then what is a "natural number"? There is a set-theoretical definition of this term too. It says that $0 = \emptyset$, $1 = 0 \cup \{0\}$, $2 = 1 \cup \{1\}$, and in general $n + 1 = n \cup \{n\}$. Or in other words, if we're to have a set $S$ of all of them, it should satisfy $\emptyset \in S \land (\forall_x (x \in S \rightarrow x \cup \{x\} \in S))$. But that's exactly the same property that our "infinite" set is defined to have!

So, there is an even simpler proof! It's axiomatic that there are infinitely many natural numbers.

This isn't the only way to define "natural numbers" in $\text{ZF}$ (although it is the canonical one), nor is there only one way to define "infinite" (see for example the idea of Dedekind-infinite). Note that I didn't actually define "infinite" anywhere, but we can take that to mean anything we want, as long as it applies to the set asserted to exist by the axiom of infinity. A standard definition is that a set $S$ is infinite if it has a surjection to the natural numbers, which in this case is witnessed by the identity function. We can prove that as well if there is any doubt about the right name for the axiom.

Furthermore, $\text{ZF}$ is not the only way to talk about infinity and natural numbers; we can do it in plain-old Peano arithmetic. Natural numbers are our intended domain of discourse, and if a proposition $P(x)$ is true for infinitely many numbers $x$, we can write $\forall_n \exists_x (x \geq n \land P(x))$, or since $\geq$ is not in the language of $\text{PA}$, $\forall_n \exists_x \exists_y (x = n + y \land P(x))$. Taking $P(x) =\top$, we can interpret the sentence $\forall_n \exists_x \exists_y (x = n + y)$ to mean there are infinitely many natural numbers, and this can be proved by existential instantiation from the sentence $\forall_n (n + 0 = n + 0)$, a tautology of first-order logic with equality. That's close to your argument formalized, but it is tautologous, relying not on any axioms of Peano arithmetic but on the interpretation we assign the symbols.

$\endgroup$
4
$\begingroup$

The problem with your definition is that in order to consider the operation $+1$ you should have before defined a set on whic it is defined (the map $+1: S\to S$....) No construction of such a set can be made, and generally people accept this as an axiom. Then they have curious name for the the axiomatic ZF is the most common choice, but you can also take Peano.

A famous example the "Goodstein sequence" (http://mathworld.wolfram.com/GoodsteinSequence.html) is a example of a concrete sequence of natural numbers which converges to $0$ for the ZF theory, but you cannot prove it in the the Peano axiomatic. This example show that defining $\bf N$ really depends on the axiomatic you prefer.

There is no "proof" that an infinite set exists, this is an axiom.

$\endgroup$
  • $\begingroup$ What does it mean that "no construction of such a set can be made"? That's assuming a set of axioms that don't allow such a construction. There's no "proof" that any set exists; this is an axiom. Set theories with no sets are rather trivial, but logically exist. The axiom of infinity is hardly special, and the question of the size of the natural numbers is usually not a direct statement of the axiom of infinity, even if the proof is usually rather short once the axiom of infinity is assumed. $\endgroup$ – prosfilaes Jan 12 '18 at 11:39
3
$\begingroup$

Many details are missing from this proof. Perhaps they were presented in the text. Normally, however, a formal definition of a finite set would be something like:

A set $X$ is finite iff there does not exist an injective (1-1) mapping from $N$ to $X$.

If we had only this definition and the definition of the natural numbers from, say, Peano's Axioms, we could not infer the existence of a largest number in $N$, as in line 2 of the proof.

$\endgroup$
3
$\begingroup$

The proof idea is correct, the actual proof has some issues.

Let's go step by step.

First the title:

Is this a valid proof that natural numbers are infinite?

No. There are no valid proofs that natural numbers are infinite, because natural numbers are not infinite. However, fortunately your post does not attempt to try this futility, rather it tries to prove that the set of natural numbers is infinite. This is an important distinction, and if you don't make it, sooner or later you'll make the mistake in a context where it is not obvious that what you say is not what you meant. Just remember that "infinite" is not a number, but a property.

OK, but now to the actual proof:

  1. Let $\mathbb N$ be the set of natural numbers.

OK, here you just introduce the common notation; of course there's nothing wrong with that.

  1. Assume that $\mathbb N$ is finite.

So you're going to prove by contradiction. Still OK.

Now consider an arbitrary number $K$, where $K$ is the largest number in $\mathbb N$.

That sentence is self-contradictory. Either $K$ is arbitrary, then it might not be the largest number in $\mathbb N$. Or $K$ is fixed to be the largest number of $\mathbb N$, then it is not arbitrary. From the following, it is obvious that you meant the second.

However, you are making a leap here: To define $K$ as the largest element of $\mathbb N$ you first have to establish that, under the assumption, $\mathbb N$ has a largest element. Now the reason why this is true is that

  1. $\mathbb N$ is totally ordered
  2. Every totally ordered finite set has a maximal element.

You have to at least state the reason (e.g. "Be $K$ the largest element of $\mathbb N$; this exists because $\mathbb N$ is totally ordered and by assumption finite). If any of the results is not already known (either as axiom or as previous theorem), you'll also have to prove that.

$K+1$ is also a natural number such that $K+1>K$.

Here you should state based on what that statement is true. For example:

"But if $K$ is a natural number, due to (the axioms or a previously proved theorem) $K+1$ is another natural number with $K+1>K$."

Of course, as before, you can only use that if it is already in the axioms or a previous theorem; otherwise you'll first need to prove it as well.

  1. Therefore, $\mathbb N$ cannot be finite.

You should explicitly state that the result of point 3 is a contradiction. For example:

"But this means that, in contradiction to the assumption, $K$ cannot be the maximal element. Therefore, $\mathbb N$ cannot have a maximal element, and thus cannot be finite."

$\endgroup$
  • $\begingroup$ Infinite is an adjective right? $\endgroup$ – BCLC Jan 13 '18 at 18:25
  • $\begingroup$ @BCLC: Yes, like "even" or "odd". For example, it would be wrong to write "2, 4 and 6 are odd numbers", although those are three numbers, and three is odd. $\endgroup$ – celtschk Jan 13 '18 at 18:54
  • $\begingroup$ I usually hear 'infinity is not a number. Should '"infinite" is not a number, but a property' be instead '"infinite" is not a quantity/amount, but a property' ? Probably dumb question because it's 3am in my timezone. I think this is like how colours are adjectives or nouns. $\endgroup$ – BCLC Jan 13 '18 at 19:21
  • $\begingroup$ Well, neither "infinity" nor "infinite" is a number. "Infinite" is an adjective describing a property. "Infinity" is a noun and describes a formal value sometimes added to the numbers, but that formal value itself is not a number; in particular it doesn't follow the arithmetic rules. On the other hand there are number systems with infinite numbers (the most prominent are the ordinal numbers and the cardinal numbers), but those always have many infinite numbers (indeed, infinitely many), and therefore it makes no sense to call a single one of them "infinity". $\endgroup$ – celtschk Jan 13 '18 at 20:01
  • $\begingroup$ "There are no valid proofs that natural numbers are infinite" It's possible that the asker left out a "the" because their native language is something like Russian or Japanese. $\endgroup$ – David Richerby Jan 14 '18 at 1:35
2
$\begingroup$

Depends on what we assume with 'natural numbers'. Obviously we don't assume natural numbers are infinite.

  • Do we assume that 1 + any natural number is a natural number?
  • Do we assume '1 +' means going to the next highest natural number?
  • Do we assume the natural numbers have an order?
$\endgroup$
1
$\begingroup$

If we assume that N IS finite then we should have... n1,n2,n3,...nk i.e. there must be some biggest number Say nk

but.nk+1 is also natural number that is it is never going to be finite Also natural numbers are countable infinite That is we can have a one-one correspondence with natural numbers itself(identity map).

$\endgroup$
1
$\begingroup$

That K+1 exists is an axiom in many number systems. That K+1 > K also is provable in the natural numbers. However, this isn't true in all number systems; for instance, if you treat the positions on a clock face as a number system, you have that "+1" means move clockwise to the next position. But ">" isn't well-defined in this system, since every position is "after" every other. So it is possible to have a number system where every element has a successor, but the number of elements is finite.

So this proof can be made valid by filling in some axioms, but as it stands it isn't rigorous, as it leaves many steps as being implicit.

$\endgroup$
1
$\begingroup$

Let us start from the definition of an inductive set.

A set $S$ is said to be inductive if it satisfies the following condition.$$ x\in S\to (x+1)\in S$$ The set of natural numbers is defined to be the intersection of inductive sets which contain $1$.

Therefore if $n$ is a natural number, so is $n+1.$ Now if you assume K is the largest natural number you get a contradiction because $K+1$ is a natural number larger than $K$.

We do not approve of contradictions so the set of natural numbers is not finite.

$\endgroup$
0
$\begingroup$

Let's work within Peano Arithmetic. If the set of natural numbers, $S$, is finite, we can create a new set $S'$ comprising the successor to every member of $S$. Plainly, the members of $S$ and $S'$ enjoy a one-to-one correspondence. Also, $S'$ does not contain $0$ as a member, because $0$ is not the successor to any number. Now we create a third set, $S''$, comprising $0$ and the members of $S'$. NB: if $S$ is finite, then $S'$ and $S''$ are also finite.

By the axioms of Peano Arithmetic, every member of $S''$ is a natural number, but there is plainly at least one member of $S''$ that is not in $S$, as $S''$ has one more member than does $S$.

Thus, something about the assumption is wrong. Either $S$ is not the set of natural numbers (that is, the meaning of 'the set of natural numbers' is elusive in some fundamental sense), or the set of natural numbers is not finite.

The contradiction involves the fifth Peano axiom, which says that if any set $S$ contains $0$ and the successor to every number in $S$, it contains all the natural numbers. But what is shown above is that if $S$ is finite, using the other Peano axioms we can construct a natural number that is not in $S$. Hence, $S$ cannot be finite. Note that using this approach, it is not necessary to postulate, prove, or identify any particular $k\in S$ that is the largest member of $S$.

Also, the above reasoning does not create a contradiction if $S$ is infinite, as the 'manufacture' of some new element does not change the size of $S$ under that assumption. That is, a new element added to a finite set disrupts an existing one-to-one correspondence with another set, but does not disrupt a one-to-one correspondence between two (countably) infinite sets.

$\endgroup$

protected by Daniel Fischer Jan 12 '18 at 16:25

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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