[eperdew]

I started to write out what is happening here more formally, but I think it was not very elucidating. No matter what, the problem is that the proof of the inductive step is wrong. The problem is (as mentioned in the article), that for sets of size two, your inductive hypothesis is not sufficient to prove that h1 and h2 are the same color.

Saying it's the base case that's wrong is a little weird. In general your base case can be vacuously true without any issue. However, if it is (and your goal is non-vacuously true for something), then your inductive step will require a branch in it. One side of the branch in your proof will look like a proof of a base case.

I have maybe a skewed view on this from using Coq.

[amitkgupta84]

You're 100% correct. I would be more unequivocal -- saying that the problem is the base case isn't just a little weird, it is incorrect. Your analysis nails it.

[diffeomorphism]

Disagree. The induction step works perfectly fine for n>=2. In particular, if you can give me the base case "any two horses have the same color", then this proof works and all horses have the same color.

The problem is that the base case is n=2, but the student checked n=0 and n=1.

[amitkgupta84]

The base case is not n=2, it’s clearly stated as n=1 in the proof.

The inductive step works fine if you introduce the premise n>=2. It is not valid to introduce that premise. The inductive step is therefore wrong.

The proof in the post is saying the base case is P(1) and the inductive case is that for all n, P(n) => P(n+1)

“P(1)” is true. “For all n, P(n) => P(n+1)” is false. The inductive step is wrong

A completely different proof not present in this post could be:

Base case: P(1) and P(2) Inductive case: for all n > 1, P(n) => P(n+1)

In that completely different proof, the inductive step would be correct and the base case would be wrong. That proof is not in the original post.

[diffeomorphism]

We don't even disagree about anything here.... We both say "P(n) => P(n+1)" does not work for n=1, but does work for n>1.

I would like to give the student partial credit for the "works for n>1" part and deduct points for the missing n=1 case. The two obvious ways to "fix" that are either giving a proof for "P(1)=>P(2)" (which is currently missing) or establishing P(2) another way and then using induction. Both are fixes of the same thing and not at all "completely different".

[Jensson]

The proof has errors, there is no fixing it, you can't prove that all horses have the same color given no data about horses. In this proof the base statement is 100% correct, in all sets of 1 horse all horses will have the same color. Hence the error has to be in the other part.

If a student was tasked with proving that all horses has the same color given no information about horses then the correct answer is "I can't prove this", the answer given in this article would give 0 points since the student obviously doesn't understand what they are doing. When you check that test, would you mark the base case as the source of the error of the proof, or would you mark the inductive step? The base case is correct, if you marked that part wrong the student would rightfully complain, their logic works there.

[shkkmo]

The base case is proven correctly, the inductive rules is proven OK except that the transitive set rule they invoke requires n>1

As such, the only data you would need yo prove that all sets of horses are the same color is that all pairs of horses are the same color.

I think zero points would be a very harsh grade given that an understanding of how to do an inductive proof was demonstrated and one minor error was made in an otherwise correct proof.

[diffeomorphism]

> The proof has errors, there is no fixing it,

You mean to tell me that horses are actually different colors? Really? /s

Anyways, as I said we agree already so no reason to waste further time on this.

[wisty]

No, the induction step works for n>=3. The induction step fails for n=2.

For n=2, you can't prove h1 is the same colour as h2, because you don't have a h3 to compare it to.

[diffeomorphism]

tomayto tomahto

We are talking about the exact same case. The induction step is n-> n+1 and works perfectly well for n+1=3 horses.

[mcphage]

Their inductive step is perfectly valid. However, requires a group of horses with one removed to still have a horse remaining. Using N=1 is an incorrect base case. Had they proved the N=2 base case, their entire argument would work.

Of course, you can’t prove the N=2 base case, so that’s why the argument uses the wrong base case.

[amitkgupta84]

The inductive step introduces a premise that “requires a group of horses with one removed to still have a horse remaining.” It is not valid to introduce this premise. The inductive step is not valid.

[diffeomorphism]

It is completely valid to do that. The induction starts at n=2. Nothing unusual about it, e.g. you can show that 2^n >10 for n>=4 that way.

[amitkgupta84]

