home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10234 < prev    next >
Encoding:
Text File  |  1992-08-13  |  2.2 KB  |  46 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!mcsun!sunic!sics.se!sics.se!torkel
  3. From: torkel@sics.se (Torkel Franzen)
  4. Subject: Re: Expansion of set theory
  5. In-Reply-To: boshuck@triples.math.mcgill.ca's message of Thu, 13 Aug 92 17:44:08 GMT
  6. Message-ID: <1992Aug13.190645.19211@sics.se>
  7. Sender: news@sics.se
  8. Organization: Swedish Institute of Computer Science, Kista
  9. References: <1992Aug7.002122.24601@access.usask.ca>
  10.     <1992Aug12.164408.10547@thunder.mcrcim.mcgill.edu>
  11.     <1992Aug12.182912.4659@sics.se>
  12.     <1992Aug13.174408.10574@thunder.mcrcim.mcgill.edu>
  13. Date: Thu, 13 Aug 1992 19:06:45 GMT
  14. Lines: 30
  15.  
  16. In article <1992Aug13.174408.10574@thunder.mcrcim.mcgill.edu> boshuck@triples.
  17. math.mcgill.ca (William Boshuck) writes:
  18.        
  19.        >On the other
  20.        >hand, I don't quite know what theorems you may be talking 
  21.        >about. A big theorem in this area, that there is no uniform 
  22.        >algorithm to decide whether a given Diophantine equation has
  23.        >solutions (due to Matiesevitz (spelling?) I think) doesn't 
  24.        >use any aspects of the theory of large cardinals (an easy
  25.        >presentation of this theorem can be found in Bell and 
  26.        >Machover's book on mathematical logic).
  27.  
  28.    I had in mind the following application of the theorem of Matiyasevic
  29. (which built on work by Davies, Putnam, and Robinson). The theorem states
  30. that every recursively enumerable set is Diophantine, i.e. is equal to
  31. the set of k such that the equation P(k,x1,..xn)=0 has a solution, for some
  32. integer polynomial P. This is very remarkable. The theorem is, as you note,
  33. elementarily provable. This means that an ordinary consistency statement -
  34. say "ZF is consistent" - is elementarily equivalent to the statement that
  35. a certain Diophantine equation has no solution. Since the consistency
  36. statement is provable e.g. in ZF+"there is an inaccessible cardinal", the
  37. assumption that there is an inaccessible cardinal has consequences regarding
  38. the unsolvability of Diophantine equations that are not provable in ZF
  39. itself.
  40.  
  41.   For a given Diophantine equation - e.g. Fermat's - this of course tells
  42. us nothing. But it is a striking fact concerning the relation between
  43. "concrete" and "metaphysical" mathematics that should be more widely known
  44. than it is.
  45.  
  46.