7 ms·

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

by 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?
  - quantum_state 4y ago
    Not aware of how to provide one due to constraint of the discrete nature of the language would have been used to describe the example … however, imagine entities that are able to communicate via continuous means … they would be able to … but would we be able to find ways to get it?
  - didericis 4y ago
    Any visual geometric proof. You can build an uncountably infinite set of different sized variations proving the same underlying relationships like this: https://youtu.be/CAkMUdeB06o https://youtu.be/CAkMUdeB06o Whether or not a visual demonstration like that is actually a “proof” is a separate question. It definitely wouldn’t satisfy Hilbert, and doesn’t meet this definition: > A proof of a statement S is a finite sequence of assertions S(1), S(2), … S(n) such that S(n) = S and each S(i) is either an axiom or else follows from one or more of the preceding statements S(1), …, S(i-1) by a direct application of a valid rule of inference. I also don’t know of any visual “proof” like that which can’t be explained much more rigorously and powerfully with a formal set of assertions. But pulling threads like this and really asking what makes a proof a “proof” are some of the deepest questions I think a person can ask. It’s worth doing if only to appreciate what an incredible accomplishment all of the formal set theory work is in unifying and attempting to define meta concepts like “proof” itself.
    - jhanschoo 4y ago
      > You can build an uncountably infinite set of different sized variations proving the same underlying relationships like this For such proofs to be contained in a finite space, the verifying person or machine needs to be able to distinguish between arbitrarily minute differences between proofs.
      - didericis 4y ago
        You don’t need to go through every possible element in that infinite uncountable set to prove that relationship, though. You can create an arbitrary demonstration that you can then manipulate in your head. Once you see that water demonstration you can inuit how that relationship must persist at different sizes. Again, that doesn’t really count as a “proof” by modern standards, but it’s how the ancient greeks thought (they used more than just visual intuition/they also used more rigorous and formal propositions than that water thing, but they were visual and didn’t involve finite sets)
- pfortuny 4y ago
  That is not a “proof” in the statement of Gödel’s theorem. A proof (there) is just a finite number of symbols which happens to have a specifix form (A=>B AND A), where A and B are sentences, which are finite sequences of symbols having a slecific form… Wait, I am telling you a half of what Gödel did to prove his result.
adastra22 4y ago
I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?
- voldacar 4y ago
  >Are there actually interesting properties which are true but can’t be proven? Goodstein's theorem and the Paris-Harrington theorem are some examples of this for ZFC. There are several more, maybe a logician could chime in
