Proof by Contradiction and Examples

15 Feb 2016

Given a set of premises S, a proposition P, and a contradiction F, the proof by contradiction is represented as:

S U {~P} |= F implies S |= P

Example

Prove that there is no greatest even integer.

Suppose that the proposition is false, i.e. there is greatest even integer N. We then need to show a contradiction.

There is greatest even integer N <==> for every even integer n, N >= n.

Now, suppose M = N + 2. Then, M is also an even and M > N (because M = N + 2). Hence, this contradicts the supposition that N >= n for all even integers.

Hence, the supposition is false and the statement there is no greatest even integer is true.

This completes the proof.

More Details

1. Link to Proof Theory section of Prof. Rashid’s homepage

2. Link to Wikipedia page