Massachusetts Institute of Technology Handout 34 6.042J/18.062J: Mathematics for Computer Science October 15, 1998 Professors Nancy Lynch and Srinivas Devadas

Common Errors on Problem Sets

Problem 1. Write the statement “n is prime” in propositional form. Let the universe of discourse be the natural numbers N.

Incorrect answer:

(n > 1) ∧ (∀x : (¬(x = 1) ∧ ¬(x = n)) ∧ (n/x ∉ N))

The problem is in the long chain of ANDs. The last AND should be swapped for an IMPLIES. As it stands, this proposition is satisfied for NO number n ∈ N. One of the things it says is ∀x : ¬(x = 1). There is, however, a value of x for which (x = 1), namely, 1. Students often mistakenly swap → and ∧.

The following is a correct answer:

(n > 1) ∧ (∀x : (¬(x = 1) ∧ ¬(x = n)) → (n/x ∉ N))

Problem 2. Write the statement “There is a deceitful person who did not give gifts to anyone”. Let the universe of discourse be all people. Let D(x) be true iff x is deceitful. Let G(x, y) be true iff x gave a gift to y.

Incorrect answer:

∃x¬∃y : (D(x) ∧ G(x, y))

The problem is that the statement does not say that such a person exists. Suppose everyone in the world gave a gift to someone, and at least one person, call her z, is not deceitful. Then the statement “There is a deceitful person who did not give gifts to anyone” is certainly not true. There does exist an x, however, for which there is no person y for which x is deceitful and generous. If x = z, then there is no y for which D(x) holds. The problem arises when placing statements, such as D(x) inside a ∃ or ∀ with which they have nothing to do(i.e. ∃y : D(x).

Another incorrect answer:

∃x : (D(x) → ¬∃y : G(x, y))

The problem here is once again the swapping of → and ∧. If D(x) is not satisfied, then you have the case of false implies anything. Once again, if x = z, the rest of the statement holds, but there is no deceitful person who was unkind to everyone.

The following is a correct answer:

∃x : (D(x) ∧ ¬∃y : G(x, y))

Problem 3. A real number r is called sensible if there exist positive integers a and b such that \sqrt{a/b} = r. For example, setting a = 2 and b = 1 shows that \sqrt{2} is sensible. Prove that 3 \sqrt{2} is not sensible. (Consider only positive real roots in this problem.)

Incorrect proof:

Proof. The proof is by contradiction. Assume for the purpose of contradiction that ^{3} \sqrt{2} is sensible. Then there exist positive integers a and b such that \sqrt{a/b} = ^{3} \sqrt{2}. Squaring both sides of this equation gives a/b = ^{3} \sqrt{4}. This can be rewritten as a = b · ^{3} \sqrt{4}. Because ^{3} \sqrt{4} is not an integer, at least one of a and b is not an integer, which leads to a contradiction.

The error is in the last sentence. It states that multiplying an integer by a non-integer yields a non-integer. This is incorrect. Consider the following values for a, b, and c. a = 2, b = 5, c = 2/5 (2 = 5 ∗ 2/5) ∧ (2/5 ∉ Z), but 2 and 5 are both integers.

A correct proof should show that ^{3} \sqrt{4} is not rational in order to reach a contradiction.

Problem 4. Use induction to prove that the following equation holds for all n ≥ 2.

(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n}) = \frac{1}{n}

Proof. The proof is by induction on n. In the base case, P (2) is true because (1 − \frac{1}{2}) = \frac{1}{2}. In the inductive step, for n ≥ 2 assume P (n) to prove P (n + 1) as follows.

(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n}) (1 − \frac{1}{n + 1}) = \frac{1}{n + 1}
P (n) · (1 − \frac{1}{n + 1}) = \frac{1}{n + 1}
\frac{1}{n} · (1 − \frac{1}{n + 1}) = \frac{1}{n + 1}
\frac{1}{n} · \frac{n}{n + 1} = \frac{1}{n + 1}
\frac{1}{n + 1} = \frac{1}{n + 1}

This shows that P (n) implies P (n + 1) and the claim is proved by induction.

There are three problems with this proof. The first is that the inductive hypothesis, P (n), was never defined. Even though it may seem obvious to you what it is, you should always define it. The second problem is a misuse of the inductive hypothesis in the proof. The proof makes the statement:

P (n) · (1 − \frac{1}{n + 1}) = \frac{1}{n + 1}

The problem here is that the proof uses P (n) to be the expression

(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n})

In reality, the proposition P (n) is the entire statement of equality, namely

(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n}) = \frac{1}{n}

The final problem is the chain of “equalities”. The first equality is P (n + 1), which isn’t known yet to be true. The way to do this correctly is to reverse the equalities to start with something true and work from there.

A corrected proof, by reversing the order of the steps follows:

Proof. The proof is by induction on n. Let P (n) be the proposition that the above equation holds. In the base case, P (2) is true because (1 − \frac{1}{2}) = \frac{1}{2}. In the inductive step,for n ≥ 2 assume P (n) to prove P (n + 1) as follows.

\frac{1}{n + 1} = \frac{1}{n + 1}
\frac{1}{n} · \frac{n}{n + 1} = \frac{1}{n + 1}
\frac{1}{n} · (1 − \frac{1}{n + 1}) = \frac{1}{n + 1}
(1 − \frac{1}{2}) (1 − \frac{1}{3}) ⋯ (1 − \frac{1}{n}) (1 − \frac{1}{n + 1}) = \frac{1}{n + 1}

This shows that P (n) implies P (n + 1), and the claim is proved by induction.