home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10722 < prev    next >
Encoding:
Text File  |  1992-08-31  |  2.3 KB  |  48 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!mcsun!news.funet.fi!ajk.tele.fi!funic!nokia.fi!newshost!chalcraft
  3. From: chalcraft@uk.tele.nokia.fi (Adam Chalcraft)
  4. Subject: Re: Another induction problem
  5. In-Reply-To: weemba@sagi.wistar.upenn.edu's message of 30 Aug 92 22:19:39 GMT
  6. Message-ID: <CHALCRAFT.92Aug31105002@laurel.uk.tele.nokia.fi>
  7. Sender: usenet@noknic.nokia.fi (USENET at noknic)
  8. Nntp-Posting-Host: laurel.uk.tele.nokia.fi
  9. Organization: cpd
  10. References: <ARA.92Aug30103547@camelot.ai.mit.edu> <87431@netnews.upenn.edu>
  11. Date: Mon, 31 Aug 1992 08:50:02 GMT
  12. Lines: 34
  13.  
  14. Any chance of explaining how an induction can get that complicated?
  15.  
  16. Ordinary induction works because w (read omega, the ordinal) is well-ordered,
  17. so there must be a minimal counter-example.
  18. "Two deep" induction (of the form: Induce over pairs (x,y), where a pair
  19. (x,y) < (x',y') iff x<x' or (x=x' and y<y'), i.e. so long as x goes down, I
  20. don't care how much y goes up) works because w^2 is well-ordered.
  21. My thesis goes up to w^3.
  22. The proof that Conway's Sylver Coinage game (see Winning Ways) terminates
  23. works because w^w is well-ordered.
  24.  
  25. There are other well-ordered sets, of course, but the very definition of
  26. ordinals means that every well-ordered set is order-equivalent to an ordinal.
  27.  
  28. Maybe I've missed something. Can induction exist without relying on a well-
  29. ordered set? Are we talking about transfinite induction? But it seems to me
  30. that the complexity of any induction scheme can be described by quoting the
  31. ordinal it relies on.
  32.  
  33. Of course, writing down an ordinal can be tricky (Challenge for the naive
  34. reader: Devise a general scheme for writing down any ordinal :-) :-) :-)),
  35. but is that really the major conceptual difficulty here?
  36.  
  37. Thanks.
  38. --
  39.   ____________________________________________________________________________
  40.  /  _Name: Adam|Names are linguistic constructs expressed in some language._  \
  41. |\_|/|Chalcraft|They correspond to objects in some universe of discourse. |\|_/|
  42. |`   |         |The corresponence between names (in the language) and     |`   |
  43. |`   |Opinions:|objects (in the universe of discourse) is the  relation of|`   |
  44. |`   |     Mine|identifying. A name identifies the object to which it is  |`   |
  45. |`   |_________|bound.__________________________ISO_7498-3_:_1989_(E)_5.1_|`   |
  46.  \__/                                                                      \__/
  47.  
  48.