I mean “valid” in the mathematical/logical sense. It does not follow from the stated assumptions that n > 1, in the inductive step is this proof.

This has nothing to do with the idea that it can be common practice to prove claims of the form for all n > N, P(n) by induction when N is a number like 4. Yes there is a perfectly valid way to use proof by induction to do such proofs. Has nothing to do with this blog post.

[shkkmo]

In a proof, you can absolutely assume something like "A is true", you do it as a part of a sub-proof. Then anything you prove in the sub-proof like "B is true" can be brought back into the main proof in the form: A implies B is true.

The blog post glosses over this assumption and thus ends up concluding "p(n) implies p(n+1)" instead of "p(n) implies (n>1 implies p(n+1))”

[mcphage]

The inductive step would work just fine with the correct base case.

[Jensson]

Nah, the inductive step is simply incorrect. For it to be correct it needs to say "for n > 1 the following is true", but it doesn't, the statement isn't true since they forgot to add that part. And if you added "for n > 1" to make the inductive statement correct then it is obvious where the reasoning goes wrong.

In other words, the base case is correct, in all sets of 1 horse all horses has the same color. The inductive step is not correct. Even if you changed the where you put the base case to N=2, the inductive steps reasoning is still wrong as long as it doesn't include the "for n > 1" part.

[mcphage]

You wouldn't need to add "for n > 2" to the inductive step, any more than you need to include "for n > 1" for arguments where the base step is 1, or "for n > 20" for arguments where the base step is 20.

[dsizzle]

The “vacuously true” part seems unnecessary (and weirdly subjective). The N=1 base case requires considering N=2 when you apply the inductive step and that fails.

[eperdew]

The example I'm about to give is overkill, but I'm trying to make my point very carefully.

Suppose you want to prove something for integers >= 2. E.g., suppose you want to prove for all n >= 2, n is positive. The statement you're trying to prove for a given n is actually

P(n) := n >= 2 -> n is positive

Let's prove it by induction.

P(0) is 0 >= 2 -> 0 is positive. P(0) is vacuously true, because 0 < 2.

Suppose P(n). We want to show P(n + 1). Our goal is

n + 1 >= 2 -> n + 1 is positive. Let's break this into the cases n >= 2 and n < 2.

For n >= 2, we assume P(n) and have the LHS of the implies. This gives us n is positive. Say by definition or by a lemma that n positive -> n + 1 is positive, and we handle this branch.

For n < 2, the inductive hypothesis tells us nothing. Assume the LHS of our goal, i.e. n + 1 >= 2. We want to prove n + 1 is positive. Well 2 is positive and therefore n + 1 is positive by transitivity.

This is what I mean by the base case not being special. E.g., in Coq, induction over the natural numbers always starts at 0. When you think about doing induction starting at another number, you're transforming your goal to include something of the form n >= m -> P(n).

[ashtonbaker]

> E.g., in Coq, induction over the natural numbers always starts at 0. When you think about doing induction starting at another number, you're transforming your goal to include something of the form n >= m -> P(n).

The concept of a “minimal base case” really weirded me out but I couldn’t quite put my finger on why. Thanks for the painstaking explanation, this was perspective-broadening.

[tsimionescu]

But does this do anything meaningful, or is it just pointless drudgery because Coq is a machine and can't 'understand'/assume even simple maths/logic if it isn't explicitly stated? This is not a slight on Coq by any means, just pointing out the difference between human proofs and machine proofs. (Humans can of course be tricked into thinking that subtly false statements are trivially true, which the much more meticulous machine proof would discover)

That is, what is being gained by looking at the vacuously true cases where n<2, when the only interesting base case is the one where the LHS of the implication is true?

[eperdew]

I wrote out quite a bit for this, but I think that the main point is that by falling back to the formalism, we see the the LHS of the implication affects our inductive hypothesis. I think this is something that is not clear if you just do "base case starting at n" style proofs."

As far as drudgery, Coq will solve the trivial cases automatically, so you'd never have to prove the n = 0 case by hand. That said, there's a reason most math is done on paper and not in Coq - there's usually an order of magnitude more detail and drudgery in a formal proof, even with automation.

[Ericson2314]

Pre formal methods, sophists spin false proofs like this example. Post formal methods, sophists spin false propositions.

