We do accept this axiom, don't we?

_________________
Geek of all trades, master of none: the motto for my blog mostlymaths.net

Let's break down assuming a largest number. We assume that a largest natural number exists. If it does exist, there is only one of them, and we can give it a name, so that we can designate it. We do not have to actually find the largest number. We can talk about it, anyway. Just like they talk about the UNSUB on "Criminal Minds" without knowing who it is. Next, with what we know about natural numbers, we can show that if the largest natural number exists, there is a larger natural number than it. ("It" is a pronoun that lets us talk about the supposed largest natural number.) That fact is a contradiction, which shows that one of our assumptions is false.

Well, one of our assumptions is that there is a largest natural number. Another is that we can talk about it, even if it does not exist. Another is that every natural number has a successor. Another is that the successor of a natural number is greater than that number. The last two we are sure of, because of what we know about natural numbers. The first assumption, that the largest natural number exists, is the one we want to give up. However, it may well be that the second assumption is false, that we cannot really talk about something that does not exist, or about something that may not exist. But if the largest natural number existed, there would be no trouble with talking about it, so the second assumption is a problem only when the first assumption is false. So we still end up with the first assumption being false.

I know I kind of went around the bush there, but I wanted to be clear that we did not identify the largest natural number, we simply talked about it as though it existed.



No, because we never looked for one in the first place. It is not like we found one and then said, this is not it. We simply talked about one as though it existed. Once we show that one does not exist, what is there to look for?



I have seen some old problems that do not use variables. They are often not easy to understand. Even the easy ones are like, "Heap, its third, . . ." You can think of variables as linguistic devices that refer to things and help us keep track of what we are saying. Like pronouns.



Suppose that something is true for each member in a set. We can then use "x" to denote some member of the set (without necessarily knowing which one) and prove something else about it, using only what is true for each member of the set. Then we know that what we have proved about it is true for each member of the set. It is not that "x" covers all members of the set, it is that we restricted our proof to what is true about each member of the set.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Well, it was the only book in the library about go that wasn't obviously trivial.

How about that?

You prove that L cannot be the largest number, because L+1 is its successor. I say: Fine, but L+1 is a natural number too (you could use the variable S(uccessor) for it) and that very number cannot be among what L stands for in your proof, so whatever your proof states, it is not for all natural numbers and therefore your proof is incomplete (= no proof). To complete it you'd need to repeat the proof for L+1/S and that would cause a chain that would never end if there are indeed infinite many natural numbers (= no proof).

No , I proved that L does not exist. Assuming that it does exist leads to a contradiction. I proved that if a largest natural number existed, then there was a larger natural number than it. Tilt!



No. If L does not exist, then neither does L+1. (Or for that matter, L-1, or 2*L, or any other number expressed in terms of L.) A non-natural number does not have a successor which is a natural number. I do not have to prove anything about such supposed numbers.



The proof does not claim to be for all natural numbers, only for the possible largest natural number. Which, it turns out, does not exist.

----

IIRC, you mentioned that the rational numbers are dense, i. e., that between any two rational numbers there is another rational number. OK. Is there a smallest positive rational number? What say you and what is your proof?

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Hmm...I think L does exist, because by assumption it was assumed to be a natural number, but it didn't have the property to have not a successor. THAT's what you proved. So you proved that any number that can be pulled into L is a) a natural number and b) with a successor, therefore can't be the largest one. But since L+1 is not covered under L then the question arises if L+1 is the natural number that hasn't a successor.

Here is my line of thinking:

1. We assume a natural number L that has the property to have no successor.
2. We find through Peano 2 that any n € N has a successor n+1 € N.
3. Through mp we find that L must have a successor L+1.
4. Lines 1 and 3 contradict each other, so either one must be false (by the way I have no idea why we do not kill 3 here, maybe someone can tell which one of two contradictory statements can be erased), and we agree?!? that it's line 1, therefore: L has not the property to have no successor.
5. But this proof in 1-4 just tells us about L and not about L+1. L+1 is not covered by L (otherwise L=L+1) therefore a very formal proof would have to prove now that L+1 has not the property to have no successor and so forth.

