Proving Induction from the Well-Ordering Principle

In summary: 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?
  • #1
Adonis1
14
1

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?
 
Physics news on Phys.org
  • #2
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 [itex]S=\{x\in \mathbb{N}~\vert~\text{x does not have property P}\}[/itex]. Now use well-ordering.
 
  • #3
micromass said:
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 [itex]S=\{x\in \mathbb{N}~\vert~\text{x does not have property P}\}[/itex]. 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.
 
  • #4
Adonis1 said:
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!
 
  • #5
Adonis1 said:
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?
 
  • #6
micromass said:
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?
 
Last edited:
  • #7
micromass said:
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?
 
  • #8
Adonis1 said:
:) 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.
 
  • #9
micromass said:
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?
 
  • #10
Adonis1 said:
we should stipulate that P be a property not incompatible with those of the Natural number system

What do you mean with this??
 
  • #11
micromass said:
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: [itex] If: 0 \in \mathbb{N}, and: if: n \in \mathbb{N}, then: n+1 \in \mathbb{N} [/itex].

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

[itex]S=\{x\in \mathbb{N}~\vert~\text{x is not a natural number}\}[/itex], will not work, so we can't even be able to use well-ordering.
 
  • #12
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 [itex]S\subseteq \mathbb{N}[/itex]. We want to prove that [itex]S=\mathbb{N}[/itex]. So IF
  • [itex]0\in S[/itex],
  • For [itex]n\in S[/itex] it holds that [itex]n+1\in S[/itex]
then [itex]S=\mathbb{N}[/itex].

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
[tex]S=\{n\in \mathbb{N}~\vert~n=0~\text{or n is of the form k+1 for a k}\in \mathbb{N}\}[/tex]
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 [itex]S=\mathbb{N}[/itex].
 
  • #13
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.
 
  • #14
gopher_p said:
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.
 
  • #15
micromass said:
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 [itex]S\subseteq \mathbb{N}[/itex]. We want to prove that [itex]S=\mathbb{N}[/itex]. So IF
  • [itex]0\in S[/itex],
  • For [itex]n\in S[/itex] it holds that [itex]n+1\in S[/itex]
then [itex]S=\mathbb{N}[/itex].

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
[tex]S=\{n\in \mathbb{N}~\vert~n=0~\text{or n is of the form k+1 for a k}\in \mathbb{N}\}[/tex]
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 [itex]S=\mathbb{N}[/itex].

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.
 
  • #16
Adonis1 said:
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 :wink: 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.
 
  • #17
gopher_p said:
...

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 :wink: 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 (:kiss:). Again thank you this has all been extremely helpful. I feel as if I'm starting to understand. Hopefully I'm not deluded.
 

1. What is the Well-Ordering Principle?

The Well-Ordering Principle is a fundamental concept in mathematics that states that every non-empty set of positive integers has a least element. This means that there is always a smallest number in any given set of positive integers.

2. How is the Well-Ordering Principle used in proving induction?

The Well-Ordering Principle is used as the basis for mathematical induction. It provides a starting point for the induction proof by establishing that there is always a smallest number in a set of positive integers. This allows us to prove that a statement is true for the smallest number, and then show that if it is true for a particular number, it is also true for the next number. This process can be repeated infinitely, proving the statement for all positive integers.

3. What is the difference between strong and weak induction?

Strong induction and weak induction are two different forms of mathematical induction. In strong induction, we assume that the statement is true for all positive integers up to and including a certain number, and then prove that it is also true for the next number. In weak induction, we only assume that the statement is true for a particular number, and then prove that it is also true for the next number. In both cases, we are using the Well-Ordering Principle as the starting point for the induction proof.

4. Can the Well-Ordering Principle be used to prove other mathematical concepts?

Yes, the Well-Ordering Principle can be used to prove many other mathematical concepts, such as the existence of prime factorizations and the existence of greatest common divisors. It is a powerful tool for proving statements that involve the set of positive integers.

5. Are there any limitations to using the Well-Ordering Principle in mathematical proofs?

While the Well-Ordering Principle is a useful tool in mathematical proofs, it does have some limitations. It can only be used for sets of positive integers, and it does not apply to infinite sets. In some cases, other proof techniques may be more appropriate or necessary.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Topology and Analysis
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
8K
  • Precalculus Mathematics Homework Help
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
24
Views
4K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
Back
Top