2
$\begingroup$

I was looking for examples of Proof by contradiction to teach my A-Level students and chanced upon this website:http://www.personal.kent.edu/~rmuhamma/Philosophy/Logic/ProofTheory/proof_by_contradictionExamples.htm

I don't believe that Example 4 (appended below) is proof by contradiction and I hope that someone is able to concur. I think the method used is actually Proof by Contrapositive where the author shows that (not Q) implies (not P) and therefore P implies Q. Proof by Contradiction should entail supposing that the contrary is true at the beginning and then hope to find a contradiction along the way. The contrary would be if $n^2$ = odd then n is even.

Going with this idea, if we let $n^2$ = 2p + 1 and let n = 2q where p, q are integers, there must exist some p and q such that $$(2q)^2=2p+1$$ $$4q^2=2p+1$$ $$p=2q^2-1/2$$ The right hand side expression is not an integer (given the 1/2) and therefore p is not an integer. We arrive at a contradiction since we said at the beginning that p and q are integers. The contrary is shown to be false and therefore the original premise must be true ie if $n^2$ is odd then n is odd.

Is my argument correct?


Example 4: Prove the following statement by contradiction: For all integers n, if $n^2$ is odd, then n is odd.

Proof:

Suppose not. [We take the negation of the given statement and suppose it to be true.] Assume, to the contrary, that ∃ an integer n such that $n^2$ is odd and n is even. [We must deduce the contradiction.] By definition of even, we have

                                                    n = 2k  for some integer k.

So, by substitution we have

                                                    n . n = (2k) . (2k)

= 2 (2.k.k)

Now (2.k.k) is an integer because products of integers are integer; and 2 and k are integers. Hence,

                                                    n . n = 2 . (some integer)

or $n^2$ = 2. (some integer)

and so by definition of $n^2$ even, is even.

So the conclusion is since n is even, $n^2$, which is the product of n with itself, is also even. This contradicts the supposition that $n^2$ is odd. [Hence, the supposition is false and the proposition is true.]


$\endgroup$
3
  • 1
    $\begingroup$ But can a proof by contrapositive not be recognized as a proof by contradiction in disguise? You want to prove $p\to q $ and try to achieve that by showing that the assumption $\neg[ p\to q] $ or equivalently $p\wedge \neg q $ leads to a contradiction. This by showing that $\neg q\to\neg p $. $\endgroup$
    – drhab
    Apr 1, 2020 at 9:57
  • $\begingroup$ If we go by the "definition" of Proof by Contradiction, it has to begin with the supposition that the contrary is true which is not the route the author is taking. Being new to this area myself, I am not sure and hence my question. $\endgroup$
    – ertorque
    Apr 1, 2020 at 11:05
  • $\begingroup$ Proofs that we write in textbooks or homework or research articles are not formal proofs in the sense of mathematical logic -- they are sketches of formal proofs with enough detail to make clear (to an appropriate reader) that it describes a valid formal proof. So the distinction between proof by contradiction vs. proof by contrapositive -- which might be clear in a totally formal proof -- may be ambiguous in the written sketch, and ultimately come down to the translation that is made from the sketch to the formal proof -- both translations are possible. $\endgroup$
    – Ned
    Apr 1, 2020 at 15:14

1 Answer 1

1
$\begingroup$

Your proof by contradiction is fine (except that it contained a typo that I fixed in an edit).

But also the proof appended below can be classified as a proof by contradiction.

The other starts with "suppose not" which means that an integer $n$ must exist with: $$n^2\text{ is odd and }n\text{ is even }\tag1$$

Then he reaches the conclusion that:$$n^2\text{ is even}\tag2$$

It is evident that $(1)$ and $(2)$ cannot be true together so a contradiction is found.

The conclusion is that $(1)$ is false.


Actually both a proof by contradiction and a proof by contrapositive rest on the Boolean assumption that a statement is true or false and there is no third possibility (tertium non datur).

$\endgroup$
3
  • $\begingroup$ I now see the logic of your argument that the author's proof can (also) be considered proof by contradiction but it is apparent that it is also proof by contrapositive. No wonder you call the latter a disguise of the former. $\endgroup$
    – ertorque
    Apr 1, 2020 at 16:06
  • $\begingroup$ Still it's hard to wrap my head around the fact that one same method can be considered as either this or that proof. Will there be a proof question whose method is considered to be solely "by contrapositive"? $\endgroup$
    – ertorque
    Apr 1, 2020 at 16:22
  • $\begingroup$ Not that I can think of. I am not a logician but in introductions I never encountered that the two concepts were treated separately in an explicit way. Also - as I argued in my answer - they rest on the same principle. It is no coincidence that both are forbidden in intuitionistic logic. $\endgroup$
    – drhab
    Apr 1, 2020 at 17:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .