February | 2007 | A kind of library

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:

$\omega^\omega,\dots,\omega^{\omega^\omega},\dots\,$ .

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.

1 Comment | 117b: Computability theory | Tagged: Undecidability and incompleteness | Permalink
Posted by andrescaicedo

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:

It proves more theorems than $T$ ; for example, $\varphi$ .
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}$ .

Leave a Comment » | 117b: Computability theory | Tagged: Undecidability and incompleteness | Permalink
Posted by andrescaicedo

117b – Homework 7

February 22, 2007

Due Thursday, March 1 at 1pm.

4 Comments | 117b: Computability theory | Permalink
Posted by andrescaicedo

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_n$ –truth 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)$ .

Leave a Comment » | 117b: Computability theory | Tagged: Undecidability and incompleteness | Permalink
Posted by andrescaicedo

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:

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.
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 $\omega$ –consistency.

Leave a Comment » | 117b: Computability theory | Tagged: Undecidability and incompleteness | Permalink
Posted by andrescaicedo

117b- Homework 6

February 15, 2007

Due Thursday, February 22 at 1pm.

4 Comments | 117b: Computability theory | Permalink
Posted by andrescaicedo

117b – Undecidability and incompleteness – Lecture 8

February 15, 2007

We introduced Robinson’s arithmetic $\mathsf{Q}$ . It is a weak (and sound) theory that proves all true $\Sigma^0_1$ sentences. We also introduced Peano Arithmetic $\mathsf{PA}$ . $\mathsf{PA}$ is sound and designed to “capture” all true first-order statements about ${\mathbb N}$ . (The incompleteness theorems will show that it does not suceed: There are true statements that $\mathsf{PA}$ does not prove.)

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

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

Leave a Comment » | 117b: Computability theory | Tagged: Undecidability and incompleteness | Permalink
Posted by andrescaicedo

117b – Undecidability and incompleteness – Lecture 7

February 13, 2007

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 showed 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 ${\bf 0}'$ with no c.e. branches.

We showed that if $\varphi$ is $\Sigma^0_0$ 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 used this to prove Craig’s trick showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We defined (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.

Leave a Comment » | 117b: Computability theory | Tagged: Undecidability and incompleteness | Permalink
Posted by andrescaicedo

Nosferatu

February 8, 2007

Subtitled eine Symphonie des Grauens, `A symphony of horror’, this 1922 German film is very different visually from most other expressionist films from this period. As mentioned during my entry on The cabinet of Doctor Caligari, the imagery (usually expressed in the visual look of the sets of the movie) plays an important role in expressionist films. It tends to consist of highly artificial sets and there is almost no use of exteriors. In contrast with these common techniques, a large portion of Nosferatu is shot outdoors, and naturalistic images play an important role in the tone and mood of the film. There are some really beautiful scenes of dusk, and a couple of scenes where we see spiders advancing on their prey, or carnivore plants; I imagine these scenes were significantly difficult to achieve with the technical restrictions of the early 1920s.

The DVD commentary contained some nice details that added to my appreciation of the film. For example, night scenes used to be shot during the day, and then the film was painted on, usually with blue tones, to simulate darkness. Again, the musical score in the DVD was recorded specifically for it, and it was very carefully done and a great addition to the overall effect of the story.

Nosferatu is based on Dracula. This is acknowledged during the opening credits, but the names of the main characters, locations, and situations are sufficiently changed so that Enrico Dieckmann and the other producers felt confident there was no need to acquire the rights to use the story. Apparently, they had tried to do so unsuccessfully, and later Stoker’s widow tried to sue the company. Unfortunately for her, Dieckmann’s company had gone bankrupt so instead of money she tried to ensure that all existing copies of the movie were destroyed. Luckily for us, her efforts proved futile.

The story stays closes to Dracula in style and plot. We have therefore an offscreen narrator telling us the events as he has finally been able to understand them, several different fonts used on screen to represent letters or books the characters read, as opposed to dialogue between them which, while present, is kept to a minimum. There are significant differences in how the story ends and on the effect of the vampire (Nosferatu, count Orlock) on the townfolks. Also, instead of London, part of the action is translated to Schleswig-Holstein, Germany.

The relatively recent revival of the vampire genre probably originates with Stephen King’s ‘Salem’s Lot. Clearly inspired by Dracula, Nosferatu is also an acknowledged influence for this novel. We see for example that Barlow, King’s vampire, relocates to Jerusalem’s Lot with the help of a local businessman, Mr. Straker, corresponding to Knock, the real estate agent of the movie.

Many elements of vampire lore are incorporated into the film, some without being mentioned explicitly. Thus, a river stops Orlock from leaving his castle, and only by having other people carry him across can he journey. Also, he cannot enter a place unless their owners invite him in. There are also references to the power of vampires to transmute, and people refer to a werewolf in the area which seems to actually be Orlock himself.

Very well made and sufficiently creepy, this is a really good movie. There were a few odd details with how the story is told. For example, Bulwer, the Van Helsing character, has a very small role and his scenes, though quite beautiful and useful to set the tone of the story, seem completely unnecessary from the point of view of the actual tale. And Hutter, the Harker character, really comes out as a clueless buffoon, although his character is actually more complicated and his relationship with his wife is rather strange and indicative of serious problems and shortcomings on his part. At the end, events happen to him and very little is the result of his own actions.

Nosferatu, played by Max Schreck, is itself a very scary figure, his grotesque features becoming more exagerated as the story progresses. Now I think I should rewatch Shadow of the vampire to see how close Dafoe comes to capture Schreck’s nuances.

Leave a Comment » | Movies | Permalink
Posted by andrescaicedo

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.’)

Leave a Comment » | 117b: Computability theory | Permalink
Posted by andrescaicedo

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library

117b – Some additional remarks on provably recursive functions

117b – Undecidability and incompleteness – Lecture 11

117b – Homework 7

117b – Undecidability and incompleteness – Lecture 10

117b – Undecidability and incompleteness – Lecture 9

117b- Homework 6

117b – Undecidability and incompleteness – Lecture 8

117b – Undecidability and incompleteness – Lecture 7

Nosferatu

117b – Homework 2 – Solution to problem 3

Categories

Recent Comments

Mathematical links

My pages

Others

Mathoverflow

Math.StackExchange

Archives