What is the proof that there is no greatest natural number?

[matheinste]

In several places I have come across what seems to be a standard proof by contradiction that there is no greatest natural number. As follows:-

Assume there is a greatest natural number (+ve integer). Call it n. Add 1 to it to get n+1.
n+1 is an integer greater than n. Therefore n cannot be the largest +ve integer.

This proof seems to fall down because we are assuming in the proof that there is a larger +ve integer than n which we can obtain by adding 1 to n. If n were indeed the largest integer then we could not do this.

I know it is intuitively obvious that there is no greatest integer but is there another proof.

The Peano construction, I believe, have as an axiom that every integer has a sucessor and soit follows that there can be no greatest integer by definition. But that is a definition and so we would not need to prove it.

Where is my logic, or lack of it, failing me.

Matheinste.

 

[hamster143]

The Peano construction was formulated in 1889, the successor axiom is not much older than that, but the theorem you're talking about was already known at the time of Euclid. So, for 2000 years before Peano, the theorem had to be proved using a different set of axioms. Two of those axioms were (a) that the set of natural numbers is closed under addition, and (b) that the sum of any two natural numbers is greater than either of them.

 

[matheinste]

The Peano construction was formulated in 1889, the successor axiom is not much older than that, but the theorem you're talking about was already known at the time of Euclid. So, for 2000 years before Peano, the theorem had to be proved using a different set of axioms. Two of those axioms were (a) that the set of natural numbers is closed under addition, and (b) that the sum of any two natural numbers is greater than either of them.

Thanks for your response which I understand. But do you consider the reasoning of the quoted proof to be flawed.

Matheinste.

 

[hamster143]

I suppose. A lot of folk arithmetics is flawed.

 

[robert Ihnot]

The matter is we have to start with axioms. It may be true that you could define the integers as never ending, which is what the Piano postulates incorporate. Now it may be true that the Greeks had a different set of axioms to show that there is always a greater integer.

Actually, it is really also a definition of what traits an integer incorporates. You might decide that only one symbol numbers from 0 to 9 are actually integers. That could be your definition if you like.

I suppose you could put the matter to rest by just calling it an axiom that the integers are never ending.

 

[matheinste]

The matter is we have to start with axioms. It may be true that you could define the integers as never ending, which is what the Piano postulates incorporate. Now it may be true that the Greeks had a different set of axioms to show that there is always a greater integer.

Actually, it is really also a definition of what traits an integer incorporates. You might decide that only one symbol numbers from 0 to 9 are actually integers. That could be your definition if you like.

I suppose you could put the matter to rest by just calling it an axiom that the integers are never ending.

Yes. I understand what you are saying.

I supose my question is probably not very realistic because it seems to be asking " If we did not know that the integers were not in any way already defined in such a way that they were infinite in number, then would the reasoning of that particular proof would not be valid "

Matheinste.

 

[robert Ihnot]

Well, to go a little further: There is, so I have read, an animal counting sense, where they seem to understand number of chicks, pups, etc. up to 7. There may be primitative tribes that can not count beyond a certain number, and could not identify the exact number of trees, fish, enemies, etc. seen by scouts.

The largest symbol the Romans had was the myraid, which represented 10,000. But Archimedies considered--using exponents-- the counting of gains of sand, which he estimated at 10^62.

 

[g_edgar]

The reasoning is fine based on standard properties of natural numbers, such as ordering. If you don't believe in those standard properties (which will be in the textbook before this proof), then of course you cannot follow the proof.

 

[CRGreathouse]

Well, to go a little further: There is, so I have read, an animal counting sense, where they seem to understand number of chicks, pups, etc. up to 7. There may be primitative tribes that can not count beyond a certain number, and could not identify the exact number of trees, fish, enemies, etc. seen by scouts.

The largest symbol the Romans had was the myraid, which represented 10,000. But Archimedies considered--using exponents-- the counting of gains of sand, which he estimated at 10^62.