[sidedishes]

I don't understand why it's more or less weird to say the base case is wrong vs. the inductive case is wrong. If H(n) is 'all sets of horses of size n contain horses of the same colour', the linked argument seems like

H(1) is true

H(n) => H(n+1) (with a sleight of hand that it's only for n >= 2)

It seems to me like changing either the argument to assert H(2) is true, or the scope of the second statement to include n = 1, would be enough. It seems the fault of both statements equally to not fit with the other, so why is it weirder to say the base case is wrong?

[amitkgupta84]

You just said it. The base case is true. The inductive case is wrong. You called it true “with sleight of hand”, but that’s more of a poetic statement; mathematically it’s simply wrong.

One could write a completely different proof where the base case(s) cover n=1,2 and the inductive step is as in the post. In such a proof, the base case would be wrong and the inductive step would be correct. But that’s a different proof, not the one in the post.

[Dylan16807]

> You just said it. The base case is true. The inductive case is wrong.

Not really. H(1) is true. H(2) is false. But either one could be your base case.

The inductive step could be true or false, again depending on what you call your base case.

[poetically]

I don't think this is correct. The main argument uses a very specific inductive invariant of applying transitivity of equality to a non-empty set. The argument doesn't apply in the base cases because it is vacuously true so the minimal base case is actually a set with 3 horses because that is the only case where transitivity of equality can be used non-trivially.

[dwohnitmok]

> The argument doesn't apply in the base cases

No I'm still with eperdew on this. You don't apply an inductive argument to base cases, so that statement doesn't really make sense. From a pedagogical point of view, I think it is very important to drive home the point that there is nothing special about your choice of base case, other than that it affects the argument in your inductive step, otherwise it's too easy to make the choice of base case seem "magical."

In fact I'd go further. Whenever you have an error in an inductive argument, it is always in the inductive step and never the base case, since you can always choose whatever base case you want (you might just find it makes your inductive step impossible to prove, so if you do prove something, you've made a logical error in your inductive step).

At worst, an "error" in choice of base case leads to a proof that cannot be completed, not an erroneous proof.

EDIT: "it is always in the inductive step and never the base case" except of course if you've somehow made an error in the initial proof of the base case, but that is distinct from choosing the "wrong" base case.

