3 ms·

> How exactly did you think "Any system less powerful than PA is trivially incomplete." conveyed any of this? I thought it was understood that the word "incomp

by lisper 4y ago

> How exactly did you think "Any system less powerful than PA is trivially incomplete." conveyed any of this? I thought it was understood that the word "incomplete" in the context of a discussion of Godel's Incompleteness Theorem meant incomplete with respect to the truths of arithmetic, because that is what Godel's Incompleteness Theorem is about. It didn't seem like a huge leap at the time. > You seem to be claiming two almost opposite things about PA. And those two things would be...?

dvt 4y ago
> incomplete with respect to the truths of arithmetic This is not at all what it's about. First of all, "incompleteness" has a very specific meaning in logic, namely that the following conditional (what we call "completeness") does not hold hold for some formal system S: Γ ⊨ φ → Γ ⊢ φ Second of all, Godel's first incompleteness theorem doesn't concern itself with "truths of arithmetic" but about any sufficently-powerful logical formalism. This is why I contend that Godel numbering is actually where the trickery kind of comes in: it's what gives Godel the self-referrentiality he needs in PA. A more general definition of the theorem, and one I generally favor over ones that bring up arithmetic, is[1]: "Any adequate axiomatizable theory is incomplete. In particular the sentence 'This sentence is not provable' is true but not provable in the theory." [1] https://math.hawaii.edu/~dale/godel/godel.html https://math.hawaii.edu/~dale/godel/godel.html
- Tainnor 4y ago
  > This is not at all what it's about. First of all, "incompleteness" has a very specific meaning in logic, namely that the following conditional (what we call "completeness") does not hold hold for some formal system S: > Γ ⊨ φ → Γ ⊢ φ That is, unfortunately, a misunderstanding because the words "(in)completeness" have two very distinct meanings that are both used in logic. One is the completeness of some system of logic, namely what you mentioned: "Γ ⊨ φ → Γ ⊢ φ". That's provably true for fist-order logic (though not for second-order logic), giving rise to Gödel's completeness proof. It remains true when Γ = PA (more specifically, first-order PA). In other words, any truth about numbers that follows from PA has a proof. When we talk about the incompleteness theorems, however, we're talking about the completeness of theories. A theory Γ is said to be complete whenever for all sentences we have either Γ ⊨ φ or Γ ⊨ ¬φ. While there are examples of complete theories (I linked the Wiki article in a comment more up-thread, but it includes simple examples like the theory of dense linear orders sets with endpoints), it is also easy enough to construct a theory that is not complete. In particular (and this follows from the first incompleteness theorem), first-order PA is not complete. What this also implies is that not every true statement about the natural numbers follows from PA, or equivalently, that there are models of PA, i.e. structures in which all axioms of (again, first-order) PA are true, that are nevertheless distinct from the natural numbers because some sentences that are true in the one structure are false in the other. More precisely, the first incompleteness theorem states something like "any effectively axiomatisable theory that is sufficiently strong is incomplete", where "effectively axiomatisable" means that we can determine in finite time whether something is an axiom of that theory, and "sufficiently strong" means something like "can encode every primitive recursive function" (the exact formulation depends a bit, because there are several different "flavours" of the first incompleteness theorem). In particular, it also states that any theory that includes Robinson arithmetic (e.g. PA) is incomplete.
  - lisper 4y ago
    > A theory Γ is said to be complete whenever for all sentences we have either Γ ⊨ φ or Γ ⊨ ¬φ. You mean Γ ⊢ φ or Γ ⊢ ¬φ . But note that what you said is not mutually exclusive with what /u/Tainnor said, i.e. Γ ⊨ φ → Γ ⊢ φ The proof of Godel's theorem is to exhibit a φ for which "Γ ⊢ φ or Γ ⊢ ¬φ" is false. From that you conclude that "Γ ⊨ φ → Γ ⊢ φ" is false on the assumption that "Γ ⊨ φ" is true. But that last part is an informal argument. We believe that "Γ ⊨ G" is true for the Godel sentence G but we (obviously) can't prove it. Indeed, adding ¬G as an axiom to PA produces a consistent system where "Γ ⊢ G" is (trivially) true. The semantics of this system are quite interesting. The semantics of that system say that there exists a Godel number of a proof of G, but no natural number is that number. It is similar to adding axioms like "there exists a number whose successor is zero" or "there exists a number whose square root is the number whose successor is zero", which have obviously been very fruitful extensions of PA.
    - Tainnor 4y ago
      > You mean Γ ⊢ φ or Γ ⊢ ¬φ . In principle no, though it's possible that it's defined like that in certain places, since in first-order logic, that amounts to the same thing (given the completeness theorem). But "completeness" is a notion from model theory that doesn't care about proof systems. In a system where the completeness theorem is not true, such as second-order logic with standard semantics, we do have complete theories (such as second-order PA), where we always have Γ ⊨ φ or Γ ⊨ ¬φ, but that doesn't mean that every statement is either provable or disprovable. > The proof of Godel's theorem is to exhibit a φ for which "Γ ⊢ φ or Γ ⊢ ¬φ" is false. From that you conclude that "Γ ⊨ φ → Γ ⊢ φ" is false on the assumption that "Γ ⊨ φ" is true. But that last part is an informal argument. We believe that "Γ ⊨ G" is true for the Godel sentence G but we (obviously) can't prove it. I think that has it a bit backwards. It's not that we believe that PA ⊨ G - in fact, if we believed that, it would immediately imply PA ⊢ G, when that's exactly what we showed to be impossible. It's that we believe that G is true in the natural numbers, which is not the same thing as being true in PA, and that belief rests in our belief that PA is sound (which we can't prove, but seems reasonable). (There are some different "flavours" of the incompleteness theorems, some of them rely on soundness of PA and others only on it being consistent.) > But note that what you said is not mutually exclusive with what /u/Tainnor said, i.e. That's because that's me. ;)
