13 ms·

How can a statement that is unprovable be true? I always had the impression that unprovable means you could add either the statement or its negation as an axio

How can a statement that is unprovable be true? I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with

Twisol 4y ago
Good question! In this context, we're relating a system of proofs to the properties of a desired model. If you start from a sufficiently expressive model and try to design a proof system where valid proofs correspond to true properties, then you will either miss some properties (an unproveable truth) or you will have too many proofs (proveable falsehoods). Without biasing for a particular model, we could simply say that every sufficiently expressive proof system admits either zero models or more than one model.
fao_ 4y ago
Without a telescope I can't prove to you that andromeda is a galaxy, but it is.
- frimsah 4y ago
  following this analogy: is it possible with the proper instrumentation, or axioms, that a mathematical statement might become provable?
  - schoen 4y ago
    Yes, you can add more axioms and produce a more powerful system which can resolve more questions. In some cases you actually have a choice about whether to assume that something is true or that it's false (for example you can assume the continuum hypothesis or its negation!), and neither choice on its own produces an inconsistency, but either choice makes a different set of conclusions provable. However, Gödel made explicit in the very first statement of his incompleteness theorem that assuming more axioms cannot ever eliminate incompleteness (except by the extremely undesirable event of eliminating consistency). Gödel shows that, if a set of axioms (including additional axioms on top of your original set) doesn't allow you to prove everything (by virtue of being inconsistent, something called the "principle of explosion"), then there are necessarily statements that those axioms can't resolve the truth of. So you can add more axioms and that will either make your system more powerful or inconsistent (depending on whether you chose inconsistent axioms to add), but you still can't get rid of the incompleteness phenomenon that way!
black_knight 4y ago
> How can a statement that is unprovable be true? If you are a platonist and believe in some preferred model where every statement is decided this makes perfect sense. For the rest of us, this just means that in a sufficiently complex system there will be undecided statements. Which is not such a big surprise – but a rather awesome technical exercise!
- trashtester 4y ago
  Undecided is not quite the same as true. My understanding is that there can be statements that are necessarily true within a given set of axioms, but still unprovable using a proof of limited length.
  - black_knight 4y ago
    Not sure what you are thinking of here. In first order logic if something is true in all models it is also provable. This is called completeness. And is one of the sanity requirements of a semantics.
    - trashtester 4y ago
      I was thinking that something could be true and undecidable (as for the halting problem). I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model. For instance, there may be statements acting on infinite sets (such as N) that may not be compressed into a recoursive formulation, which means that a proof of the valididity of the statement (if it is true) would require an infinite number of steps.
      - black_knight 4y ago
        > I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model. The term "standard model" is interesting, because it pushes the problem a bit. So, let us take the natural numbers. Sure, we can prove in set theory that some of the undecided statements of Peano arithmetic are true for the standard model. But seen from the outside this means that we have changed our axiomatic system from Peano arithmetic to set theory. But there are still undecided statements – even arithmetic ones – in this new system! These will hold in some models of set theory, while being false in some other. So, saying “Oh, I mean the standard ℕ, not any of those other ones” does not get us off the hook, because it raises the question: “The standard ℕ... in which model of ZF?”
x3n0ph3n3 4y ago
Because as soon as you have a system that includes that new axiom, _new_ true statements can be created that are not provable. It's true for every formal system with any finite number of axioms.
gerdesj 4y ago
"This statement is false". GEB is a marvellous work that is accessible to anyone with reasonably good school grade maths. I chanced upon it by accident in the school library one day and was hooked after a few pages. Anyway the crux of the matter is that you can very carefully construct a statement about a system that can't be either proven or disproven by that system! I don't have anything like the formal knowledge to really get to grips with it and the discussions on infinities and so on are pretty mind blowing. However, you feel that DH is imparting glimpses into the sheer beauty of the ideas he covers. Wait 'til you discover what ricercar and quining is all about - bloody lovely. Just read it but take your time. There is something in there for everyone. You often get told by clever people about the links between maths, music and art. Mr H easily gives the best argument I've ever seen that attests to that being true, whilst giving your brain a right good kicking. There was a Dutchman, a German and an Austrian who walked into a book ...
- alimov 4y ago
  Read it over the course of a couple months during my commute, my back hurt but as you said it was marvelous.
