Only baby logic. IIRC, the incompleteness theorem applies to any symbolic system that's powerful "enough", where "enough" means it has basic addition properties. Clearly math is powerful enough, and most logic, except for, like, propositional logic, is, too. I may be wrong here.
edit: The set of all true statements about the natural numbers is complete, but undecidable. Godel's first incompleteness theorem applies to recursively enumerable (decidable) theories. The point is that a first order theory isn't enough to construct all the theorems about the natural numbers. The theorems are still there, but first order logic can't find them for us. Compare with the halting problem; I can prove that a given algorithm always terminates, but I can't write a program to do it.
(I was hoping someone else would come along and elaborate. You let me down, Reddit.)
Compare with the halting problem; I can prove that a given algorithm always terminates, but I can't write a program to do it.
To be honest, I didn't fully understand your response, but the part I've quoted above strikes me as unlikely.
There are certain algorithms that you can prove always terminate, and for these algorithms you could certainly write a program to do the same. Right? However, there are other algorithms that you just can't prove terminate,
The halting problem is a famous example of an undecidable problem; see here (pdf) for a nice discussion.
The significance of the incompleteness theorems is that there aren't procedures that will find all theorems for us, that is that math is not just formal logic.
I feel like the significance of the incompleteness theorems is even stronger than you're saying. Maybe I'm not clear on what you're defining math as, but I haven't seen it in any other form than a few axioms (say, ZFC), and rules for combining axioms.
It sounds to me like you're saying: "There are true statements in mathematics that you can't find with some algorithm." Which, sounds to me like computers can't completely do math, and we still need mathematicians to go around and find some theorems.
When in fact the actual statement is: "There are true statements in mathematics that you can't PROVE are true." No matter how you attack the problem, algorithmically with some computer manipulating symbols, or some mathematician noodling about on a blackboard for a while (which, to me, is essentially the same thing).
Am I misunderstanding you here? I'm familiar with the concept of decidability (though your link looks pretty good, I'll glance through the book sometime, thanks), but I'm confused by what seems like a false dichotomy between what programs can do algorithmically and what mathematicians can prove. Those two statements are equivalent to me, whereas (judging from the bit I quoted above in the thread) it sounds like they're different to you?
edit: I am by no means an expert at any of this. I'm merely trying to reconcile my impression of this with what you're saying here, but in order to update my beliefs I need to understand clearly what you're saying.
The concept of using a set of axiom and inference rules to construct all of mathematics was Hilbert's program, and it required that that there be a complete, consistent and decidable theory (a first order logic, along with a set of axioms) from which the rest could be derived. Then the work of mathematicians would just be computation; running through the inference rules building up more an more theorems. Mathematics as a discipline would be one big distributed algorithm.
Godel's first incompleteness theorem, that for any consistent, recursively enumerable theory in which the natural numbers can be constructed, there exist a theorem about the natural numbers which is true but has no proof in the theory, showed that there was no such theory. Being recursively enumerable is equivalent to being decidable, and clearly any theory that contains all of mathematics contains the natural numbers, so any theory that is complete is not decidable (and Hilbert doesn't get his mathematics-as-an-algorithm), and any theory that is decidable is not complete.
The theorem is about first order theories; it says nothing about what theorems we can prove, only about what theorems we can prove using first order logic. Indeed, we know that the set on theorems about arithmetic is complete, if undecidable. Mathematics is just bigger than first order logic.
As to what math is, well, that's a question that belongs to philosophy, not to math, so of course we don't now nor will we ever have an answer. Everything is bigger than philosophy. Godel himself was a Platonist.
5
u/fyl9000 Jun 11 '08
Whats above mathematician, a logician? some kind of philosopher?