EDIT 2: I just understood what you meant by "apply," (doesn't fulfill the preconditions of the inductive step, vs I thought you meant relevant to proving the base case) sure that's a reasonable way of looking at it too, but again I'm very wary of saying that it's the wrong base case that leads to proving a falsehood as I lay out elsewhere.

[shkkmo]

> you might just find it makes your inductive step impossible to prove, so if you do prove something, you've made a logical error in your inductive step

The inductive step should be proven completely independently of proving a base case. Indeed, if the inductive step is proven correctly you see that it is limited in scope to n>1.

You can then use any base case you can prove where n>1. Let's say you pick a base case of one trillion. Easy enough to show thay every set of one trillion horses is the same color (since no such sets can exist). You can then easily use induction to show that every set larger than one trillion horses is also the same color!

So really, both base and induction were wrong in different ways but if the induction had been proven correctly, the inapplicable base case would have been clear.

[poetically]

So what would say is the error in the inductive step here?

[dwohnitmok]

The inductive step is being obscured (intentionally of course in the article to illustrate how the error can hide) behind the n.

The inductive step here is not true for all n, n + 1 pairs.

It is only true for all n, n + 1 pairs given that n is greater than or equal to 2.

The error is to drop that >= condition. Hence the inductive step is wrong as stated in the article (for all n), and its proof is erroneous.

Again while changing the base case can "fix" the argument in that it no longer proves an falsehood, without altering the statement of the inductive step it is still not a valid argument and only happens to prove a true statement "by chance."

If the base case was the error in the sense of proving a falsehood, then it would be possible to have an unsound inductive argument by choosing the wrong base case, but that's impossible. Rather the wrong base case (but correct inductive step) simply means you end up unable to complete your proof.

[dan-robertson]

I think that is a complicated way to look at things. The error is that the argument assumes that for a, b being elements of H, the sets H - {a} and H - {b} meet. This is true for |H|>2 but the first induction case is for |H|=2, where the assumption is obviously false. But when you read the induction case you may think of n as being large and so not notice the error.

[poetically]

Yes, this is what I said in another comment.

[dan-robertson]

I don’t understand what you mean?

I think that what I wrote is implicitly agreeing with the GP that the induction argument is wrong not the base case. And I think that you attempted to refute it, but I couldn’t really understand how what you wrote would relate to either side. Do you mean that you agree that your description above was complicated, or that you agree that what I wrote is a fair description of the problem, or do you (now as opposed to before?) think that the problem was the induction step not the base case? Or are you talking about the statement that it is easy to miss the error by thinking of n as big rather than n=2? Maybe it doesn’t matter.

[poetically]

The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c. This argument is valid only if A ⋂ B ≠ ∅. It doesn't apply to the base cases because anything is true for the empty set and any function on a one element set is trivially constant. So the minimal case where this can be applied in a non-trivial way is a set with 3 elements.

[thaumasiotes]

> The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c.

This is not the argument.

> This argument is valid only if A ⋂ B ≠ ∅.

No, it isn't; it isn't even valid then. Consider a function over sets of real numbers:

    f([0,2]) = 5
    f([1,3]) = 5
    f([1,2]) = 5
    f([0,3]) = 6
    plus other values...

I've constructed this function so that, obviously, f(A) = f(B) = f(A ⋂ B) = 5, and A ⋂ B = [1,2] ≠ ∅, but f is not a constant function and f(A ⋃ B) is not 5. f is still a function.

We can state the proposition "in a group of N or fewer horses, all of the horses are the same color" like so:

    ∀G∃c∀x( (|G| ≤ N ∧ x ∈ G) → f(x) = c )

where f is the function that tells you what color a horse is, and N is a free variable.

The proof claims that if this proposition is true for the value N = k, then it is also true for the value N = k+1. This claim is correct for all k > 1, but it is not correct for k=1. The problem is that we only show the truth of the proposition for N=1.

Abstracting a little further, we can view the proposition above as the potential output of a function of N:

    p(0) = ∀G∃c∀x( (|G| ≤ 0 ∧ x ∈ G) → f(x) = c )
    p(1) = ∀G∃c∀x( (|G| ≤ 1 ∧ x ∈ G) → f(x) = c )
    p(2) = ∀G∃c∀x( (|G| ≤ 2 ∧ x ∈ G) → f(x) = c )
    p(3) = ∀G∃c∀x( (|G| ≤ 3 ∧ x ∈ G) → f(x) = c )
    p(4) = ∀G∃c∀x( (|G| ≤ 4 ∧ x ∈ G) → f(x) = c )

We can now say that the proof is claiming that whenever p(k) is true, p(k+1) is also true, that this claim is correct for all k > 1, and that p(1) has been established. But p(2) has not.

[fnord123]

Why is the base case 3? H(1) contains one colour of horse. H(2) when removing one horse contains one colour of horse.

The problem afaics is that there is a supposition that we are talking about sets of horses with the same colour. So if you "suppose for all sets of n horses, every horse in the set has the same color" then you can prove that horses in that set have the same colour. If P then P.

[GhettoComputers]

Is Godel's theorem what you're referring to? https://plato.stanford.edu/entries/goedel-incompleteness/

[andi999]

Yes, I also think it has nothing to do with base case and general case, there is just a flaw in the argument. When arguing that h2 also is brown one assumes wrongly that there are other elements in the reduced set left.

[phkahler]

The problem is the second line:

"Now suppose for all sets of n horses, every horse in the set has the same color."

There is no justification for that. They then go on to talk about removing a horse from such a set, but we've already lost.

[nnoitra]

It's part of the inductive proof process. Assuming that it holds for n you need to show that it implies that it holds for n + 1 as well.

[phkahler]

>> It's part of the inductive proof process. Assuming that it holds for n you need to show that it implies that it holds for n + 1 as well.

No. That's wrong. They assert it up front (that it is true for any n horses) and then go on to use it in the proof for n+1. The only time it's OK to assert your claim up front is if you're trying to prove it false by contradiction.

For an inductive proof, you must prove that if it holds for one case (n=1 here) it also holds for the next case. The base case is important and is proven (or obviously) true. A set of n is not the base case here, and they assert something about it without proof.

EDIT: Nope, my dumb. The wording is odd, but for induction we show that it is true for n=X (X is the base case and is 1 in this example). the inductive step is to show that being true for n implies being true for n+1 which is what they did here.

[shkkmo]

That isn't really a problem, just poorly worded (like a number of sentences in the article.) This is a pretty standard step of an inductive that should read more like: Given that n is some positive integer where every set of n horses has the same color...then you try to prove that holds true for n+1 as well.

The actual problem in that proof is setting up the proofs of the inductive rule. There is an implicit assumption/condition that n+1 >= 3 that is not acknowledged.

If you acknowledge that condition, then it becomes quite clear that you can only prove a base case for n = 1 and only prove an induction rule for n >= 2 .

[throwvirtever]

I feel like I'm too ignorant of mathematics to be confused by this "proof".

When you set out to prove "for any set of n horses, every horse in that set has the same color" and you then "suppose for all sets of n horses, every horse in the set has the same color" as a first step, you're messing with a tautology, aren't you? I mean if you've supposed that it's true for all, it's definitely true for any, right?

What am I missing that makes the problem subtle and interesting, rather than just blatantly circular from the start?

[mannerheim]

The inductive step assumes the hypothesis is true for n, and proves it for the n+1 case. The overall proof is then for all positive integers, n.

[na85]

But why would anyone assume that n horses, for arbitrary n, are the same color?

That's absurd. Anyone who's ever seen a field with horses in it would trivially know that this is a faulty assumption to make.

You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate".

It's equally valid logic.

[ajuc]

> But why would anyone assume that n horses, for arbitrary n, are the same color?

because that's how inductive proofs work. You assume something is true for N and show that this implies that it's also true for N+1. This combined with base case (for example for N=1) proves that it's true for all N >= 1.

The assumption is just a tool used to check if you can prove the implication, the real "meat" of the proof is in the implication.

Are you aware of proofs by contradiction? A: "assume N is the largest natural number". If that's true then there shouldn't be any natural numbers larger than N, but we can create N+1 and show it's larger AND natural, so assumption A leads to contradiction, so there is no such thing as the largest natural number.

We used false assumption in our proof, but the proof was correct.

It's a similar idea with inductive proofs - you make an assumption and see where it leads you. You don't use the assumption for the proof, you use the implication A(N)=> A(N+1) for the proof, the assumption A is just a way to see if you can prove the implication.

> You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate". It's equally valid logic.

The logic isn't actually circular, your coconut analogy is wrong. Correct analogy would be:

"when we assume N coconuts can migrate we can formally show that it implies N+1 coconuts can migrate" + "we can show that 1 coconut can migrate". You only need these 2 facts to prove all coconuts can migrate.

[na85]

>because that's how inductive proofs work.

Well, anyone who's seen a field of horses knows that "assume any set of n horses has the same color" is not valid.

So if what you say is true, then that implies the entire field of inductive reasoning is horse shit. But I don't think that's the case, so something's missing.

[mannerheim]

So it's worth noting that the inductive hypothesis isn't false for all values of n - namely, it is true for n = 0,1.

But beyond that, in mathematical logic, for p -> q, you can still prove this to be true, even if p is false. In fact, if you can prove p is always false, p -> q is 'vacuously true' - it's true because you can never come up with an example of 'p and not q'.

So mathematically, there's no problem with assuming an induction hypothesis that's actually false here. The real problem occurs is that the result doesn't follow from the assumption because the induction step of the 'proof' sneakily assumes that n >= 3, i.e., the induction step simply doesn't work for the n = 2 case.

[phkahler]

>> The inductive step assumes the hypothesis is true for n

You don't get to assume the thing you're trying to prove is true as a part of the proof that it's true. The only time we assume something like that is in a proof by contradiction, where the contradiction implies either an error in our logic, or an error in the assumptions.

[mannerheim]

An inductive proof has two steps:

1) Prove H(0)

