Massachusetts Institute of Technology Handout 2 Mathematics for Computer Science August 1, 2005 Professor 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 cannot 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 the value \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}.