3
$\begingroup$

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.

enter image description here

$\endgroup$
6
  • 15
    $\begingroup$ You can't seriously believe there are only finitely many numbers. "If a natural is finite, then that natural plus one is finite, hence the set of all naturals is finite" - this is a non sequitor, the set of all naturals is not itself a natural number. $\endgroup$
    – anon
    Commented Jun 29, 2014 at 20:30
  • 2
    $\begingroup$ Manish, do you distinguish between the statements "all numbers are finite" and "the set of all numbers is finite"? $\endgroup$
    – user21467
    Commented Jun 29, 2014 at 20:52
  • $\begingroup$ Imagine infinity as the supremum of set N. $\endgroup$
    – Lucian
    Commented Jun 29, 2014 at 21:02
  • $\begingroup$ @blue he doesn't claim there are only finitely many. He claims that the logic as presented doesn't prove there are infinitely many. $\endgroup$ Commented Feb 15, 2018 at 16:04
  • $\begingroup$ It is best to define an infinite set as one which can be put into one-one correspondence with one of its proper subsets. And the set if finite if it is not infinite. Given this definition we can easily show that $\mathbb{N} $ is an infinite set. The idea that each individual natural number is finite is altogether a different concept and and can not really be compared with the notion of infinite set. $\endgroup$
    – Paramanand Singh
    Commented Feb 16, 2018 at 2:33

10 Answers 10

17
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ This proof by contradiction can be used to prove that there exist a natural number which is not finite.Let say all natural numbers are finite and m is the highest number. Successor of m i.e. (m+1) will be greater than m. Hence our initial assumption was incorrect. So all natural numbers can not be finite. Am I right ? But this has led us against the proof provided in the book. $\endgroup$ Commented Jun 29, 2014 at 20:29
  • 1
    $\begingroup$ @blue that is not the problem here $\endgroup$ Commented Jun 29, 2014 at 20:32
  • 7
    $\begingroup$ @John Oh? Manish said "let's say all natural numbers are finite" and then proceeded to say "and $m$ is the highest number." I don't know what that tells you, but that tells me Manish believes the first implies the second, and the only way that can be true in someone's mind is if they don't get the distinction between each natural being finite and the set of naturals being finite. $\endgroup$
    – anon
    Commented Jun 29, 2014 at 20:34
  • 1
    $\begingroup$ @ManishKhokhar The initial part or your argument is fine, but the conclusion is a little off. You have said "let all natural numbers are finite AND m is the highest number." Then you correctly drew a contradiction, meaning the statement "all natural numbers are finite AND m is the highest number" is false. However, this only means that at least one of the statements "all natural numbers are finite" or "m is the highest number" is false. Here "m is the highest number" is false because it supposes a maximum element exists, when in actuality no such element exists, so we can't get your result. $\endgroup$ Commented Jun 29, 2014 at 20:43
  • 1
    $\begingroup$ @ all: Yes you are right, "m is the highest number" is the mistake in my argument. @PeterWoolfitt Peter you said "The induction argument fails because it shows P(n) is finite for every natural number n, but it does not show that "P(∞)" is finite because ∞ is not a natural number." Right, ∞ is not a natural number, so there is no such thing as P(∞). So how can we use it to reject Induction argument? $\endgroup$ Commented Jun 29, 2014 at 21:15
6
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .