• alcontali
    1.3k
    In the Wikipedia page for Turing's Halting problem, they mention that you can prove Gödel's First Incompleteness theorem from it.

    That is superb because the proof for Turing's Halting problem is really easy to understand. So, it is a great starting point for any downstream proof. This is the relevant quote:

    Assume that we have a sound (and hence consistent) and complete
    axiomatization of all true first-order logic statements about natural
    numbers. Then we can build an algorithm that enumerates all these
    statements. This means that there is an algorithm N(n) that, given a
    natural number n, computes a true first-order logic statement about
    natural numbers, and that for all true statements, there is at least
    one n such that N(n) yields that statement. Now suppose we want to
    decide if the algorithm with representation a halts on input i. We
    know that this statement can be expressed with a first-order logic
    statement, say H(a, i). Since the axiomatization is complete it
    follows that either there is an n such that N(n) = H(a, i) or there is
    an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until
    we either find H(a, i) or its negation, we will always halt, and
    furthermore, the answer it gives us will be true (by soundness). This
    means that this gives us an algorithm to decide the halting problem.
    Since we know that there cannot be such an algorithm, it follows that
    the assumption that there is a consistent and complete axiomatization
    of all true first-order logic statements about natural numbers must be
    false.


    After reading this proof, I wondered if a very similar proof by contradiction could also prove Tarski's Undefinability theorem? I was thinking of something along the following lines:

    Imagine that a truth predicate isTrue() for any arbitrary logic sentence s were computable. In that case, this predicate would also be able to compute the truth status for any arbitrary H(a,i). Therefore, we would be able to compute isTrue() for any possible H(a,i). Consequently, such isTrue() predicate would solve Turing's Halting problem, while we already know that it is fundamentally unsolvable. Therefore, such truth predicate is not computable.

    Is there a flaw or a problem with this proof strategy?

    The fact that the Wikipedia page mentions this proof strategy for Gödel's First Incompleteness but not for Tarski's Undefinability got me wondering. Maybe it does not work for Tarski after all? What's the catch?
  • god must be atheist
    5.1k
    Is there a flaw or a problem with this proof strategy?alcontali

    Yes, there is. I don't understand a word of it. That's a HUGE problem. (The strategy may be solid, though. I am no judge of that.)
  • alcontali
    1.3k
    (The strategy may be solid, though. I am no judge of that.)god must be atheist

    Concerning the proof strategy for Gödel's incompleteness theory, the Wikipedia page makes the following remark:

    This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. — Wikipedia

    At the same time, I have found the following academic publication by Jeremy Avigad, "Incompleteness via the halting problem". Apparently, the Wikipedia page editors do not allow to list this particular publication as a source for the section.

    The page history does not clarify why this decision was made.

    In the following math stackexchange discussion I have found the following damning criticism:

    I don't know of any proof of the full incompleteness theorem (the one that assumes only consistency) just from the unsolvability of the halting problem, and I doubt such a proof exists for two reasons. — Math stack exchange

    The page itself says:

    In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that an axiomatization of the natural numbers that is both complete and sound is impossible. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers. — Wikipedia page

    I suppose that the weaker system is not pressured to disprove false statements (only to prove true ones).

    Hence, this proof strategy is deemed a bit controversial for Gödel's incompleteness theorem, let alone, for Tarski's undefinability. I personally like it, however, because it is much easier to understand than the alternatives.
  • god must be atheist
    5.1k
    the undecidability of the halting problem — Wikipedia page

    What is the undecidability of the halting problem? What is the halting problem? This is factual knowledge to gain before anyone can contribute to your thread in any meaningful way.
  • god must be atheist
    5.1k
    And while you are at it, maybe you could give a brief (one or two paragraphs, no longer than 80 words each) summary of what Goedel's incompleteness theorem states.

    If it has to do something with the fact that the axioms of math are dependent in some way on the workings of math, yet they are the basic underlying principles of math, then I say that's true, but can't be proven without introducing some OTHER logical systems (such as what language is and how it works) that also suffer, so to speak, of the woes of the first, second, third, ... and nth incompleteness theorem.

    In fact, the whole universe, if it indeed exists, can't be proven to exist, because the proof would need to pull in some systems that are built on axioms that are pulled from the physical universe, and used in the proof of the universe's existence.

    In fact, this applies to any physical or other empirically observed phenomenon.
  • god must be atheist
    5.1k
    To prove that the system of math, the system of the universe, or anything empirical is impossible to prove because of the need to use parts of the system in axioms or premises, is not possible, for if it were possible, then we could describe the system precisely without the knowledge of axioms, and unfortunately axioms are required for the proof. Without axioms, there are no premises, so there is no thing to prove or to disprove.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment

Welcome to The Philosophy Forum!

Get involved in philosophical discussions about knowledge, truth, language, consciousness, science, politics, religion, logic and mathematics, art, history, and lots more. No ads, no clutter, and very little agreement — just fascinating conversations.