Q6: What is wrong with the following \"proof\"? (3pt) Show that \"all horses are

Question

Q6: What is wrong with the following "proof"? (3pt) Show that "all horses are the same color" Let P(n) - a set of n horses being the same color Basis step: P(1) is true because one horse is the same color Assume P(k) is true, i.e., all the horses in any set of k horses are the same color Show that P(k + 1) is true: Let h1, h2,..., hx,hk+1 be k +1 horses in a set By inductive hypothesis [hi, h2. .../h^) has the same color and (h2,h3,, hk+1) have the same color. Therefore h1, h2, h3, ..., hk+1) has the same color. 2,n3nk+1

Explanation / Answer

Suppose we assume that k=1

In this case, 1 horse is of the same color. This holds true.

Now suppose there are (k+1) that is two horses.

P(1) is true because 1 horse has the same colour.

However {1} and {2} may be disjoint sets. This means that the horse 2 might have a different colour than horse1.

Therefore, although {h1, h2,...hk) hold and {h2, h3, ....hk+1) hold, {h1, h2,h3,....hk+1) which in our case is {h1,h2} is not true. Therefore the proof is incorrect.

However {1} and {2}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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