# Proof by contradiction (2 ways of writing it)

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 ?)

• 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. Jul 14, 2020 at 1:19
• 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. Jul 14, 2020 at 1:20

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.

• You mean they both are contradiction proofs, but apply the method in different steps/places. And they both valid proofs ? Jul 13, 2020 at 20:00
• yes, indeed. Both are valid and both use contradiction. Jul 13, 2020 at 20:01

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}$$

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.