Proving Induction from the Well-Ordering Principle

[Adonis1]

Homework Statement

Prove Mathematical Induction using the Well-Ordering Principle.

Homework Equations

None.

The Attempt at a Solution

Every solution I can think of, and every solution I've seen, at some point along the proof, seems to me to employ the very reasoning that is used when we prove problems by mathematical induction, the only difference in this proof is we add in the method of proof by contradiction. So, in other words, it seems to me the only way to accomplish a solution is by employing circular reasoning. That doesn't strike me as a very satisfying way to solve this problem.

So, to be clear, I'm not asking for a solution to be handed to me, I just want to know if there is actually a way to accomplish this proof that doesn't beg the question, i.e. that does not employ mathematical inductive reasoning?

 

[micromass]

So let P be our property that we want to prove. We know the folowing:

1) 0 has property P,
2) If n has property P, then n+1 has property P

We must prove that all natural numbers have property P. Right??

To do this, proceed by contradiction, and assume that there is an element that does not have property P.
Look at S=\{x\in \mathbb{N}~\vert~\text{x does not have property P}\}. Now use well-ordering.

 

[Adonis1]

So let P be our property that we want to prove.

Ok

We know the folowing:

1) 0 has property P,
2) If n has property P, then n+1 has property P

I don't see how we know this at this point. This is the conclusion we are aiming to prove, so if we assume it as knowledge, aren't we begging the question?

We must prove that all natural numbers have property P. Right??

Exactly.

To do this, proceed by contradiction, and assume that there is an element that does not have property P.
Look at S=\{x\in \mathbb{N}~\vert~\text{x does not have property P}\}. Now use well-ordering.

Right, if S is the empty set, then S doesn't have a least member and it contradicts the Well-Ordering Principle. So in order to generate the contradiction, we must show S to be empty. Now, we know 0 is not in S; we know 1 is not in S; we know 2 is not in S, etc. We can check numbers individually and show they are not in S, but the problem, so it seems to me, is that the Natural numbers are infinite, and the only way to guarantee they will all have our property P is to use induction. Otherwise, without induction, we would need to check every member of the natural number set, which in principle, can never be verified since that would require infinite time, which we do not have. So again I'm not seeing how to do this in a non-circular/question begging way. The proof presupposes the conclusion, so far as my feeble mind can see.

 

[micromass]

I don't see how we know this at this point. This is the conclusion we are aiming to prove, so if we assume it as knowledge, aren't we begging the question?

No, that's the point of the exercise. We KNOW that 0 is in P and we KNOW that if n is in P, then so is n+1. Convince yourself of the fact that we know this!

If we didn't know this, then there would be nothing we could do!

 

[micromass]

Now, we know 0 is not in S;

Why?

we know 1 is not in S;

Why?

we know 2 is not in S,

Why?

 

[Adonis1]

No, that's the point of the exercise. We KNOW that 0 is in P and we KNOW that if n is in P, then so is n+1. Convince yourself of the fact that we know this!

If we didn't know this, then there would be nothing we could do!

Ugh! I'll keep trying to convince myself :)

Thanks for your help. It does seem to be though that induction will have to be an axiom we accept and that is not reducible to any other, like the Well-Ordering. Perhaps that's why Peano didn't take the Well-Ordering Principle as primitive but rather chose induction?

 

[Adonis1]

Why?



Why?



Why?

:) Because we said we were checking for property P. Say our property P is simply reflexivity. Then 0=0, 1=1, 2=2, etc. Maybe I'm missing something else?

 

[micromass]

:) Because we said we were checking for property P. Say our property P is simply reflexivity. Then 0=0, 1=1, 2=2, etc. Maybe I'm missing something else?

Say your property P is ≠, then 0≠0 is false. So P is not true for 0!

So again, how do you know P is true for 0, for 1, for 2, etc.?

Induction IS reducible to well-ordering.

 

[Adonis1]

Say your property P is ≠, then 0≠0 is false. So P is not true for 0!

So again, how do you know P is true for 0, for 1, for 2, etc.?

Induction IS reducible to well-ordering.

Please have patience with my slow and feeble mind. I'm not trying to give anyone a hard time, just trying to wrap my head around this.

