1
$\begingroup$

I have a question regarding proof by contradiction (more like the way of writing it).

Let try to prove an easy proposition : For all integer $n$, if $n$ is even, then $n+1$ is odd.

  1. Negate the whole proposition : There exists an integer $n$ such that $n$ is even and $n+1$ is even. Since $n+1 = 2k$ for some integer $k$, $n = 2k-1$, a contradiction.

  2. Let $n$ be an integer. Assume that n is even. We want to show that $n+1$ is odd. Suppose to the contrary that $n+1$ is even. Then $n+1=2k$ which gives $n = 2k-1$, a contradiction.

So the first way (1) negate the whole thing and get a contradiction. Along the way, there are steps setting up quantifier "there exists".

The second way, first set up the direct proof (there is a step doing for all quantifier). Then proceed to suppose a contradiction later.

The question is : Are they both a valid proof ? Are they both called a contradiction ? Or the first one is the contradiction ?(In this case, what is the second approach called ? Or it is NOT a valid proof ?)

$\endgroup$
2
  • $\begingroup$ They are both valid proofs by contradictions. The difference is subtle but they are equivalent. In the first you assume an exception and get a contradiction. In the second you show that $n$ is not that exception but that because $n$ is arbitrarty there can be no exception. $\endgroup$
    – fleablood
    Jul 14, 2020 at 1:19
  • $\begingroup$ This isn't part of the question but I wouldn't say $n = 2k-1$ is a contradiction that $n$ is even unless you prove $2k -1$ is always odd. $\endgroup$
    – fleablood
    Jul 14, 2020 at 1:20

3 Answers 3

1
$\begingroup$

Formally proof by contradiction is following: $$[(\neg P \Rightarrow Q) \land (\neg P \Rightarrow \neg Q)]\Rightarrow P$$ You first case directly use this formula from scratch. In second you use it from middle. Whenever you use it, imho, you can say, that you use proof by contradiction.

$\endgroup$
2
  • $\begingroup$ You mean they both are contradiction proofs, but apply the method in different steps/places. And they both valid proofs ? $\endgroup$
    – user117375
    Jul 13, 2020 at 20:00
  • 1
    $\begingroup$ yes, indeed. Both are valid and both use contradiction. $\endgroup$
    – zkutch
    Jul 13, 2020 at 20:01
1
$\begingroup$

Let $P(n)$ be that $n$ is even. So you want to prove the desired result of: $$\forall n\in\Bbb Z~.(P(n)\to\neg P(n+1))$$


  1. Negate the whole proposition : There exists an integer $n$ such that $n$ is even and $n+1$ is even. Since $n+1 = 2k$ for some integer $k$, $n = 2k-1$, a contradiction.

Because a contradiction is derived under the assumption that there exists some integer $n$ where $P(n)\wedge P(n+1)$ holds, therefore the desired result is proven.  A few extra steps may make this clearer.

$$\begin{split}\because\quad& \Big(\exists n\in\Bbb Z~.\big(P(n)\wedge P(n+1)\big)\Big)\to\bot\\&\neg \exists n\in\Bbb Z~.\big(P(n)\wedge P(n+1)\big)\\&\forall n\in\Bbb Z~.\neg\big(P(n)\wedge P(n+1)\big)\\\hline\therefore\quad &\forall n\in\Bbb N~.\big(P(n)\to\neg P(n+1)\big)\end{split}$$


  1. Let $n$ be an integer. Assume that n is even. We want to show that $n+1$ is odd. Suppose to the contrary that $n+1$ is even. Then $n+1=2k$ which gives $n = 2k-1$, a contradiction.

Because, for any integer $n$, we derive a contradiction under the assumption that $P(n+1)$ holds while also under the assumption that $P(n)$ holds; therefore the desired result is proven.

$$\begin{split}\because\quad&\forall n\in\Bbb Z~.\Big(P(n)\to\big(P(n+1)\to\bot\big)\Big)\\\hline\therefore\quad&\forall n\in\Bbb Z~.(P(n)\to\neg P(n+1))\end{split}$$

$\endgroup$
0
$\begingroup$

This is a useful question. Allow me to streamline the contrast between the two setups:

  1. Assume (to the contrary) that there exists an integer $n$ such that $n$ is even and $n+1$ is even.
  2. Let $n$ be an integer, supppose that $n$ is even, and assume (to the contrary) that $n+1$ is even.

When the two assumptions are negated, statements (1) and (2) become equivalent.

$\endgroup$

You must log in to answer this question.

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