Massachusetts Institute of Technology Handout 2 Pre-Algorithms Minicourse July 30, 2001 Charles E. Leiserson

Proofs: Valid or Invalid?

Determine whether the following proofs are valid. If a proof is wrong, pinpoint the precise error. If it is correct, justify each step. Problem 1. Claim: The number lg 3 = log_{2} 3 is irrational. Proof. A number is irrational if it is not the ratio of two integers. Therefore, since lg 3 can not be written in the form a/b where a and b are integers, it is irrational. □

Problem 2. Claim: If n^{2} ≤ 9 then, n ≤ 3. Proof. If n > 3, then n^{2} > 9. □

Problem 3. Claim: If a and b are two equal real numbers, then 2 = 1. Proof.

a = b
a^{2} = ab
a^{2} − b^{2} = ab − b^{2}
(a − b)(a + b) = (a − b)b
a + b = b
2b = b
2 = 1
□

Problem 4. Claim: There exist irrational numbers a and b such that a^{b} is a rational number. Proof. Note that \sqrt{2} is irrational. Now consider \sqrt{2}^{\sqrt{2}}. If this quantity is rational, then the claim holds for a = \sqrt{2} and b = \sqrt{2}. On the other hand, if the quantity \sqrt{2}^{\sqrt{2}} is not rational, then the claim holds for a = \sqrt{2}^{\sqrt{2}} and b = \sqrt{2}. □