Explain in detail why the following \"proof\" is incorrect. Theorem 1. All posit

Question

Explain in detail why the following "proof" is incorrect. Theorem 1. All positive integers are equal. Proof. We show that any two positive integers are equal, from which the result follows. We do this by induction on the maximum of the two numbers. Let P(n) be the statement "if r and s are positive integers and max{r, s} = n then r = s". Clearly P(1) is true. Suppose that P(n) is true and let r, s be positive integers whose maximum is n + 1. Then max{r - l, s - 1} = n. By the inductive hypothesis, r - 1 = s - 1 and hence r = s. Thus P(n + 1) is true. The result is now proved by mathematical induction.

Explanation / Answer

The "proof" is incorrect because r-1 and s-1 need not be both positive integers.

For e.g, if r = 1 and s = 6, then r-1 = 0 and s-1 = 5.

Further the "proof" is incorrect as it decrements (increments) both r and s by 1.

P(1) only compares r = 1 and s = 1. Therefore any P(n) would be the case for r = s only and not for any r ans s.

For e.g if we have r = 1 and s = 2, then max{r,s} = 2. Max {r-1,s-1} = max{0,1} and not {1,1} as expected.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.