lmm 4y ago
> I thought it was understood that the word "incomplete" in the context of a discussion of Godel's Incompleteness Theorem meant incomplete with respect to the truths of arithmetic, because that is what Godel's Incompleteness Theorem is about. What does "with respect to the truths of arithmetic" even mean? How is Presburger Arithmetic "incomplete" in this sense? > And those two things would be...? That it's so complex as to be obviously incomplete, but also so simple that anything smaller than it is obviously trivial. There are interesting systems smaller than PA, and none of this is obvious.
- lisper 4y ago
  > What does "with respect to the truths of arithmetic" even mean? It means: with respect to some axiomatization of arithmetic that allows Godel numbers to be constructed. Peano arithmetic, for example. > obviously incomplete I guess that depends on what you consider "obvious". It was far from obvious before Godel proved it. But nowadays it's not hard to understand. One generation's "obvious" is a prior generation's major breakthrough. The big surprise in Godel's theorem is that the amount of complexity you need to introduce into a theory to render it incomplete is quite small. Peano arithmetic is sufficient, but not necessary.
  - lmm 4y ago
    > It means: with respect to some axiomatization of arithmetic that allows Godel numbers to be constructed. That's circular logic; why would that be an interesting question to investigate absent the incompleteness theorem? > The big surprise in Godel's theorem is that the amount of complexity you need to introduce into a theory to render it incomplete is quite small. Agreed, but that implicitly requires understanding that small theories like Presburger Arithmetic are complete (which they are in every usual meaningful sense, but you seem to be claiming otherwise).
    - lisper 4y ago
      > That's circular logic; why would that be an interesting question to investigate absent the incompleteness theorem? Because the amount of logical infrastructure that you need is surprisingly small. All you need is to be able to do basic grade-school arithmetic: add, subtract, multiple, divide, test for equality. And you don't even need all that. You can build everything you need from much simpler primitives. The reason this is not circular is that before Goedel's theorem mathematicians were trying to construct a formal system that would allow you to derive all true statements about not just arithmetic, but all of mathematics. It turns out that this is impossible. As soon as you can do arithmetic, Goedel's theorem applies and you have lost. > that implicitly requires understanding that small theories like Presburger Arithmetic are complete I don't see why. Goedel's theorem matters in the context of trying to reduce all of mathematics to a formal system. Presburger arithmetic fails not because it is syntactically incomplete but because it cannot (for example) do division, so it cannot formulate (for example) the concept of a prime number and so it cannot (for example) prove the fundamental theorem of arithmetic. So yes, PB is decidable, but it is not a plausible candidate for a complete (in the informal sense) formulation of all of mathematics. Goedel's theorem shows that if you can add, subtract, multiply and divide and test for equality, then you have lost. And if you can't do those things, then you have also lost, but you don't need a theorem to tell you that.

