Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!harpo!gummo!whuxlb!pyuxll!eisx!npoiv!npois!hogpc!houxm!5941ux!dje
From: dje@5941ux.UUCP
Newsgroups: net.math
Subject: Re: A new paradox?
Message-ID: <410@5941ux.UUCP>
Date: Fri, 16-Sep-83 13:34:28 EDT
Article-I.D.: 5941ux.410
Posted: Fri Sep 16 13:34:28 1983
Date-Received: Sat, 17-Sep-83 06:30:10 EDT
References: ecn-ed.204
Lines: 28

Several responses were received on the paradox of "proving" by mathematical
induction that all elements in a finite set are equal.

Two responses missed the boat.

rabbit!ss claimed that the inductive step of the proof assumed truth for
N, derived truth for N-1 and then demonstrated truth for N (circularly).
This is not the case.  The only assumption in the inductive step was the
truth for N-1, not for N.  The elements x(1), ..., x(N) were not assumed
equal!

pur-ee!norris said the inductive step was invalid because of the choice of
ordering of the elements.  The argument was in fact independent of the 
ordering.  Any finite set can be enumerated with integer indices, so simply 
numbering the elements of an N-member set x(1), ..., x(N) does not invalidate 
the proof.

The fallacy, as several respondents correctly pointed out, is in applying
the transitivity property.  If x(1), ..., x(N-1) are all equal and if
x(2), ..., x(N) are all equal, then x(1), ..., x(N) are all equal PROVIDED
there is overlap.  Overlap occurs for N >= 3; for N=2 the two (N-1)-sets are
disjoint.  Thus the inductive step won't take you from 1 to 2; the fact that
it takes you for N-1 to N for N >= 3 sounds convincing but doesn't mean very 
much.

Dave Ellis / Bell Labs, Piscataway NJ
...!{hocda,ihnp4}!houxm!houxf!5941ux!dje
...!floyd!vax135!ariel!houti!hogpc!houxm!houxf!5941ux!dje