4 ms·

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 w

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.
  - kubanczyk 4y ago
    > if all swans in the given universe ARE white, and you have no way of inspecting every one, you can never PROVE Yes, you can. Math is not physics. Pythagoras was able to prove his theorem about every triangle in the universe without inspecting every triangle in the universe. The trick is that "the universe" is not the physical universe, it's just a choice of axioms.
    - trashtester 4y ago
      > Pythagoras was able to prove his theorem about every triangle in the universe without inspecting every triangle in the universe. My understanding is that statements about members of infinite sets can be decidable if there exists a method to set up use recoursion/induction to cover all of them. For the set of right triangles, this is relatively straight forward (if we ignore the complexity introduced by real numbers). For statements on infinite sets where it is not possible to reduce a proof to such recoursion/induction, you quickly end up needing an infinite number of steps to cover all cases, meaning the problem is undeciable/uncomputable. See the Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
trashtester 4y ago
> 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!). Lets hypothetize that Goldbach's conjecture is true and unprovable (let's call it S1). In that case, the following statments are both true: C1) It is impossible to prove S1. C2) It is impossible to prove the converse of S1. (since in this case S1 is true, the converse is actually false, so cannot be proven). Now, if we go into meta-proofs, we may be able to prove C1 (whether or not S1 is true). But we will never be able to prove C2 (if S1 is true and unprovable, C2 will also be true and unprovable). Now, if S1 is actually false, We may actually at some point find a proof of that. But that's not really so interesting. The interesting part is that there DOES exist statements like this that ARE true AND unprovable (even if we don't know which statments), we just don't know WHAT statments those are.

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.
- kubanczyk 4y ago
  > if all swans in the given universe ARE white, and you have no way of inspecting every one, you can never PROVE Yes, you can. Math is not physics. Pythagoras was able to prove his theorem about every triangle in the universe without inspecting every triangle in the universe. The trick is that "the universe" is not the physical universe, it's just a choice of axioms.
  - trashtester 4y ago
    > Pythagoras was able to prove his theorem about every triangle in the universe without inspecting every triangle in the universe. My understanding is that statements about members of infinite sets can be decidable if there exists a method to set up use recoursion/induction to cover all of them. For the set of right triangles, this is relatively straight forward (if we ignore the complexity introduced by real numbers). For statements on infinite sets where it is not possible to reduce a proof to such recoursion/induction, you quickly end up needing an infinite number of steps to cover all cases, meaning the problem is undeciable/uncomputable. See the Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

trashtester 4y ago

> 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!). Lets hypothetize that Goldbach's conjecture is true and unprovable (let's call it S1). In that case, the following statments are both true: C1) It is impossible to prove S1. C2) It is impossible to prove the converse of S1. (since in this case S1 is true, the converse is actually false, so cannot be proven). Now, if we go into meta-proofs, we may be able to prove C1 (whether or not S1 is true). But we will never be able to prove C2 (if S1 is true and unprovable, C2 will also be true and unprovable). Now, if S1 is actually false, We may actually at some point find a proof of that. But that's not really so interesting. The interesting part is that there DOES exist statements like this that ARE true AND unprovable (even if we don't know which statments), we just don't know WHAT statments those are.