2) Prove that if H(n), then H(n+1)

Then, by the axiom of induction, this is proven for all positive integer values of n. Because if those two conditions hold, we would have

H(0) is true

H(1) is true because H(0) -> H(1) ((2) with n=0) and H(0)

H(2) is true because H(1) -> H(2) ((2) with n=1) and H(1)

and so on.

The assumption isn't what's being proven, it's proving the inductive hypothesis for the next integer.

[phkahler]

Yes, I was being dumb.

As the article says there is a problem talking about equality among members of a set with size 1. So saying "all the horses in a set of size 1 are the same color" begs the question "same as what?" and that's where the real problem is, and the difficulty in pinning down that kind of thing is why I'm not a mathematician ;-)

[shkkmo]

There are two steps of an inductive proof

one is proving the inductive rule that: p(n) implies p(n+1)

the other is proving that there exists some number i for which p(i) is true. This, combined with the proof of the inductive rule, allows you to prove that p(n) is true for all n >= i.

[LanceH]

In simpler terms the two steps for this problem are:

1. There exists some number of horses where all horses are of the same color. This is obviously true when you have 1 horse.

2. The second step is that you have to prove that if you have some number of horses n, and they are all of the same color, then if you add another horse all the horses are of the same color.

He's saying there is some set of n+1 horses, n of which are of the same color. Then he makes the (false) claim that removing one horse at random leaves you with n horses, which therefore must all be of the same color. This is incorrect because the assumption is that there is a set of n horses, not "if you have n number of horses they are all the same color.

