4 ms·

> because for Gödel's theorem to actually work on theories of arithmetic the encodings of formulas have to be numbers ASCII codes are numbers. > but that's no

by lisper 4y ago

> because for Gödel's theorem to actually work on theories of arithmetic the encodings of formulas have to be numbers ASCII codes are numbers. > but that's not as directly amenable to a rigorous mathematical proof Why not? > you technically have to prove that that encoding scheme doesn't lead to ambiguities, ASCII is unambiguous. In fact, the only difference between ASCII and Godel numbers is that ASCII encodes strings as powers of 256 whereas Godel numbers encode strings as powers of prime numbers. > i.e. every string has (at most) a unique parsing Huh? That makes no sense. Did you mean that every number has a unique mapping to a string? Because ASCII certainly meets that requirement. > The more technically relevant part about Gödel's proofs that doesn't just readily follow from the halting problem is the fact that incompleteness of first-order theories has only very weak conditions - Robinson arithmetic is already sufficient. Why does that matter? This seems to me like an interesting bit of trivia about Robinson arithmetic, but I don't see why this matters to the main point. Any system less powerful than PA is trivially incomplete.

lmm 4y ago
> Why does that matter? This seems to me like an interesting bit of trivia about Robinson arithmetic, but I don't see why this matters to the main point. Any system less powerful than PA is trivially incomplete. Isn't this backwards? Systems that are simple enough (e.g. Presburger arithmetic) are complete, which is what we'd expect.
- lisper 4y ago
  I guess I should have been more precise: trivially incomplete with respect to truths about numbers, which is the thing we actually care about. It is trivial to construct a complete system that is completely (!) uninteresting. The empty system is complete with respect to its own theorems, of which there are none, but that is about as uninteresting as it gets. The interesting thing is that as soon as you get a system that is sufficiently expressive to capture even an elementary subset of what we would consider "truths about numbers" that system is necessarily incomplete, and it cannot be made complete by making it more powerful. That is the interesting thing, and proving it does not depend (AFAICT) on the details of any particular encoding of truths about numbers as long as it is well defined.
  - lmm 4y ago
    How exactly did you think "Any system less powerful than PA is trivially incomplete." conveyed any of this? You seem to be claiming two almost opposite things about PA.
    - 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.
deepnet 4y ago
ASCII has 7 bits ASCII encodes strings as powers of 128. :-D Otherwise seems legit
Tainnor 4y ago
Your point about ASCII codes ignores that we don't just want individual symbols to be numbers, we want entire formulas to be numbers too. Of course, you can encode any sequence of ASCII codes as a number (just concatenate the binary digits), I didn't doubt that. But to formally prove that this leads to unique parsing requires unnecessary technical work that mathematicians prefer to avoid because the exact coding scheme doesn't matter. > Any system less powerful than PA is trivially incomplete. That is false. See here for examples of complete theories, for which Gödel's incompleteness theorems don't apply because they are not strong enough: https://en.m.wikipedia.org/wiki/Complete_theory https://en.m.wikipedia.org/wiki/Complete_theory (Moreover, there are theories that are neither stronger nor weaker than PA. One such theory can give rise to an interesting proof of consistency of PA: https://en.m.wikipedia.org/wiki/Gentzen%27s_consistency_proof https://en.m.wikipedia.org/wiki/Gentzen%27s_consistency_proo...)

by lisper 4y ago

lmm 4y ago

> Why does that matter? This seems to me like an interesting bit of trivia about Robinson arithmetic, but I don't see why this matters to the main point. Any system less powerful than PA is trivially incomplete. Isn't this backwards? Systems that are simple enough (e.g. Presburger arithmetic) are complete, which is what we'd expect.

lisper 4y ago
I guess I should have been more precise: trivially incomplete with respect to truths about numbers, which is the thing we actually care about. It is trivial to construct a complete system that is completely (!) uninteresting. The empty system is complete with respect to its own theorems, of which there are none, but that is about as uninteresting as it gets. The interesting thing is that as soon as you get a system that is sufficiently expressive to capture even an elementary subset of what we would consider "truths about numbers" that system is necessarily incomplete, and it cannot be made complete by making it more powerful. That is the interesting thing, and proving it does not depend (AFAICT) on the details of any particular encoding of truths about numbers as long as it is well defined.
- lmm 4y ago
  How exactly did you think "Any system less powerful than PA is trivially incomplete." conveyed any of this? You seem to be claiming two almost opposite things about PA.
  - 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.

deepnet 4y ago

ASCII has 7 bits ASCII encodes strings as powers of 128. :-D Otherwise seems legit

Tainnor 4y ago

Your point about ASCII codes ignores that we don't just want individual symbols to be numbers, we want entire formulas to be numbers too. Of course, you can encode any sequence of ASCII codes as a number (just concatenate the binary digits), I didn't doubt that. But to formally prove that this leads to unique parsing requires unnecessary technical work that mathematicians prefer to avoid because the exact coding scheme doesn't matter. > Any system less powerful than PA is trivially incomplete. That is false. See here for examples of complete theories, for which Gödel's incompleteness theorems don't apply because they are not strong enough: https://en.m.wikipedia.org/wiki/Complete_theory https://en.m.wikipedia.org/wiki/Complete_theory (Moreover, there are theories that are neither stronger nor weaker than PA. One such theory can give rise to an interesting proof of consistency of PA: https://en.m.wikipedia.org/wiki/Gentzen%27s_consistency_proof https://en.m.wikipedia.org/wiki/Gentzen%27s_consistency_proo...)