Kurt Gödel and the romance of logic
prospectmagazine.co.uk
prospectmagazine.co.uk
All you have to know that the process of proving a statement is a fairly mechanical, step-by-step process. At that point, "statements that can be proven true" and "statements that be proven false" are two fairly defined sets. At that point, "there are some true statements that cannot be proven true" is moderately clear.
Then you introduce the idea of a model and make the concept fully exact.
The thing to remember is Gödel himself never really liked this simple view and wanted truth to be more transcendent. He shared with Einstein the quality of not liking the results of his discoveries, perhaps a source of their friendship.
In the context for the Incompleteness theorems, there are two 'kinds' of truths: a more informal kind used by all of us everyday and the mathematical kind as in, proven true under a given system.
The entire purpose of the theorems is to establish that there exists theorems in the first set that are not in the second set, while being expressable in the system. To deny the existence of the first kind of true statements ignores the entire purpose of it all.
Your third paragraph doens’t make sense. In first order logic a theorem is a statement that is true in all models and is one that is provable. This is a result of the Completeness Theorem.
[1] https://www.quora.com/How-did-G%C3%B6del-believe-the-US-coul...
[2] https://www.quora.com/What-was-the-flaw-Kurt-G%C3%B6del-disc...
----
from https://www.newyorker.com/magazine/2005/02/28/time-bandits-2
So naïve and otherworldly was the great logician that Einstein felt obliged to help look after the practical aspects of his life. One much retailed story concerns Gödel’s decision after the war to become an American citizen. The character witnesses at his hearing were to be Einstein and Oskar Morgenstern, one of the founders of game theory. Gödel took the matter of citizenship with great solemnity, preparing for the exam by making a close study of the United States Constitution. On the eve of the hearing, he called Morgenstern in an agitated state, saying he had found an “inconsistency” in the Constitution, one that could allow a dictatorship to arise. Morgenstern was amused, but he realized that Gödel was serious and urged him not to mention it to the judge, fearing that it would jeopardize Gödel’s citizenship bid. On the short drive to Trenton the next day, with Morgenstern serving as chauffeur, Einstein tried to distract Gödel with jokes. When they arrived at the courthouse, the judge was impressed by Gödel’s eminent witnesses, and he invited the trio into his chambers. After some small talk, he said to Gödel, “Up to now you have held German citizenship.”
No, Gödel corrected, Austrian.
“In any case, it was under an evil dictatorship,” the judge continued. “Fortunately that’s not possible in America.”
“On the contrary, I can prove it is possible!” Gödel exclaimed, and he began describing the constitutional loophole he had descried. But the judge told the examinee that “he needn’t go into that,” and Einstein and Morgenstern succeeded in quieting him down. A few months later, Gödel took his oath of citizenship.
----
Another one: https://www.quickanddirtytips.com/education/science/when-g-d...
---
EDIT: something I also missed in this piece was that Gödel developed rheumatic fevers as a child and started reading medical books with the age of 8 to learn more about the condition. He concluded that he had a weak heart :D
Gödel is really worth studying closer and this article just leaves out a lot.
Any reccs on books to read, more focused on their theories than their lives?
This is a gross misinterpretation of Gödel's actual theorem that helps perpetuate irrational superstitious attitudes against science, mathematics, and logic.
What Gödel showed was that proofs are relative to some underlying axiomatic model and that for any particular axiomatic model there are always truths unprovable by it.
That doesn't mean "there are truths that humans can never prove", all it means is that we have to extend our axiomatic systems in order to prove some truths. (And whether they are true or false "in reality" is another question, to be determined empirically.)
A more accurate (and just-as-click-baity) way of interpreting Gödel's theorem is that "mathematicians and logicians will always have a job".
Mathematical and logic truths have highest apstraction level.By definition they can 't be proved or disapproved in reality they exist only in apstraction.
It is, it really is. Yet is also an interpretation that Gödel himself would indulge in.
Consider his most famous quote: "Either mathematics is too big for the human mind, or the human mind is more than a machine." (I remember reading this statement in the Time-Life book on mathematics when I was a kid).
I don't think it's irrational or anti-science to say or think that. It just seems like it might be a possibility, which sure, why the hell not?
"There's this thing we can't prove under the given axioms"..."Ok, well just extend the axioms"..."Right but there is still this other thing we can't prove under that set of axioms."..."Ok, so rinse and repeat?"
How, if you can't prove it, do you figure out if it is an axiom in the first place?
But what's say there was some conjecture that if proved to be the case proved a unifying theory of everything in Physics that relied on that conjecture, but that conjecture couldn't be proven under the given set of axioms... then in that case wouldn't it be that there were some truths about the universe that aren't possible to prove?
- Well, the axioms of a given model generally can't be proven. Every model one builds begins with "unprovable things". However, the "truth about the universe" would have to be demonstrated by experimentation and mathematics would only provide the model. So every theory about the universe is using something unprovable (the axioms of its model). But Godel's theorem in particular (technically Godel's 1st incompleteness theorem) is still just a statement about proof processes work and how truth-assignments work. Whether are ineffable truths or not is a different question.
"There's this thing we can't prove under the given axioms"..."Ok, well just extend the axioms"..."Right but there is still this other thing we can't prove under that set of axioms."..."Ok, so rinse and repeat?"
- Yes, you can do that, well you can talk about doing it. In fact, Godel's "completeness theorem" is based on this procedure, more or less. The thing is you start with a set of axioms, add a proposition that can't be proven either true or false under the axioms, and decide arbitrarily whether to make it true or false. Continue forever (or transfinitely, depending how huge your system is) and you get a complete truth-assignment. Of course, there's no algorithm for finding all these undecidable propositions so this procedure is very theoretical. You or I or an AI couldn't do this to arrive pocessing this complete set but mathematically you can say "I hereby choose all the unprovable axioms and string them together thus (one of those weird "axiom of choice" things). So this approach is used, it's just it doesn't us to escape unprovable things.
If I'm understanding things right it's that proving things with logic means you are showing that something is consistent within a system and that is all you are definitely able to say from that. Not whether something is 'true' in a wider sense outside of that system. And all axioms are assumptions, so all our proofs are saying is that 'assuming that these things are the case then we can show the following result is commensurate with those assumptions and completely internally consistent'.
If you believe that the only consequence to Gödel's theorem is we need to "extend our axiomatic system", I do think you've missed the point.
For one thing, I think Gödel's theorem and Gödel's proof are unfortunately conflated.
Gödel's proof is lovely and elegant, and can be understood with minimal knowledge of logic, but, ultimately, all it does is provide a counter example. So when people read his proof and understand it, they tend to be unimpressed with its power because the counter example is very generic and seems an uninteresting barrier to our ability to discern "truth". But that says nothing about there may be lots of other kinds of unprovable statements.
Ultimately, Gödel's theorem tells us one absolute kernel of truth by saying all but very basic axiomatic models are necessarily incomplete. However which way you want to make the philosophical leap to connect that to our notion of "truth" seems far more up to interpretation, but it annoys me when people disrespect the theorem because they're unimpressed with the counter examples the proof constructs.
This is not acceptable to a constructivist, for whom “a statement is true if we have a proof of it, and false if we can show that the assumption that there is a proof for the statement leads to a contradiction”[1]. The parent poster, whatshisface, may be a constructivist.
[1] Troelstra A., D. van Dalen (1988) “Constructivism in mathematics: an introduction”
The weirdness of True Arithmetic comes not from proofs (which are trivial) but from the axioms themselves. You can object that it’s not a “reasonable” or “proper” theory because it’s not recusively axiomatizable (i.e. there’s no effective procedure for even deciding whether a statement is an axiom), but I don’t think that objection is specifically constructivist.
You seem to be confusing "true" and "provable", as far as first order logic is concerned those are equivalent (by another theorem of Gödel, the completeness theorem), but the first in defined in terms of models and the second is purely syntactic
Also, it doesn’t seem right to use the informal “take” when the object in question is not computable.
Also intuitionist logic is not my area, but isn't it divided in inference rules for provability and (Heyting or Kripke) semantic for model theory and truth just like FOL?
I suspect you haven't gone through the actual rigorous proof which is highly technical and requires more than a "minimal knowledge of logic"
It’s important that we are talking about models of the first order Peano Axioms. One can always find a system of axioms in which all true statements are provable. To do this just take the collection of all true statements in the standard model. Now every true statement is a theorem. It’s easy to have a complete set of axioms. What can’t happen is a recursively enumerable set of axioms that is complete and consistent.
Recursively enumerability is needed so that one can have an effective means of determining if a statement is an axiom. Think computable when I say effective.
When talking about truth we need to be careful because this is tied to a model of an axiomatic system. By the Completeness Theorem a statement that is true in all models of the system is provable.
I used both the words "truth" and "provable" in the correct and appropriate ways. Both are distinct concepts that form an important part of the theory.
But the very interesting part is that you might keep extending and extending two axiomatic systems until every true statement is provable in one or the other system. However, you're guaranteed that in that case, the two systems will be inconsistent with each other such that they cannot be combined into a consistent whole.
Well, if there’s an analogue of a Gödel sentence for humans...
Also of interest is Godel's AMS Gibbs Lecture, which unfortunately I have not been able to locate on-line. It can be found in Volume 3 of Godel's Collected Works, alongside his paper / lecture notes on closed time loops in general relativity.
If you allow the use of a three-valued logic, for example, with (true, undetermined, false), the Gödel statement, “I am not provable" amounts to saying "My provability is false or undetermined".
The same problem occurs in Russell's paradox, "Does the set of all sets that do NOT contain themselves, contain itself?"
The use of the NOT-operator is degenerated in a cyclic group Z2. It is the only situation in which the NOT-operator is not set-valued.
In my opinion, if the "isProvable()" predicate allowed for multi-valued logic, Gödel's incompleteness theorem would look much less paradoxical. In other words, the paradoxical outcome could simply be the result of Boolean shoehorning.
To be pithy, if we choose a (true, undetermined, false) compatible with topos logic, we should be able to encode Gödel's work using only the "true" and "false" values.
You have hit upon something important, though. Recall that, in constructive logic, (WFF) statements are either true, false, or not false, where "not false" is not an actual intermediate truth value, merely a potential truth value. If we take as an axiom that statements that are not false are true (double-negation elimination) then we can derive LEM. Nonetheless, "not false" is a wonderful truth value to assign to the classic paradoxes.
To continue to be pithy, and to paraphrase a category theorist, "not false" is something that we see from the outside, but it isn't visible from the inside, and Gödel's theorems are all about encoding things into the inside.
Suppose, indeed, that we write out the Gödel statement G in some formalized English, as "This statement is true and unprovable within Formal English." Can G be true? Yeah, sure, it's true in the integers, but not in a way that Formal English can show. (That's the incompleteness!) Can G be false? Meh, yes, but it gets nasty, because G is true in the integers, so ~G leads to a non-standard model. Could G be not false? Surprisingly, yes!
I wonder whether this is the line of thought that led Bishop to his terminology.
Note that there are camps that have been disputing this (e.g. McCullough’s Objection):
http://www.deepideas.net/godels-incompleteness-theorem-and-i...
and
https://www.iep.utm.edu/lp-argue/#H3
sadly, I'm not even close to figuring out if the Roger-Penrose argument is valid. Nada, not even a gut-feeling!