All Horses Are the Same Color | Hacker News Reader

All Horses Are the Same Color

jeremykun.com

153 pointspoetically179 comments

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.

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.

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.

Yes, this is what I said in another comment.

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.

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.

> 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.

I don't understand what you're arguing. What exactly is incorrect in what I wrote?

> The argument in the article is the following:

This is incorrect. You attribute an argument to the article that it does not make.

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

This is vacuously true in that the argument is not valid and its validity therefore implies all propositions including that A ⋂ B ≠ ∅. Although I tend to suspect that that isn't what you meant to say. It is equally true that "This argument is valid only if A ⋂ B = ∅". It is not true that if a function f takes a constant value, you can conclude that A ⋂ B ≠ ∅ for arbitrary A and B.

Great, glad we cleared that up.

> 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.

This is exactly what the person you are responding to was saying. They were talking about the transitive part of the inductive step that the article handwaves to with this line:

>> In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown.

the "remaining horses" is the A ⋂ B set that was mentioned and if that set is empty then know it is the same color as set A is meaningless. Thus given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you only know that f(A ⋃ B) is constant if A ⋂ B is non-empty.

Given that in this case A and B are formed by removing different elements from a set of size n+1, the proof only works if n+1>=3 so that A ⋂ B can have at least one member.

> Thus given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you only know that f(A ⋃ B) is constant if A ⋂ B is non-empty.

But this is wrong. Given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you do not know that f is constant, regardless of whether A ⋂ B is or isn't a non-empty set. poetically described a completely different and obviously false claim instead of the actual claim made by the false proof.

You must not understand the notation. f(A ⋂ B) = f(A) is saying that every result of f(A ⋂ B) is equal to every result of f(A), this is trivially true if A ⋂ B is the empty set and thus tells you nothing. However if A ⋂ B is not empty, it follows from knowing f(A) is constant.

Poetically is correctly identified the exact step when the n>1 assumption is introduced. The argument is condensed but accurate.

> 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 is very clearly the assumption that "all the remaining horses" is not empty that introduces the n>1 condition. It is the non emptiness of that set that allows you to say that since f(A) is constant and f(B) is constant (and we already know that because |A|=n and |B|=n), then f(A ⋃ B) is also constant.

You've gotten confused somewhere.

> However if A ⋂ B is not empty, it follows from knowing f(A) is constant.

That f(A) is constant is supposedly a conclusion, not a premise. It is not a valid conclusion to draw from the stated premises.

> f(A ⋂ B) = f(A) is saying that every result of f(A ⋂ B) is equal to every result of f(A)

As I just responded above, interpreting the claim this way doesn't get it to make any more sense. When f(A ⋂ B) = f(A), there is no basis from which to conclude that f is constant. You have no information about whether f is or isn't constant.

This is not the claim made in the false proof, nor does it have anything to do with the claim made in the false proof. It is a creation of poetically's own mind, and it makes no sense.

> You have no information about whether f is or isn't constant

You seem to have forgotten what we are talking about. A ⋃ B is an arbitrary set of horses of size n+1, A and B are subsets of A ⋃ B, each with a single different element removed and thus of size n. We already know that f() is constant over A and over B because they are of size n and we have assumed that all sets of horses of size n have the same color (which I already pointed out in my last comment.) We also know that f() is constant over A ⋂ B becasue it is a subset of sets we already know f() is constant over. The only thing that needs to be proven is that f() is constant over the set A ⋃ B. That proof is impossible if A ⋂ B is empty. We can only assert A ⋂ B is not empty if we assume that A ⋃ B must have a size of at least 3. From assuming n+1>=3 we are able to correctly conclude that n>1 implies the inductive step is valid.

> Consider a function over sets of real numbers …

I think you just misunderstood the notation. f is a function from (say) X -> Y. But the parent talks about it as if it were a function from the power set P(X). That is, for A a subset of X, when the commenter above says that f(A) is a constant, they meant that f(A) = {c} for some c in X. This is a bit of loose usage of the standard notation f(A) := {f(a) : a in A} is commonly understood.

Obviously an arbitrary function f : P(X) -> … needn’t satisfy the properties but no one was suggesting that.

Under your interpretation, poetically's claim still does not reflect the claim from the false proof, and it is still itself obviously wrong.

