6 ms·

So the problem with logic and in particular model theory is that you always have to assume some sort of logic for the world where your models live in (a meta-lo

So the problem with logic and in particular model theory is that you always have to assume some sort of logic for the world where your models live in (a meta-logic) - otherwise you can't talk about anything. If you take e.g. ZFC for granted in the world of your models, then you can talk about "the" natural numbers, where every number is finite, as a model of PA. And you can also define non-standard models of PA which include infinite numbers. If you use some other foundation, you can probably also define these models in some way. Now whether these constructions mean anything to you, or capture your intuition about "finiteness" is another thing entirely... The problem is that from within the theory you cannot distinguish between these different models. 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. And in general, it's worse than that. As long as your first-order theory allows for any infinite model, there exist models of that theory of any infinite cardinality (this is the Löwenheim-Skolem theorem). So, in general, first-order logic cannot pin down structures uniquely. (Again, this is assuming ZFC in the world of our models.) This btw also leads to the "Skolem paradox" which states that there are countable models of (first-order) ZFC, even though ZFC says that there exist uncountable sets. But this is only a "paradox" until you realise that "countable" and "uncountable" don't mean the same thing within the model as they do outside of the model.

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

> 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.