5 ms·

> There's no way of defining a predicate "finite" in first-order PA that agrees with the notion of "finite" that you've established in your meta-logic. Why doe

by lisper 2y ago

> There's no way of defining a predicate "finite" in first-order PA that agrees with the notion of "finite" that you've established in your meta-logic. Why doesn't this work? Define the predecessor function P such that P(S(n)) = n for all n (and maybe S(P(n)) = n for all n != 0). FINITE(n) := (n=0) OR FINITE(P(n)) i.e. a number is finite if it is zero or if it predecessor is finite. Why doesn't that work? BTW, as an aside, since you seem to know your stuff I thought I'd ask: I noticed as part of a separate discussion over on /r/math that AFAICT there is nothing in PA that distinguishes successor and predecessor until you get to the definition of multiplication. Is that right? Is it noteworthy?

btilly 2y ago
In any model of PA, all natural numbers will be finite by this definition. Even if we, from outside of the model, know that many of them aren't. You've been presented with two different ways to prove this, and a standard textbook. Perhaps read the textbook? On your aside, in PA there is one element that is not the successor of any other. And it likewise has no predecessor. (It is a matter of convention whether you call that special number 0 or 1.) That special number is always the base case of all induction proofs.
zajio1am 2y ago
You can have an infinite chain of predecessors of non-standard numbers, each claiming being FINITE(). That satisfies your definition. This could be easily demonstrated in Robinson arithmetic, which has simple, understandable non-standard models.
- lisper 2y ago
  > You can have an infinite chain of predecessors of non-standard numbers, each claiming being FINITE(). Ah. That makes sense. Thanks. So surely someone has come up with a system that captures the intuitive spirit of mathematical induction, i.e. that the chain has to actually be rooted at 0 rather than have an infinite chain of predecessors or be a loop? How hard could that be?
  - btilly 2y ago
    How hard could that be? It seems like it should be straightforward. But it's mathematically impossible. Similarly, it seemed to David Hilbert like it should be possible to have a system of formal logic that all could accept, which would prove itself to be consistent. But that also proved to be impossible. And the logic which lead to that being proved impossible is deeply connected to the first line of reasoning that I gave you for why this is also impossible. And in the end what they all come down to is some kind of self-reference. In this case, to have a finite statement define what it means to be finite, we must already know what finite means. Second order logic sort of assumes that we can simply know what finite means. First order logic doesn't allow you to wave your hands like that. You can't cheat in any way. And so you can't find a way to do it.
    - lisper 2y ago
      > Second order logic sort of assumes that we can simply know what finite means. First order logic doesn't allow you to wave your hands like that. OK, this I do not understand. How does 2ndOL "sort of assume that we can simply know what finite means"? That seems like an extraordinarily imprecise characterization of 2ndOL. 2ndOL is a formal system just like 1stOL. Neither one lets you "wave your hands" about anything AFAICT.
      - btilly 2y ago
        Read https://plato.stanford.edu/entries/logic-higher-order/ https://plato.stanford.edu/entries/logic-higher-order/ if you wish. I view the "for all properties" bit as handwaving. See particularly section 6 of that article, which at one point gives: The semantics of second-order logic depending on these hard questions of set theory puts second-order logic into the same “basket” with set theory. Criticism of set theory becomes criticism of second-order logic and vice versa. My Constructivist tendencies are due to my discomfort with accepting the validity of set-theoretic constructions with decisions based on unverifiable truths. Accepting second order logic requires accepting quantifying over similar collections of unverifiable claims. I'm going to be no more sympathetic.
- btilly 2y ago
  Robinson arithmetic is an excellent example here. Using ZFC, Robinson can take a standard model of the reals and construct a nonstandard model, and a function from the standard model to the nonstandard model. Every possible statement of first order logic that can be made about the standard model is true in the nonstandard model. Likewise every possible statement of first order logic that can be made in the nonstandard model only involving things that came from the standard model are also true of the standard model. This is his "transfer principle". However the nonstandard model comes with things like infinitesmals, and infinite numbers. So in the nonstandard world we can really do things like define a derivative as dy/dx, or an integral as an infinite sum. Then recover the classical definitions through the transfer principle. See https://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-management/ https://terrytao.wordpress.com/2007/06/25/ultrafilters-nonst... for an explanation of how this actually works in some detail. But if you get your head around it, you'll see exactly why first order logic cannot possibly capture the idea of being a standard model. Because, in first order logic, the nonstandard model really is indistinguishable. And so finite cannot be expressed in first order logic.
  - zajio1am 2y ago
    Note that i meant https://en.wikipedia.org/wiki/Robinson_arithmetic https://en.wikipedia.org/wiki/Robinson_arithmetic , while you wrote about results from different Robinson: https://en.wikipedia.org/wiki/Nonstandard_analysis https://en.wikipedia.org/wiki/Nonstandard_analysis .
    - btilly 2y ago
      Oops, thank you for the correction! I learned something today. Though I'm sure you can see how I thought that the other Robinson fitted in the conversation,