(I'll assume that when you say "f(A) = {c} for some c in X", you mean "f(A) = {c} for some c in Y", since the values of f come from Y.)

So consider these definitions:

    f(x) = x²
    A = [0,1]
    B = [-1, 1]

We can easily see that f(A) = f(B) = f(A ⋂ B) = A. But it is not true that f takes a constant value over any of those domains. (It is true that f(A ⋃ B) = f(A), but this is required by the premise f(A) = f(B).)

In your example f(A) is not a singleton. I think that the image f(A) being a singleton {c} is what was meant by “f(A) is some constant c”.

It feels to me like you are taking advantage of imprecise language to demonstrate counter-examples to statements that no one was trying to prove.

Do you actually think that 'poetically (or I) are trying to use obviously false properties of functions (specifically the properties you keep providing counter-examples to) or are just being nit-picky about language?

Usually I find much mathematical writing can be hard to read because much of the context or scope of variables, assumptions, or definitions is so implicit. But when something seems obviously wrong it is an exercise to figure out what constraint I’ve missed that makes it true.

When one first learns analysis, the statement of so many of the theorems begins “given a continuous function f” and this continues in formal writing but when people communicate more casually they usually just say function and everyone knows/figures that a continuous function is meant instead of pointing out an obvious counter-example.

In the context of this thread, it is obvious to me that the thing being talked about is when the image of a function restricted to some subset of the domain is a singleton. The reasons it is obvious to me are:

- The f(A) := {f(a) | a in A} notation is standard and implied by the choice of letters

- It is meaningless to say that the value of a function is constant—you always get the same result, so for the word to mean something, I think it is reasonable to take it as implying the restriction is a constant function, or in other words that f(A) = {c}, a singleton.

- It seemed obvious to me from the context of the article

- It seems a reasonable interpretation that changes the statements from nonsense into a reasonable description

At first I thought you just weren’t familiar with the notation, but now it seems you knew it so was it just not obvious to you that that is what was meant? Or do you actually think people were trying to prove or rely on the statements you disproved? Or that people should write more precisely and deserve to be punished with pedantry when they assume some mathematical maturity instead? I’m genuinely curious what you think is going on here because I’m struggling to fit these comments to a model of how hn commenters think and act.

> In your example f(A) is not a singleton. I think that the image f(A) being a singleton {c} is what was meant by “f(A) is some constant c”.

What? What are you quoting? Here's the full relevant text I responded to:

> 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.

There is no claim (in the premises) that f is constant over A. There is such a claim in the conclusion, since that is a corollary of f being constant everywhere. But it's not in the premises.

So this is my model of what's happening:

- poetically has attempted to write down the claim of the false proof. He probably has a fair, if fuzzy, idea of what the proof is saying. But he doesn't know how to write it down; he has written down some things that sound kind of similar while, in the details, being mostly unrelated to the false proof. While I do believe that he broadly understands the OP, I do not believe that he understands the stuff he wrote down himself.

- You have a clear idea of what the proof is saying and you would like to read poetically as saying the same thing if at all possible. This is causing you to read things into poetically's claim that aren't there, but which would be necessary in order for him to be making sense. So it's unfair for me to use an example in which the image of A isn't a singleton, because, in the original post, the image of every set is a singleton. That the image of every set is a singleton is part of the inductive hypothesis. But in the claim attributed to the post, A is a set with no constraints on it, and f is a function with no constraints on it.

- At a wider level, poetically has described a post which contains a pretty clever false proof which is very nearly correct as instead making a claim which is so obviously incorrect that, if you believe poetically, it would make no sense to read the post.

So my initial thought process went like this:

1. Read poetically's comment. Notice that it is presented as a description of the argument in the post, but it makes no sense.

2. Leave a comment explaining how to describe the argument in the post.

This was a failure, in that poetically responded to the effect that he didn't see any difference between what he wrote and what I wrote.

In this subthread, you keep trying to provide interpretations that would cause poetically's original claim to make more sense, and I keep pointing out that the new interpretation doesn't help. In this case, the image of A being a singleton is most definitely not part of the original claim. But if I assume that it was, the adjusted claim still makes no sense. The new counterexample is:

    f(x) = ⌊x⌋
    A = [0.2, 0.6]
    B = [0.4, 0.8]

This function is constant over A, B, and -- of necessity -- A ⋂ B. A ⋂ B is a nonempty set. But the function is not constant everywhere.

Moving back into the project of reading poetically's mind, I have to interpret his statement "This argument is valid only if A ⋂ B ≠ ∅" as an attempt to explain under what circumstances the argument he describes in the previous sentence is valid. This indicates a fairly serious error in understanding somewhere, because that argument is never valid. The observation that the intersection of A and B is or isn't empty has zero explanatory power.

(Note also that if you believe poetically was restricting himself to cases where the image of every set under consideration is a singleton, it doesn't make a lot of sense to describe for him to state his premise as "f(A) = f(B) = f(A ⋂ B)". When every image is a singleton, it's sufficient to say that "f(A) = f(B)". (And this is exactly how the false proof proceeds - it proves that f(A) = f(B) by observing that each is necessarily equal to f(A ⋂ B).) But this is fairly weak evidence; people bring up redundant information all the time.)

> At first I thought you just weren’t familiar with the notation, but now it seems you knew it so was it just not obvious to you that that is what was meant?

Yes, I'm familiar with that notation, and no, it wasn't obvious to me that that was what was meant. It still isn't, frankly. I cannot be confident about what was meant because there are no options that would make sense.

However, I will note that I don't think my response above indicates that I was familiar with the notation. You provided a definition and I used it while talking to you; I'm using "singleton" in this comment and that is a usage I was not previously familiar with.

> 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.

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

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.

> 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.

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.

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.

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.

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).

> 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.

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?

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.

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

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.

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.

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

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.

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.