- flebron 4y ago
  Well, most interesting properties about computer programs are, in general for all programs, undecidable (https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem). Undecidability is a closely related notion to unprovability (https://en.wikipedia.org/wiki/Undecidable_problem#Relationship_with_G%C3%B6del's_incompleteness_theorem) https://en.wikipedia.org/wiki/Undecidable_problem#Relationsh....
- thayne 4y ago
  I don't know if it is quite what you are looking for, but with the normal mathematical axioms, it isn't possible to prove whether or not the there are any sets with a cardinality between the cardinality of the natural numbers and the cardinality of the real numbers. But one of those two must be true, you just can't prove it. Of course you can add a new axiom that allows you to prove one or the other (or accept one of those statements as an axiom), but you will still have other statements that you can't prove.
  - DontchaKnowit 4y ago
    This is super interesting. Was not aware of this. Is there a proof that this is not provable?
    - 4y ago
deleted 4y ago
[deleted]
red_trumpet 4y ago
What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no prove for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"? Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!). >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). Don't we only care about the countable set of statements that can written down in a given logical system? Say second order logic + ZFC.
- gsinclair 4y ago
  > What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no [edited:] proof for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"? By “converse” I think you mean “negation”. A statement being unprovable means we will never know whether it is this or false. > Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!). Nope: demonstrating that (the opposite of Goldbach’s conjecture) is unprovable is logically equivalent to demonstrating that (Goldbach’s conjecture) is unprovable. It means we’ll never know either way.
  - trashtester 4y ago
    > Nope: demonstrating that (the opposite of Goldbach’s conjecture) is unprovable is logically equivalent to demonstrating that (Goldbach’s conjecture) is unprovable. It means we’ll never know either way. I think this is false. If you find a number N that is not the sum of two primes, you did disprove Goldbach's conjecture. Any such number would be smaller than infinity, and so there would only be a finite set of primes smaller it to check for. So basically, if Goldbach's conjecture turns out to be false it IS going to be PROVABLY false. Only if Goldbach's conjecture is actually true will it be the case that it is impossible to prove its negation. But if it is ALSO unprovable (but STILL true) you will NOT be able to prove that the negation is unprovable, because that would mean that there doesn't exist ANY number N that disproves the conjecture, so would prove the unprovable original conjecture.... Consider the statement "All swans are white", but you live in a universe with an infinite number of swans. Lets assume that there exists at least one black swan. Proving the statement false is trivial once you find the first black swan. However, if all swans in the given universe ARE white, and you have no way of inspecting every one, you can never PROVE that they are all white. Also you can NOT prove that it is impossible to prove the negation.

by mreid 4y ago

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?
- quantum_state 4y ago
  Not aware of how to provide one due to constraint of the discrete nature of the language would have been used to describe the example … however, imagine entities that are able to communicate via continuous means … they would be able to … but would we be able to find ways to get it?
- didericis 4y ago
  Any visual geometric proof. You can build an uncountably infinite set of different sized variations proving the same underlying relationships like this: https://youtu.be/CAkMUdeB06o https://youtu.be/CAkMUdeB06o Whether or not a visual demonstration like that is actually a “proof” is a separate question. It definitely wouldn’t satisfy Hilbert, and doesn’t meet this definition: > A proof of a statement S is a finite sequence of assertions S(1), S(2), … S(n) such that S(n) = S and each S(i) is either an axiom or else follows from one or more of the preceding statements S(1), …, S(i-1) by a direct application of a valid rule of inference. I also don’t know of any visual “proof” like that which can’t be explained much more rigorously and powerfully with a formal set of assertions. But pulling threads like this and really asking what makes a proof a “proof” are some of the deepest questions I think a person can ask. It’s worth doing if only to appreciate what an incredible accomplishment all of the formal set theory work is in unifying and attempting to define meta concepts like “proof” itself.
  - jhanschoo 4y ago
    > You can build an uncountably infinite set of different sized variations proving the same underlying relationships like this For such proofs to be contained in a finite space, the verifying person or machine needs to be able to distinguish between arbitrarily minute differences between proofs.
    - didericis 4y ago
      You don’t need to go through every possible element in that infinite uncountable set to prove that relationship, though. You can create an arbitrary demonstration that you can then manipulate in your head. Once you see that water demonstration you can inuit how that relationship must persist at different sizes. Again, that doesn’t really count as a “proof” by modern standards, but it’s how the ancient greeks thought (they used more than just visual intuition/they also used more rigorous and formal propositions than that water thing, but they were visual and didn’t involve finite sets)
pfortuny 4y ago
That is not a “proof” in the statement of Gödel’s theorem. A proof (there) is just a finite number of symbols which happens to have a specifix form (A=>B AND A), where A and B are sentences, which are finite sequences of symbols having a slecific form… Wait, I am telling you a half of what Gödel did to prove his result.

adastra22 4y ago

I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?

voldacar 4y ago
>Are there actually interesting properties which are true but can’t be proven? Goodstein's theorem and the Paris-Harrington theorem are some examples of this for ZFC. There are several more, maybe a logician could chime in
flebron 4y ago
Well, most interesting properties about computer programs are, in general for all programs, undecidable (https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem). Undecidability is a closely related notion to unprovability (https://en.wikipedia.org/wiki/Undecidable_problem#Relationship_with_G%C3%B6del's_incompleteness_theorem) https://en.wikipedia.org/wiki/Undecidable_problem#Relationsh....
thayne 4y ago
I don't know if it is quite what you are looking for, but with the normal mathematical axioms, it isn't possible to prove whether or not the there are any sets with a cardinality between the cardinality of the natural numbers and the cardinality of the real numbers. But one of those two must be true, you just can't prove it. Of course you can add a new axiom that allows you to prove one or the other (or accept one of those statements as an axiom), but you will still have other statements that you can't prove.
- DontchaKnowit 4y ago
  This is super interesting. Was not aware of this. Is there a proof that this is not provable?
  - 4y ago

deleted 4y ago

[deleted]

red_trumpet 4y ago

What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no prove for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"? Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!). >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). Don't we only care about the countable set of statements that can written down in a given logical system? Say second order logic + ZFC.

gsinclair 4y ago
> What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no [edited:] proof for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"? By “converse” I think you mean “negation”. A statement being unprovable means we will never know whether it is this or false. > Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!). Nope: demonstrating that (the opposite of Goldbach’s conjecture) is unprovable is logically equivalent to demonstrating that (Goldbach’s conjecture) is unprovable. It means we’ll never know either way.
- trashtester 4y ago
  > Nope: demonstrating that (the opposite of Goldbach’s conjecture) is unprovable is logically equivalent to demonstrating that (Goldbach’s conjecture) is unprovable. It means we’ll never know either way. I think this is false. If you find a number N that is not the sum of two primes, you did disprove Goldbach's conjecture. Any such number would be smaller than infinity, and so there would only be a finite set of primes smaller it to check for. So basically, if Goldbach's conjecture turns out to be false it IS going to be PROVABLY false. Only if Goldbach's conjecture is actually true will it be the case that it is impossible to prove its negation. But if it is ALSO unprovable (but STILL true) you will NOT be able to prove that the negation is unprovable, because that would mean that there doesn't exist ANY number N that disproves the conjecture, so would prove the unprovable original conjecture.... Consider the statement "All swans are white", but you live in a universe with an infinite number of swans. Lets assume that there exists at least one black swan. Proving the statement false is trivial once you find the first black swan. However, if all swans in the given universe ARE white, and you have no way of inspecting every one, you can never PROVE that they are all white. Also you can NOT prove that it is impossible to prove the negation.