Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site umcp-cs.UUCP
Path: utzoo!linus!philabs!seismo!rlgvax!cvl!umcp-cs!israel
From: israel@umcp-cs.UUCP
Newsgroups: net.math
Subject: Re: A new paradox?
Message-ID: <2588@umcp-cs.UUCP>
Date: Thu, 15-Sep-83 16:17:23 EDT
Article-I.D.: umcp-cs.2588
Posted: Thu Sep 15 16:17:23 1983
Date-Received: Fri, 16-Sep-83 20:28:58 EDT
References: <406@5941ux.UUCP>
Organization: Univ. of Maryland, Computer Science Dept.
Lines: 40


	From: dje@5941ux.UUCP

	Here's a little paradox based on mathematical induction.

	Theorem:  In any set of N elements (N >= 1), all elements in
		  the set are equal.

	Proof:  By induction on N.

	. . .

The problem is in the inductive step.  This step says

"...  all N-1 are the same.  Take one out and put another in.  The new
set is still the same, therefore the new element was the same value as
the set's value.  Put back in the old one (which was clearly the same
value) and voila!"

This reasoning is perfectly correct, FOR N = THREE AND UP!!!!!!  When
you take one out and put one in, there is an implicit assumption that
there is another element in there that you are comparing both the
removed object and the new object to.  For N == 2 (the first time around
of the inductive step) this isn't true.

What it looks like for N = 2 is as follows:

You have a set of one element, a white object.  You also have a black
object.  The elements of the set are all the same color (white), so
let us call the set's color white.  You take the white object out, and
put in the black one.  The set is still all the same color (black), so
the new element must be white (the color of the set).

I've used this proof to prove that all horses are the same color,
which is a lemma necessary to prove that all horses have an infinite
number of legs.  (But that is a different problem).
-- 

~~~ Bruce
Computer Science Dept., University of Maryland
{rlgvax,seismo}!umcp-cs!israel (Usenet)    israel.umcp-cs@Udel-Relay (Arpanet)