Tainnor 2y ago
> I noticed as part of a separate discussion over on /r/math that AFAICT there is nothing in PA that distinguishes successor and predecessor until you get to the definition of multiplication. Is that right? Is it noteworthy? I'm not entirely sure what you mean by this. "PA without multiplication" is basically Presburger Arithmetic (https://en.m.wikipedia.org/wiki/Presburger_arithmetic https://en.m.wikipedia.org/wiki/Presburger_arithmetic). One of its axioms (as in PA) is that 0 has no predecessor - but clearly every number, including 0, has a successor. So that's a way of distinguishing predecessor and successor functions. I believe that when you look at nonstandard models (which basically look like N + any number of copies of Z), the order isn't fixed in those copies of Z (unlike N), so you could swap predecessor and succesor within those copies, but I haven't really looked into that all that much.
- lisper 2y ago
  Yeah, that's not quite what I meant. What I was trying to get at was more analogous to the ambiguity of i and -i. Suppose I wanted to create a system of math whose intended model was the negative naturals rather than the positive naturals. Let's call this new system NPA. NPA has the exact same axioms as PA except with predecessor instead of successor as the core axiomatic construct. So zero has a predecessor, but no successor. Everything works as before, except with the letter P instead of the letter S. Addition still works, you're just adding negative numbers and getting negative numbers as the result, which is what you would expect. It doesn't break down until you get to multiplication, where, if you follow the same definition as standard PA you get the "wrong" result because you want the product of two negative numbers to be a positive number, and there are no positive numbers in NPA. So AFAICT multiplication is required to distinguish PA from NPA. Which raises an interesting question: is there a non-trivial operation you can define to distinguish i from -i the way that multiplication allows you to distinguish 1 from -1?
  - btilly 2y ago
    If you start with NPA it is identical as PA. You can apply all the same logic and all the first theorems. The problem with multiplication is not that the proofs fall apart, it is that multiplication does not mean what you want it to mean. When you go to the complex numbers, you have a similar situation. The only thing that distinguishes i from -i is what you want the principal branch of sqrt to be. Otherwise nothing would change if you flip them.

by lisper 2y ago

btilly 2y ago

In any model of PA, all natural numbers will be finite by this definition. Even if we, from outside of the model, know that many of them aren't. You've been presented with two different ways to prove this, and a standard textbook. Perhaps read the textbook? On your aside, in PA there is one element that is not the successor of any other. And it likewise has no predecessor. (It is a matter of convention whether you call that special number 0 or 1.) That special number is always the base case of all induction proofs.

zajio1am 2y ago

You can have an infinite chain of predecessors of non-standard numbers, each claiming being FINITE(). That satisfies your definition. This could be easily demonstrated in Robinson arithmetic, which has simple, understandable non-standard models.

lisper 2y ago
> You can have an infinite chain of predecessors of non-standard numbers, each claiming being FINITE(). Ah. That makes sense. Thanks. So surely someone has come up with a system that captures the intuitive spirit of mathematical induction, i.e. that the chain has to actually be rooted at 0 rather than have an infinite chain of predecessors or be a loop? How hard could that be?
- btilly 2y ago
  How hard could that be? It seems like it should be straightforward. But it's mathematically impossible. Similarly, it seemed to David Hilbert like it should be possible to have a system of formal logic that all could accept, which would prove itself to be consistent. But that also proved to be impossible. And the logic which lead to that being proved impossible is deeply connected to the first line of reasoning that I gave you for why this is also impossible. And in the end what they all come down to is some kind of self-reference. In this case, to have a finite statement define what it means to be finite, we must already know what finite means. Second order logic sort of assumes that we can simply know what finite means. First order logic doesn't allow you to wave your hands like that. You can't cheat in any way. And so you can't find a way to do it.
  - lisper 2y ago
    > Second order logic sort of assumes that we can simply know what finite means. First order logic doesn't allow you to wave your hands like that. OK, this I do not understand. How does 2ndOL "sort of assume that we can simply know what finite means"? That seems like an extraordinarily imprecise characterization of 2ndOL. 2ndOL is a formal system just like 1stOL. Neither one lets you "wave your hands" about anything AFAICT.
    - btilly 2y ago
      Read https://plato.stanford.edu/entries/logic-higher-order/ https://plato.stanford.edu/entries/logic-higher-order/ if you wish. I view the "for all properties" bit as handwaving. See particularly section 6 of that article, which at one point gives: The semantics of second-order logic depending on these hard questions of set theory puts second-order logic into the same “basket” with set theory. Criticism of set theory becomes criticism of second-order logic and vice versa. My Constructivist tendencies are due to my discomfort with accepting the validity of set-theoretic constructions with decisions based on unverifiable truths. Accepting second order logic requires accepting quantifying over similar collections of unverifiable claims. I'm going to be no more sympathetic.