You need to do it because you prove the statements separately. Currently the inductive step statement is false, it says that applies for all sets. It doesn't.

Note that you can use false intermediate steps like that and still reach a correct conclusion. Then the conclusion is correct but the proof is still wrong since the steps you used were wrong.

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.

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.

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))”

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.

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.

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.

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.

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".

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.

> 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.

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

Right, the goal here is to find the logical error in an obviously wrong proof, not how to fix this proof as the proof is obviously wrong from the start. You trying to argue how to "fix" it is the one side-tracking the whole thing.

If you say "B wouldn't be wrong if you changed A, so A is wrong!" then that isn't how you find errors. If A is a correct statement and B is an incorrect statement then B is the wrong statement. If you can make B correct by changing A, then B is still an incorrect statement.

If this was a memorization question where you were supposed to find a particular A and B, then you could say that A is wrong even if the statement is correct, since you knew what A and B are supposed to be. But it isn't, we are just here to find the error in the statement to prove that the proof is wrong, we aren't here trying to find a correct version of this statement.

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.

> 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.

Who says the question was to demonstrate an inductive proof? Being able to prove that all horses are the same color if all pairs of horses are the same color isn't particularly useful, as typically that would be the definition of all horses having the same color. All that humbug didn't add any extra information to the problem at all, it didn't make things clearer it just made them harder to understand.

To prove something like that you pretty much have to use a proof by induction or a proof by contradiction.

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

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?

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.

> 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.

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.

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

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.

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.

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

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.

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?

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.

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.

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.

> 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.

>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.

What is missing is understanding that in math the sentence "if X = 3 then 2 * X = 6" is true even when X = 5.

For the proof to work the implication must be true, not the assumption.

But you're not trying to prove X = 3 and starting out by assuming X = 3.

There wasn't even an attempt to disprove the assumption in TFA.

> But you're not trying to prove X = 3 and starting out by assuming X = 3.

No, you're trying to prove

    for all N>=1: A(N) is true

and start by proving that

    IF A(N) is true THEN A(N+1) is true

This implication can be true even if A(N) is false, and your final proof will only use the implication, not the assumption used when proving that implication.

Assumptions in math proofs can have scopes. For example in many proofs you split the domain into subsets and prove that something is true assuming X>=0 and X<0 separately. Naively you would say that we cannot assume X>=0 and then assume X<0 in the same proof because that's a contradicion.

But these assumptions were used in different scopes so there's no contradiction.

We're talking past each other. I give up.

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

That's not even true! If n is 0 or 1 then the statement is correct, for example.

If your response is "It's not true for all n, though." well, the inductive proof doesn't assume it for all n either. It only assumes it for one n at a time.

But also, you're getting too hung up on the exact wording of the statement.

For example, we could do the same proofs, but put "on farmer Joe's land" onto the statements.

If we do that, "anyone who's every seen a field with horses in it" can't tell us if the statement is true or not. Maybe all groups of 2 horses in a field on farmer Joe's land do have the same color, because he sorts his horses. And obviously all groups of 3 horses would have to have the same color, etc. etc.

So on farmer Joe's land, A(n=2) is true. And the induction is valid. And using it gives you the correct results! What's the problem with inductive reasoning here?

You seem upset that the induction itself might be valid even if n=2 isn't, but I don't know why. The induction is the same no matter whose farm you're on. That's why you need to prove the base case too.

> But you're not trying to prove X = 3 and starting out by assuming X = 3.

It's really not. There's an entire series of X, and we're saying if we can prove one we can prove the next. You never assume an X when proving that X. And you never assume a higher X when proving a lower X. There are no circles. It's a chain.

"Assume X is 3. Then 2*X=6" is just a different way of saying "If X is 3, then 2*X=6"

You can rewrite the entire thing without the word assume if you want.

You can do the whole thing as "if Y, then Z". "if A(n), then A(n+1)". If pairs of horses are the same color, then triples of horses must be the same color. If triples of horses are the same color, then quads of horses must be the same color. Those sound like reasonable statements to me.

Even if we're talking about all horses in the entire world, I could theoretically go kill every non-brown horse, and the original statements would all become true.

This is math. You can't object to abstract logic by mentioning real-world facts that could change at any moment.

>> 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.

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.

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 ;-)

There are several 'mathematical' ways you could phrase it (glossing over how to define the colour of a horse):

1) In a set of horses with size n, if horses A and B being both members of this set implies horse A has the same colour as horse B, then all horses in the set have the same colour.

2) In a set of horses with size n, and let f be a function on this set that produces each horse's colour. Then all horses in this set have the same colour if and only if the codomain of f on this set has size 1.

You could probably prove these are equivalent definitions.

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.

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.

> 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.)

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.

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.

>> 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.

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 .

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.

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.

This post is basically a paraphrase of a well-known example, which has its own Wikipedia page https://en.m.wikipedia.org/wiki/All_horses_are_the_same_colo...

I think the fallacy is explained better there tbh.

I also think it’s confusing to say one isn’t the base case. When you apply the inductive step there you hit N=2, and indeed the step fails because there’s no overlap.

