I have a question regarding proof by contradiction and the well ordering principle on integers.

Okay lets says for example an arbitrary value $p$ is a positive integer and which I assume is the smallest positive integer for some property.

Then lets say I find an arbitrary value $r$, also a positive integer, which I calculate to be less than $p$ for the same property. Then I have a contradiction.

So my question is how is this possible. Lets substitute $1$ for $p$ and it satisfies the property, then how can I find $r$ since there is no smaller positive integer? I'm not sure if $0$ is considered a positive integer but if it is then substitute $p$ for $0$.

  • 2
    $\begingroup$ Another term for this is proof by infinite descent. I don’t have time to write an answer but you may find something helpful here en.m.wikipedia.org/wiki/Proof_by_infinite_descent $\endgroup$ – spaceisdarkgreen Mar 1 at 20:18
  • 1
    $\begingroup$ It will also help to get more of a feel for the hypothetical nature of proofs by contradiction by studying other proofs by contradiction that might be easier to understand. $\endgroup$ – spaceisdarkgreen Mar 1 at 20:21

The point of the proof by contradiction is that you can find no such $r$. That's the contradiction. You assume something you want to be false, then prove something that can't be possible. It may be helpful to give a specific example of a proof that's confusing you.

  • $\begingroup$ mathoverflow.net/questions/107153/… $\endgroup$ – rert588 Mar 1 at 20:13
  • $\begingroup$ See the answer using the well ordering principle $\endgroup$ – rert588 Mar 1 at 20:13
  • $\begingroup$ from the link sent $\endgroup$ – rert588 Mar 1 at 20:14
  • $\begingroup$ Yeah, so in that proof you assume that $\sqrt{2}$ is irrational. Then using well ordering you can find a least $q$ such that $q\sqrt{2}$ is an integer. Then without assuming anything else, you can find $r < q$ a positive integer such that $r \sqrt{2}$ is a positive integer, which is a contradiction by minimality of $q$. $\endgroup$ – bitesizebo Mar 1 at 20:17
  • $\begingroup$ So the fact that an r can't actually be found is part of the contradiction. Am I correct? $\endgroup$ – rert588 Mar 1 at 20:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.