dje@5941ux.UUCP (09/14/83)
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.
For N=1, the theorem is clearly true. If N>1, then we can inductively assume
that the theorem is true for all sets of N-1 elements. Select a set of N
elements x(1), ..., x(N). The elements x(1), ..., x(N-1) constitute a set of
N-1 elements, which by the inductive hypothesis are all equal. Similarly,
the elements x(2), ..., x(N) constitute a set of N-1 elements, which by the
inductive hypothesis are all equal. Consequently, by the transitive property
of equality, all the elements x(1), x(2), ..., x(N-1), x(N) are equal. This
completes the proof.
Where's the fallacy?
Dave Ellis / Bell Labs, Piscataway NJ
...!{hocda,ihnp4}!houxm!houxf!5941ux!dje
...!floyd!vax135!ariel!houti!hogpc!houxm!houxf!5941ux!djess@rabbit.UUCP (09/15/83)
-------------------------------
Theorem: In any set of N elements (N >= 1), all elements in the
set are equal.
Proof: By induction on N.
For N=1, the theorem is clearly true. If N>1, then we can inductively
assume that the theorem is true for all sets of N-1 elements. Select
a set of N elements x(1), ..., x(N). The elements x(1), ..., x(N-1)
constitute a set of N-1 elements, which by the inductive hypothesis
are all equal. Similarly, the elements x(2), ..., x(N) constitute
a set of N-1 elements, which by the inductive hypothesis are all equal.
Consequently, by the transitive property of equality, all the elements
x(1), x(2), ..., x(N-1), x(N) are equal. This
completes the proof.
Where's the fallacy?
Dave Ellis / Bell Labs, Piscataway NJ
------------------
What are you trying to prove?? All that the above says is that IF x(1) -- x(N)
are in the set of equals THEN all N-1 element sub-sets of this set are in
the set of equals and (here is the nice part) THEREFORE x(1) --- x(N) are in
the set of equals.
It certainly does not prove that ANY N element set has equal elements.
Sharad Singhalisrael@umcp-cs.UUCP (09/15/83)
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)ecn-ec:ecn-pc:ecn-ed:vu@pur-ee.UUCP (09/15/83)
(And yet another dummy) That "paradox" is rather old and well-known. The fallacy lies in the fact that induction does not apply to all sets. Take your set of n-1 elements. Which one is x(1) ? How did you pick it ? You say "pick any of them" ? No: the choice must be objective (Try to program a computer to pick an number, any number, from a set of data !! If you use random number, the computer is not picking A number, it is picking THE number that conforms somehow to the random number it generated). In fact, principle of inductions applies for a set N if and only if N has a smallest element, whereas "smallest" doesn't necessarily means numerically smallest. If you can somehow OBJECTIVELY define an order in your set of n-1 element, then induction will apply. But you can't. So induction doesn't apply. Hao-Nhien Vu (pur-ee!norris)
tjj@ssc-vax.UUCP (T J Jardine) (09/15/83)
In response to Dave Ellis' "paradox", I first restate the problem:
Theorem: In any set of N elements (N >= 1), all elements in the set
are equal.
Proof: By induction on N.
For N=1, the theorem is clearly true. If N>1, then we can inductively
assume that the theorem is true for all sets of N-1 elements. Select
a set of N elements x(1), ..., x(N). The elements x(1), ..., x(N-1)
constitute a set of N-1 elements, which by the inductive hypothesis
are all equal. Similarly, the elements x(2), ..., x(N) constitute a
set of N-1 elements, which by the inductive hypothesis are all equal.
Consequently, by the transitive property of equality, all the elements
x(1), x(2), ..., x(N-1), x(N) are equal. This completes the proof.
Where's the fallacy?
The fallacy is in the difference between the method of proof used and the
method of mathematical induction. Mathematical induction states that if a
sequence of elements in a set are such that a statement can be proven for
one element AND if true for a preceding element in sequence it can be shown
to be true for the element in question, then the statement is true for all
elements of the set. The step of showing that the property is true for
N=1 corresponds to the first part; however, in attempting the second part
of the proof the possibility that the two sets {x(1) ... x(N-1)} and
{x(2) ... x(N)} are disjoint is totally ignored. In the case that they
are (as for N=2) there is no middle element to which transitivity can be
applied.
TJ (with Amazing Grace) The Piper
...!uw-beaver!ssc-vax!tjjstuart@rochester.UUCP (Stuart Friedberg) (09/16/83)
The inductive step is not legal because your base case is "1". The set S(1) .. S(N-1) = S(1) and the set S(2) .. S(N) is null. If you could show the statement for the case N = 2, then the induction would follow. It's awfully hard to show that any two arbitrary numbers or even any two consecutive numbers are the same!
leimkuhl@uiuccsb.UUCP (09/16/83)
#R:5941ux:-40600:uiuccsb:9700006:000:355 uiuccsb!leimkuhl Sep 15 21:38:00 1983 The problem lies in your assumption that n=1 is adequate "base case." Mathematical induction defined: If P1 and Pn-1 => Pn (for n=2,3...) then Pn (for n=1,2...) In this case Pn is the statement "any n numbers are equal." And the problem is that your induction step implicitly assumes n>2 so that P1=>P2 is never checked (and of course, this fails).
dje@5941ux.UUCP (09/16/83)
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!djedebray@sbcs.UUCP (Saumya Debray) (09/17/83)
Theorem: In any set of N elements (N >= 1), all elements
in the set are equal.
Ah yes! The problem with the proof, of course, lies in the induction step
going from N=1 to N=2:
Select a set of N elements x(1), ..., x(N). The elements
x(1), ..., x(N-1) constitute a set of N-1 elements, which
by the inductive hypothesis are all equal. Similarly, the
elements x(2), ..., x(N) constitute a set of N-1 elements,
which by the inductive hypothesis are all equal. Consequently,
by the transitive property of equality, all the elements
x(1), x(2), ..., x(N-1), x(N) are equal.
For the set with N=2, the subsets {x(1), ..., x(N-1)} and {x(2), ..., x(N)}
are disjoint, so the transitivity of equality can't be applied.
Saumya Debray
SUNY at Stony Brookmark@umcp-cs.UUCP (09/17/83)
So why can't I use the induction to show that all sets of size
equal to or greater than 3 are equal? I'll just start my induction
base at 3, and then everything works out fine. Right? Why not?
--
spoken: mark weiser
UUCP: {seismo,allegra,brl-bmd}!umcp-cs!mark
CSNet: mark@umcp-cs
ARPA: mark.umcp-cs@UDel-Relaylevy@princeton.UUCP (09/18/83)
Now let's hear the proof that all horses have an infinite number of legs (using the fact that all horses are the same color, of course). I'm curious...
pearlman@trw-unix.UUCP (09/20/83)
"So why can't I use the induction to show that all sets of size equal to or greater than 3 are equal? I'll just start my induction base at 3, and then everything works out fine. Right? Why not?" Because "starting your induction base at 3" means proving that all sets of size 3 are equal, which is really hard to do. -- Laura Pearlman ...decvax!trw-unix!pearlman
bennety@tektronix.UUCP (Bennet Yee) (09/22/83)
From ...!{hocda,ihnp4}!houxm!houxf!5941ux!dje:
--------------------------------------------------------------------------------
"Theorem: In any set of N elements (N >+ 1), all elements in the
set are equal."
"Proof": By induction on N.
For N=1, the theorem is clearly true. If N>1, then we can inductively
assume that the theorem is true for all sets of N-1 elements. Select
a set of N elements x(1), ..., x(N). The elements x(1), ..., x(N-1)
constitutes a set of N-1 elements, which by the inductive hypothesis
are all equal. Similarly, the elements x(2), ..., x(N) constitues a
set of N-1 elements, whcih by the inductive hypothesis are all equal.
Consequently, by the transitive property of equality, all elements
x(1), x(2), ..., x(N-1), x(N) are all equal. This completes the
proof.
--------------------------------------------------------------------------------
The transitivity argument holds iff there is overlap in your subsets.
For the case of N=2, however, this is not the case. The two subsets are
disjoint, and transitivity is no longer applicable.
Bennet Yee
tektronix!bennetymcewan@uiucdcs.UUCP (mcewan ) (09/29/83)
#R:tektroni:-137500:uiucdcs:28200018:000:278 uiucdcs!mcewan Sep 28 11:08:00 1983 So why can't I use the induction to show that all sets of size equal to or greater than 3 are equal? I'll just start my induction base at 3, and then everything works out fine. Right? Why not? -- I'll beleive it when I see your proof for the basis (N=3). How about it?