6.3 Combining Techniques

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

Proof by Contradiction

Example

• Proposition Every non-zero rational number can be expressed as a product of two irrational numbers. Reworded as ” If r is a non-zero rational number, then r is a product of two irrational numbers.”
  • Proof Suppose $r$ is a non-zero rational number. Then $r=ab$ for integers $a$ and $b$. Also, $r$ can be written as a product of two numbers as follows: $r=\sqrt{2}\ast \frac{r}{\sqrt{2}}$
  • Assume for the sake of contradiction that $\frac{r}{\sqrt{2}}$ is rational.
  • This means: $\frac{r}{\sqrt{2}}=\frac{c}{d}$
  • for integers $c$ and $d$, so $\sqrt{2}=r\frac{d}{c}$
  • But we know $r=ab$ , which combines with the above equation to give: $\sqrt{2}=r\frac{d}{c}=\frac{a}{b}\ast \frac{d}{c}=\frac{ad}{bc}$
  • This means $\sqrt{2}$ is rational, which is a contradiction because we know it is irrational.
  • Therefore $\frac{r}{\sqrt{2}}$ is irrational
  • Hence $r=\sqrt{2}\ast \frac{r}{\sqrt{2}}$ is a product of two irrational numbers