Alright, so it seems to me you are right, when we begin our proof, we can make P any property we choose, say for instance ≠. But then using Set theory and Natural deduction we will not be able to generate addition, succession, and all the other Field Order Axioms that we need in order to produce the Natural numbers, since our logical system requires reflexivity, transitivity, symmetry, etc. So, perhaps when we begin this proof we should stipulate that P be a property not incompatible with those of the Natural number system, (like P is irreflexive). We probably should also specify that P isn't induction, since again we are attempting to prove induction, not presuppose it.

Does that help? Or am I hopelessly confused?

 

[micromass]

we should stipulate that P be a property not incompatible with those of the Natural number system

What do you mean with this??

 

[Adonis1]

What do you mean with this??

Good question. I confess it isn't entirely clear what I meant. Talk of properties is confusing. Perhaps I can ask for a little help here. You said earlier:

So let P be our property that we want to prove.

What did you mean? I thought I understood but now I don't think I did, so perhaps I can try and use your definition and see where it leads me. Or, maybe the thing to do is to give a definition of induction that doesn't rely on properties:

So we might say: If: 0 \in \mathbb{N}, and: if: n \in \mathbb{N}, then: n+1 \in \mathbb{N}.

But then we will need to proceed by contradiction with a new definition of S, for our initial one:

S=\{x\in \mathbb{N}~\vert~\text{x is not a natural number}\}, will not work, so we can't even be able to use well-ordering.

 

[micromass]

OK, working with properties P is confusing since we don't know precisely what a property is. So let's work with sets instead. The idea is that S\subseteq \mathbb{N}. We want to prove that S=\mathbb{N}. So IF

• 0\in S,
• For n\in S it holds that n+1\in S

then S=\mathbb{N}.

We do not want to prove that n+1 is in S, that is given.

Of course, if we want to APPLY induction, then we do need to prove that the hypotheses are satisfied. So in that case we must prove that 0 is in S, and that n+1 is in S for each n.

For example, let
S=\{n\in \mathbb{N}~\vert~n=0~\text{or n is of the form k+1 for a k}\in \mathbb{N}\}
Clearly, 0 is in S.
Now, let n be in S, then n+1 is certainly of the form k+1 (take k=n). So n+1 is in S.

It is NOW that we apply induction to conclude that S=\mathbb{N}.

 

[gopher_p]

The statement of the Well-Ordering Principle is

$WOP=\forall A\subset\mathbf{N}\left[A=\emptyset\lor\exists x\in\mathbf{N}\left(x\in A\land\forall y\in A\left[\left(x=y\right)\lor \left(x<y\right)\right]\right)\right]$-Every subset of the natural numbers is either empty or it contains a least element.

The statement for induction says (where $S$ is the successor function)

$IA=\forall A\subset\mathbf{N}\left[\left(0\in A \land \forall x\in\mathbf{N}\left[x\in A\rightarrow S(x)\in A\right]\right)\rightarrow A=\mathbf{N}\right]$-Every subset of the natural numbers which contains the element $0$ and is closed under succession must be the whole set of natural numbers.

It is often the case that IA is assumed (as an axiom) and is used to prove WOP. The point of your exercise is to show that if WOP is assumed (as an axiom) that it proves IA.

Here is where I think you are having trouble: When you do a proof by induction you are essentially proving $0\in A$ and $x\in A\rightarrow S(x)\in A$ and then use IA to say that $A=\mathbf{N}$. But you're proving something about a specific $A$. That is not what you're doing here. Here you essentially need to show that if $A$ (arbitrary) satisfies $0\in A$ and $x\in A\rightarrow S(x)\in A$, then it follows from WOP that $A=\mathbf{N}$.

Think about it this way. To prove the statement "Every differentiable function is continuous", you don't need to show that a function is differentiable. You just need to show that under the assumption that an arbitrary function is differentiable, it follows necessarily that it is continuous. Here to prove all "All sets satisfying the 'property of induction' (the $\left(0\in A \land \forall x\in\mathbf{N}\left[x\in A\rightarrow S(x)\in A\right]\right)$ part of IA) also satisfy the 'property of being the whole set of natural numbers'", you don't need to show that a particular set satisfies the property of induction. You assume that an arbitrary set satisfies the property of induction, and then show that it must be true that it also satisfies the property of being the whole set of natural numbers.