- Kranar 4y ago
  >"This statement is false". Close but not quite as that's an inconsistent statement. "This statement is unprovable." is the approach Godel takes and eliminates the inconsistency. Either that statement is true, in which case it's unprovable, or it's false in which case there exists a proof of a false statement.
  - gerdesj 4y ago
    It obeys all the "laws" (OK vagaries) of English grammar. There is nothing in the rules of grammar that requires a statement in English to actually be self-consistent. The problem only surfaces once you attach the associated meanings to the various components. I just picked a classic to start off my prior comment which morphed more into praise for GEB than Goedel's brain breaker. I have dim memories of a cracking constructive argument starting off with some very basic axioms where one was written as S, and two as SS and so on, then it all went a bit mad but the genius of Hofstadter is to make all that impenetrable palava nigh on accessible to the layman (with a bit of effort from the reader). The horrendous thing about Goedel is that the final flourish is clearly correct (I assume that responsible adults have filled in the formal bits, I'm sticking to the lies to children version). It is both terrifying and perhaps obvious at the same time. I can imagine the sense of dread when mighty edifices such as Herr Hilbert's suddenly looked a bit shady and then anger, followed by disbelief and finally acceptance as the big hitters really got to grips with it. The world hasn't come to an end because of Goedel but it certainly got a bit more interesting. I think that it is almost comforting that we have a system that can be complicated enough be to capable of saying things about itself that can't be proven within itself. I think that there is a good chance that our system of mathematics will eventually become complicated enough and no more. Obviously there will always be spherical cows and some absolutely mad numbers and when I say eventually - that will take forever (nearly).
scrame 4y ago
The caveat is that it's a rule of _formal systems_. Any formal system that can represent multiplication can be shown to have unreachable truths or provable falsities.
pvarangot 4y ago
So "famous" undecidable statements, which is what you mention, are an example of statements that strongly opinionated people believe enough that are probably true but unprovable. You are probably familiar with the Continuum Hypothesis or the Axiom of Choice, the latter being so "probably true" in the model that the axioms for set theory try to capture that it's usually added as another axiom. Kruskal's tree theorem is a more interesting example, you should look into that. You can prove it undecidable, so you can add either it or it's negation like you say, in Peano's arithmetic, but you can prove it ZFC or I think even less expressive axiomatic systems for set theory.
bedman12345 4y ago
True, but if you add too many axioms, the resulting set of axioms will not be computable anymore. If you allow your set of axioms to not be computable you can of course just use the set of statements that are true for whatever model of the natural numbers you have in mind. The whole point is that it's not possible to write down any sensible definition of what natural numbers are supposed to be.
shagie 4y ago
Veritasium - Math's Fundamental Flaw https://youtu.be/HeQX2HjkcNo https://youtu.be/HeQX2HjkcNo At 13:46 it gets into the "is there a way to prove every complete statement?" and furthermore goes into the Godel math for "there is no proof for the statement with Gödel number g" where that statement itself has a number "g". The entire video is a good watch though. And the related problem is that with Godel we don't know if math is consistent either.
mreid 4y ago
It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integers. A *proof* of Goldbach's conjecture consists of a finite number of formal reasoning steps that start with some axioms and end up at the statement of the result. To this day, it seems as though Goldbach's conjecture is true. It holds for every number we've been able to test. However, no one has proved it is true or false yet (or proved that it is unprovable). The proof of Gödel's result's involves very carefully formalizing what statements and proofs mean so that they can be encoded as statements about arithmetic. He then shows there is a statement with encoding G that says "The statement with encoding G cannot be proved" – if it is true, then it cannot be proved. It's kind of confusing at first, but there is an easier way to get an intuition why there might be true statements that cannot be proved. Think of each statement about the natural numbers as a subset where each number in the subset makes the statement true. There are uncountably many subsets of the natural numbers (by Cantor's diagonalization argument). Proofs are finite chains of finite statements so there are only countably infinitely many of these. Therefore there must be subsets/statements that are true that do not have a matching proof. The approach that Gödel's proof takes is not too different to the above argument – it is essentially a diagonalization argument – the complexity is in making the encoding of statements are numbers very precise.
- quantum_state 4y ago
  what if the proofs cannot be described as finite or countable sets that does not render a straightforward application of diagonalization? What happens to Goedel’s theorem then?
  - teawrecks 4y ago
    What's an example of an uncountably infinite proof?
    - 4y ago
jcranmer 4y ago
I'll explain it in a different way than normal. We can define a notion of complexity for any given integer as being the size of the smallest program that returns that integer. Obviously, I'm being imprecise here, but it should hopefully be clear that it is possible to get the details right and the precise nature of those details aren't going to be relevant for what follows. Now suppose we have a program that can find the complexity of a given integer. Then, we can write the following program: for (i = 0; ; i++) { if (complexity(i) > 2*K) { return i; } } (where K is the size of this program). Now we have a contradiction: we've constructed a program of size K that computes an integer i, but the smallest program that can do so is of size 2*K. This means that one of our assumptions is wrong, and the only one that can be wrong is that we could write a program that computes complexity. As a result, we have some integer that has a complexity--it's still well-defined (at least if you have the axiom of choice, but I'm not sure if that axiom is necessary)--but we can't necessarily prove that any integer has a given complexity.
- btilly 4y ago
  Any statement that can be made from the Peano axioms that is provable in ZFC is provable in ZF without C. So the axiom of choice should be irrelevant. However we can write a program that does a brute force search through all proofs from ZF looking for the complexity of i. As you just showed, this program will not establish the complexity of all integers. But how does it fail? It fails because there are programs which do not halt, that it can't prove don't halt, which if they halted COULD return i. And therefore the complexity cannot be determined from ZF. The prevailing philosophy of mathematics says it is well-defined. But there are alternate (entirely consistent!) philosophies under which complexity is not well-defined at all.
