Is this a valid proof that there are infinitely many natural numbers?

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!

Solution 1:

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.

Solution 2:

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.

Solution 3:

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

Solution 4:

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.

Solution 5:

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.