Problem proving a basic theorem using induction

[Dale10101]

Attached are Peano’s axioms and three basic follow-up theorems, it is the third theorem that I am having trouble with. I can see the logic of the proof but I am having trouble with the formalization. I can sort of hand wave through it but in trying to pin down exactly what is being said I run into problems.

First, my take on what the proof is trying to prove:

Peano’s axioms state that each natural number has a unique successor, this proof endeavors to prove that every natural number has a unique “precursor” except for the number 1.

To prove the case:

1. Let N denote the set of natural numbers, and with “n” as a variable pointer that can point to any particular natural number.
2. M is a set of natural numbers with the additional property that its elements have precursors, also that M contains the number 1 which has no precursor.
3. Let x be a pointer variable that points to any particular element of M.
4. Let u and u’ be pointer variables to any particular element of N since we are trying to prove a proposition that is valid over N.

So what must be proved is that no matter which natural number is pointed to by u’ there exists a corresponding unique precursor that can be pointed to by u.

After settling the case for x = 1, the proof goes on saying let u “denote” x, which I interprets as saying let u point to any value of M which is currently being pointed to by x.

The proof then says that x’ = u’ and here I run into problems.

The inductive hypothesis is that M contains those elements of N that have precursors (plus the element 1) but we have not yet proved that M contains all n of N so how one use the symbol x’ at this point, maybe M does not contain x’, the natural number successor of x? For example M might contain 2 and 4 but not 3

Hmmm, so maybe the author does not intend x to be a pointer to elements of M after all but, like n, to be a pointer to any element of N and consequently to any of element of M as well … but that doesn't help because x’ will then exist but now there is no guarantee that x’ is in M.

Possibly the author means that the prime of x for x element of M denotes a different successor than the prime of n element n of N. For example, since we have not proved yet that M contains all n of N, M might contain 2 and 4 but not 3, in this case if x = 2 then x’ = 4 … can that be right?

Well my dilemma is illustrated it seems that the author is using x to point to only those natural number that have a precursor (elements of M) but uses the same pointer variable as though it were pointing to elements of N without the additional restrictive properties of those element of N that are required to also be a member of M.

This is confusing to think about and confusing to explain however I hope I have done an adequate job. Any help would be appreciated as I have been going in circle for about a week.

 

[HallsofIvy]

View attachment 4173View attachment 4174View attachment 4175

Attached are Peano’s axioms and three basic follow-up theorems, it is the third theorem that I am having trouble with. I can see the logic of the proof but I am having trouble with the formalization. I can sort of hand wave through it but in trying to pin down exactly what is being said I run into problems.

First, my take on what the proof is trying to prove:

Peano’s axioms state that each natural number has a unique successor, this proof endeavors to prove that every natural number has a unique “precursor” except for the number 1.

To prove the case:

1. Let N denote the set of natural numbers, and with “n” as a variable pointer that can point to any particular natural number.
2. M is a set of natural numbers with the additional property that its elements have precursors, also that M contains the number 1 which has no precursor.
3. Let x be a pointer variable that points to any particular element of M.
4. Let u and u’ be pointer variables to any particular element of N since we are trying to prove a proposition that is valid over N.

So what must be proved is that no matter which natural number is pointed to by u’ there exists a corresponding unique precursor that can be pointed to by u.

After settling the case for x = 1, the proof goes on saying let u “denote” x, which I interprets as saying let u point to any value of M which is currently being pointed to by x.

The proof then says that x’ = u’ and here I run into problems.

The inductive hypothesis is that M contains those elements of N that have precursors (plus the element 1) but we have not yet proved that M contains all n of N so how one use the symbol x’ at this point, maybe M does not contain x’, the natural number successor of x? For example M might contain 2 and 4 but not 3

The proof has not yet said that x' is in M. It has only said that x'= u'. But since every number u has a successor, u' exists and therefore so does x'. That shows that x is the precursor of x', therefore x' has a precursor and, by the definition of M, x' is in M.

Hmmm, so maybe the author does not intend x to be a pointer to elements of M

Yes, he does. That was exactly what (3), above, said..

after all but, like n, to be a pointer to any element of N and consequently to any of element of M as well … but that doesn't help because x’ will then exist but now there is no guarantee that x’ is in M.

Possibly the author means that the prime of x for x element of M denotes a different successor than the prime of n element n of N. For example, since we have not proved yet that M contains all n of N, M might contain 2 and 4 but not 3, in this case if x = 2 then x’ = 4 … can that be right?

Well my dilemma is illustrated it seems that the author is using x to point to only those natural number that have a precursor (elements of M) but uses the same pointer variable as though it were pointing to elements of N without the additional restrictive properties of those element of N that are required to also be a member of M.

This is confusing to think about and confusing to explain however I hope I have done an adequate job. Any help would be appreciated as I have been going in circle for about a week.

 

[Dale10101]

Less puzzled but not yet confident

The proof has not yet said that x' is in M. It has only said that x'= u'. But since every number u has a successor, u' exists and therefore so does x'. That shows that x is the precursor of x', therefore x' has a precursor and, by the definition of M, x' is in M.


Yes, he does. That was exactly what (3), above, said..

I think what I am finding confusing is that it seems that you can take any natural number x in M and call it x'. Any particular number in M can be pointed to using the pointer variable x but any particular x is also a successor of a precursor else it would not be in M so you can use a pointer variable called x' and point to the same number you were calling x. It is for that reason that you must let x' = u' etc to establish that x' has a precursor.

Is that correct? In particular is my first sentence correct?

If I am right it seems it would be less confusing to say let x = v', let v' = u' etc to establish that v' has a precursor therefore x = v' by definition of M is in M.