mwg@allegra.UUCP (Mark Garrett) (05/07/84)
The problem with using induction here is that the assignment of the 'interesting' property to a number is not independent of whether other numbers share this property. If a number A is interesting because it is the least (previously) uninteresting number and a larger number B is declared interesting for the same reason, then A has lost its interest, hasn't it? This has a (slightly) interesting (no pun) connexion to a race-around condition in flip-flops. Mark Garrett BCR, Murray Hill
csc@watmath.UUCP (Computer Sci Club) (05/11/84)
...
The proof that all numbers are interesting (given the questionable
assumption that the least uninteresting number is interesting) is not
an inductive proof but a proof by contradiction. If we assume the set
of non-interesting numbers is non empty then there is a least non-
interesting number which is by assumption an element of both sets (we
do not remove it from the set of non-interesting numbers, it is already
assumed to be an element of that set) and we have a contradiction. This
proof is quite valid and very silly. Note also, although under the normal
ordering of the reals, there exist subsets with no least element, there
exists (if like all right thinking mathematicians you accept the axiom of
choice) an ordering of the reals such that every subset has a least element.
Hence it follows that all real numbers are interesting!
William Hughes
DOWN WITH INTUITIONISM!!mnc@hou2g.UUCP (05/12/84)
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<n that
has the property. In the latter case we use induction to claim
that there is a smallest. Hence the claim is true for all
i <= n.
If you are a normal human-been with an average attention span you are
by now asleep, so it probably would be a waste of my time to continue
with a translation into formal first-order logic ... Unless you really
want to see it ... Okay, okay, I get the hint.
Michael Condict ...!{ihnp4|allegra}!hou2g!mnc
AT&T Bell Labs, Holmdelpkelly@westcsr.UUCP (05/17/84)
We have a proof that all numbers, for example 1,2,3... are interesting since any set of non-interesting number drawn form the number set must have a least element, which will be interesting if only for that reason. If, for a moment, we accept this, and disregard the reasonable objections that (1) this is silly, and (2) the induction implied doesn't work since once you choose your next 'interesting' set to exclude the least element of the previous one, you make that element boring again. We can then note that the argument doesn't follow for reals, leaving open the assertion that real numbers are proportionately less exciting than rational, naturals etc (constructivists who might up to now have shuddered at the naivete of the discussion can now cheer). The reason is that a set of real numbers can be bounded below without containing its bound - there might be an infinite progression of decreasing boring numbers (perish the thought), which neither stop decreasing nor reach any chosen value without eventually crossing it. The argument follows, of course, for lots of other uncountable sets. Yours, Paul Kelly. PS The rationals example takes a little explanation - instead of taking the least el. as your new interesting value, take the first in some enumeration (diagonalisation) of the rationals.