Why set of natural numbers is infinite, while each natural number is finite?

Question

In his book Analysis Vol. 1, author Terence Tao argues that while each natural number is finite, the set of natural numbers is infinite (though has not defined what infinite means yet). Using Peano Axiom, if a property holds for P(0) and whenever P(n) is true, P(n+1) is also true, then it is true for all natural numbers. [See image attached at the end.]

However, he has not provided an argument/proof why the set of natural numbers in infinite. If we go by the same argument, the set of natural numbers should also be finite.

Just like finiteness let’s say P is property called count associated with each natural number. Count can be defined as P(n) = n+1. (Intuitively count means number of elements in the set till n, or the number of elements in the set till n). Now P(0) = 1, which is finite. If P(n) is finite (i.e. n+1), then P(n+1) will also be finite. Hence, the number of elements in the set of natural numbers should also be finite.

Answer 1

Suppose for the sake of contradiction that the set of natural numbers is finite. Then there exists a maximum element $m$. But $m+1=n$ is also a natural number and $n>m$. This contradicts the maximality of $m$, so our original assumption was false, and hence set of natural numbers is not finite but rather infinite.

The induction argument fails because it shows $P(n)$ is finite for every natural number $n$, but it does not show that $P(\infty)$ is finite because $\infty$ is not a natural number.

Answer 2

You can use induction there, but it doesn't give the conclusion you think.

Let $S_1=\{1\}$ and $S_n=S_{n-1}\cup\{n\}$ for $n>1.$ Then you can prove by induction that $S_n$ is finite for each $n$. But this doesn't show that the natural numbers are finite!

Answer 3

Your argument only shows that the count/cardinality of the collection {$0,1,2,..,n$} for any_finite_ $n$ is $n+1$. But we can show that no one collection {$0,1,2,..,n$} is in bijection with all natural numbers, by, e.g., Peter's argument above, i.e., the collection {$0,1,2,..,n$} will not contain $n+1$.

Answer 4

Consider the statement $P(n):$$ $ $\{1,2,3,\cdots,n\}$ is a finite set for each natural number $n$

Then $P(1)$ is true because the set $\{1\}$ is a finite set .

Let $P(n)$ be true for some $n=k$ i.e the set $\{1,2,\cdots,k\}$ is a finite set. Now adding one more natural number $k+1$ its remains a finite set. Thus we have proved that the set $\{1,2,3,\cdots,k,k+1\}$ is a finte set

Hence by PMI the set $\{1,2,\cdots,n\}$ is a finite set for each natural number $n=1,2,\cdots $

From here we can not make a claim that the set of natural number $\mathbb{N}$ is a finite set because the set $\{1,2,\cdots,n\}\ne\mathbb{N}$, for any natural number $n$.

Answer 5

It is true that whenever you add one more element to a finite set, you get a finite set. Thus the sets \begin{align} & \{1\} \\ & \{1,2\} \\ & \{1,2,3\} \\ & \{1,2,3,4\} \\ & \qquad \vdots \end{align} are all finite.

If to every finite set of natural numbers one can always add one more to get a larger set of natural numbers, that proves the set of all natural numbers is infinite. But the set you get when you add one more will always be finite.

Answer 6

The fact that the infinitude of the natural numbers is effectively taken as an axiom in set theory illustrates to some degree the difficulty in proving that there are infinitely many natural numbers. And you are correct to observe that "infinite" needs to be correctly defined before it makes sense to claim the natural numbers are infinite in number.

What we can quickly and easily do, is to prove that your claim there are finitely many natural numbers, is contradictory.

If as you state, $P(n)$ counts every natural number then since $P(n)=n+1$ it follows by the law of induction that $P(n)$ is itself a natural number and also by induction that $P(n)+1$ is a natural number. Then the contradiction immediately follows that for every $P(n)$ there is some integer greater than it so every $P(n)$ fails to enumerate the natural numbers.

It does not take a huge leap of logic to add to our system the axiom that some number exists called $\infty$ which is greater than all natural numbers.

Intuitively, my preference is to a) aspire to only use infinity in supposition with a view to demonstrating a contradiction and b) also I prefer the notion that infinity is algebraically independent of addition rather than that it exists and is greater than every integer, but this is VERY FAR from standard.

I don't think it's wise to criticise a Fields medal winner for not providing a proof of an Informal Remark. You can rest assured he is extremely adept at constructing rigorous formal arguments when required to do so.

Answer 7

Natural numbers can be arbitrarily large. But arbitrarily large is not same as infinitely large.

Consider this infinite series- 0.9+0.09+0.009+0.0009+......

The sum of n terms of the above series = 1 - 1/10^n. By the principal of mathematical induction it can be shown that 1-1/10^n will always be <1 for n belonging to the set of natural numbers.

It requires all the countably infinite terms of the above series for the sum to add to 1.Any natural number of terms sum would be < 1. So clearly no natural number can be = infinity.

But mind you the sum is not 1 because we had put infinity in 1/10^n. That operation is meaning less.Their are other formal methods to arrive at the result.

Answer 8

The reason why we say this is because a set, $A$, is defined to be finite if and only if #$A=n$, for some natural number $n$. Let $A=\left\{1,2,3,...,n\right\}$ to see this. Now, each natural number carries the value equal to the set containing all the elements from 1 to that number. No matter which number that is, it can't be the last natural number, because there is no last natural number. This is because of the definition of natural numbers: 1 is a natural number, and if $x$ is a natural number, then $x+1$ is too. So supposing $y$ were the last natural number, we produce a natural number $y+1$ which is bigger than $y$. So there can't be a biggest natural number. Now the set containing every natural number is infinite because there's no particular natural number, $m$, that we can create a set from 1 to $m$, while preserving the crucial condition that the sets have equal cardinalities, because $m$ would have to be the last natural number, which doesn't exist.

Answer 9

Because numbers like $99999\dots$ (this one having a infinite string of $9$'s) don't make any sense. If we were to multiply it with $10$ it would not change: i.e its value would remain the same. If rather the infinite string was ending at the right side like this $\dots99999.0 +1$ then logically this would give $0$ because there wouldn't be a place for the carried over $1$ to go since their is no leftmost place for an infinite string ending at right side. The sequence of natural numbers can approach infinity but can never reach it.

Answer 10

I am reading the book and I had the same query. I think Tao's presentation of the idea is incorrect. I say that because the property of a natural number being finite cannot be deduced from the axioms Tao's provided. This is so for the axioms he's provided do not address the finite property of all natural numbers. In addition, his induction argument is unnecessarily confusing because one has to assume that 0 is finite and its successors are also finite leading to a circular argument.

I think Tao's made an error in the way he's presented the idea. I think he wants to say that a set that consists of only one natural number is finite and the set containing all natural numbers is infinite. The reason I say his argument is circular is because the finiteness or infiniteness of a set is dependent on the definition of counting (mapping the elements of a set to a set of natural numbers). In the chapter that Manish is referring to, Tao wanted to present an idea on the inductive property of natural numbers and made a mistake in choosing the example he's chosen (since the example depends on definitions he hasn't presented yet).