4 ms·

> 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

by 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.
- lisper 2y ago
  Thanks, that was very helpful. One question though: > there is absolutely no statement in first order logic that can explain what we mean by finite That seems implausible. All natural numbers are finite. I can easily express that in F.O.L.
  - btilly 2y ago
    Well, you can define something meaning "finite" in first order logic. It just won't mean what we want it to mean. Take your example. "All natural numbers are finite." How do we define the natural numbers in first order logic? Let's use PA. Now take a nonstandard model of PA in which you can prove that PA is inconsistent. You will have a "proof" in that model that PA is inconsistent. That "proof" has a length. In that model, that "proof" will be of "finite" length. There is no contradiction here...but only because that "proof" is (from our point of view) infinitely long. So the proof can go wrong even though it goes wrong at no step. From my point of view, first order logic captures the idea of "finite" as well (or poorly) as classical mathematics captures the idea of "exists". And second order logic requires accepting the truth of unprovable things. But if you're willing to accept the truth of unprovable things, and the existence of non-constructible ones, we get the standard mathematics that mathematicians use without questioning too hard.
    - lisper 2y ago
      > Now take a nonstandard model of PA in which you can prove that PA is inconsistent. Sorry, I lost you there. You don't prove things in models, you prove things in systems. Models are semantic things, proofs are syntactic things, so a "proof in a model" sounds like a category error to me.
      - Tainnor 2y ago
        Proofs are natural numbers via Gödel's encoding, or any other encoding scheme that you'd like (e.g. ASCII). The sentence "PA is inconsistent" can be stated in the language of PA and it means "there is a number that encodes a valid proof from the axioms of PA to a contradiction (e.g. 0 ≠ 0)". This sentence is either true in all models of PA (in which case PA would be inconsistent, which we don't think it is), or it is true in some models and false in others - it can't be false in all models because otherwise, by completeness, there'd be a proof of PA's consistency in PA which is what the second incompleteness theorem rules out. The reason why this is not a category error is because of the self-referentiality of strong enough systems of logic.

by lisper 2y ago

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.

lisper 2y ago
Thanks, that was very helpful. One question though: > there is absolutely no statement in first order logic that can explain what we mean by finite That seems implausible. All natural numbers are finite. I can easily express that in F.O.L.
- btilly 2y ago
  Well, you can define something meaning "finite" in first order logic. It just won't mean what we want it to mean. Take your example. "All natural numbers are finite." How do we define the natural numbers in first order logic? Let's use PA. Now take a nonstandard model of PA in which you can prove that PA is inconsistent. You will have a "proof" in that model that PA is inconsistent. That "proof" has a length. In that model, that "proof" will be of "finite" length. There is no contradiction here...but only because that "proof" is (from our point of view) infinitely long. So the proof can go wrong even though it goes wrong at no step. From my point of view, first order logic captures the idea of "finite" as well (or poorly) as classical mathematics captures the idea of "exists". And second order logic requires accepting the truth of unprovable things. But if you're willing to accept the truth of unprovable things, and the existence of non-constructible ones, we get the standard mathematics that mathematicians use without questioning too hard.
  - lisper 2y ago
    > Now take a nonstandard model of PA in which you can prove that PA is inconsistent. Sorry, I lost you there. You don't prove things in models, you prove things in systems. Models are semantic things, proofs are syntactic things, so a "proof in a model" sounds like a category error to me.
    - Tainnor 2y ago
      Proofs are natural numbers via Gödel's encoding, or any other encoding scheme that you'd like (e.g. ASCII). The sentence "PA is inconsistent" can be stated in the language of PA and it means "there is a number that encodes a valid proof from the axioms of PA to a contradiction (e.g. 0 ≠ 0)". This sentence is either true in all models of PA (in which case PA would be inconsistent, which we don't think it is), or it is true in some models and false in others - it can't be false in all models because otherwise, by completeness, there'd be a proof of PA's consistency in PA which is what the second incompleteness theorem rules out. The reason why this is not a category error is because of the self-referentiality of strong enough systems of logic.