Problem 1

Find the error on the following proof that 2 = 1. Consider the equation a = b. Multiply both sides by a to obtain a2 = ab. Subtract b2 from both sides to get a2 b2 = ab b2. Now factor each side to get (a + b)(a b) = b(a b). Now divide each side by (ab) to get a+b = b. Finally, let a and b equal 1, which shows that 2 = 1.

Problem 2

Prove or disprove the following equality: ({a}{b}) = {a, b}

Problem 3

Prove that a language, L, is recursive iff there exists an algorithm that enu- merates L.