With help from wikipedia, here's my summary of Godel's Theorems:
Godel's incompleteness theorems talk about the limitations of formal systems. First, two definitions: A set of axioms is consistent if you can't find a statement such that you can prove the statement and its negation from those axioms. A set of axioms is complete if for any statement in the axioms' language, you can prove it or its negative using those axioms.
So there are actually two theorems. The first one is something like "any system capable of expressing basic arithmetic cannot be both consistent and complete." So, if a system can prove basic arithmetic, then there is an arithmetic statement that is true, but not provable in that system.
The second theorem is something like "for any system that can express arithmetic and provability, that system can describe its own consistency if (and only if) it's inconsistent.
This was a big deal when Godel proved this, because mathematicians at the time were trying to rebuild math from the ground up, 100% provable and complete, and he basically showed that it was an impossible task.
So that's my non-mathematician's interpretation.
As far as our class and first order logic, the question becomes, is first order logic sufficiently capable of expressing basic arithmetic such that it must be either consistent or complete, but not both? This matters because we need to know if an agent can reach faulty conclusions because its logic is inconsistent, or if true statements can't be reached because its logic is incomplete, right?
Based on what Rao said in class, Godel's theorem doesn't apply to first order logic. Is it because you can create an infinite number of axioms in first order logic, and thus it's impossible to try and prove a given statement starting from an infinity of axioms? Or is there another reason? I'm not good enough at math to see the answer on my own.
(Also, there's a great book called "Godel, Escher Bach" that I think everyone in this class would really like).
Subscribe to:
Post Comments (Atom)
I was not in the class when Rao talked about FOL. But here is my understanding of the problem: FOL is sound and complete (people interested in can ask me for a proof but be prepared to spend few days on it) but if you try to extend FOL to cover basic arithmetic, then it can not be both sound and complete.
ReplyDeleteRao, please correct me if this is not what you mean.
Ah, I was thinking it could cover basic arithmetic with functions (he shows a SqrRt function in the slides). But if it can't, then that makes perfect sense. Thanks!
ReplyDelete