5 ms·

What are your opinions of all the theorems that rely on RH as an excluded middle? Constructivists reject exmid, saying instead that a proof of "A or B" require

by cvoss 2y ago

What are your opinions of all the theorems that rely on RH as an excluded middle? Constructivists reject exmid, saying instead that a proof of "A or B" requires you to have in hand a proof of A or a proof of B. And nobody yet has a proof of RH nor a proof of ~RH. This is important in so-called incomplete logical systems, where some theorems are neither provable nor disprovable, and, therefore, exmid is an inadmissible axiom.

nerdponx 2y ago
Aren't those sort of different things? I thought the whole point of provability was that it was distinct from truth.
- floxy 2y ago
  How do you know something is true if you don't have a proof? It all depends on you views on the philosophy of mathematics. Are there "true" statements that don't have proofs? Some say yes, there are platonic ideas that are true, even if they aren't provable. Others say, "what does it even mean to say something is true, if there is no proof. What you really have is a conjecture."
  - lisper 2y ago
    There is another possibility: it could be an arbitrary choice, as in the case of the parallel postulate, the axiom of choice, and non-standard models of the Peano axioms.
    - btilly 2y ago
      According to logicians, it always is an arbitrary choice. But we have a second-order notion of what "finite integer" should mean. And within that notion the idea might be false. Here's how that plays out. Suppose that the RH cannot be proved or disproved from ZF. (It turns out that choice cannot matter for all theorems in number theory, so ZF is enough.) That means that there is a model of ZF in which RH is true. Every model of ZF contains a finite calculation for any non-trivial zero of the Riemann function. (The word "finite" is doing some heavy lifting here - it is a second order concept.) That calculation must work out the same in all models. Therefore every finite nontrivial zero has complex part 0.5. Therefore RH is actually true of the standard model of the integers. Therefore every model of ZF where RH is false, is non-standard. The truth of RH is therefore independent of ZF. But it's true in our second order notion of what the integers are.
      - lisper 2y ago
        > The word "finite" is doing some heavy lifting here - it is a second order concept. Sorry, you're going to have to explain that to me. The word "finite" has only one meaning AFAIK and on that definition it is definitely not the case that "every model of ZF contains a finite calculation for any non-trivial zero of the Riemann function." I don't even know what it means for ZF to "contain a calculation." The concept of calculation (at least the one that I'm familiar with) comes from computability theory, not number theory.
        lupire 2y ago
        "finite" means what you think it means: a program that halts. Look at Peano Axioms: https://en.m.wikipedia.org/wiki/Peano_axioms https://en.m.wikipedia.org/wiki/Peano_axioms The Induction axiom allows us to write finite proofs of otherwise infinite facts, like every positive integer has a predecessor. Without it, you'd be stuck with finitism (since only a finite number of numbers can be constructed in finite time, there is only a finite number of numbers.)
        lisper 2y ago
        I think you're confusing PA with computability theory and Turing machines. "Program" is not a thing in PA.
        Tainnor 2y ago
        PA can model Turing Machines and reason about them. I feel like you missed the important link between logic and computability theory.
        btilly 2y ago
        How much explanation do you want? Any consistent first order set of axioms that has a model, has multiple models. In the case of the Peano Axioms, there is one and only one model that we're interested in - the finite integers. All the others we call nonstandard. But there is absolutely no statement in first order logic that can explain what we mean by finite, and why THIS model is what we want, and THAT model should be considered nonstandard. However there is something called second order logic. As https://www.lesswrong.com/posts/3FoMuCLqZggTxoC3S/logical-pinpointing https://www.lesswrong.com/posts/3FoMuCLqZggTxoC3S/logical-pi... correctly says, in second order logic we really can say that something is finite, and mean it. But as https://www.lesswrong.com/posts/SWn4rqdycu83ikfBa/second-order-logic-the-controversy https://www.lesswrong.com/posts/SWn4rqdycu83ikfBa/second-ord... explains, anyone with Constructivist tendencies is going to look at second order logic's definition of finite and call it wordy hogwash. Regardless, we can look at things this way. Given any two models of the same set of axioms, we can try to set up a correspondence between the models. Each may contain some things not in the other. For example a model of PA + (PA is inconsistent) will contain a proof of inconsistency that is not in a standard model of PA. The standard model of PA is simply this, it is a model of PA which is contained in every other model of PA. And so, whether or not two models agree on the Riemann Hypothesis, they will all agree on what the billionth zero is. And the trillionth. And so on for every finite number. Why? Because those are all in the standard model. And everything in the standard model is included in every other.
  - xrisk 2y ago
    Didn’t Gödel show that in most useful logical systems there are true statements that cannot be proved?
    - xavxav 2y ago
      Indeed, the first incompleteness theorem tells us that any logical framework which can express Peano arithmetic must necessarily contain true (resp. false) facts for which no (resp. counter) proof can be given. Sometimes you can prove that no proof exists about a specific sentence (that's what his incompleteness proof does), and I think you could extend this technique to construct sentences where no proof exists of whether it has a proof, etc...
      - Filligree 2y ago
        The latter would be an axiom. A disproof would be a proof that there is no proof, so if you’d proven that no proof exists one way or the other then you’ve proven it can’t be disproven _or_ proven. Which means you’ve hit a branch in mathematics. You can assume it to be either true or false, and you’ll get new results based on that; both branches are equally valid.
        LegionMammal978 2y ago
        Constructively speaking, a disproof is a "proof that a statement leads to a contradiction". A "proof that there is no proof (assuming consistency)" can exist just fine, and that's exactly what the incompleteness theorem is, alongside a "proof that there is no disproof, i.e., that a contradiction cannot be derived from the statement (assuming consistency)".
      - strbean 2y ago
        > any logical framework which can express Peano arithmetic (with a finite list of axioms)
        jrvidal 2y ago
        I think the precise pre-condition is that the theory should be recursive, which means either a finite list of axioms _or_ a computable check to determine whether a given formula is an axiom.
  - lupire 2y ago
    Probability is relative to an axiom systems. A more powerful system can prove statements that are true but not provable in a weaker system. For example "This sentence is not provable." (Godel's statement, written informally) is true, but not provable, in first order arithmetic logic. https://en.m.wikipedia.org/wiki/Diagonal_lemma https://en.m.wikipedia.org/wiki/Diagonal_lemma In constructivist mathematics, proving that a statement is not false is not a proof that it is true. Non-constructivist mathematics, on the other hand, has the axiom, for all P: P or not-P, also stated as not-not-P implies P.
- alex_smart 2y ago
  Not according to constructivists.
- zajio1am 2y ago
  The whole point of provability is that it is purely syntactic process that could be verified in finite time. Ideally it would be the same as truth, but there are some caveats.
riemann12 2y ago
I’ve heard this argument: If RH is unprovable one way or another, then certainly no counterexample can exist to the RH otherwise you could find it and prove the RH to be false. Hence if RH is unprovable, it must be true. I suppose this uses logic outside the logical system that RH operates in.

by cvoss 2y ago

nerdponx 2y ago

Aren't those sort of different things? I thought the whole point of provability was that it was distinct from truth.

floxy 2y ago
How do you know something is true if you don't have a proof? It all depends on you views on the philosophy of mathematics. Are there "true" statements that don't have proofs? Some say yes, there are platonic ideas that are true, even if they aren't provable. Others say, "what does it even mean to say something is true, if there is no proof. What you really have is a conjecture."
- lisper 2y ago
  There is another possibility: it could be an arbitrary choice, as in the case of the parallel postulate, the axiom of choice, and non-standard models of the Peano axioms.
  - btilly 2y ago
    According to logicians, it always is an arbitrary choice. But we have a second-order notion of what "finite integer" should mean. And within that notion the idea might be false. Here's how that plays out. Suppose that the RH cannot be proved or disproved from ZF. (It turns out that choice cannot matter for all theorems in number theory, so ZF is enough.) That means that there is a model of ZF in which RH is true. Every model of ZF contains a finite calculation for any non-trivial zero of the Riemann function. (The word "finite" is doing some heavy lifting here - it is a second order concept.) That calculation must work out the same in all models. Therefore every finite nontrivial zero has complex part 0.5. Therefore RH is actually true of the standard model of the integers. Therefore every model of ZF where RH is false, is non-standard. The truth of RH is therefore independent of ZF. But it's true in our second order notion of what the integers are.
    - lisper 2y ago
      > The word "finite" is doing some heavy lifting here - it is a second order concept. Sorry, you're going to have to explain that to me. The word "finite" has only one meaning AFAIK and on that definition it is definitely not the case that "every model of ZF contains a finite calculation for any non-trivial zero of the Riemann function." I don't even know what it means for ZF to "contain a calculation." The concept of calculation (at least the one that I'm familiar with) comes from computability theory, not number theory.
      - lupire 2y ago
        "finite" means what you think it means: a program that halts. Look at Peano Axioms: https://en.m.wikipedia.org/wiki/Peano_axioms https://en.m.wikipedia.org/wiki/Peano_axioms The Induction axiom allows us to write finite proofs of otherwise infinite facts, like every positive integer has a predecessor. Without it, you'd be stuck with finitism (since only a finite number of numbers can be constructed in finite time, there is only a finite number of numbers.)
        lisper 2y ago
        I think you're confusing PA with computability theory and Turing machines. "Program" is not a thing in PA.
        Tainnor 2y ago
        PA can model Turing Machines and reason about them. I feel like you missed the important link between logic and computability theory.
      - btilly 2y ago
        How much explanation do you want? Any consistent first order set of axioms that has a model, has multiple models. In the case of the Peano Axioms, there is one and only one model that we're interested in - the finite integers. All the others we call nonstandard. But there is absolutely no statement in first order logic that can explain what we mean by finite, and why THIS model is what we want, and THAT model should be considered nonstandard. However there is something called second order logic. As https://www.lesswrong.com/posts/3FoMuCLqZggTxoC3S/logical-pinpointing https://www.lesswrong.com/posts/3FoMuCLqZggTxoC3S/logical-pi... correctly says, in second order logic we really can say that something is finite, and mean it. But as https://www.lesswrong.com/posts/SWn4rqdycu83ikfBa/second-order-logic-the-controversy https://www.lesswrong.com/posts/SWn4rqdycu83ikfBa/second-ord... explains, anyone with Constructivist tendencies is going to look at second order logic's definition of finite and call it wordy hogwash. Regardless, we can look at things this way. Given any two models of the same set of axioms, we can try to set up a correspondence between the models. Each may contain some things not in the other. For example a model of PA + (PA is inconsistent) will contain a proof of inconsistency that is not in a standard model of PA. The standard model of PA is simply this, it is a model of PA which is contained in every other model of PA. And so, whether or not two models agree on the Riemann Hypothesis, they will all agree on what the billionth zero is. And the trillionth. And so on for every finite number. Why? Because those are all in the standard model. And everything in the standard model is included in every other.
- xrisk 2y ago
  Didn’t Gödel show that in most useful logical systems there are true statements that cannot be proved?
  - xavxav 2y ago
    Indeed, the first incompleteness theorem tells us that any logical framework which can express Peano arithmetic must necessarily contain true (resp. false) facts for which no (resp. counter) proof can be given. Sometimes you can prove that no proof exists about a specific sentence (that's what his incompleteness proof does), and I think you could extend this technique to construct sentences where no proof exists of whether it has a proof, etc...
    - Filligree 2y ago
      The latter would be an axiom. A disproof would be a proof that there is no proof, so if you’d proven that no proof exists one way or the other then you’ve proven it can’t be disproven _or_ proven. Which means you’ve hit a branch in mathematics. You can assume it to be either true or false, and you’ll get new results based on that; both branches are equally valid.
      - LegionMammal978 2y ago
        Constructively speaking, a disproof is a "proof that a statement leads to a contradiction". A "proof that there is no proof (assuming consistency)" can exist just fine, and that's exactly what the incompleteness theorem is, alongside a "proof that there is no disproof, i.e., that a contradiction cannot be derived from the statement (assuming consistency)".
    - strbean 2y ago
      > any logical framework which can express Peano arithmetic (with a finite list of axioms)
      - jrvidal 2y ago
        I think the precise pre-condition is that the theory should be recursive, which means either a finite list of axioms _or_ a computable check to determine whether a given formula is an axiom.
- lupire 2y ago
  Probability is relative to an axiom systems. A more powerful system can prove statements that are true but not provable in a weaker system. For example "This sentence is not provable." (Godel's statement, written informally) is true, but not provable, in first order arithmetic logic. https://en.m.wikipedia.org/wiki/Diagonal_lemma https://en.m.wikipedia.org/wiki/Diagonal_lemma In constructivist mathematics, proving that a statement is not false is not a proof that it is true. Non-constructivist mathematics, on the other hand, has the axiom, for all P: P or not-P, also stated as not-not-P implies P.
alex_smart 2y ago
Not according to constructivists.
zajio1am 2y ago
The whole point of provability is that it is purely syntactic process that could be verified in finite time. Ideally it would be the same as truth, but there are some caveats.

riemann12 2y ago

I’ve heard this argument: If RH is unprovable one way or another, then certainly no counterexample can exist to the RH otherwise you could find it and prove the RH to be false. Hence if RH is unprovable, it must be true. I suppose this uses logic outside the logical system that RH operates in.