Re: Admire the rentacoder.com

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 01/23/05 

Date: Sun, 23 Jan 2005 11:21:14 -0500 (EST)

On Sun, 23 Jan 2005, CBFalconer wrote:
>
> infobahn wrote:
>> You will understand the falsity of that statement when you can
>> find the flaw in the following proof that all integers have the
>> same value.
>>
>> Statement A: "All integers in any group of n integers have the
>> same value." (The word 'group' here is used in the loose sense
>> of 'collection', 'bunch', basketful', not in its mathematical
>> sense. No, that's not the flaw.)
>>
>> We seek to show that Statement A is true for all n. To do this,
>> we will use proof by induction. That is, we will prove that
>> A(1) is true, and then prove that, if A(n) is true, then A(n+1)
>> is true as well.
>>
>> In any group containing only one integer, that integer must have
>> the same value as itself, so we have proved that A(1) is true.
>>
>> Now we need only prove that, given A(n) is true, A(n + 1) is also
>> true. If so, then we can construct an induction ladder from 1 to
>> infinity.
>>
>> If A(n) is true, then every integer in a group of n integers has
>> the same value. Let Z be an arbitrary group containing n + 1
>> integers. If we can show that /any/ two members of Z must have
>> the same value, then we're done.
>>
>> Let Zi, Zj, Zk be arbitrarily-chosen members of Z.
>>
>> Consider the subgroup Y, which comprises all members of Z except
>> Zi. Clearly, Y has n integers, so all members of Y have the
>> same value. Y contains Zj and Zk, so Zj = Zk.
>>
>> Consider the subgroup X, which comprises all members of Z except
>> Zj. Clearly, X has n integers, so all members of X have the
>> same value. X contains Zi and Zk, so Zi = Zk.
>>
>> Two things that are equal to the same thing must be equal to
>> each other. Since Zi = Zk and Zj = Zk, Zi = Zj, i.e. any
>> two arbitrarily chosen members of Z (with n + 1 members) are
>> equal.
>>
>> We have shown that, if A(n) is true, then A(n + 1) is true.
>> We have shown that A(1) is true. Classic proof by induction.
>>
>> All your number are belong to us - unless you are good
>> enough at mathematics to spot the problem. If so, you
>> should have no problem understanding why this...
>
> Love it. I can't put my finger on the flaw, except that the case
> N=2 is conspicuously absent. For it we can't have 3 items.

Also love it. You /did/ put your finger on the flaw --- that's all
there is to it! Since the case n=2 doesn't work, the premise for
all other inductive cases (n>=3) doesn't work. So the only case in
which the proof works is that in which n=1, and that's no surprise.

   One of the better math teachers at CMU, whose course in graph theory
I'm currently taking, devoted part of a lecture recently to the fact
that when mathematicians say "two," quite often what they really mean
is "two or one." E.g., "Each edge of a graph connects two nodes,"
or "Y contains [the two elements] Zj and Zk." :-)

   (Of course, there's another flaw that might be even more apparent
to a trained mathematician: the use of the words "group" and "subgroup"
instead of "set" and "subset." Removing one element from a group
doesn't always leave a group! ;)

-Arthur,
pedant

Loading