fettywap1738
New Member
- Joined
- Feb 24, 2018
- Messages
- 6
- Gender
- Undisclosed
- HSC
- 2019
What are the limitations of the method of proof by induction? i.e. What cant induction be used to solve?
Limitations of Induction Proofs (1 Viewer)
- Thread starter fettywap1738
- Start date
sida1049
Well-Known Member
- Joined
- Jun 18, 2013
- Messages
- 926
- Gender
- Male
- HSC
- 2015
Proof by induction is almost worthless if you don't have a gist of what you're looking for.
Induction won't work for statements over uncountable sets. For example, induction might work for statements of the form S(k) where k is a natural number, but not when k can take arbitrary real numbers (or enumeration over other uncountable sets).
In order for proof by induction to work, it's typical that the statement you're trying to proof exhibits some kind of dependent structure. That is, you can expect the truth of S(k+1) to be contingent on S(k) being true. If what you're trying to proof lacks this sort of connection between S(k+1) and S(k), then don't expect induction to work.
I've stumbled across various examples of induction failing for the three issues I've mentioned, but I can't offer them off the top of my head, since I always find them by accident in the process of brainstorming an attack on a problem.
Induction won't work for statements over uncountable sets. For example, induction might work for statements of the form S(k) where k is a natural number, but not when k can take arbitrary real numbers (or enumeration over other uncountable sets).
In order for proof by induction to work, it's typical that the statement you're trying to proof exhibits some kind of dependent structure. That is, you can expect the truth of S(k+1) to be contingent on S(k) being true. If what you're trying to proof lacks this sort of connection between S(k+1) and S(k), then don't expect induction to work.
I've stumbled across various examples of induction failing for the three issues I've mentioned, but I can't offer them off the top of my head, since I always find them by accident in the process of brainstorming an attack on a problem.