The base case of n=1 is just fine. It's adding a randomly colored horse to a set of horses that doesn't always result in an n+1 set of like-colored horses. He doesn't even explain the illogical step correctly, so the whole thing is a mess.

[shkkmo]

> He's saying there is some set of n+1 horses, n of which are of the same color.

> This is incorrect because the assumption is that there is a set of n horses, not "if you have n number of horses they are all the same color.

You have this exactly backwards. The assumption you say is not being made is exactly the one that is being made (and is a step that occurs similarly in every inductive proof.)

[ajuc]

It's not circular, because you aren't using the assumption A in the final proof, you are just using the implication A(N) => A(N+1) in the final proof.

the final proof is:

    A(1) is true
    AND
    A(N) implies A(N+1)
    means that
    A(N) is true for all N >= 1

the assumption that A is true for N was just used as a condition in the implication

If A(N) is false in general - you would realize that despite assuming it - because the implication or the base case couldn't be proven.

[indianboy42]

Isn't that just how proof by induction works? You assume the hypothesis is true for n and prove it for n+1

[ahartmetz]

But you don't go from n-1 to n. You'd have to start at the infinite horses case where the conjecture must be true for, well, who knows what reason. Intuitively, "Consider the conjecture proven. If we reduce the difficulty, it's still proven" just seems obviously wrong.

[Arcsech]

There are two parts to an inductive proof:

1. Assuming that a property is true for N, prove that it is true for N+1.

2. Prove that the property is true for some concrete N where the proof for step 1 holds.

The trick is that you need to be sure to pick your concrete N correctly, as the article demonstrates. In particular, the problem with the "solution" in the article is that the proof given for step 1 doesn't hold for N=1, because N+1=2, and then just follow the rest of the argument from the article.

[runarberg]

I still don’t quite understand. The inductive step shows n + 1 → n right? However with any positive base case b, n → n + 1 isn’t certain for any integers above b, only below it.

Say you’ve proved the case for n = 3 and that n + 1 → n. Then you’ve proven that 2 + 1 → 3, and by induction 1 + 1 → 2, However you’ve never proven it for n = 4 because n → n + 1 has never been established.

Or am I missing something here?

EDIT: I’ve seen in other posts that this the problem with OP is that it hides the transitivity of the operation. In fact the failure of the proof was that it proved transitivity with a false premise. If transitivity was true, then using n + 1 → n is just fine. The Wikipedia article for this statement is actually a lot clearer. https://en.wikipedia.org/wiki/All_horses_are_the_same_color

[joshuamorton]

You've got it backwards. Induction is usually proving that n implies n+1, So knowing it's true for 2 you can prove for 3.

The issue is that this proof only works with the base case of 2, for...reasons.

[smohare]

That’s not the issue at all, since the base case of n=1 is established trivially and so the quoted statement is merely the inductive hypothesis. But the inductive argument relies on n>2 to invoke transitivity on a non-empty intersection necessitating a separate justification for n=2.