Edit: Why did this get moved to precalculus? This is barely in the ballpark of undergraduate math.

 

[Adonis1]

The statement of the Well-Ordering Principle is

$WOP=\forall A\subset\mathbf{N}\left[A=\emptyset\lor\exists x\in\mathbf{N}\left(x\in A\land\forall y\in A\left[\left(x=y\right)\lor \left(x<y\right)\right]\right)\right]$-Every subset of the natural numbers is either empty or it contains a least element.

The statement for induction says (where $S$ is the successor function)

$IA=\forall A\subset\mathbf{N}\left[\left(0\in A \land \forall x\in\mathbf{N}\left[x\in A\rightarrow S(x)\in A\right]\right)\rightarrow A=\mathbf{N}\right]$-Every subset of the natural numbers which contains the element $0$ and is closed under succession must be the whole set of natural numbers.

It is often the case that IA is assumed (as an axiom) and is used to prove WOP. The point of your exercise is to show that if WOP is assumed (as an axiom) that it proves IA.

Here is where I think you are having trouble: When you do a proof by induction you are essentially proving $0\in A$ and $x\in A\rightarrow S(x)\in A$ and then use IA to say that $A=\mathbf{N}$. But you're proving something about a specific $A$. That is not what you're doing here. Here you essentially need to show that if $A$ (arbitrary) satisfies $0\in A$ and $x\in A\rightarrow S(x)\in A$, then it follows from WOP that $A=\mathbf{N}$.

Think about it this way. To prove the statement "Every differentiable function is continuous", you don't need to show that a function is differentiable. You just need to show that under the assumption that an arbitrary function is differentiable, it follows necessarily that it is continuous. Here to prove all "All sets satisfying the 'property of induction' (the $\left(0\in A \land \forall x\in\mathbf{N}\left[x\in A\right arrow S(x)\in A\right]\right)$ part of IA) also satisfy the 'property of being the whole set of natural numbers'", you don't need to show that a particular set satisfies the property of induction. You assume that an arbitrary set satisfies the property of induction, and then show that it must be true that it also satisfies the property of being the whole set of natural numbers.

This is exactly what I was looking for! Thank you for this very clear explanation. I do have one question regarding this explanation however. This is certainly good enough for my purposes though, and my question is off-topic, i.e. not related to this problem. Anyway, you say that I can proceed "under the assumption" that I've selected an arbitrary set that satisfies the property of induction, and then show that it must be true that it also satisfies the properly of being the whole set of natural numbers, using the WOP. Well that's fine, but how do I know I have actually selected an arbitrary such set? Yes, we "stipulate" it when we carry out the proof, i.e., we say "I've selected an arbitrary such set that I name A", that's what's meant by your phrase "under the assumption that..." but how do I actually know that such an assumption is legitimate in the first place? How do I know I am not subject to confirmation bias? Perhaps more directly, how do I know such an arbitrary A even exists in the first place? If such an assumption could be shown, then there is no problem, the proof strikes me as perfect. But can I ever legitimate that assumption?

But maybe I'm stretching things into epistemology here?

Edit: Why did this get moved to precalculus? This is barely in the ballpark of undergraduate math.

I posted it here, sorry if it was in the wrong section. I've not taken classes so I didn't know where it belonged.

 

[Adonis1]

OK, working with properties P is confusing since we don't know precisely what a property is. So let's work with sets instead. The idea is that S\subseteq \mathbb{N}. We want to prove that S=\mathbb{N}. So IF

• 0\in S,
• For n\in S it holds that n+1\in S

then S=\mathbb{N}.

We do not want to prove that n+1 is in S, that is given.

Of course, if we want to APPLY induction, then we do need to prove that the hypotheses are satisfied. So in that case we must prove that 0 is in S, and that n+1 is in S for each n.

