4
$\begingroup$

When I was in highschool I was taught how to prove statements using Proof by contrapositive. I also learned how to prove statements using mathematical induction. Now I realize that, as the inductive step is a conditional statement, it might be proved using proof by contrapositive. However, I cannot find an example that uses this technique but in an easier way than regular induction. Is there a case where this is useful? (Using both concepts)

$\endgroup$
3
$\begingroup$

As a concrete example, consider the following two Peano Axioms:

$PA 1: \forall x \ \neg s(x) = 0$

$PA 2: \forall x \forall y (s(x) = s(y) \rightarrow x = y$

These two axioms are about the successor function $s$, normally understood as $s(x) = x+1$

Using induction and contraposition, you can now prove that $\forall x \ s(x) \not = x$:

Base: $x=0$. By $PA1$, we have $s(0) \not = 0$. Check!

Step: Take some arbitrary $n$. We want to show the conditional $s(n) \not = n \rightarrow s(s(n)) \not = s(n)$

Well, we can do this by contraposition: By $PA2$ we immediately get $s(s(n))=s(n) \rightarrow s(n)=n$. Check!

===

As a more general comment, I think you might also be interested in learning about the proof technique of Proof by Infinite Descent, which combines ideas from induction and proof by contradiction.

In infinite Descent, you prove that no natural number has a certain property by proving that if there is a number with that property, then there will always be a smaller number with that property. But since such a 'descent' along the natural numbers has to come to a stop at some point, no 'infinite descent' is possible.

As it turns out, Infinite Descent is very closely related (in fact, it is equivalent) to Strong Induction, but it has a different conceptual flavor.

$\endgroup$
1
$\begingroup$

In the sequel $\mathbb N=\{0,1,2,3,\dots\}$.


You can start any proof by induction - where you prove something of the form $\forall n\in\mathbb N[P(n)]$ and $P$ denotes a property of natural numbers - by assuming that the statement is not true.

That means that the set $\{n\in\mathbb N\mid \neg P(n)\}$ is not empty and non-empty subsets of $\mathbb N$ have a smallest element.

Now let $n_0$ denote this element, so that $\neg P(n_0)$ and for every $k<n_0$ we have $P(k)$.

Then the base case is the same as proving that $n_0\neq0$ so that $n_0-1\in\mathbb N$ with $P(n_0-1)$.

Then the inductive step is the same as proving that $P(n_0-1)$ implies $P(n_0)$ and a contradiction is found.

A contrapositive proof with application of induction is born.

$\endgroup$

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.