- erodommoc 4y ago
  I feel like I'm missing something here - wouldn't the shortest program that returns the integer i just be "return i"? The length of that seems pretty easy to compute.
bo1024 4y ago
Oof @ many of these answers. The reason is that there are multiple "models" of the natural numbers that satisfy the axioms, and the statement is true in the usual model that we all know, but in some other models the statement is false. See https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Truth_of_the_G%C3%B6del_sentence https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... and https://en.wikipedia.org/wiki/Peano_axioms#Nonstandard_models https://en.wikipedia.org/wiki/Peano_axioms#Nonstandard_model... Godel's "completeness" theorem gives a converse. If the statement were true about all possible models, then it would be provable.
- cruegge 4y ago
  That's a good intuition for first order PA, where the completeness theorem holds, but not the full story either. PA in second order logic only has a single model, but is still incomplete: there are statements that are true in the only model, but not provable.
  - bedman12345 4y ago
    Yeah but second order logic itself is incomplete. ZFC doesn't have a single model, too, btw. In the end unprovable sentences exist because there are multiple models satisfying your axioms.
    - cruegge 4y ago
      What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in more general conditions. Concerning multiple models of ZFC: I'm always confused by such statements about the foundations of set theory itself, they seem weirdly self-referential. ZFC certainly can't prove that it has multiple (or even any) models. Does such a statement need additional axioms, or is there a general theorem like "If a first order theory has any model, then it has multiple ones."?
      - bedman12345 4y ago

Twisol 4y ago

Good question! In this context, we're relating a system of proofs to the properties of a desired model. If you start from a sufficiently expressive model and try to design a proof system where valid proofs correspond to true properties, then you will either miss some properties (an unproveable truth) or you will have too many proofs (proveable falsehoods). Without biasing for a particular model, we could simply say that every sufficiently expressive proof system admits either zero models or more than one model.

fao_ 4y ago

Without a telescope I can't prove to you that andromeda is a galaxy, but it is.

frimsah 4y ago
following this analogy: is it possible with the proper instrumentation, or axioms, that a mathematical statement might become provable?
- schoen 4y ago
  Yes, you can add more axioms and produce a more powerful system which can resolve more questions. In some cases you actually have a choice about whether to assume that something is true or that it's false (for example you can assume the continuum hypothesis or its negation!), and neither choice on its own produces an inconsistency, but either choice makes a different set of conclusions provable. However, Gödel made explicit in the very first statement of his incompleteness theorem that assuming more axioms cannot ever eliminate incompleteness (except by the extremely undesirable event of eliminating consistency). Gödel shows that, if a set of axioms (including additional axioms on top of your original set) doesn't allow you to prove everything (by virtue of being inconsistent, something called the "principle of explosion"), then there are necessarily statements that those axioms can't resolve the truth of. So you can add more axioms and that will either make your system more powerful or inconsistent (depending on whether you chose inconsistent axioms to add), but you still can't get rid of the incompleteness phenomenon that way!

black_knight 4y ago

> How can a statement that is unprovable be true? If you are a platonist and believe in some preferred model where every statement is decided this makes perfect sense. For the rest of us, this just means that in a sufficiently complex system there will be undecided statements. Which is not such a big surprise – but a rather awesome technical exercise!