by lisper 4y ago

dvt 4y ago

> incomplete with respect to the truths of arithmetic This is not at all what it's about. First of all, "incompleteness" has a very specific meaning in logic, namely that the following conditional (what we call "completeness") does not hold hold for some formal system S: Γ ⊨ φ → Γ ⊢ φ Second of all, Godel's first incompleteness theorem doesn't concern itself with "truths of arithmetic" but about any sufficently-powerful logical formalism. This is why I contend that Godel numbering is actually where the trickery kind of comes in: it's what gives Godel the self-referrentiality he needs in PA. A more general definition of the theorem, and one I generally favor over ones that bring up arithmetic, is[1]: "Any adequate axiomatizable theory is incomplete. In particular the sentence 'This sentence is not provable' is true but not provable in the theory." [1] https://math.hawaii.edu/~dale/godel/godel.html https://math.hawaii.edu/~dale/godel/godel.html

Tainnor 4y ago
> This is not at all what it's about. First of all, "incompleteness" has a very specific meaning in logic, namely that the following conditional (what we call "completeness") does not hold hold for some formal system S: > Γ ⊨ φ → Γ ⊢ φ That is, unfortunately, a misunderstanding because the words "(in)completeness" have two very distinct meanings that are both used in logic. One is the completeness of some system of logic, namely what you mentioned: "Γ ⊨ φ → Γ ⊢ φ". That's provably true for fist-order logic (though not for second-order logic), giving rise to Gödel's completeness proof. It remains true when Γ = PA (more specifically, first-order PA). In other words, any truth about numbers that follows from PA has a proof. When we talk about the incompleteness theorems, however, we're talking about the completeness of theories. A theory Γ is said to be complete whenever for all sentences we have either Γ ⊨ φ or Γ ⊨ ¬φ. While there are examples of complete theories (I linked the Wiki article in a comment more up-thread, but it includes simple examples like the theory of dense linear orders sets with endpoints), it is also easy enough to construct a theory that is not complete. In particular (and this follows from the first incompleteness theorem), first-order PA is not complete. What this also implies is that not every true statement about the natural numbers follows from PA, or equivalently, that there are models of PA, i.e. structures in which all axioms of (again, first-order) PA are true, that are nevertheless distinct from the natural numbers because some sentences that are true in the one structure are false in the other. More precisely, the first incompleteness theorem states something like "any effectively axiomatisable theory that is sufficiently strong is incomplete", where "effectively axiomatisable" means that we can determine in finite time whether something is an axiom of that theory, and "sufficiently strong" means something like "can encode every primitive recursive function" (the exact formulation depends a bit, because there are several different "flavours" of the first incompleteness theorem). In particular, it also states that any theory that includes Robinson arithmetic (e.g. PA) is incomplete.
- lisper 4y ago
  > A theory Γ is said to be complete whenever for all sentences we have either Γ ⊨ φ or Γ ⊨ ¬φ. You mean Γ ⊢ φ or Γ ⊢ ¬φ . But note that what you said is not mutually exclusive with what /u/Tainnor said, i.e. Γ ⊨ φ → Γ ⊢ φ The proof of Godel's theorem is to exhibit a φ for which "Γ ⊢ φ or Γ ⊢ ¬φ" is false. From that you conclude that "Γ ⊨ φ → Γ ⊢ φ" is false on the assumption that "Γ ⊨ φ" is true. But that last part is an informal argument. We believe that "Γ ⊨ G" is true for the Godel sentence G but we (obviously) can't prove it. Indeed, adding ¬G as an axiom to PA produces a consistent system where "Γ ⊢ G" is (trivially) true. The semantics of this system are quite interesting. The semantics of that system say that there exists a Godel number of a proof of G, but no natural number is that number. It is similar to adding axioms like "there exists a number whose successor is zero" or "there exists a number whose square root is the number whose successor is zero", which have obviously been very fruitful extensions of PA.
  - Tainnor 4y ago
    > You mean Γ ⊢ φ or Γ ⊢ ¬φ . In principle no, though it's possible that it's defined like that in certain places, since in first-order logic, that amounts to the same thing (given the completeness theorem). But "completeness" is a notion from model theory that doesn't care about proof systems. In a system where the completeness theorem is not true, such as second-order logic with standard semantics, we do have complete theories (such as second-order PA), where we always have Γ ⊨ φ or Γ ⊨ ¬φ, but that doesn't mean that every statement is either provable or disprovable. > The proof of Godel's theorem is to exhibit a φ for which "Γ ⊢ φ or Γ ⊢ ¬φ" is false. From that you conclude that "Γ ⊨ φ → Γ ⊢ φ" is false on the assumption that "Γ ⊨ φ" is true. But that last part is an informal argument. We believe that "Γ ⊨ G" is true for the Godel sentence G but we (obviously) can't prove it. I think that has it a bit backwards. It's not that we believe that PA ⊨ G - in fact, if we believed that, it would immediately imply PA ⊢ G, when that's exactly what we showed to be impossible. It's that we believe that G is true in the natural numbers, which is not the same thing as being true in PA, and that belief rests in our belief that PA is sound (which we can't prove, but seems reasonable). (There are some different "flavours" of the incompleteness theorems, some of them rely on soundness of PA and others only on it being consistent.) > But note that what you said is not mutually exclusive with what /u/Tainnor said, i.e. That's because that's me. ;)