Myriad is Greek, not Roman. And the Romans had symbols for more than that: (((|))) is 100,000. But it is true that in early Roman times it wasn't common to use symbols beyond ((|)); I recall a triumphal obslisk with ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) ((|)) for 130,000.

Archimedes' "Sand Reckoner" didn't exactly use exponents, but that's the essential idea. He derived an upper-bound for the number of grains of sand that could fill the entire universe as it was understood at that time.

 

[robert Ihnot]

CRGreathouse: Archimedes' "Sand Reckoner" didn't exactly use exponents, but that's the essential idea. He derived an upper-bound for the number of grains of sand that could fill the entire universe as it was understood at that time.

Reading further, the Greeks did use the myriad myriad = 10^8, which seems the basis on which Archimedes built.

matheinste: I supose my question is probably not very realistic because it seems to be asking " If we did not know that the integers were not in any way already defined in such a way that they were infinite in number, then would the reasoning of that particular proof would not be valid "

An idea here is that while man had difficulity enumerating large quantities, he had much less, or probably no problem in realizing that quantities could be as large as imagined, starting with: gains of sand, drops of rain (suggesting to a kid the name "google" ) and stars in the sky, etc.

Thus I think that the idea that the integers are unbounded is a perfectly natural concept, and one that most people find intutive.

 

[matheinste]

Thanks for your replies.

I think my concern with this particular proof is probably not well presented. However, as a general question, if we are required to prove a fact, can we use a result which is dependent on that fact in that proof.

Have no worries, I have no doubt of the fact of the unboundedness of the integers.

Matheinste.

 

[robert Ihnot]

Well, if I remember right, I had a logic professor, who put it something like this: To prove X we could take it as an axiom, and then based on the logic:

X implies X

Now its a theorem.

 

[hamster143]

I think my concern with this particular proof is probably not well presented. However, as a general question, if we are required to prove a fact, can we use a result which is dependent on that fact in that proof.

No, we definitely can't. But we must be accurate with our logic and our axioms. The result could be dependent on our fact in one set of axioms, independently provable in another, and be an axiom in yet another.

The proof as usually presented is flawed, because it does not specify which axioms are used as a basis.

To quote your original post

Assume there is a greatest natural number (+ve integer). Call it n. Add 1 to it to get n+1.
n+1 is an integer greater than n. Therefore n cannot be the largest +ve integer.

This proof seems to fall down because we are assuming in the proof that there is a larger +ve integer than n which we can obtain by adding 1 to n. If n were indeed the largest integer then we could not do this.

We are assuming that it is allowed to add 1 to n, and that the integer thus obtained is greater than n.

In a set of axioms where it's always allowed to add a to b and a+b is axiomatically greater than both a and b, the "result" we're assuming follows from axioms and it can be used on its own standing.

 

[HallsofIvy]

In several places I have come across what seems to be a standard proof by contradiction that there is no greatest natural number. As follows:-

Assume there is a greatest natural number (+ve integer). Call it n. Add 1 to it to get n+1.
n+1 is an integer greater than n. Therefore n cannot be the largest +ve integer.

This proof seems to fall down because we are assuming in the proof that there is a larger +ve integer than n which we can obtain by adding 1 to n. If n were indeed the largest integer then we could not do this.

No, we are not assuming that. We are assuming that for any integer n, n+1 exists. That should follow from however you are defining addition for integers. The fact that n+1 is larger than n then follows from the definition of ">".

I know it is intuitively obvious that there is no greatest integer but is there another proof.

The Peano construction, I believe, have as an axiom that every integer has a sucessor and soit follows that there can be no greatest integer by definition. But that is a definition and so we would not need to prove it.

No, the fact that there is no greatest integer is NOT "a definition". I don't see how you arrive at that. To prove that "every integer has a successor" implies "there is no largest integer" you must first prove that the successor of n cannot be less than n. That can be proved from the definition of ">" but requires proof.

Where is my logic, or lack of it, failing me.

Matheinste.

 

[matheinste]

Than you all for your responses. I am quite happy with, and understand your answers.

Thanks again.

Matheinste.