For example, let
S=\{n\in \mathbb{N}~\vert~n=0~\text{or n is of the form k+1 for a k}\in \mathbb{N}\}
Clearly, 0 is in S.
Now, let n be in S, then n+1 is certainly of the form k+1 (take k=n). So n+1 is in S.

It is NOW that we apply induction to conclude that S=\mathbb{N}.

Thanks for your explanation. I agree sets seems the best way to go, and if I'm not misreading you, you seem to be pointing to a similar worry as Gopher identified. Anyway, I think you (two) have helped me achieve my goal. I'm very grateful for your patience and help.

 

[gopher_p]

This is exactly what I was looking for! Thank you for this very clear explanation. I do have one question regarding this explanation however. This is certainly good enough for my purposes though, and my question is off-topic, i.e. not related to this problem. Anyway, you say that I can proceed "under the assumption" that I've selected an arbitrary set that satisfies the property of induction, and then show that it must be true that it also satisfies the properly of being the whole set of natural numbers, using the WOP. Well that's fine, but how do I know I have actually selected an arbitrary such set? Yes, we "stipulate" it when we carry out the proof, i.e., we say "I've selected an arbitrary such set that I name A", that's what's meant by your phrase "under the assumption that..." but how do I actually know that such an assumption is legitimate in the first place? How do I know I am not subject to confirmation bias? Perhaps more directly, how do I know such an arbitrary A even exists in the first place? If such an assumption could be shown, then there is no problem, the proof strikes me as perfect. But can I ever legitimate that assumption?

But maybe I'm stretching things into epistemology here?

This is going to seem way off, but I promise it'll come around.

Pretend for a second that we have very precise definitions of "zombie apocalypse", "prepared for", and "survive". We could presumably prove that every member of the set of humans who is prepared for the zombie apocalypse is also in the set of humans who will survive the zombie apocalypse. If we couldn't then we might need to adjust our definitions. It might turn out that, just as a side result of our definitions, that other statements using the terms "zombie apocalypse", "prepared for", and "survive" are also provable. Perhaps some of them would be obvious, others not so obvious. But they would all be logical consequences in a universe where those who are prepared survive.

We don't really care if our definitions are reasonable or achievable. Maybe "prepared" is far too strict. Maybe "survive" means "survives for 10 seconds", maybe it means "survives for 10 years". We don't really care as long as preparedness implies survival. We also don't care if zombie apocalypse is an event that can happen (at least for the purpose of this analogy). Maybe it can, maybe it can't. We don't know. But what we do know is that, in our construct, if there is a zombie apocalypse and if you are prepared, then you will survive.

This is precisely the type of argument that we've made here. We've defined the natural numbers to satisfy certain axioms (probably Peano). We've also defined things like "set", "subset", etc. (probably Zermelo–Fraenkel). Are sets real? Do numbers exist? We'd like to think so, but that's really question for the philosophers. As mathematicians, we move forward and prove other statements as if they are real and do exist ... somewhere. We are concerned with having precise definitions (so that there is no ambiguity) and an appropriate logical framework in which to work.

And in that logical framework, if WOP is true and if a set has the "property of induction" (notice how we've defined in this post what it means for a set to have the property of induction that's our term), then that set must be all natural numbers. It doesn't matter to us one bit if there really are sets, natural numbers, or whether or not it's possible for a set to possesses the property of induction.

 

[Adonis1]

...

This is precisely the type of argument that we've made here. We've defined the natural numbers to satisfy certain axioms (probably Peano). We've also defined things like "set", "subset", etc. (probably Zermelo–Fraenkel). Are sets real? Do numbers exist? We'd like to think so, but that's really question for the philosophers. As mathematicians, we move forward and prove other statements as if they are real and do exist ... somewhere. We are concerned with having precise definitions (so that there is no ambiguity) and an appropriate logical framework in which to work.

And in that logical framework, if WOP is true and if a set has the "property of induction" (notice how we've defined in this post what it means for a set to have the property of induction that's our term), then that set must be all natural numbers. It doesn't matter to us one bit if there really are sets, natural numbers, or whether or not it's possible for a set to possesses the property of induction.

Perfecto! Muuah (). Again thank you this has all been extremely helpful. I feel as if I'm starting to understand. Hopefully I'm not deluded.