p.s. I just wanted to line out how the proof functions to me to make u understand my position better. It's possible I may not have understood your position correctly, if that's the case just point it out and I will read in more carefully, this is just a "out-of-the-hip-answer".

The predicate N means 'is a natural number'. > is greater than, < less than. x, w, y, z are variables. l and b are constants. It's been a while since I've done a formal proof and I apologize for the ugly formatting (and the lack of set-theoretic notation, but the structure of the argument shouldn't be different from if you did it set-theoretically):

1.E(x)A(y)[Nx & {Ny -> x > y}]
2. A(y)[Nl & {Ny -> l > y}] Existential elimination from 1
3. A(z)E(w)[Nz -> Nw & w > z] (this comes from the Peano axioms, see P2 here)
4. E(w)[Nl -> Nw & w > l] Universal elimination from 3
5. Nl -> Nb & b > l Existential elimination from 4
6. Nl & {Nb -> l > b} Universal elimination from 2
7. Nl Conjunction elimination from 6
8. Nb -> l > b Conjunction elimination from 6
9. Nb & b > l Conditional elimination from 7 and 5
10. Nb Conjunction elimination from 9
11. l > b Conditional elimination from 10 and 8
12. b > l Conjunction elimination from 9

11 and 12 contradict. So, we have a reductio ad absurdum on one of two premises (the rest of the premises follow deductively in first-order logic):

Premise 1, which we stipulated (i.e. that there is a largest natural number) or Premise 2, which is a part of the definition of 'natural numbers' (i.e. that every natural number has a successor natural number).

There are four choices:

Reject the first premise, which means rejecting the claim that there exists a largest natural number.
Reject the third premise, which means rejecting the definition of natural numbers, which means you aren't talking about the natural numbers.
Reject some rule of natural deduction in first-order logic. Your choices: existential elimination, universal elimination, conditional elimination and conjunction elimination.
Reject reductio ad absurdum proofs.

The important thing is that in the first choice, we are not rejecting the claim 'L is the largest number', we have the deductive warrant to reject the first premise which is the claim that there exists a largest natural number.

EDIT: To be clear about the point of this: when Bill Spight begins the proof by saying something along the lines of: 'Assume there is a largest natural number, call that number L' there is a logical move occurring, though there doesn't appear to be. You're treating the proof as if premise 1 doesn't exist, and it starts only with premise 2. You would be correct that if the proof began by stipulating premise 2, then we could only prove things about l. However, the real premise that is stipulated is 1, and 2 ('call that number L') is just an inference from 1.

No. You've got it backwards. Go back to what I said. I did not start by positing an L, and then assuming that L is a natural number, and then assuming that it is the largest natural number, and then proving that the third assumption was wrong, so that we end up with a natural number, L, that is not the largest. Where does that get us?

Instead, what you do -- what I did --, is first assume that the largest natural number exists, and then make other assumptions, if necessary, that depend upon its existence. Well, of course, if the largest natural number exists, it is a natural number. Furthermore, we can call it L. (Not that we have to call it anything. ) Then when we prove that the first assumption is wrong, we are done.



No, I did not pull any number into L. L is not necessary to the proof. It is just a convenient way to refer to the largest natural number.



We don't kill 3 because it follows from the definition of natural number. So if we kill it we are no longer talking about a hypothetical natural number.

1. has two problems. First, it is false on its face, because every natural number has a successor. Second, it is not clear that it is talking about the existence of a natural number. Better:

1. There is a largest natural number.

Now, that is false, but not false on its face. Furthermore, when we have disproved it, we do not have to worry about there being any largest natural number.

The proof is a little longer, because we have to prove that the successor of a number is greater than it is. (I skipped that, since it is part of common knowledge. But nobody has objected. )

I have omitted labeling the largest natural number, because that has caused some confusion. However, let us say that L stands for "the largest natural number" and substitute it in your 4. and 5. Then we get this:



Does the largest natural number+1 make sense to you?

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Stop right there.

The "natural numbers" were defined as "things" which have certain properties. Those properties include:

Every natural number has a successor.

So if some "thing" doesn't have a successor then it can't be a natural number.

Ok, I understand that and agree with it. But why then do they construct this reductio proof if it follows already DIRECTLY from Peano 2 that there are infinite many nat. numbers? Peano 2: ∀n: (n ∈ N -> n' ∈ N). With Peano 2 we can directly show that for all n follows that if n is a natural number it must have a successor, so (because of the allquantor or the fact that n stands basically for any object of N resp.) we can conclude: no natural number cannot have no successor. Why the indirect way at all?

I don't know in general. I find the reductio slightly easier to state.
Another conceivable reason is that you can study Peano arithmetic without the axiom of induction (PA-), so the reductio is more general. I believe the ordinals model PA-, for instance, though they do have a closely related form of induction, so it may not matter for them.

_________________
Occupy Babel!

Not quite. Did you follow the proof the way I did it?

A bit "naive" (in the formal logic sense) to jump to the conclusion. The axiom of "induction" was included for a purpose. Necessay. The way you are thinking about getting to "all" is the way a positive direction proof might have been done prior to formalization of logic (19th Century) and is open to exactly the objection SmoothOper raised << that you can show it for any n you try, you are showing it only for those finite number of n's that you try ---- your jump to "that means all" can't be done when the logic is by formal symbols >>

That is perhaps when other here are demonstrating by the negative proof.

@Mike: I don't think you need the axiom of induction for such a proof. Peano 2 is sufficient.

1. n ∈ N -> n' ∈ N; n stands for any possible object of N, precisely: n holds a place for one object out of N that is assumed to be takeable by any object of N. (This is the reason why you can universally generalize from n to ∀n here. Maybe someone knows universal generalization and can show how to come from "n ∈ N -> n' ∈ N" to ∀n, n': (n ∈ N -> n' ∈ N) in a formal way).

2. Since there can't be any natural number that is not represented by n it follows that because of Peano 2 and mp no natural number cannot have no successor.

Not enough for you that Peano did? (thought it was necessary)

Did you understand SmoothOper's objection? Every time you select an n within N you can show that this n is not the largest. But no matter for how many n's you have shown this to be true, there still exists an n' for which you have not (yet) shown it to be true. Yes of course, you can now show it true for this n', but you don't have a finite proof (no last step).

I agree with that proof. It isn't necessary to generate every element, since he proved it for every element of the set each element behaving according to certain properties.

I have problems with proofs that have one object in the set and an infinite number of arguments. IE when the natural numbers are defined recursively.

Does there exist a last post in this thread?

_________________
I think I am so I think I am.

Sorry, no.

To prove that there is no natural number without a successor, the axiom of induction is unnecessary. Axiom 2 says that every natural number has a successor. These two statements are logical negations of each other.

Order theory definition of maximal element: Let R be a binary relation on the set P. An element of P is said to be R-maximal if there does not exist a R-greater element of P.

The successor relation defines an order relation: For all pairs m,n in N, let mRn if and only if m succeeds n and say that "m is greater than n".

To get a total, reflexive, transitive, well-founded relation ≥ that extends R, you need the rest of the axioms.

The relevant facts: To show the non-existence of a natural number that is greater than or equal to (according to the order that is the transitive and reflexive closure of R) every natural number, you need the other axioms (which ensure that there is an appropriate extension of R to a nice total order). The non-existence of a natural number that has no greater natural number is logically equivalent to Axiom 2.

What this conversation reveals is that when we get down to the foundations of mathematics, even things like "largest" have to be defined carefully in order for two people not to talk past each other.

PS: I always found the well-ordering principle to be a much nicer way of stating the induction axiom. Equivalent, but one is more aesthetically pleasing than the other (subjectively speaking of course).

Anyway has anyone else noticed how ugly, Bill Spight, Dr. Straw, and RB's arguments become when confronted with the fact that division isn't defined over integers? Not to practice apologetics, but it seems that academics have no sense of shame.

Weren't you banned? In any case, division is defined over the integers. It's called integer division, in that case.

_________________
Geek of all trades, master of none: the motto for my blog mostlymaths.net