TECTechnics Classroom   TECTechnics Overview

The Contradiction Proof Technique is one of the common proof techniques used when the Forward-Backward Proof Technique is not suitable for the given proof problem.
Suppose If A then B is a proposition involving statements A and B. The contradiction proof technique (Figure 121.3) begins by assuming that B is false (i.e, not B). The problem is proved if at the end the assumption is contradicted.

(a) Prove, by contradiction, that if n is an integer and n2 is even, then n is even.
(b) Prove, by contradiction, that at a party of x people, where x ≥ 2, there are at least two people who have the same number of friends at the party.
(c) Prove, by contradiction, that there are an infinite number of primes.

The strings: S7P2A21 (Identity - Physical Property).

The math:
Pj Problem of Interest is of type identity (physical property). Proofs establish truths. So they are identity problems.

(a) Initial assumption: not B.
So, for n2 even, n is odd.
So, there is an integer k such that n = 2k + 1.
So, n2 = (2k + 1)2
So, n2 = 4k2 + 4k + 1
So, n2 = 2(2k2 + 2k) + 1
So, n2 is odd.

(b) Initial assumption: not B.
So, no two people at the party has the same number of friends
So, the people at the party can be numbered in such away that can be represented by an ordered pair (p,f). Where p is the xth person at the party and f is the number of friends p has. The ordered pair will look like this:
(1,0), (2,1) ...(x, x-1)
It then follows that the person with (x-1) friends is a friend with the person with no friends. A contradiction.