btilly 2y ago
Robinson arithmetic is an excellent example here. Using ZFC, Robinson can take a standard model of the reals and construct a nonstandard model, and a function from the standard model to the nonstandard model. Every possible statement of first order logic that can be made about the standard model is true in the nonstandard model. Likewise every possible statement of first order logic that can be made in the nonstandard model only involving things that came from the standard model are also true of the standard model. This is his "transfer principle". However the nonstandard model comes with things like infinitesmals, and infinite numbers. So in the nonstandard world we can really do things like define a derivative as dy/dx, or an integral as an infinite sum. Then recover the classical definitions through the transfer principle. See https://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-management/ https://terrytao.wordpress.com/2007/06/25/ultrafilters-nonst... for an explanation of how this actually works in some detail. But if you get your head around it, you'll see exactly why first order logic cannot possibly capture the idea of being a standard model. Because, in first order logic, the nonstandard model really is indistinguishable. And so finite cannot be expressed in first order logic.
- zajio1am 2y ago
  Note that i meant https://en.wikipedia.org/wiki/Robinson_arithmetic https://en.wikipedia.org/wiki/Robinson_arithmetic , while you wrote about results from different Robinson: https://en.wikipedia.org/wiki/Nonstandard_analysis https://en.wikipedia.org/wiki/Nonstandard_analysis .
  - btilly 2y ago
    Oops, thank you for the correction! I learned something today. Though I'm sure you can see how I thought that the other Robinson fitted in the conversation,

Tainnor 2y ago

> I noticed as part of a separate discussion over on /r/math that AFAICT there is nothing in PA that distinguishes successor and predecessor until you get to the definition of multiplication. Is that right? Is it noteworthy? I'm not entirely sure what you mean by this. "PA without multiplication" is basically Presburger Arithmetic (https://en.m.wikipedia.org/wiki/Presburger_arithmetic https://en.m.wikipedia.org/wiki/Presburger_arithmetic). One of its axioms (as in PA) is that 0 has no predecessor - but clearly every number, including 0, has a successor. So that's a way of distinguishing predecessor and successor functions. I believe that when you look at nonstandard models (which basically look like N + any number of copies of Z), the order isn't fixed in those copies of Z (unlike N), so you could swap predecessor and succesor within those copies, but I haven't really looked into that all that much.

lisper 2y ago
Yeah, that's not quite what I meant. What I was trying to get at was more analogous to the ambiguity of i and -i. Suppose I wanted to create a system of math whose intended model was the negative naturals rather than the positive naturals. Let's call this new system NPA. NPA has the exact same axioms as PA except with predecessor instead of successor as the core axiomatic construct. So zero has a predecessor, but no successor. Everything works as before, except with the letter P instead of the letter S. Addition still works, you're just adding negative numbers and getting negative numbers as the result, which is what you would expect. It doesn't break down until you get to multiplication, where, if you follow the same definition as standard PA you get the "wrong" result because you want the product of two negative numbers to be a positive number, and there are no positive numbers in NPA. So AFAICT multiplication is required to distinguish PA from NPA. Which raises an interesting question: is there a non-trivial operation you can define to distinguish i from -i the way that multiplication allows you to distinguish 1 from -1?
- btilly 2y ago
  If you start with NPA it is identical as PA. You can apply all the same logic and all the first theorems. The problem with multiplication is not that the proofs fall apart, it is that multiplication does not mean what you want it to mean. When you go to the complex numbers, you have a similar situation. The only thing that distinguishes i from -i is what you want the principal branch of sqrt to be. Otherwise nothing would change if you flip them.