Analyzing Induction Proof: Correct or Not?

[ryou00730]

Homework Statement

Consider the following induction proof.
Discuss whether the proof is correct or not, and if not, explain precisely why
not.
Theorem: Every cpu is made by the same manufacturer.
Proof: We prove this by induction. Let P(n) mean that for any set of n
cpu’s , they are all made by the same manufacturer.
Base case: P(1) means that any set of a single cpu is made by a same
manufacturer. But this is obviously true, since a single cpu can only be made
by a single manufacturer.
Induction step: Assume as an induction hypothesis that for any set of k
cpu’s, they must all be made by the same manufacturer. We now prove that
this implies that any set of k + 1 cpu’s are made by the same manufacturer.
Let S = {c1, c2..., ck, ck+1} be any set of k+1 cpu’s. We will show that we
can prove all these cpu’s are made by the same manufacturer, assuming the
induction hypothesis. Consider the set S − {ck+1}. This is a set of k cpu’s,
so by the induction hypothesis they are all made by the same manufacturer,
say M. Thus c1 and ck are both made by M. Now consider the set S −{ck},
which is also a set of k cpu’s. Again by the induction hypothesis the cpu’s
are all made by the same manufacturer, so c1 and ck+1 are made by the same
manufacturer. As c1 is made by M, then ck+1 is also made by M. Thus M
makes all the cpu’s in S. qed.


I think that the flaws in this are that they should be assuming n, and proving n+1, not assuming k, and prooving n+1. I also think that they should have stated somewhere a relationship between the set S, and P(n), because it doesn't really define P(n) to be anything to do with the set S = ... Does anyone see what I should be pointing out?

 

[hgfalling]

Who is this "the same manufacturer" character?

 

[ryou00730]

I'm not really certain. I feel like he would need another base case as well.. like base of P(2), because just because one cpu is made by this "same manufacturer" doesn't mean that 2 are, or all are for that matter. I'm not really sure here what's wrong though, or what I'm suppose to be doing.

 

[hgfalling]

In order for induction to work, one has to prove the P(k)->P(k+1) for all k greater than or equal to a base case.

Now in this proof, they used the base case of P(1), which was fine. Then they claimed that P(k) implies P(k+1) for all k $\geq$ 1. Try to verify their proof for k=1.

 

[ryou00730]

I don't exactly follow what you want me to do. So you want me to verify in the proof for k=1? So you mean you want me to verify that it works for P(2) or? Now that I look at it, the proof looks correct, or is there something in there actually completely wrong?

 

[hgfalling]

Let's go through the induction step for P(k)->P(k+1). Then we'll fill in 1 for k, and see how that works out.

Claim.
Assume that P(k) is true. All sets of k cpus are made by a single manufacturer.
Then this implies that P(k+1) is true; all sets of k+1 cpus are made by a single manufacturer.

Proof.
Let S={c1,c2,...,ck,ck+1}.
Consider the set S-{ck+1}. This set consists of k cpu, so it is made by a single manufacturer M because we assume P(k) is true. Then c1 and ck are made by M.
Next consider the set S-{ck}. This set consists of k cpu also, so it is made by a single manufacturer as well. So c1 and ck+1 are made by the same manufacturer.

Now fill in 1 for k.

Claim.
Assume that P(1) is true. All sets of 1 cpu are made by a single manufacturer.
Then this implies that P(2) is true; all sets of 2 cpus are made by a single manufacturer.

Proof.
Let S={c1,c2}.
Consider the set S-{c2}={c1}. This set consists of 1 cpu, so it is made by a single manufacturer M because we assume P(1) is true. Then c1 and c1 are made by M.
Next consider the set S-{c1}={c2}. This set consists of 1 cpu also, so it is made by a single manufacturer as well. So c1 and c2 are made by the same manufacturer.

OOPS! False claim. Why?

 

[ryou00730]

Mistake: The inductive step fails from n=1 to n=2. If we assume S=(c1, c2..., ck, ck+1) is a set of k+1 cpus, then when k=2, S=(c1, c2). If we take S-c1 then this is a set of k cpus and we get S-c1 = (c2) should be a set of k cpus (specifically k=1), but we already showed k=1 is P(1) = (c1). So we have a contradiction here, which means since the inductive step fails from n=1 to n=2, the statement is not proved.
Does this seem correct? Or would you be able to help me better word it?

 

[ryou00730]

Oh I didn't notice you posted a reply. So this is a false claim because P(1)= (c1), and we did not prove that it could also equal (c2)?

 

[hgfalling]

OK, no. P(1) is the statement that any set of 1 cpu is made by a single manufacturer. This is obviously true. P(2) is the statement that any set of 2 cpus is made by a single manufacturer.

Now their proof tries to work like this:

They pick a k-sized subset of k+1 cpus which include c1 and ck+1. By their assumption that any k-sized set is made by a single manufacturer, c1 and ck+1 are made by some manufacturer M.
Then they pick a different k-sized subset which includes c1 through ck. Again by the assumption than any k-sized set is made by a single manufacturer, c1 and ck are made by the same manufacturer. Since c1 is made by M from the first part, c1 through ck are made by M, and so all the cpus are made by M. So any set of size k+1 is made by M.

But when k is 1, this all fails, because a 1-sized subset can't include both c1 and ck+1, which means you can't link up the manufacturer of ck+1 to the other cpus. Does that make sense?

 

[ryou00730]

hmmm, not entirely. I follow most of it, just the part where you get down to a 1 size subset. Why does when k=1 necessarily have to have c1 and ck+1 in the size one subset? I thought it was okay to have just c1 in the size 1 subset as proven in the base step?

 

[hgfalling]

Well, you need to have two different cpus in some subset of size k at some point, otherwise there's no "same manufacturer." But if k is one, there can never be two different cpus in a size-k subset.