
Math General Math Forum  For general math related discussion and news 
 LinkBack  Thread Tools  Display Modes 
April 5th, 2014, 08:18 PM  #1 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,622 Thanks: 2611 Math Focus: Mainly analysis and algebra  Completeness, consistency, and what we can know
I've been a bit of a fan of GÃ¶del for many years without seriously studying any of his work. Indeed, the closest I've come is in reading Hofstadter and I'm not sure I followed all that he said in there. But today I came across this thread which has reignited my interest in a particular question. Given that any formal system sufficiently strong can not be both complete and consistent, what limits are placed on our ability to know the universe and what limits are placed on our ability to know the mathematical landscape? My particular take on this is that mathematics is doesn't seem to be a strictly formal system because we operate as much on the level of metamathematics (and metametamathematics, etc.) as we do in mathematics itself. And as such, despite destroying Hilbert's program, there is no certainty that GÃ¶del places any limits on human knowledge. That said, there are clearly some undecidable propositions that can be coded into mathematics: in particular we can encode "this theorem cannot be proven" (or something similar) into the language of a strictly formal system. Another related question is whether anything useful is hidden by GÃ¶del's theorems? He showed that we can deliberately code a paradox into a formal system and (thankfully) find it unprovable, but that doesn't necessarily mean that there is anything of substance that is not provable. What do you think? 
April 5th, 2014, 08:55 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
There are definite limits. For one, we can't gain full mathematical certainty that the systems we use are consistent. That's a bit discouraging, especially since some formal systems have been shown inconsistent. For another, we must give up hope on a general procedure to prove an arbitrary proposition. Absent Goedel's theorem, you might think that such a thing would be possible. And indeed, in some systems too weak for Goedel's theorem to apply, we do have such procedures! For example, the truth of any statement in Presburger arithmetic can be determined by a fixed procedure which takes finite (but possibly very long!) time which can be bounded as a function of the length of the statement. The same is true of Skolem arithmetic. So quantified sentences over the integers containing either multiplication or addition, but not both, can be decided in a completely automatic way. (Combining the two gives Peano arithmetic, which Goedel proves to be undecidable.) Similarly, there is an algorithm for deciding the truth of a statement in real closed fields. So quantified sentences over the real numbers containing addition and multiplication can be similarly decided. This is perhaps unobvious: real numbers are, in a deep sense, easier than integers. It follows from the decidability of real closed fields that elementary geometry and arithmetic over the complex numbers are both decidable. In summary: there are weak (but still interesting) systems where we have procedures for answering all questions, though finding the answers may take a long time. Goedel's result shows that we can't extend this to more powerful systems. 
April 6th, 2014, 05:52 PM  #3  
Math Team Joined: Dec 2013 From: Colombia Posts: 7,622 Thanks: 2611 Math Focus: Mainly analysis and algebra  Quote:
Is Mathematics in general a formal system? Does the way we think about it on many different levels mean that it breaks the bounds of formal systems? Or is it just and extremely complicated formal system? Certainly, our attempts to base all proofs on existing theorems would suggest that it is a formal system, but our ways of thinking about Mathematics, especially when we are looking for a likely solution to a problem (perhaps before proving the result), seems to transcend formal rules at times.  
April 7th, 2014, 07:30 PM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
Quote:
 

Tags 
completeness, consistency 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Consistency  Robert Lownds  Advanced Statistics  1  December 1st, 2013 12:59 PM 
Completeness of real numbers  OriaG  Algebra  6  November 2nd, 2012 11:33 PM 
Countability and completeness  Huitzyl  Real Analysis  1  August 2nd, 2012 02:28 PM 
Geometric mean  consistency test  Dinis  Linear Algebra  0  November 25th, 2011 01:33 PM 
Gödel's Completeness Theorem  Hyperreal_Logic  Applied Math  0  December 31st, 2009 05:27 PM 