6.1 Proving Statements with Contradiction

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-06 Teacher: Prof. Musacchio

Proof by Contradiction

Rational Def

• A real number $x$ is rational if $x=a/b$ for some $a,b\in \mathbb{Z}$. Also, $x$ is irrational if it is not rational, that is if $x\ne a/b$ for every $a,b\in Z$

Example 1

• Proposition The number $\sqrt{2}$ is irrational.
  • Proof. Suppose for the sake of contradiction that it is not true that $\sqrt{2}$ is irrational.
  • Then $\sqrt{2}$ is rational, so there are integers $a$ and $b$ for which $\sqrt{2}=a/b$ . (6.1)
  • Let this fraction be fully reduced; in particular, this means that a and b are not both even. (If they were both even, then the fraction could be further reduced by factoring 2’s from the numerator and denominator and canceling.)
  • Squaring both sides of Equation 6.1 gives $2=a^2{b}^2$ , and therefore $a^2=2b^2$. (6.2)
  • From this it follows that $a^2$ is even. But we proved earlier (Exercise 1 on page 136) that $a^2$ being even implies a is even.
  • Thus, as we know that a and b are not both even, it follows that b is odd.
  • Now, since a is even there is an integer $c$ for which $a=2c$.
  • Plugging this value for a into Equation (6.2), we get $(2c{)}^2=2b^2$, so $4c^2=2b^2$, and hence $b^2=2c^2$. This means $b^2$ is even, so $b$ is even also. But previously we deduced that $b$ is odd.
  • Thus we have the contradiction $b$ is even and $b$ is odd.