This is indeed much clearer than the OP's version. In this one, the transitivity is obvious, because the article clearly explains that you may take out any horse from n + 1 and note that the remaining n have the same color, then do that observation again with another one, and use the horses that never left the group as a transitive link.

I agree this is much more worth looking at.

(wiki) Thus in any group of horses, all horses must be the same color.

Yes, iff n horses have the same color. I fail to see any paradox here (and in subj tfa too) and why induction is of any importance to it. We worked it all out of a restricting assumption which wasn’t contradicted, but that’s it. It doesn’t tell us anything about all other cases, e.g. when n horses do not have the same color.

Can someone please explain what I’m missing here?

The inductive step allows you to stipulate what seems like a strong assumption, in this case that all horses in sets of size N have the same color. I think you're reacting to that seeming like it's the problem, because at first that seems like where the "cheating" is occuring: you can obviously have a set of horses that aren't all the same color.

But actually that's part the power of the inductive step: you do have the freedom to choose whatever assumptions you want. The question is whether it's true for N+1, for all N. In this case, it's not: the inductive step fails. But there's nothing flawed with the starting premise per se (aside from it being intuitively obvious that it will never work). The interest here is that it seems you can get further than you should be able to, and it's a little tricky to figure out where the logic falls apart.

What you're missing is that "n horses have the same color" is true for n=1. So therefore we should be able to invoke the induction to bigger and bigger numbers.

If the induction actually was valid for 1->2, we'd have a hell of a problem.

Now I think I understand the subtlety, thanks! The induction part is important here because we start from n=1 (where the assumption is not as obviously questionable as for n in general, because it’s coincidentally/degeneratively true in relation to our reasoning) and then the “base error” allows us to generalize into a bigger mistake.

Yeah, it's phrased weird. In the inductive step, what you want to do is prove that "if all sets of horses with size n have the same color, then all sets of horses with size n+1 have the same color." In order to prove that, you start with the assumption that all sets of horses with size n have the same color. They're not actually assuming it's true for all n right away, they're just assuming that they've gotten it for some n.

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

This sounds so obviously false to me, that I initially thought that he must have meant "now suppose for all sets of n horses such that every horse in the set has the same color". I.e. take all sets of n horses and then filter them to only get the uniformly colored sets.

But he doesn't mean that, it is meant as the induction step:

"Now suppose a world where for all _possible_ sets of n horses, it turns out that every horse in the set _necessarily_ has the same color."

In my mind, the article is a bit poorly worded, but then again, maybe it makes sense for mathematicians.

I'm not sure any wording helps, because the reason it strikes us so poorly is that it's such an implausible idea.

It might help to make it more concrete, to say “assume that we've proven this for say n = 3, all sets of three horses have the same color. Then I can prove it’s true for n+1, because my set {Auris, Brunellus, Camper, Diego} of four horses is the union of two overlapping 3-sets, {Auris, Brunellus, Camper} and {Brunellus, Camper, Diego}. By the transitive property, Diego must have the same color as Auris and the result holds. But obviously this works not just for 3 going to 4, but also 4 going to 5... Any set of size n+1 is made up of two overlapping sets of size n.”

Maybe also someone can then intuit that the wool is being pulled over their eyes in this step?

That is the same sentence just abbreviated and using standard words. Nobody says "suppose a world where", you just say "suppose that". Also, you just say "if ..., then ...", not "suppose if ..., then it necessarily turns out that ...".

> In my mind, the article is a bit poorly worded, but then again, maybe it makes sense for mathematicians.

That is the point. This example is given to first year students to show them why you need to be careful in your proofs and why properly wording/formulating statements is important.

There are variations of this style of proof the shows all horses have an infinite number of legs, since horses must have an even number of legs to stand, yet they have two legs in back and forelegs in front, giving them six legs which is an odd number of legs for a horse. The only number that is even and odd is infinity, hence horses have an infinite number of legs.

There is also lemma that since Alexander the Great rode a Black horse, he did not exist, but if he did exist he would have an infinite number of arms and legs

I don't understand. How is that six legs? How is that an odd number? Am I missing a joke?

Six legs on a horse would be very odd indeed

The situation could be much worse.

https://www.penny-arcade.com/comic/2008/05/26/the-unhorse

Wow, I can't believe Penny Arcade is still publishing comics. What a run!

They have an expo too. https://en.wikipedia.org/wiki/PAX_(event)

fourlegs

Yes, it's an English language joke:

Two legs in back, and "forelegs" in front (four-legs). 2 + 4 = 6, which is a peculiar (aka odd) number of legs for a horse to have. Thus horses have both odd and even number of legs, meaning horses have infinite legs.

Actually, the argument was that Alexander the Great had an infinite number of arms. You see, in a famous battle he was forewarned. And as we all know, forewarned is four armed. The rest of the argument is similar.

If this wasn't in Mathematics Made Difficult it should be

It was in "A Stress Analysis of a Strapless Evening Gown", I believe.

Indeed it's there in Joel Cohen, "On the Nature of Mathematical Proofs", pp. 84-90.

(Good recollection!)

Holy moly did I miss the joke

I'm a complete native and fluent English speaker for 30+ years.

Thank you for the explanation - I know others here may need it but, and in all kindness, I'm lmaoing over here being explained this joke like a toddler.

forelegs means "front legs", but also sounds like "four legs". "odd number" means "strange number", and also "number not divisible by 2".

infinity is typically not defined to be even or odd.

This is clever, but I wouldn't call it a variation on this style of proof — the OP was an example of a somewhat-subtle logic error, while this is just two instances of wordplay (forelegs ⇔ four legs; six legs being an 'odd' number of legs for a horse).

The joke is funny though

Wow, I guess I should have studied logic!

Can someone explain in English how the author goes from "[now] suppose for all sets of n horses, every horse in the set has the same color" to 'proving' anything?

He does't. Read the last paragraph:

This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not n=1, but rather n=2. Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.

This is standard induction: let P(n) be some statement about the number n. If you can establish that P(n) implies P(n+1) for all n >= 1, and that P(1) is true, then P must be true for every positive integer. You can find many examples by googling for “induction proof”.

The problem in the proof is that the inductive step P(n) implies P(n+1) only holds for n >= 3, and so the fact that P(1) is true does not imply anything for the larger integers.

Okay, but my issue and I think the one of the OP is that even for n >= 3 how did they prove that all horses are the same color for n >= 3?

Yeah this is why I'm confused as well. I don't follow how if we assume n are the same color, that it implies anything about n+1. It sounds like the article is saying that the N+1 logic makes sense for n > 2, but I don't see how it does.

Assume (accept without questioning) that it’s a property of the universe that any group of 2 horses are the same color.

Now, say you have a group of 3 horses, A, B, and C. You can use your knowledge about groups of 2 horses here: A and B must be the same color because they are a group of 2 horses. B and C must be the same color for the same reason. So all the horses are the same color.

You can now use the proof for groups of 3 horses to prove the same fact about groups of 4 horses, and so on.

The flawed inductive proof tries to generalize this argument to all groups of n and n+1 horses. That is, assume the property is true for groups of n horses, and show that it logically follows that it’s true for groups of n+1 horses. The structure of the argument is the same as my 2/3 horses example. However, you can’t use an argument like that for any value of n, as it isn’t true for n=1. That is, it’s not true that if every group of 1 horses is the same color (a true fact in nature) then it follows that every pair of horses is the same color.

It’s more like “in a world where every group of n horses are the same colour”, no matter of whether that world is the real world or not, “prove that any group of n+1 horses are the same colour”. This inductive step proves nothing about the real world, it needs a base case to kick things off. If you can prove it true for n=5 say, then the inductive step gives you every higher number.

The idea is that if it holds for n = 3 then it holds for n > 3. The way to show that it holds for n = 3 is to show that it holds for n = 2, which it doesn't.

It's not proven in a vacuum: it's proven under the assumption that it's true for N-1. E.g. if we assume that all groups of 2 horses are the same color, we can prove that all groups of 3 horses are by labelling them A, B, C. A and B are the same color because they are a group of 2; B and C are the same color because they are also a group of 2; A and C are the same color transitively (or because they are also a group of 2). Therefore A, B, and C are the same color. This step is logically sound, and you can do this for any N greater than three.

The problem is that this fails when tried for N=2, because then each sub-group can have only one horse in it. We already know that each horse is the same color as itself, so we don't actually reveal any new information by doing this. Since it doesn't work for N=2, the base assumption used for the N=3 case is incorrect.

Though incorrect, this is meant to be an example of proof by induction. Proof by induction is (to simplify a little) where you prove that any number N+1 will have a given property as long as N has that property. You can use this same rule twice to prove that N+2 has this property, and so on.

Finally, you prove that any arbitrary number (say, 1) has the property in another way, and you've proven that property for all N greater than or equal to 1.

The error in the proof is explained in the linked page, but basically the problem is that the proof that N implies N+1 doesn't actually work for all N, and particularly it doesn't let us go from 1 to 2.

This is called proof by induction. There is an intuitive path to understand it: Consider the set of the natural numbers; it contains 0 (zero) and for any K which belongs to this set, its successor (K + 1) also does. It is clear that if a property if valid for 0 and, in the case it is valid for a K which is not 0 implies it is also valid for K + 1, then such property is valid for all natural numbers.

This is quite tricky to do, because it’s almost a sleight of hand and expressing it in English is like watching the trick from behind the magician - you can obviously see the wrongness.

But: if you skip a pair of horses (which is how the trick is done/the error introduced) it might be:

Assume any group of 3 horses are the same colour. Can we show that adding another horse will result in a group of horses that are all the same colour?

Well yes: take your new group of 4 horses, and extract 1. (h1). Three horses remain and they must by definition be the same colour. Put h1 back and extract a different horse (h2). Now three remain and must by definition be the same colour as each other.

But when h2 was out, h1 was part of a group that was all the same colour. And when h1 was out, h2 was part of a group that was all the same colour. Therefore they must all be the same colour. It doesn’t matter how many different horses you find and bring to your initial group of 3, the rules will mean the resulting group of 4 is always the same colour. And so it is true for a group of 4 horses.

By the same reasoning, it must then be true for a group of 5, and so on up to all horses.

So all horses are the same colour, so long as the first assumption (that any group of 3 horses must be the same colour) holds.

The trick/error is jumping from “a group of 1 horses must all be the same colour” to “a group of 3 horses must be the same colour” which is an easy jump to miss if you go from “1” to “n”, instead of “1” to “3”.

(The logic doesn’t work for a pair of horses, because once h1 is taken out there are no other horses left that h2 must be the same colour as.)

This brings up an interesting problem with inductive arguments I’ve never thought of: how does one prove a base case is a sufficient starting point for induction? In the horse example, we know there can be groups of multi-colored horses so our intuition guides us to a counter example, but it seems like a detail like that could easily be overlooked for something more complicated.

You have to find the minimal case where the inductive invariant is valid. In this case when the horses are separated into two groups, A and B, the assumption is that their intersection is non-empty (A ∩ B ≠ ∅). Because only in the case where the intersection is non-empty can we apply transitivity of equality to conclude that their union (A ⋃ B) satisfies what we are trying to prove. But as the article argues this fails for a very simple counter-example where A and B are non-empty but their intersection is empty.

Sorry, this answer is confusing. The base case just needs to have the property you want to prove. The induction step does all of the heavy lifting to go from n to n+1. In this case, the induction step fails, because it cannot go from 1 to 2. Simple as that.

Edit: I removed the wrong. It’s just confusing.

Where exactly is my error?

In your first sentence. What is the inductive invariant you are talking about?

See https://news.ycombinator.com/item?id=29445794.

You explain how the induction step works. That step from n to n + 1 only works for n > 1. But 2 is not a proper base case. 3 is neither. Actually, the only potential base cases are 0 or 1.

So the proper explanation why this argument doesn’t work is that the potential base cases are not covered by the induction step. And not that “the real base case is 2”.

Actually, now that I have explained the argument I realize it has nothing to do with induction. The logic of the argument is unrelated to induction, it's simply about functions that take constant values on some sets and what is required to extend a function to a larger set and conclude that it is constant on the larger set.

Your argument still explains the induction step. In the end, P[n] => P[n+1] is just a statement that has “nothing to do with induction” once it is formed.

You have obviously the right intuition about induction, but I think you are confused about its exact nature.

We'll have to agree to disagree then.

You prove "n+1=>n" instead of "n=>n+1"

I don't think so but we can agree to disagree.

In your induction you start by "Consider a set of n+1 horse" then conclude "By the inductive hypothesis, all of the n remaining horses are the same color".

You did the induction in the wrong direction.

"We can agree to disagree" is not a valid mathematical in my opinion. At least one of us is wrong (and maybe we are both wrong).

Well, in this case, you are wrong ;-)

You don't have to. See my top level comment. In short, you have to strengthen your goal in order to have a strong enough inductive hypothesis to prove anything. E.g., instead of "picking a base case" that's sufficient, you work the base case into the goal, like n >= 2 -> P(n). Then you do the base case as part of a branch in the inductive step, without using your inductive hypothesis.

You can't, you just make assumptions with imperfect information. https://plato.stanford.edu/entries/goedel-incompleteness/

Any example is a base case that is sufficient for starting an inductive truth, as long as it is covered in your inductive rule.

The actual error is is a logic error in the proof of the inductive rules that takes a logical step that only holds for n>=2 but doesn't acknowledge that condition. If that logical step is done properly and the condition made explicit, it is clear that a base case of n=1 won't prove anything with that inductive rule that only applies to n>=2.

> In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown. Hence, all horses in H are brown.

This is an error. h1 and h2 don’t have to be the same by any previous conclusions. If you have two horses, white and brown, it’s true to say if we remove one or another that “all horses that are left are same colour”, but they by no means need to be of same colour between themselves.

Reminds me of "everything has a 50/50 chance".

Because for any event or proposition it will either happen or not happen, two possible states. And you figure probabilities from the canonical fair coin and come up with two states & a 50/50 chance of either one coming up. So the proposition "A giant meteor will hit the Earth tomorrow" will either happen or not happen, so there's a 50/50 chance of a global extinction event tomorrow.

Hmm, I think there is a more basic error here. If you remove an element from your set of n + 1 horses, you get different sets of n horses depending on which one you take out. Here's where the mistake is:

"Consider any set H of n+1 horses. We may pick a horse at random, h_1 in H, and remove it from the set, getting a set of n horses. By the inductive hypothesis, all of the n remaining horses are the same color.

On the other hand, if we remove a different horse h_2 in H, we again get a set of n horses which are all the same color. Let us call this color “brown,” just to give it a name. In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown. Hence, all horses in H are brown."

Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another. The ambiguity lies in the English phrase "same color" which can be interpreted in two different ways. It could mean "uniform color within the set of n horses" or "uniform across every set of n horses".

Consider if it were true that, for any set of 3 horses, they were all the same color (within the set of three).

This would mean it would be impossible to have a set of 3 brown horses and a white horse hanging around.

Why? Because if you added the white horse to the group and removed another horse, then you wouldn't have a group of three of the same color. So this would contradict our assumption.

So, if our assumption at top is true, it can only be true if all horses are the same color.

That's all that the original proof is saying, only stated slightly differently. It's saying that the only way the hypothesis could be true for N is if it's also true for N + 1.

Edit: You seem to have deleted the part I was responding to. Here's a new response:

> Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another.

This part of the proof happens sneakily here:

>> But when we removed h_1, we got that all the remaining horses had the same color as h_2.

The sneaky part is 'all the remaining horses' which does allow you to prove they're all the same color if the number of "remaining horses" is > 0.

This is where the inductive step sneaks in the n>=2 assumption.

Original:

> The base case is the former but the inductive step appears to be assuming the latter

The inductive step doesn't make that assumption. What it does do is assume that n>=2. The step basically says: from a set s1 of n+1 horses, remove horse h1 (this assumes n>=0). This gives you a set s2 of n horses, and we already know that all sets of n horses have horses of one color. Now take the original set of n+1 horses and remove a different horse (h1<>h2 assumes n>=1), leaving a set s2 of n horses, which we again already know are all same color. Now assume that there is yet another horse h3 (h1<>h2<>h3 assumes n>=2) that is in the original set s1. Since h3 is in s2 with h1 and in s3 with h2, h3 is the same color as h1 and h2. Since h3 is any arbitrary member of s1 besides h1 and h2 we know that all members of s1 are the same color.

Thus the inductive rule is indeed valid for every n≥2. If you can ever prove that every pair from a horse population has the same color you have also shown that every size of sets of horses from that population will also all have the same color.

You can conclude that H - {h1} and H - {h2} share the same color with each other because (assuming n >= 2), there will be a third horse h3 in both those sets. Therefore by transitivity, these two sets must have the same color.

This is implied and not explicitly stated, so it could be clarified.

This reminds me of another story involving horses and, while not quite as formal as this, at least involved some creative (or humorous at least) argumentation.

A while back in Sweden some fella started a movement which argued that horses are in fact a fruit that does not exist. It became a quite popular meme and the founder was even interviewed on national television. (Yes, really.) When asked how a horse could possibly be a fruit that doesn't exist, he likened them to dragons. See, dragons are a kind of lizard, but they're also just a figment of our imagination and so therefore can not possibly exist. Horses are the same except they're a fruit, and they don't exist. He presented this argument with a straight face in the middle of a riding school with horses in the background, leaving the interviewer dumbfounded. It was a glorious and hilarious moment in Swedish television history.

Unrelated to inductive reasoning, but a fascinating fact is that humans are naturally dark skinned (native Europeans used to have blue eyes and dark skin), some humans today have melanin mutations that cause them to be lighter, and chimpanzees are all white: they are just covered in black hair.

Related to skin pigmentations, a "white" horse with a black nose is, in fact, a fully greyed-out horse. True white horses have pink noses and are much rarer.

I think a better explanation would be that the induction step missed an edge case: To claim that H/h1 and H/h2 are the same color, we need the two sets to overlap by at least one horse. This actually works perfectly for all but n=2...

Things like this make me lose confidence not in Mathematics itself, but in the brain's ability to truly 'grasp' Math. I know I am a layman, and this particular example is peanuts to an adept, but I am sure similar examples exist at a higher level to confound the adept, and the master, and so on. Maybe past a certain level of complexity, Math is really beyond our capability for ordered thought, and only computers may proceed? Hopefully not!

> We will show, by induction, that [for all sets] of n horses, every horse in [each] set has the same color.

> Now [assume that] for all sets of n horses, every horse in [each] set has the same color.

QED.

This is just tautology. No further analysis needed, really.

(If your proof includes your hypothesis as an assumption, then it must be a proof by contradiction.)

EDIT: Before you refute, read again carefully. The assumption _is_ the hypothesis. It is not existentially quantified or set in the base case. It is the entire, universally quantified hypothesis.

Proof by inductions often involve showing that Pn implies Pn+1. That is, that a statement's truth for n implies it's truth for n+1. That's what's being done here, and it's a perfectly valid part of this type of proof.

This is how induction proof work. You prove that something is true for a base (n = 1) case then you prove that if it is true for n it has to be true for n + 1. Therefore it is true for any n.

The flaw is that the second part of the proof requires n >= 2

I understand and agree but read carefully. The assumption _is_ the (entire) hypothesis. It is not existentially quantified or set in the base-case. It is the entire hypothesis.

You should read “n” as “some arbitrary n” in the quote you posted. It’s not an assumption for all n.

edit: sorry, you’re right that the wording is a bit sloppy. The “n” in the first quote is “for all n” and the n in the second quote is “some specific n” or “some arbitrary n”. They’re not meant to be the same statement. I don’t think it’s a very carefully written article.

The assumption that the case holds for n while the goal is to show the case holds for n+1. It is not well worded to make clear the intent of making an assumption about modal possibility. However, to see it as begging the question requires imposing a statement of modal necessity that simply isn't there.

Yet, that assumption is not needed for the proof and can simply be removed. I think OP just wanted to say "what follows is the proof for the induction step".

I thought the same thing as you at first, but you need to read more carefully.

The proof is showing that it is true for n=1, and then showing that if it is true for n (the part where we "suppose it is") then it is true for n+1, proving by induction that it is true for all n >= 1.

Clearly a logical error, not a base-case error

> But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown.

Right, but for transitivity you actually need there to be a third horse to connect h_1 and h_2. i.e. for this logical chain, you need "all the remaining horses" to be a non-empty set.

For understanding: this proof makes sense if you (incorrectly) assume that any two horses are the same color, because then you can take any pair of horses in an n-sized group and split it into intersecting pairs to show that theyre all the same color. With this assumption, this inductive proof would work as well.

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

But that is clearly not true if I have a set of n horses, n-1 out of which are black and one is brown. So the premise is already wrong.

Interesting how every time a proof by induction is posted here many commenters seem absolutely stunted by it. Maybe it is time to create a "Warning: induction" tag?

I remember this 'proof' from an exercise sheet in a first semester math class. You had to explain why the argument was wrong. I liked this one :)

Perhaps some time with Hume’s Problem of Induction, Karl Popper, or more accessibly “Fooled by Randomness” by Taleb.

When reading the title I thought: wow this might be true, maybe all horses share the same skin (not fur) color.

>We will show, by induction, that for any set of n horses, every horse in that set has the same color.

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

"We will prove that $thing is true. Step 1: assume $thing is true"

I guess I don't see what the big deal is. Of course you can befuddle someone if they don't carefully read what you wrote.

Originally I had the same impression as you, but I'm starting to think the author didn't actually mean to imply your step 1. Their "now suppose for all sets of n" was a poor choice of phrasing and they meant something else than what the average person would assume. For example see https://news.ycombinator.com/item?id=29445778

Except white horses. White horses are not horses at all (at least according to Gongsun Long)

There’s a lot of confusion in this thread, and the original post.

To diagnose the problem with the proof, it’s worth knowing why proof by induction works, to thereby know how it actually works, and then diagnose which part of how it’s meant to be executed isn’t actually being executed in this blog post.

We need a starting point. For natural numbers, that’s Peano arithmetic. For simplicity, Peano arithmetic says that for any unary predicate P, the following is axiomatic:

P(1)

And

For all n > 0, P(n) => P(n+1)

Then

For all n > 0, P(n)

Proof by induction involves formulating your hypothesis in the form “For all n > 0, P(n)”, then proving the two conjuncts “P(1)” and “For all n > 0, P(n) => P(n+1)”, and finally concluding your hypothesis by modus applied to the inductive Peano axiom for P.

In this case:

P(n) is “in all sets of horses of size n, all the horses in the set are the same color”

The first conjunct, P(1), generally referred to as the base case, is true, and correctly recognized as such in the blog post.

The second conjunct, “For all n > 0, P(n) => P(n+1)”, generally referred to as eg inductive case, is false for this P.

It’s not about “would the inductive case be true if the base case were different”. There is a single proof presented in the article. It has a base case which is a true statement, and an inductive case which is a false statement. So the problem is the inductive case.

You could have a different proof which, reformulating the Peano axioms a little, could look like:

Base: P(1) and P(2)

Inductive: For all n > 1, P(n) => P(n+1)

In this different proof, let’s call this Proof 2, the base case would be false and the inductive case would be true.

Maybe the author is not intending to say the base case is “wrong” in that is false, but that is “wrong” in that it should have been formulated as in Proof 2, and that the inductive case is valid when interpreted in the sense of Proof 2. But this is completely confused. Why would it have been better for the proof presented in the article be interpreted as a proof (Proof 2) that’s not presented in the article? Both proofs fail, neither is a “better” formulation.

Rather than saying: the proof presented in the article should instead have be formulated in a superficially different but fundamentally equally invalid way, under which formulation the base case would be wrong.

Let’s just say: the inductive case of the proof presented in the article is false.

Am I the only one who doesn't like titles this cryptic/unrelated to the topic?

Does induction generally work for sets of n given any precondition?

Yes. Induction is the mathematics equivalent of recursion. Well, at least if you stay within the space of finite things.

Example: prove that a tree of size n has exactly n-1 edges.

All horses are the same color, on the inside.

Once you get beyond the surface of the problem things are simple. and tasty.

This case is so contrived and meaningless I am forced to believe it is satire.

It's a common "false proof" example that's taught in many introductory college classes. I learned this in my discrete math class.

Yawn. How did this make it to the top? I thought programmers were supposed to be good at math.

I don't think most programmers are "good" at math. Not to say that they're bad either or don't have the ability to get good if they put in the effort. It's just that most programmers don't learn how to prove things because only math majors in college really need to prove things.

It could be useful if programmers actually learned how to properly prove things. That way they would realize how full of holes their code tend to be.

Reply on news.ycombinator.com