Find the error in the following proof that all horses are the same color.

CLAIM: In any set of hhorses, all horses are the same color.

PROOF: By induction on h.

Basis: For$\mathit{h}\mathbf{}\mathbf{=}\mathbf{}\mathbf{1}$ . In any set containing just one horse, all horses clearly are the

same color.

Induction step: For $\mathit{k}\mathbf{\ge }\mathbf{1}$, assume that the claim is true for $\mathit{h}\mathbf{}\mathbf{=}\mathbf{}\mathit{k}$ and prove that

it is true for $\mathit{h}\mathbf{}\mathbf{=}\mathbf{}\mathit{k}\mathbf{}\mathbf{+}\mathbf{}\mathbf{1}$ . Take any set H of $\mathit{k}\mathbf{}\mathbf{+}\mathbf{}\mathbf{1}$horses. We show that all the horses

in this set are the same color. Remove one horse from this set to obtain the set ${\mathit{H}}_{\mathbf{1}}$

with just $\mathit{k}$ horses. By the induction hypothesis, all the horses in ${\mathit{H}}_{\mathbf{1}}$ are the same

color. Now replace the removed horse and remove a different one to obtain the setrole="math" localid="1664255899729" ${\mathit{H}}_{\mathbf{2}}$

. By the same argument, all the horses in ${\mathit{H}}_{\mathbf{2}}$are the same color. Therefore, all

the horses in H must be the same color, and the proof is complete.

Step by step solution

01

Explain the given information.

Given is the claim that in any set of h horses, all horses are the same color. The claim has been proved by the induction method.

02

Find the error in the proof.

There are two statements are provided in the proof, $H_1\text{and}{H}_2$ .

The induction is valid for greater than 2 only.

The given proof, indicates that all the horses present in $H=H_1\cup H_2$are identical if $H=H_1\cap H_2$is not empty. This results in true always. Then exactly one horse out of the two horses will be consist in each $H_1\text{and}{H}_2$.

Certainly the single horse in $H_1$and the single horse in $H_2$has its peculiar color. Therefore, it has no meaning to conclude that the horses have the same color.

So, the given proof is wrong.

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!