trashtester 4y ago
Undecided is not quite the same as true. My understanding is that there can be statements that are necessarily true within a given set of axioms, but still unprovable using a proof of limited length.
- black_knight 4y ago
  Not sure what you are thinking of here. In first order logic if something is true in all models it is also provable. This is called completeness. And is one of the sanity requirements of a semantics.
  - trashtester 4y ago
    I was thinking that something could be true and undecidable (as for the halting problem). I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model. For instance, there may be statements acting on infinite sets (such as N) that may not be compressed into a recoursive formulation, which means that a proof of the valididity of the statement (if it is true) would require an infinite number of steps.
    - black_knight 4y ago
      > I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model. The term "standard model" is interesting, because it pushes the problem a bit. So, let us take the natural numbers. Sure, we can prove in set theory that some of the undecided statements of Peano arithmetic are true for the standard model. But seen from the outside this means that we have changed our axiomatic system from Peano arithmetic to set theory. But there are still undecided statements – even arithmetic ones – in this new system! These will hold in some models of set theory, while being false in some other. So, saying “Oh, I mean the standard ℕ, not any of those other ones” does not get us off the hook, because it raises the question: “The standard ℕ... in which model of ZF?”

x3n0ph3n3 4y ago

Because as soon as you have a system that includes that new axiom, _new_ true statements can be created that are not provable. It's true for every formal system with any finite number of axioms.

gerdesj 4y ago

"This statement is false". GEB is a marvellous work that is accessible to anyone with reasonably good school grade maths. I chanced upon it by accident in the school library one day and was hooked after a few pages. Anyway the crux of the matter is that you can very carefully construct a statement about a system that can't be either proven or disproven by that system! I don't have anything like the formal knowledge to really get to grips with it and the discussions on infinities and so on are pretty mind blowing. However, you feel that DH is imparting glimpses into the sheer beauty of the ideas he covers. Wait 'til you discover what ricercar and quining is all about - bloody lovely. Just read it but take your time. There is something in there for everyone. You often get told by clever people about the links between maths, music and art. Mr H easily gives the best argument I've ever seen that attests to that being true, whilst giving your brain a right good kicking. There was a Dutchman, a German and an Austrian who walked into a book ...

alimov 4y ago
Read it over the course of a couple months during my commute, my back hurt but as you said it was marvelous.
Kranar 4y ago
>"This statement is false". Close but not quite as that's an inconsistent statement. "This statement is unprovable." is the approach Godel takes and eliminates the inconsistency. Either that statement is true, in which case it's unprovable, or it's false in which case there exists a proof of a false statement.
- gerdesj 4y ago
  It obeys all the "laws" (OK vagaries) of English grammar. There is nothing in the rules of grammar that requires a statement in English to actually be self-consistent. The problem only surfaces once you attach the associated meanings to the various components. I just picked a classic to start off my prior comment which morphed more into praise for GEB than Goedel's brain breaker. I have dim memories of a cracking constructive argument starting off with some very basic axioms where one was written as S, and two as SS and so on, then it all went a bit mad but the genius of Hofstadter is to make all that impenetrable palava nigh on accessible to the layman (with a bit of effort from the reader). The horrendous thing about Goedel is that the final flourish is clearly correct (I assume that responsible adults have filled in the formal bits, I'm sticking to the lies to children version). It is both terrifying and perhaps obvious at the same time. I can imagine the sense of dread when mighty edifices such as Herr Hilbert's suddenly looked a bit shady and then anger, followed by disbelief and finally acceptance as the big hitters really got to grips with it. The world hasn't come to an end because of Goedel but it certainly got a bit more interesting. I think that it is almost comforting that we have a system that can be complicated enough be to capable of saying things about itself that can't be proven within itself. I think that there is a good chance that our system of mathematics will eventually become complicated enough and no more. Obviously there will always be spherical cows and some absolutely mad numbers and when I say eventually - that will take forever (nearly).

scrame 4y ago

The caveat is that it's a rule of _formal systems_. Any formal system that can represent multiplication can be shown to have unreachable truths or provable falsities.

pvarangot 4y ago

So "famous" undecidable statements, which is what you mention, are an example of statements that strongly opinionated people believe enough that are probably true but unprovable. You are probably familiar with the Continuum Hypothesis or the Axiom of Choice, the latter being so "probably true" in the model that the axioms for set theory try to capture that it's usually added as another axiom. Kruskal's tree theorem is a more interesting example, you should look into that. You can prove it undecidable, so you can add either it or it's negation like you say, in Peano's arithmetic, but you can prove it ZFC or I think even less expressive axiomatic systems for set theory.

bedman12345 4y ago

True, but if you add too many axioms, the resulting set of axioms will not be computable anymore. If you allow your set of axioms to not be computable you can of course just use the set of statements that are true for whatever model of the natural numbers you have in mind. The whole point is that it's not possible to write down any sensible definition of what natural numbers are supposed to be.

shagie 4y ago

