(15 points) [Gdel's Incompleteness Theorem One of the most important results of 20th century logic (and arguably of all 20th century mathematics) was the discovery that there are some true mathematical statements that cannot be proven using the standard axioms of mathematics. This 1931 result by Kurt Gdel is known as Gdel's Incompleteness Theorem. In this problem, you will prove one version of Gdel's Theorem using what we know about Turing machines, 79 years too late to revolutionize modern mathematics. (The actual proof given by Gdel is a little more complicated, since Turing Machines hadn't been invented yet, but it relies on the same basic notion of diagonalization, and the two results are intimately related.) Some preliminaries: we say that a system of mathematics is consistent if there exists a special proof-checking Turing machine M* that can verify or reject any proof that it is given in the language of that system. In other works, there exists a machine M that decides the language PROOFS = {(RT) | P is a valid proof of statement T} Assume that our system of mathematics is consistent, so that we can check algorithmically whether a proof is correct. Assume for simplicity's sake that any statement T in our system of mathematics is either true or false exactly one of T or not (T) is true. For this question, you can express a mathematical statement in the usual way using English, rather than encoding it into any special logical language. (a) Suppose for a contradiction that every true statement T has a proof P Using this assumption, give a Turing machine decider for the language TST MTS = {(T) | T is a true statement) (b) Use the previous result to construct a Turing machine that solves the halting problem. (c) Conclude that there exists a true statement that does not have a proof, proving Gdel's Theorem. (15 points) [Gdel's Incompleteness Theorem One of the most important results of 20th century logic (and arguably of all 20th century mathematics) was the discovery that there are some true mathematical statements that cannot be proven using the standard axioms of mathematics. This 1931 result by Kurt Gdel is known as Gdel's Incompleteness Theorem. In this problem, you will prove one version of Gdel's Theorem using what we know about Turing machines, 79 years too late to revolutionize modern mathematics. (The actual proof given by Gdel is a little more complicated, since Turing Machines hadn't been invented yet, but it relies on the same basic notion of diagonalization, and the two results are intimately related.) Some preliminaries: we say that a system of mathematics is consistent if there exists a special proof-checking Turing machine M* that can verify or reject any proof that it is given in the language of that system. In other works, there exists a machine M that decides the language PROOFS = {(RT) | P is a valid proof of statement T} Assume that our system of mathematics is consistent, so that we can check algorithmically whether a proof is correct. Assume for simplicity's sake that any statement T in our system of mathematics is either true or false exactly one of T or not (T) is true. For this question, you can express a mathematical statement in the usual way using English, rather than encoding it into any special logical language. (a) Suppose for a contradiction that every true statement T has a proof P Using this assumption, give a Turing machine decider for the language TST MTS = {(T) | T is a true statement) (b) Use the previous result to construct a Turing machine that solves the halting problem. (c) Conclude that there exists a true statement that does not have a proof, proving Gdel's Theorem