lmm 4y ago

> I thought it was understood that the word "incomplete" in the context of a discussion of Godel's Incompleteness Theorem meant incomplete with respect to the truths of arithmetic, because that is what Godel's Incompleteness Theorem is about. What does "with respect to the truths of arithmetic" even mean? How is Presburger Arithmetic "incomplete" in this sense? > And those two things would be...? That it's so complex as to be obviously incomplete, but also so simple that anything smaller than it is obviously trivial. There are interesting systems smaller than PA, and none of this is obvious.

lisper 4y ago
> What does "with respect to the truths of arithmetic" even mean? It means: with respect to some axiomatization of arithmetic that allows Godel numbers to be constructed. Peano arithmetic, for example. > obviously incomplete I guess that depends on what you consider "obvious". It was far from obvious before Godel proved it. But nowadays it's not hard to understand. One generation's "obvious" is a prior generation's major breakthrough. The big surprise in Godel's theorem is that the amount of complexity you need to introduce into a theory to render it incomplete is quite small. Peano arithmetic is sufficient, but not necessary.
- lmm 4y ago
  > It means: with respect to some axiomatization of arithmetic that allows Godel numbers to be constructed. That's circular logic; why would that be an interesting question to investigate absent the incompleteness theorem? > The big surprise in Godel's theorem is that the amount of complexity you need to introduce into a theory to render it incomplete is quite small. Agreed, but that implicitly requires understanding that small theories like Presburger Arithmetic are complete (which they are in every usual meaningful sense, but you seem to be claiming otherwise).
  - lisper 4y ago
    > That's circular logic; why would that be an interesting question to investigate absent the incompleteness theorem? Because the amount of logical infrastructure that you need is surprisingly small. All you need is to be able to do basic grade-school arithmetic: add, subtract, multiple, divide, test for equality. And you don't even need all that. You can build everything you need from much simpler primitives. The reason this is not circular is that before Goedel's theorem mathematicians were trying to construct a formal system that would allow you to derive all true statements about not just arithmetic, but all of mathematics. It turns out that this is impossible. As soon as you can do arithmetic, Goedel's theorem applies and you have lost. > that implicitly requires understanding that small theories like Presburger Arithmetic are complete I don't see why. Goedel's theorem matters in the context of trying to reduce all of mathematics to a formal system. Presburger arithmetic fails not because it is syntactically incomplete but because it cannot (for example) do division, so it cannot formulate (for example) the concept of a prime number and so it cannot (for example) prove the fundamental theorem of arithmetic. So yes, PB is decidable, but it is not a plausible candidate for a complete (in the informal sense) formulation of all of mathematics. Goedel's theorem shows that if you can add, subtract, multiply and divide and test for equality, then you have lost. And if you can't do those things, then you have also lost, but you don't need a theorem to tell you that.