My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Thanks Tree4Thanks
  • 2 Post By v8archie
  • 2 Post By CRGreathouse
Reply
 
LinkBack Thread Tools Display Modes
April 5th, 2014, 08:18 PM   #1
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,664
Thanks: 2644

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 meta-mathematics (and meta-meta-mathematics, 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?
Thanks from CRGreathouse and MarkFL
v8archie is offline  
 
April 5th, 2014, 08:55 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
Thanks from MarkFL and v8archie
CRGreathouse is offline  
April 6th, 2014, 05:52 PM   #3
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,664
Thanks: 2644

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by CRGreathouse View Post
For another, we must give up hope on a general procedure to prove an arbitrary proposition.
I'm far from sure that this is a bad thing. I think much of the artistry and beauty of Mathematics comes from proving theorems. Where decision algorithms exist, there may be some interest in deciding which propositions are worth testing, and there may be some skill and even artistry in producing proofs via more usual methods when the algorithm would take a long time, but it seems to me that the romance and beauty disappears (at least to some extent).

Quote:
Originally Posted by CRGreathouse View Post
For one, we can't gain full mathematical certainty that the systems we use are consistent.
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.
v8archie is offline  
April 7th, 2014, 07:30 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by v8archie View Post
I'm far from sure that this is a bad thing. I think much of the artistry and beauty of Mathematics comes from proving theorems. Where decision algorithms exist, there may be some interest in deciding which propositions are worth testing, and there may be some skill and even artistry in producing proofs via more usual methods when the algorithm would take a long time, but it seems to me that the romance and beauty disappears (at least to some extent).
I don't disagree. Were it possible to find general methods I think finding them would be well worthwhile, but I'm not disappointed that they don't exist.

Quote:
Originally Posted by v8archie View Post
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.
I'd say a collection of formal systems rather than a (single) formal system, but that works out to be much the same. I don't think that we 'transcend' formal systems in any reasonable way. (Relatedly, I don't think the human mind 'transcends' the limits of Turing machines.)
CRGreathouse is offline  
Reply

  My Math Forum > Math Forums > Math

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
Gdel's Completeness Theorem Hyperreal_Logic Applied Math 0 December 31st, 2009 05:27 PM





Copyright © 2019 My Math Forum. All rights reserved.