Theorem: all cows have the same color. proof: let the predicate P(n) be \"in any
ID: 3109738 • Letter: T
Question
Theorem: all cows have the same color. proof: let the predicate P(n) be "in any set of n cows, all the cows have the same color". Then we will prove: for all n P(n) by induction on n (a) Base case n=1: clearly, in any set with only one cow, all cows have the same color. (b) Induction step: show P(n) DoubleRightArrow P(n+1). Assume p(n), that is in any set with n cows, all cows have the same color. We need to show P(n+1), that is, if we have a set with n+1 cows C_1, C_2, C_3 ... C_n, C_n+1 all the cows have the same color. Consider the first n cows C_1, C_2, C_3 ... C_n, by our induction hypothesys they must all have the same color. Now consider the cows C_2, C_2, C_4 ... C_n+1; this is also a set on n cows, so they must all have the same color, but then C_1, C_2, C_3 ... C_n, C_n+1 all have the same color. The theorem is clearly false: not all cows have the same color, so the proof above must be incorrect. Tell me what is wrong with the proof.Explanation / Answer
a)
We will use induction. Base case n=1, This is vacuously true.
Inductive step:
Assume this holds for n-1 cows. Then take group c of n cows and remove cow c_i. Then c/c_i is a group of n-1 cows and is thus monochromatic, so all cows but c_i have the same color. Return c_i and remove cow c_j. c/c_j is also a group of n-1 cows and is monochromatic. But then c_i has the same color as the rest of the cows, and thus c is monochromatic.
This completes the proof.
-----------------------------------------------------------------------------------------------------------------------------------------------------------
False theorem: All cows are the same color.
Proof by induction:
P(n) is the statement: In every set of cows of size n, all n cows are the same color.
Base Case or P(1): One cow is the same color as itself. This is true by inspection.
Induction Step: Assume P(k) for some k1.
Proof of P(k+1):
Since {H1,H2,...,Hn} is a set of n cows, the induction hypothesis applies to this set. Thus, all the cows in this set are the same color.
Since {H2,H3,...,Hn+1} is also a set of n cows, the induction step likewise holds for set. Thus, all the cows in this set are the same color too.
Therefore, all n+1 cows in {H1,H2,H3,...,Hn,Hn+1} are the same color.
The issue the instructor was trying to point out is clearly valid. For the case n=1, there is only H1. So this case says nothing about possible overlapping elements of each set of (n+1), for instance H2 in the above proof.
But it was proposed that this was the only problem. Had you been able to prove that P(2) were true, then a proof of the above format would have been fine.
My interpretation is that yes, you could prove all cows are the same color, if you can prove that any set of two cows will be the same color. But this format would not work.
Why not?
The problem I see is that the above proof is for the existence of at least one particular pair of sets of cows of sizes n and n+1, such that in each set, all cows are the same color. Particularly when the set of size n is a subset of the set of size n+1. In order to prove the induction step, don't you need to prove that sets of sizes n and n+1, do not necessarily contain the same, overlapping elements?
You could prove that any cows can be added to a set of 2 cows. Take the last two, and they must be the same color, and so on. Whatever color the first two happen to be, all other cows must thus be the same color.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.