I notice I am confused about Godel’s theorem, and I’m hoping there are enough mathematically minded folks here to unconfuse me. :-)
My recollection from my undergraduate days is that Godel’s theorem states that given any sufficiently powerful formal system (i.e. one powerful to encode Peano arithmetic) there are statements that can be made in that system that can neither be proven true nor proven false. I.e. the system is either incomplete or inconsistent, and generally incomplete is what seems to happen.
Here’s what confused me: I’ve noticed several recent sources stating Godel’s theorem as “no consistent system of axioms whose theorems can be listed by an “effective procedure” (e.g., a computer program, but it could be any sort of algorithm) is capable of proving all truths about the relations of the natural numbers (arithmetic). For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system.” (from Wikipedia). I.e. it’s not just that there are statements that can’t be proven, but true statements that can’t be proven. I am confused about what it means to call a mathematical statement “true” if it can’t be proven.
In particular, my recollection was that when you encountered such an unprovable statement you could add either the statement or its negation to your axioms and continue, much as with the parallel postulate in geometry. These results weren’t true or false. They were undecidable.
What am I missing? What does it mean in pure mathematics to say a statement is “true” if we can’t prove it?
These are natural mathematical equivalents of the Godel “true but undecidable” sentence. They can be proved in a larger system which is generally accepted as a valid form of reasoning, but are undecidable in a more limited system such as Peano Arithmetic.
I notice I am confused about Godel’s theorem, and I’m hoping there are enough mathematically minded folks here to unconfuse me. :-)
My recollection from my undergraduate days is that Godel’s theorem states that given any sufficiently powerful formal system (i.e. one powerful to encode Peano arithmetic) there are statements that can be made in that system that can neither be proven true nor proven false. I.e. the system is either incomplete or inconsistent, and generally incomplete is what seems to happen.
Here’s what confused me: I’ve noticed several recent sources stating Godel’s theorem as “no consistent system of axioms whose theorems can be listed by an “effective procedure” (e.g., a computer program, but it could be any sort of algorithm) is capable of proving all truths about the relations of the natural numbers (arithmetic). For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system.” (from Wikipedia). I.e. it’s not just that there are statements that can’t be proven, but true statements that can’t be proven. I am confused about what it means to call a mathematical statement “true” if it can’t be proven.
In particular, my recollection was that when you encountered such an unprovable statement you could add either the statement or its negation to your axioms and continue, much as with the parallel postulate in geometry. These results weren’t true or false. They were undecidable.
What am I missing? What does it mean in pure mathematics to say a statement is “true” if we can’t prove it?
This might be helpful.