0
$\begingroup$

I have a question about general proof writing. Unfortunately I don't have an explicit example to illustrate my question, but here it is:

Let's say you wanted to prove something by contradiction. Begin the proof as you normally would, if the statement to be proven is $P$, assume ~$P$. Now, instead of showing that this leads to a contradiction directly, choose some mathematical statement $Q$ that is known to be true and can be proven using induction. Now begin to prove $Q$ using induction, but in the inductive step, show that ~$P$ leads to failure of the inductive step. Would this be an acceptable way to prove something?

Thanks for any input.

$\endgroup$
  • $\begingroup$ Could you make your question less verbose and a little more clear? I'm genuinely having a difficult time trying to really understand what your question is. $\endgroup$ – Daniel W. Farlow Feb 8 '15 at 5:03
  • $\begingroup$ Edited. If this isn't clear enough, I can edit it again. Sorry about that, I would put an explicit example up but I'm having a tough time thinking one up. $\endgroup$ – user208786 Feb 8 '15 at 5:09
  • $\begingroup$ I think that's ok, provided the failure implies that $Q$ is wrong but not just "not able to show that $Q$ is correct by induction". $\endgroup$ – velut luna Feb 8 '15 at 5:16
0
$\begingroup$

That should work,but it seems like a rather convoluted way to solve the problem unless Q is the only relevant statement you know how to prove by induction. A direct argument by contradiction would be a better choice because it probably involves fewer steps.

In general, we use inductive proofs when the claim involves sets that are indexed by the natural numbers. Any such statement will be provable by induction if it is in fact true. If you're using contradiction,it usually proves a result for all cases and induction becomes irrelevant. A perfect example off the top of my head is the classical proof of the infinity of prime numbers. By assuming there are finitely many primes and proceeding with a prime product decomposition, the claim blows up in a few lines. No induction needed.

Does this help?

$\endgroup$
  • $\begingroup$ Yes, a lot, thank you. I agree, it does seem like a convoluted way to solve the problem. I've never actually tried this, hence the lack of explicit example, I was just wondering if one could do it if all else failed, but it seems that if this method would work, than an easier, simpler method should also work, thus there should be no need in the first place. $\endgroup$ – user208786 Feb 8 '15 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy