Turn on thread page Beta

Proof by induction(All horses are the same colour) watch

    • Thread Starter
    Offline

    7
    ReputationRep:
    Hi, I'm sure a lot of people have heard about this "famous proof" but I want to know is what is wrong with this proof? I'm not sure where the flaw is. I've tried searching the internet on it but i don't really understand their explanation. Can anyone explain this to me in a simple way. Thanks.
    Offline

    2
    ReputationRep:
    I don't recall the exact proof, but I do recall that the flaw is in something like it relies on there being an intersection of two sets, when in the case for 1 (or maybe 2) this is not the case. Look at the proof, draw some venn diagrams and it should all become clear.
    • PS Helper
    Offline

    14
    PS Helper
    It's to do with how many base cases you have and how many base cases you need.
    • Thread Starter
    Offline

    7
    ReputationRep:
    Ah ok, I'll have a look into a bit more but I sort of start to understand it now. Thanks.
    • PS Helper
    Offline

    14
    PS Helper
    (Original post by JBKProductions)
    Ah ok, I'll have a look into a bit more but I sort of start to understand it now. Thanks.
    It's quite hard to get your head round, but it makes it easier if you convert it into something more mathematical.

    Let C be a set of colours (so say C = {brown, white, black} or something), let H be the set of all horses and let c : H \to C be a function where c(h) is the colour of horse h.

    What your conjecture about the "nth case" appears to say is that for all n, and for any subset X \subseteq H of size n, then c(h_1) = c(h_2) for all h_1, h_2 \in X... but this isn't what your conjecture is actually saying. Go figure. [Or let me know if you need another shove in the right direction.]
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by nuodai)
    It's quite hard to get your head round, but it makes it easier if you convert it into something more mathematical.

    Let C be a set of colours (so say C = {brown, white, black} or something), let H_n be any set of n horses and let c : H_n \to C be a function where c(h) is the colour of horse H.

    What your conjecture appears to say is that for all n, and for all h_1, h_2 \in H_n, c(h_1) = c(h_2)... but this isn't what your conjecture is actually saying. Go figure. [Or let me know if you need another shove in the right direction.]
    Thanks but I'm still quite confused about this, any more hints you can give?
    • PS Helper
    Offline

    14
    PS Helper
    (Original post by JBKProductions)
    Thanks but I'm still quite confused about this, any more hints you can give?
    I worded that badly so read the post again... it says pretty much the same thing though.

    Using my new notation, what it actually says is not only that for each h_1, h_2 \in X, c(h_1) = c(h_2). I mean, you would take one horse and say "this horse is all the same colour" would you? There's an implicit assumption about the size of the set.

    Although, I've just thought about this a bit more, and I might be leading you up the wrong street slightly. When you assume it's true for a set of size k and show that it's true for a set of size k+1, what you do is take two subsets of size k from the set of size k+1; this assumes that the intersection of these two subsets is non-empty. [That is, there is a horse which lies in both of the size k subsets.] Can you think of a k for which this doesn't work? So how big should your base set be?

    These are basically two ways of saying the same thing; one is a common-sense approach and the other is the mathematical approach.

    EDIT: And for what it's worth this pseudo-proof does generalise, when corrected, to a very important result, which I'll tell you if you're interested (but only after you've worked out where the proof falls).
    Offline

    14
    ReputationRep:
    (Original post by nuodai)
    I worded that badly so read the post again... it says pretty much the same thing though.

    Using my new notation, what it actually says is not only that for each h_1, h_2 \in X, c(h_1) = c(h_2). I mean, you would take one horse and say "this horse is all the same colour" would you? There's an implicit assumption about the size of the set.

    Although, I've just thought about this a bit more, and I might be leading you up the wrong street slightly. When you assume it's true for a set of size k and show that it's true for a set of size k+1, what you do is take two subsets of size k from the set of size k+1; this assumes that the intersection of these two subsets is non-empty. [That is, there is a horse which lies in both of the size k subsets.] Can you think of a k for which this doesn't work? So how big should your base set be?

    These are basically two ways of saying the same thing; one is a common-sense approach and the other is the mathematical approach.

    EDIT: And for what it's worth this pseudo-proof does generalise, when corrected, to a very important result, which I'll tell you if you're interested (but only after you've worked out where the proof falls).
    Is it to do with...

    Spoiler:
    Show
    n=1?

    ie. two horses?
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by nuodai)
    I worded that badly so read the post again... it says pretty much the same thing though.

    Using my new notation, what it actually says is not only that for each h_1, h_2 \in X, c(h_1) = c(h_2). I mean, you would take one horse and say "this horse is all the same colour" would you? There's an implicit assumption about the size of the set.

    Although, I've just thought about this a bit more, and I might be leading you up the wrong street slightly. When you assume it's true for a set of size k and show that it's true for a set of size k+1, what you do is take two subsets of size k from the set of size k+1; this assumes that the intersection of these two subsets is non-empty. [That is, there is a horse which lies in both of the size k subsets.] Can you think of a k for which this doesn't work? So how big should your base set be?

    These are basically two ways of saying the same thing; one is a common-sense approach and the other is the mathematical approach.

    EDIT: And for what it's worth this pseudo-proof does generalise, when corrected, to a very important result, which I'll tell you if you're interested (but only after you've worked out where the proof falls).
    So it's when there are two horses? Since if you take two subsets(say A and B) in the set of 2 horses then the intersection of the A and B will be empty?
    • PS Helper
    Offline

    14
    PS Helper
    (Original post by JBKProductions)
    So it's when there are two horses? Since if you take two subsets(say A and B) in the set of 2 horses then the intersection of the A and B will be empty?
    Yup. So basically your "true for k implies true for k+1" only works when k \ge 2, so your base case needs not 1 horse, but 2.
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by nuodai)
    Yup. So basically your "true for k implies true for k+1" only works when k \ge 2, so your base case needs not 1 horse, but 2.
    Thanks, I understand it now. Btw what was the other resultf you was talking about? I'm interested in it now.
    • PS Helper
    Offline

    14
    PS Helper
    (Original post by JBKProductions)
    Thanks, I understand it now. Btw what was the other resultf you was talking about? I'm interested in it now.
    It's really not very interesting, it's just important because it saves a lot of work. The result is essentially that if any pair of horses are the same colour, then all horses are the same colour. But we don't have to be talking about horses and colours, we could be talking about anything. It means that if we can show that something is true for an arbitrary pair, and if that thing being true for some set of size k means that it's true for a set of size k+1, then it's true for everything; and checking these first two things is often easier than checking everything.
    • Thread Starter
    Offline

    7
    ReputationRep:
    (Original post by nuodai)
    It's really not very interesting, it's just important because it saves a lot of work. The result is essentially that if any pair of horses are the same colour, then all horses are the same colour. But we don't have to be talking about horses and colours, we could be talking about anything. It means that if we can show that something is true for an arbitrary pair, and if that thing being true for some set of size k means that it's true for a set of size k+1, then it's true for everything; and checking these first two things is often easier than checking everything.
    Thanks!
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: April 8, 2011
The home of Results and Clearing

2,504

people online now

1,567,000

students helped last year

University open days

  1. Keele University
    General Open Day Undergraduate
    Sun, 19 Aug '18
  2. University of Melbourne
    Open Day Undergraduate
    Sun, 19 Aug '18
  3. Sheffield Hallam University
    City Campus Undergraduate
    Tue, 21 Aug '18
Poll
A-level students - how do you feel about your results?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.