Veritasium - Math's Fundamental Flaw https://youtu.be/HeQX2HjkcNo https://youtu.be/HeQX2HjkcNo At 13:46 it gets into the "is there a way to prove every complete statement?" and furthermore goes into the Godel math for "there is no proof for the statement with Gödel number g" where that statement itself has a number "g". The entire video is a good watch though. And the related problem is that with Godel we don't know if math is consistent either.

mreid 4y ago

It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integers. A *proof* of Goldbach's conjecture consists of a finite number of formal reasoning steps that start with some axioms and end up at the statement of the result. To this day, it seems as though Goldbach's conjecture is true. It holds for every number we've been able to test. However, no one has proved it is true or false yet (or proved that it is unprovable). The proof of Gödel's result's involves very carefully formalizing what statements and proofs mean so that they can be encoded as statements about arithmetic. He then shows there is a statement with encoding G that says "The statement with encoding G cannot be proved" – if it is true, then it cannot be proved. It's kind of confusing at first, but there is an easier way to get an intuition why there might be true statements that cannot be proved. Think of each statement about the natural numbers as a subset where each number in the subset makes the statement true. There are uncountably many subsets of the natural numbers (by Cantor's diagonalization argument). Proofs are finite chains of finite statements so there are only countably infinitely many of these. Therefore there must be subsets/statements that are true that do not have a matching proof. The approach that Gödel's proof takes is not too different to the above argument – it is essentially a diagonalization argument – the complexity is in making the encoding of statements are numbers very precise.

quantum_state 4y ago
what if the proofs cannot be described as finite or countable sets that does not render a straightforward application of diagonalization? What happens to Goedel’s theorem then?
- teawrecks 4y ago
  What's an example of an uncountably infinite proof?
  - 4y ago

jcranmer 4y ago

I'll explain it in a different way than normal. We can define a notion of complexity for any given integer as being the size of the smallest program that returns that integer. Obviously, I'm being imprecise here, but it should hopefully be clear that it is possible to get the details right and the precise nature of those details aren't going to be relevant for what follows. Now suppose we have a program that can find the complexity of a given integer. Then, we can write the following program: for (i = 0; ; i++) { if (complexity(i) > 2*K) { return i; } } (where K is the size of this program). Now we have a contradiction: we've constructed a program of size K that computes an integer i, but the smallest program that can do so is of size 2*K. This means that one of our assumptions is wrong, and the only one that can be wrong is that we could write a program that computes complexity. As a result, we have some integer that has a complexity--it's still well-defined (at least if you have the axiom of choice, but I'm not sure if that axiom is necessary)--but we can't necessarily prove that any integer has a given complexity.

btilly 4y ago
Any statement that can be made from the Peano axioms that is provable in ZFC is provable in ZF without C. So the axiom of choice should be irrelevant. However we can write a program that does a brute force search through all proofs from ZF looking for the complexity of i. As you just showed, this program will not establish the complexity of all integers. But how does it fail? It fails because there are programs which do not halt, that it can't prove don't halt, which if they halted COULD return i. And therefore the complexity cannot be determined from ZF. The prevailing philosophy of mathematics says it is well-defined. But there are alternate (entirely consistent!) philosophies under which complexity is not well-defined at all.
erodommoc 4y ago
I feel like I'm missing something here - wouldn't the shortest program that returns the integer i just be "return i"? The length of that seems pretty easy to compute.

bo1024 4y ago

Oof @ many of these answers. The reason is that there are multiple "models" of the natural numbers that satisfy the axioms, and the statement is true in the usual model that we all know, but in some other models the statement is false. See https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Truth_of_the_G%C3%B6del_sentence https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... and https://en.wikipedia.org/wiki/Peano_axioms#Nonstandard_models https://en.wikipedia.org/wiki/Peano_axioms#Nonstandard_model... Godel's "completeness" theorem gives a converse. If the statement were true about all possible models, then it would be provable.

cruegge 4y ago
That's a good intuition for first order PA, where the completeness theorem holds, but not the full story either. PA in second order logic only has a single model, but is still incomplete: there are statements that are true in the only model, but not provable.
- bedman12345 4y ago
  Yeah but second order logic itself is incomplete. ZFC doesn't have a single model, too, btw. In the end unprovable sentences exist because there are multiple models satisfying your axioms.
  - cruegge 4y ago
    What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in more general conditions. Concerning multiple models of ZFC: I'm always confused by such statements about the foundations of set theory itself, they seem weirdly self-referential. ZFC certainly can't prove that it has multiple (or even any) models. Does such a statement need additional axioms, or is there a general theorem like "If a first order theory has any model, then it has multiple ones."?
    - bedman12345 4y ago