Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10 5/3/83 based; site hou2g.UUCP Path: utzoo!watmath!clyde!akgua!sdcsvax!dcdwest!ittvax!decvax!mcnc!unc!ulysses!mhuxl!houxm!hou2g!mnc From: mnc@hou2g.UUCP Newsgroups: net.math Subject: Re: Interesting number proof invalid Message-ID: <251@hou2g.UUCP> Date: Fri, 11-May-84 18:56:45 EDT Article-I.D.: hou2g.251 Posted: Fri May 11 18:56:45 1984 Date-Received: Sun, 13-May-84 07:36:34 EDT References: <7672@watmath.UUCP>, <2457@allegra.UUCP> Organization: AT&T Bell Labs, Holmdel NJ Lines: 31 The proof is not invalid and is not a proof by induction. It appears to be on the surface, but it is actually a proof by simple contradiction. Its framework is like this: o If there exists a number n, having specified property P, then there exists a smallest such number (obviously). o Being a smallest number with property P is incompatible with having property P, hence no such n can exist. The only induction involved is a trivial one in the first part. It is not even stated because it is obvious, but formally it is an induction that proceeds from n down to 0, so it is well-founded. If you insist on seeing it explicitly, it goes by induction on n: o Base case: n=0. If 0 is the number n with property P then 0 is the smallest as well. o Inductive case: Assume true for all i < n. If n has property P then either it is the smallest, or there is a number k