Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

?
Lv 7
? asked in Science & MathematicsMathematics · 1 decade ago

What is wrong with this proof? (Induction)?

Theorem:

Everyone has the same name.

Proof (by induction on the number of people in a group):

for n=1, a group of only one person, they obviously have the same name as everyone else in the group.

now suppose that the theorem is true for all groups of people of size k < n.

suppose we take any one person out of the group. then, by our induction hypothesis, everyone left has the same name (since we now have n-1 < n people). now add the person we took out, and take out another person. since we still have a group of n-1 < n people, they all have the same name, which shows that the person we excluded originally has the same name as all the others. thus all n people have the same name, from which we conclude that any group of of any number of people must all have the same name. therefore, everyone has the same name.

see if you can figure out what is wrong with this proof.

Update:

"assuming true for all k < n" is a valid inductive hypothesis step (a form of induction known as strong induction). no, the argument is not circular. it does indeed have a flaw (obviously not everyone has the same name). furthermore, the theorem is OBVIOUSLY true for n = 1, every person has the same name as himself (or herself). the flaw is more subtle than that.

Update 2:

i beg to differ. a group of people is a finite set, and the order of that set is most certainly a natural number. the fact that i chose a certain property (name of an element of the set) that seems non-mathematical is irrelevant. there is a flaw in the argument, and the flaw is mathematical. you are confusing content with form.

i repeat, there IS a flaw in the argument. no one has found it yet. 10 points to the first who does :)

6 Answers

Relevance
  • 1 decade ago
    Favorite Answer

    it's entirely circular, that's what's wrong with it. it's like saying "all plants are round and green. i will prove this because peas are round and green. now suppose this applies to all plants. then all plants would be round and green. see if you can figure out what is wrong with this proof." you're not supporting the induction with anything and i'm not really sure why you're asking this.

  • Pope
    Lv 7
    1 decade ago

    I think I get the question now. Let P(n) be the proposition that all people in a group of n have the same name. As part of the inductive process, you must show that P(n) must be true if P(k) is true for all k < n.

    The trouble begins when n = 2. Suppose that the two people are Bob and Doris. First we remove Bob. All of the remaining people have the same name, because P(1) has been proved (or accepted as obvious anyway). Now replace Bob and remove Doris. Again, all of the remaining people have the same name. Here is the mistake:

    "...they all have the same name, which shows that the person we excluded originally has the same name as all the others."

    No, it does not prove that. The person we originally excluded (Bob) was never compared with Doris directly. And when n = 2, we cannot use any kind of a transitive property, because there are no people with whom Bob and Doris have both been compared.

  • 1 decade ago

    The proof is invalid, because you already ASSUMED the entire group has the same name.

    If the group already has the same name, it is trivial to prove a subset has the same name!

    The problem is you need to first prove it true for ANY n, not just n = 1.

    Induction usually proves for some value, n=1, and then proves it true for n+1, NOT n-1, as you did.

  • Anonymous
    4 years ago

    no longer an entire answer...yet i'm positive i can help you you if I understand.... i do not see how your evidence for ok+a million is valid. You tell me that in case you eliminate one huge style from a chain of ok equivalent numbers that the perfect numbers are all a similar. that is clearly real. in spite of the indisputable fact that this shows me it is your assumption is real for a chain of ok numbers then it really is likewise real for ok-a million individuals of that set. It does no longer instruct me that it really is real in case you upload an more desirable huge style ...it really is for a chain of ok+a million numbers.... Please clarify why you've self assurance that your evidence demonstrates this. ok thanks for the further clarification...yet...i'm nonetheless no longer confident, the evidence would not fairly make experience to me....something is incorrect right here. obviously if this works for a 'universal' set the position all numbers are a similar..then it also ought to paintings for a particular set. So why no longer instruct me your evidence the position we start up with a chain of ok numbers...that are all equivalent to x, and let ok be 5 and x b 12. So, in different words you've a chain of 5 numbers all equivalent to 12....Please use your good judgment to instruct me that in case you upload a sixth huge style to the set that this huge style also must be 12..... obviously this isn't the case, yet my wager is that operating by this get jointly will instruct you the mistakes contained in the best judgment....Please try this as i might want to need to understand the "concern" more desirable suited...(excellent now i do not even see an situation as to me the evidence for ok+a million isn't maximum suited) i'm satisfied to debate more desirable if this facilitates.

  • How do you think about the answers? You can sign in to vote the answer.
  • 1 decade ago

    The problem with this is that it is not mathematics, and therefore not mathematical induction. Try the section dealing with Logic.

  • Anonymous
    1 decade ago

    "now suppose that the theorem is true for all groups of people of size k < n" this just doesn't make sense.

    induction is two steps:you first prove statement true for n=1 then you prove that if it is true for any n it must be true for n+1

Still have questions? Get your answers by asking now.