Archive for the ‘117b’ Category

117b – Undecidability and incompleteness – Lecture 8

February 15, 2007

We introduce Robinson’s arithmetic Q. It is a weak (and sound) theory that proves all true S01 sentences. We also introduce Peano Arithmetic PA. PA is sound and designed to “capture” all true first order statements about N. (The incompleteness theorems will show that it does not suceed: There are true statements that PA does not prove.)

We show that Q represents all c.e. sets and binumerates all recursive sets, in particular all primitive recursive functions.  PA actually proves that the representations of primitive recursive functions define functions, so in any (maybe non-standard) model of PA it makes sense to talk, for example, of the exponential function, or the function enumerating the primes.

We prove the fixed point lemma and deduce from it Tarski’s theorem on the undefinability of truth, thus formally solving the liar’s paradox.


117b – Undecidability and incompleteness – Lecture 7

February 13, 2007

We define essentially undecidable theories as those theories (of arithmetic) that are recursively axiomatizable but such that any recursive extension T is undecidable and therefore incomplete. We show that if S is essentially undecidable then there are continuum many complete extensions of S, none of which are c.e. The argument gives an example of a complete binary tree recursive in 0¢ with no c.e. branches.

We show that if j is S00 then its characteristic function is primitive recursive and that if R is a c.e. relation, then it is the range of a primitive recursive function. We use this to prove Craig’s trick showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We define (numeralwise) representability and binumerability of a relation by a formula in a given theory. Next lecture we will show that there is an essentially undecidable finitely axiomatizable theory that represents all c.e. relations and binumerates all recursive relations. This will be the key to the proof of the incompleteness theorems.

117b – Homework 2 – Solution to problem 3

February 8, 2007

Problem 3 of Homework 2 seems to have been harder than expected (there was a slight inaccuracy in its formulation, which may have somewhat contributed to this difficulty). Here is a reasonably detailed solution to this problem. It looks longer than it actually is, since I spend some time trying to explain where the requirements we use come from.


(There is a small typo on page 5, line 6. Instead of `sup’ it should be `union.’)

117b – Undecidability and incompleteness – Lecture 6

February 8, 2007

We briefly discuss the problem of generalizing the proof of unsolvability of Hilbert’s tenth problem to other (recursive) rings.

We prove a version of the first incompleteness theorem as a consequence of the unsolvability of the tenth problem: If S is any recursive set of axioms strong enough to prove a very weak fragment of arithmetic (the addition and multiplication tables for N suffice) then either S is not true of N, or else S is incomplete. The reason is that if S is true of N, then the set of consequences of S is an undecidable r.e. set (by the unsolvability of the tenth problem), but the set of consequences of a complete theory is decidable.

Additional references:

  • The incompleteness theorems,  by C. Smorynski. In Handbook of mathematical logic, J. Barwise, ed., North-Holland (1977), 821-865.
  • Models of Peano Arithmetic, by R. Kaye. Claredon Press (1991).
  • Aspects of incompleteness, by P. Lindström. Springer (1997).
  • On formally undecidable sentences of Principia Mathematica and related systems (German: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.), by K. Gödel. Monatshefte für Mathematik und Physik  38 (1931), 173-198. Reprinted in several places. See for example Collected Works, vol. I, K. Gödel. Oxford University Press (2001).

117b – Undecidability and incompleteness – Lecture 5

February 8, 2007

We complete the proof of the undecidability of Hilbert’s tenth problem, and discuss some of its consequences, tying up with the general theory of the degrees and leading directly into the second part of this topic: The incompleteness theorems.

117b – Homework 5

February 3, 2007

We will skip a week so this does not interfere with midterms. Homework 5 is due Thursday, February 15 at 1pm.

Homework 5

Important update:  The statement of problem 4 may seem a bit ambiguous. That is “a partial function in C” simply means that it is a partial recursive function.

117b – Undecidability and Incompleteness – Lecture 4

February 1, 2007

We show that a=n! is Diophantine. This implies that the prime numbers are Diophantine. Therefore, there is a polynomial in several variables with integer coefficients whose range, when intersected with the natural numbers, coincides with the set of primes. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.

We prove the bounded quantifier lemma, the last technical component of the proof. It implies that the class of relations definable by a S01 formula in the structure (N,+,´,<) coincides with the class of S1 relations (i.e., the Diophantine ones).

To complete the proof of the undecidability of the tenth problem, we will show that any c.e. relation is Diophantine. For this, we recall that a set is c.e. iff it is the domain of a Turing machine and proceed to code the behavior of Turing machines by means of a Diophantic representation. This involves coding configurations of Turing machines and it remains to show how to code the way a configuration changes into another one.

117b – Undecidability and incompleteness – Lecture 3

January 30, 2007

We conclude the proof that Matiyasevich sequences are Diophantine. This involves a delicate analysis of congruences satisfied by terms of these sequences.

It follows that exponentiation is Diophantine. Using exponentiation, we can now proceed to code finite sequences, the key idea behind both the proof of undecidability of the tenth problem and of the incompleteness theorems.

117b – Homework 4

January 25, 2007

Due Thursday, February 1 at 1:00 pm.

Homework 4

The second pdf contains some hints for problem 3.

Homework 4

117b – Undecidability and Incompleteness – Lecture 2

January 25, 2007

The core of the proof of the undecidability of the tenth problem is the proof that exponentiation is Diophantine. We reduce this to proving that certain sequences given by second-order recurrence equations are Diophantine. These are the Matiyasevich sequences: For b³4,

ab(n+2)=bab(n+1)-ab(n)  for all n.

We begin the proof that they are Diophantine by analyzing some of the algebraic identities their terms satisfy.

Additional reference:

  • Unsolvable problems, by M. Davis. In Handbook of mathematical logic, J. Barwise, ed., North-Holland (1977), 567-594.