n and m so that n and m have no common factor. A real number that is not
rational is said to be irrational. Show that is irrational.
As in all proofs by contradiction, we assume the contrary of what we want to
show. Here we assume that is a rational number so that it can be written as
where n and m are integers without a common factor. Rearranging (1.5), we have
Therefore, n 2 must be even. This implies that n is even, so that we can write n =
2k or
and
Therefore, m is even. But this contradicts our assumption that n and m have no
common factors. Thus, m and n in (1.5) cannot exist and is not a rational
number.
This example exhibits the essence of a proof by contradiction. By making a
certain assumption we are led to a contradiction of the assumption or some
known fact. If all steps in our argument are logically sound, we must conclude
that our initial assumption was false.
EXERCISES
1. Use induction on the size of S to show that if S is a finite set, then |2 S | = 2 |S| .
2. Show that if S 1 and S 2 are finite sets with |S 1 |= n and |S 2 | = m, then