117b – Unsolvable problems – Lecture 3

March 12, 2007

At the beginning of the course we built (recursively in {\bf 0}') two incomparable sets A,B. It follows that A and B have degrees intermediate between {\bf 0} and {\bf 0}'. The construction required that we fixed finite initial segments of A and B during an inductive construction in such a way that the sets are given by the union of the initial segments we fix along the way, and so it is not clear whether they are c.e. or not. (A c.e. construction would add elements to a set and we would not have complete control on what is kept out of the set, so we would not be able to go on “fixing” initial segments of the set being constructed, as this requires that we commit to keeping some elements out of it).

Post asked whether there is an intermediate c.e. degree and this was solved by Friedberg and Muchnik using what is now called a finite injury priority construction. We showed this construction; again, 2 incomparable sets A and B are built and the construction explicitly shows they are c.e. This implies they are not recursive and have degree strictly below {\bf 0}'.


117b – Unsolvable problems – Lecture 2

March 2, 2007

We discussed briefly Church’s and Trakhtenbrot’s theorems: The set of logically valid sentences and the set of sentences valid in all finite models are undecidable. More precisely: If {\mathcal L} is a language that contains either a binary symbol or the language of arithmetic, then the set of theorems of \mathsf{Q} reduces to the set of validities of {\mathcal L}, so this set is (r.e. and) undecidable. For the same {\mathcal L}, we can axiomatize the behavior of a given Turing machine on a given input (by a similar argument to the association of a semi-Thue system to each Turing machine) in such a way that this axiomatization has a finite model iff the machine converges on this input, thus the halting problem reduces to the complement of the set of finite validities, so this last set is (co-r.e. and) undecidable.

We defined Post correspondence systems and showed that the problem of determining whether such a system admits a solution is unsolvable. Two applications to the theory of formal languages follow: There is no algorithm to test whether 2 given context-free grammars have disjoint languages, and there is no algorithm to test whether a given context-free grammar is ambiguous.

117b – Unsolvable problems – Lecture 1

March 1, 2007

We defined semi-Thue processes and showed (Post, 1947) that for each e there is a semi-Thue process \Pi(\varphi_e) such that the word problem for \Pi(\varphi_e) is Turing-above the halting problem for \varphi_e.

We then proceeded to define Thue processes and showed that they give rise to semigroups. It follows (Post; Markov) that there is a presentation of a semigroup with an unsolvable word problem.

It is easy to modify a Thue process so the semigroup it generates is indeed a group. A modification of the arguments for semigroups shows (Novikov; Boone) that the word problem for groups is unsolvable. In fact (Adjan,Rabin) if {\mathcal G} is a class of groups closed under isomorphisms and subgroups which neither contains nor is disjoint from the class of finitely presented groups, then there is no algorithm that determines from a given group presentation whether it is in {\mathcal G}.

Additional references:

  • Modular machines, the word problem for finitely presented groups, Collins’ theorem, by Aanderaa, Cohen. In Word problems II. The Oxford book, Adjan, Boone, Higman, eds. North-Holland (1980), 1-16.
  • Modular machines and the Higman-Clapham-Valiev embedding theorem,  by Aanderaa, Cohen. In Word problems II. The Oxford book, Adjan, Boone, Higman, eds. North-Holland (1980), 17-28.

117b – Homework 8

March 1, 2007

Due Tuesday, March 13 at noon.

Homework 8

117b – Some additional remarks on provably recursive functions

February 28, 2007

There are quite a few examples of natural combinatorial statements not provable in \mathsf{PA} other than the ones discussed in lecture. The references listed below present several of them and provide a guide to the literature; I especially recommend the beautiful expository paper by Stephen  Simpson and in general the whole collection where that paper appeared. I will ask you to abstain from looking at the Kanamori-McAloon paper for the time being, since its main result is the content of the last homework set. The list is far from exhaustive, however. There are many more recent results by Harvey Friedman, the literature on hydras goes much further than suggested (see here, for instance), and there is significant work on phase transitions not discussed in the papers I suggest.

There are at least two basic `combinatorial’ methods for showing that a function is not provably recursive. One is to use indicators. This technique, due to Paris, requires a bit of model theory, and is the method of the proof you are asked to provide in the homework.

The other method comes from a careful analysis of which functions are provably total in \mathsf{PA}. For this, one defines a fast-growing hierarchy of recursive functions. This requires some understanding of the concept of an ordinal. The fast-growing (or Grzegorczyk) hierarchy is defined as follows:

  • F_0(n)=n+1.
  • F_{\alpha+1}(n)=F_\alpha^n(n), where the superindex means iterated n times.
  • F_\lambda(n)=F_{\lambda(n)}(n), if \lambda is limit.

Here, \{\lambda(n): n =0,1,\dots\} is some (natural) sequence converging to \lambda (if you are not aware of ordinals, ignore for the moment what the last clause means).

For example, F_1(n)=2n, F_2(n)=2^n n, F_3(n) grows like a stack of n powers of 2 and F_4(n) grows like an iterated stack of powers of 2, there being n such iterations. It is easy to see that each F_n is primitive recursive and strictly increasing, that n<m implies that F_n is eventually dominated by F_m (i.e., that F_n(k)<F_m(k) for all but finitely many values of k), and that every primitive recursive function is eventually dominated by some F_n. Thus, if a function eventually dominates each F_n, it cannot be primitive recursive.

The ordinals provide us with a method for continuing this sequence while preserving that its members are (eventually) increasing and the sequence itself is increasing under eventual domination. Say that a linearly ordered set X is well-ordered iff it has no infinite descending chains. For our purposes, the ordinals are simply a way to talk about well-ordered sets (classically, ordinals denoted the order types of the well-ordered sets, i.e., the equivalence classes of these sets under the relation of being order-isomorphic. The modern viewpoint is different and we don’t need it here). We use n to denote the order type of any linearly ordered set of n elements, and use \omega to represent the order type of the natural numbers. We `add’ two order types \alpha and \beta by forming the disjoint union of a set of order type \alpha followed by a set of order type \beta. We also say that \alpha is smaller than \beta if any set of order type \beta has a (proper) initial segment of order type \alpha. We can then continue the sequence 0,1,2,\dots of the natural numbers, as follows:

\omega,\omega+1,\omega+2,\dots,\omega 2,\omega 2+1,\dots,\omega 3,\dots,\omega^2,\dots,\omega^3,\dots

where we use \omega2 to represent \omega+\omega, etc, \omega^2 to represent \omega\omega and so on, and we can even continue  beyond all these ordinals:


Call \epsilon_0 (epsilon-0) the first ordinal \alpha obtained this way such that

\alpha=\omega^\alpha (so \epsilon_0=\omega^{\omega^{\omega^{\dots}}}).

One can show that any ordinal below \epsilon_0 admits a unique `pure base \omega‘ representation, from which there is a natural way of defining the sequence \{\lambda(n):n=0,1,\dots\} converging to \lambda whenever \lambda is a limit, which means that it is not of the form \alpha+1 for any \alpha. For example,

\omega,\omega 3,\omega^{\omega^2 3+\omega 17+8} 5+\omega^3 2, etc,

are all limits. So, for instance, the sequence \{\lambda(n): n =0,1,\dots\} corresponding to \lambda=\omega is just \lambda(n)=n and the corresponding function F_\omega is easily seen to grow as the (diagonal) Ackermann function A(n,n); the sequence corresponding to \lambda=\omega^3 4 is \lambda(n)=\omega^3 3+\omega^2 n, etc. As before, each F_\alpha is (eventually) strictly increasing and if \alpha<\beta then F_\beta eventually dominates F_\alpha. Each F_\alpha, for \alpha<\epsilon_0 (and in fact, for many more \alpha) is recursive (in the natural sense that there is a recursive well-ordering of \omega of this order-type).

The relation of this sequence with \mathsf{PA} lies in that any function provably recursive in \mathsf{PA} is eventually dominated by one of the F_\alpha with \alpha<\epsilon_0 (the proof of this fact is proof-theoretic rather than combinatorial, but once we have it we can use it as a black box). So, one purely combinatorial way of showing that a function is not provably recursive is to show that it eventually dominates each such F_\alpha. This kind of analysis was developed by Solovay and Ketonen.

There are also other ways of relating \mathsf{PA} to this number \epsilon_0, and proof theorists have a lot more to say about this relation.

Additional references:

  • Lecture notes on enormous integers, by H. Friedman. (2001)
  • Unprovable theorems,  by H. Friedman. (2005) See https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/ for additional manuscripts and details.
  • Unprovable theorems and fast-growing functions, by S. Simpson. In Logic and combinatorics, S. Simpson, ed. AMS (1987).
  • On Gödel incompleteness and finite combinatorics, by A. Kanamori and K. McAloon. Annals of Pure and Applied Logic 33 (1987), 23-41.

117b – Undecidability and incompleteness – Lecture 11

February 27, 2007

Let T\vdash Q be r.e. and suppose there is a sentence \varphi such that T does not prove \varphi. Then T+\varphi is more powerful than T in two ways:

  1. It proves more theorems than T; for example,  \varphi.
  2. It provides much shorter proofs of theorems of T; for example: For any (total) recursive function f there is a sentence \theta provable in T but such that in T+\varphi there is a proof p of \theta such that no proof of \theta in T is shorter than f(p).

This leads to considering those recursive functions f of which T can prove that they are total. One calls such functions provably recursive in T. It is easy to show that for any \Sigma^0_1-sound T\vdash\mathsf{PA}, there are recursive functions that are not provably recursive in T. The statement that f is total,

\forall x\,\exists y\,(f(x)=y),

is easily seen to be \Pi^0_2 and for T=\mathsf{PA} one can provide natural examples of such recursive but not provably recursive functions f, thus providing natural (combinatorial) examples of independent \Pi^0_2-sentences. Actually, this can also be done for much stronger systems than \mathsf{PA}, like \mathsf{ZFC}, and Harvey Friedman has provided several such examples.

For \mathsf{PA}, the most famous examples are perhaps the following:

  • Goodstein (1944). The pure base-n representation of a number m is obtained by writing m in base n, writing the exponents of this representation also in base n, writing the exponents of these representations in base n, and so on. For n\ge2 let G_n(0)=0 and for m\ge1 let G_n(m) be the result of writing the pure base-n representation of m, replacing each n by n+1, and subtracting 1. The Goodstein sequence of m is the sequence m, G_2(m), G_3(G_2(m)), G_4(G_3(G_2(m))),\dots\,. This sequence eventually converges to 0. The function F that to m assigns the number of steps necessary for this to occur is recursive but not provably recursive in \mathsf{PA}. In fact, given any f provably recursive in \mathsf{PA}, F eventually dominates f.
  • Kirby, Paris (1982). Define a hydra to be a finite rooted tree. A head of the hydra is any node (other than the head) with only one edge connected to it, together with this edge. Hercules fights the hydra by chopping off its heads one by one by stages. At stage n, the hydra grows new heads as follows: from the node that used to be attached to the head just removed, traverse one edge towards the root and from this node just reached, sprout n copies of the part of the hydra above the edge just traversed. For any hydra, no matter how Hercules battles it, he eventually wins (i.e., the hydra is reduced to a single node). Moreover, given a hydra there is an absolute bound M on the number of stages that it takes Hercules to win. Coding (in any reasonable fashion) hydras by numbers, the function that assigns this number M=F(n) to a given hydra n is recursive but eventually dominates all functions provably recursive in \mathsf{PA}.
  • Paris, Harrington (1977). Given a set A, let A^{[n]} denote the collection of its subsets of size n. Given a function f\!:A^{[n]}\to B, say that a subset C of A is homogeneous for f iff f restricted to C^{[n]} is constant, and say that it is large if |C|\ge\min(C). Ramsey’s theorem, provable in \mathsf{PA}, states that for any c,n,b there is an M such that given any A of size M, any B of size b and any f\!:A^{[n]}\to B, there is a C homogeneous for f and of size at least c. The function that to c,n,b assigns the least such M is well known to be primitive recursive (just about any standard proof of Ramsey theorem in any combinatorics book shows that it roughly grows exponentially). Paris and Harrington showed that if we also require that the homogeneous set C be large, then the new statement is also true but the resulting function (clearly recursive) eventually dominates all functions provably recursive in \mathsf{PA}.

117b – Homework 7

February 22, 2007

Due Thursday, March 1 at 1pm.

Homework 7

117b – Undecidability and incompleteness – Lecture 10

February 22, 2007

A theory T (r.e., extending \mathsf{Q}) is reflexive iff it proves the consistency of all its finite subtheories. It is essentially reflexive iff each r.e. extension is reflexive.

Then \mathsf{PA} is essentially reflexive and therefore no consistent extension of \mathsf{PA} is finitely axiomatizable. This is obtained by showing that, in spite of Tarski’s undefinability of truth theorem, there are (provably in \mathsf{PA}\Sigma^0_ntruth predicates for all n.

We defined Rosser sentences and showed their undecidability. We also showed Löb’s theorem that if T\vdash\mathsf{PA} is an r.e. theory and T\vdash{\rm Pr}_T(\varphi)\to\varphi, then T\vdash\varphi. This gives another proof of the second incompleteness theorem.

Finally, we showed that the length of proofs of \Pi^0_1-sentences is not bounded by any recursive function: For any T\vdash \mathsf{Q} r.e. and consistent, and any recursive function f, there is a \Pi^0_1-sentence \varphi provable in T but such that any proof of \varphi in T has length > f(\varphi).

117b – Undecidability and incompleteness – Lecture 9

February 20, 2007

Let S and T be r.e. theories in the language of arithmetic. Assume that S is strong enough to binumerate all primitive recursive relations. This suffices to prove the fixed point lemma:

For any formula \gamma(x) there is a sentence \varphi  such that S\vdash(\varphi\leftrightarrow\gamma(\varphi)),

moreover, \varphi can be chosen of the same complexity as \gamma.

The (Löb) Derivability conditions for S,T are the following three statements:

  • For any \varphi, if T\vdash\varphi, then S\vdash{\rm Pr}_T(\varphi).
  • S\vdash\forall\varphi,\psi,({\rm Pr}_T(\varphi\to\psi)\land {\rm Pr}_T(\varphi)\longrightarrow{\rm Pr}_T(\psi)). 
  • S\vdash\forall\varphi,({\rm Pr}_T(\varphi)\to{\rm Pr}_T({\rm Pr}_T(\varphi))).

For example, S=\mathsf{Q} suffices for the proof of the fixed point lemma and of the first derivability condition and S=\mathsf{PA} suffices for the other two.

Gödel incompleteness theorems:

  1. Let S be r.e. and strong enough to satisfy the fixed point lemma and the first derivability condition. Let T\vdash S be r.e. and consistent. Then there is a true \Pi^0_1 sentence \varphi such that T does not prove \varphi. If T is \Sigma^0_1-sound, then T does not prove \lnot\varphi either.
  2. If in addition S satisfies the other two derivability conditions, then T does not prove {\rm Con}(T), the statement asserting the consistency of T.

As a corollary, \mathsf{Q} is essentially undecidable: Not only it is undecidable, but any r.e. extension is undecidable as well. Gödel’s original statement replaced \Sigma^0_1-soundness with the stronger assumption of \omegaconsistency.

117b- Homework 6

February 15, 2007

Due Thursday, February 22 at 1pm.

Homework 6