Theories and Computability

Editorial

This chapter depends on material in the chapter on computability theory, but can be left out if that hasn't been covered. It's currently a basic conversion of Jeremy Avigad's notes, has not been revised, and is missing exercises.

Editorial

This section should be rewritten.

Q is computably enumerable complete

$\Th{Q}$source is c.e. but not decidable. In fact, it is a complete c.e. set.

Proof

It is not hard to see that $\Th{Q}$source is c.e., since it is the set of (codes for) sentences $y$source such that there is a proof $x$source of $y$source in $\Th{Q}$source:

But we know that $\Prf[\Th{Q}](x,y)$source is computable (in fact, primitive recursive), and any set that can be written in the above form is c.e.

Saying that it is a complete c.e.\ set is equivalent to saying that $K \leq_m Q$source, where $K = \Setabs{x}{!A_x(x) \downarrow}$source. So let us show that $K$source is reducible to $\Th{Q}$source. Since Kleene's predicate $T(e,x,s)$source is primitive recursive, it is representable in $\Th{Q}$source, say, by $!A_T$source. Then for every $x$source, we have

Conversely, if $\Th{Q} \Proves \lexists[s][!A_T(\num x, \num x, s)]$source, then, in fact, for some natural number $n$source the formula $!A_T(\num x, \num x, \num n)$source must be true. Now, if $T(x,x,n)$source were false, $\Th{Q}$source would prove $\lnot !A_T(\num x, \num x, \num n)$source, since $!A_T$source represents $T$source. But then $\Th{Q}$source proves a false formula, which is a contradiction. So $T(x,x,n)$source must be true, which implies $!A_x(x) \downarrow$source.

In short, we have that for every $x$source, $x$source is in $K$source if and only if $\Th{Q}$source proves $\lexists[s][T(\num x,\num x,s)]$source. So the function $f$source which takes $x$source to (a code for) the sentence $\lexists[s][T(\num x, \num x, s)]$source is a reduction of $K$source to $\Th{Q}$source.

Explain

The proof that $\Th{Q}$source is c.e.-complete relied on the fact that any sentence provable in $\Th{Q}$source is “true” of the natural numbers. The next definition and theorem strengthen this theorem, by pinpointing just those aspects of “truth” that were needed in the proof above. Don't dwell on this theorem too long, though, because we will soon strengthen it even further. We include it mainly for historical purposes: Gödel's original paper used the notion of $\omega$source-consistency, but his result was strengthened by replacing $\omega$source-consistency with ordinary consistency soon after.

Definition of omega consistency

A theory $\Th{T}$source is $\omega$source-consistent if the following holds: if $\lexists[x][!A(x)]$source is any sentence and $\Th{T}$source proves $\lnot !A(\num 0)$source, $\lnot !A(\num 1)$source, $\lnot !A(\num 2)$source, dots then $\Th{T}$source does not prove $\lexists[x][!A(x)]$source.

Omega consistent extensions of Q are undecidable

Let $\Th{T}$source be any $\omega$source-consistent theory that includes $\Th{Q}$source. Then $\Th{T}$source is not decidable.

Proof

If $\Th{T}$source includes $\Th{Q}$source, then $\Th{T}$source represents the computable functions and relations. We need only modify the previous proof. As above, if $x \in K$source, then $\Th{T}$source proves $\lexists[s][!A_T(\num x,\num x, s)]$source. Conversely, suppose $\Th{T}$source proves $\lexists[s][!A_T(\num x, \num x, s)]$source. Then $x$source must be in $K$source: otherwise, there is no halting computation of machine $x$source on input $x$source; since $!A_T$source represents Kleene's $T$source relation, $\Th{T}$source proves $\lnot !A_T(\num x, \num x, \num 0)$source, $\lnot !A_T(\num x, \num x, \num 1)$source, dots, making $\Th{T}$source $\omega$source-inconsistent.

Explain

Remember that a theory is consistent if it does not prove both $!A$source and $\lnot !A$source for any formula $!A$source. Since anything follows from a contradiction, an inconsistent theory is trivial: every sentence is provable. Clearly, if a theory if $\omega$source-consistent, then it is consistent. But being consistent is a weaker requirement (i.e., there are theories that are consistent but not $\omega$source-consistent.). We can weaken the assumption in the preceding definition of omega consistency to simple consistency to obtain a stronger theorem.

There is no universal computable binary relation

There is no “universal computable relation.” That is, there is no binary computable relation $R(x,y)$source, with the following property: whenever $S(y)$source is a unary computable relation, there is some $k$source such that for every $y$source, $S(y)$source is true if and only if $R(k,y)$source is true.

Proof

Suppose $R(x,y)$source is a universal computable relation. Let $S(y)$source be the relation $\lnot R(y,y)$source. Since $S(y)$source is computable, for some $k$source, $S(y)$source is equivalent to $R(k,y)$source. But then we have that $S(k)$source is equivalent to both $R(k,k)$source and $\lnot R(k,k)$source, which is a contradiction.

Consistent extensions of Q are undecidable

Let $\Th{T}$source be any consistent theory that includes $\Th{Q}$source. Then $\Th{T}$source is not decidable.

Proof

Suppose $\Th{T}$source is a consistent, decidable extension of $\Th{Q}$source. We will obtain a contradiction by using $\Th{T}$source to define a universal computable relation.

Let $R(x,y)$source hold if and only if

Since we are assuming that $\Th{T}$source is decidable, $R$source is computable. Let us show that $R$source is universal. If $S(y)$source is any computable relation, then it is representable in $\Th{Q}$source (and hence $\Th{T}$source) by a formula $!D_S(u)$source. Then for every $n$source, we have

and

That is, for every $y$source, $S(y)$source is true if and only if $R(\Gn{!D_S(u)}, y)$source is. So $R$source is universal, and we have the contradiction we were looking for.

True arithmetic is undecidable

True arithmetic is not decidable.

Computably axiomatizable theories are computably enumerable

Suppose $\Th{T}$source is axiomatizable. Then $\Th{T}$source is computably enumerable.

Proof

Suppose $A$source is a computable set of axioms for $\Th{T}$source. To determine if $!A \in T$source, just search for a derivation of $!A$source from the axioms.

Put slightly differently, $!A$source is in $\Th{T}$source if and only if there is a finite list of axioms $!B_1$source, dots, $!B_k$source in $A$source and a derivation of $(!B_1 \land \dots \land !B_k) \lif !A$source in first-order logic. But we already know that any set with a definition of the form “there exists dots such that dots” is c.e., provided the second “dots” is computable.

Complete computably axiomatizable theories are decidable

Suppose a theory $\Th{T}$source is complete and axiomatizable. Then $\Th{T}$source is decidable.

Proof

Suppose $\Th{T}$source is complete and $A$source is a computable set of axioms. If $\Th{T}$source is inconsistent, it is clearly computable. (Algorithm: “just say yes.”) So we can assume that $\Th{T}$source is also consistent.

To decide whether or not a sentence $!A$source is in $\Th{T}$source, simultaneously search for a derivation of $!A$source from $\Th{T}$source and a derivation of $\lnot !A$source. Since $\Th{T}$source is complete, you are bound to find one or the other; and since $\Th{T}$source is consistent, if you find a derivation of $\lnot !A$source, there is no derivation of $!A$source.

Put in different terms, we already know that $\Th{T}$source is c.e.; so by a theorem we proved before, it suffices to show that the complement of $\Th{T}$source is c.e. also. But a formula $!A$source is in $\Th{\bar T}$source if and only if $\lnot !A$source is in $\Th{T}$source; so $\Th{\bar T} \leq_m \Th{T}$source.

First incompleteness theorem from undecidability

There is no complete, consistent, axiomatizable extension of $\Th{Q}$source.

Proof

We already know that there is no consistent, decidable extension of $\Th{Q}$source. But if $\Th{T}$source is complete and axiomatized, then it is decidable.

Explain

This theorems is not that far from Gödel's original 1931 formulation of the First Incompleteness Theorem. Aside from the more modern terminology, the key differences are this: Gödel has “$\omega$source-consistent” instead of “consistent”; and he could not say “axiomatizable” in full generality, since the formal notion of computability was not in place yet. (The formal models of computability were developed over the following decade, including by Gödel, and in large part to be able to characterize the kinds of theories that are susceptible to the Gödel phenomenon.)

The theorem says you can't have it all, namely, completeness, consistency, and axiomatizability. If you give up any one of these, though, you can have the other two: $\Th{Q}$source is consistent and computably axiomatized, but not complete; the inconsistent theory is complete, and computably axiomatized (say, by $\{ \eq/[0][0] \}$source), but not consistent; and the set of true sentence of arithmetic is complete and consistent, but it is not computably axiomatized.

Provable and refutable sentences of Q are computably inseparable

$\Th{Q}$source and $\Th{\bar Q}$source are computably inseparable.

Proof

Suppose $C$source is a computable set such that $\Th{Q} \subseteq C$source and $\Th{\bar Q} \subseteq \Complement{C}$source. Let $R(x,y)$source be the relation

We will show that $R(x,y)$source is a universal computable relation, yielding a contradiction.

Suppose $S(y)$source is computable, represented by $!D_S(u)$source in $\Th{Q}$source. Then

and

So $S(y)$source is equivalent to $R(\#(!D_S(\num u)),y)$source.

Theories consistent with Q are undecidable

Let $\Th{T}$source be any theory in the language of arithmetic that is consistent with $\Th{Q}$source (i.e., $\Th{T} \cup \Th{Q}$source is consistent). Then $\Th{T}$source is undecidable.

Proof

Remember that $\Th{Q}$source has a finite set of axioms, $!Q_1$source, dots, $!Q_8$source. We can even replace these by a single axiom, $!E = !Q_1 \land \dots \land !Q_8$source.

Suppose $\Th{T}$source is a decidable theory consistent with $\Th{Q}$source. Let

We show that $C$source would be a computable separation of $\Th{Q}$source and $\Th{\bar Q}$source, a contradiction. First, if $!A$source is in $\Th{Q}$source, then $!A$source is provable from the axioms of $\Th{Q}$source; by the deduction theorem, there is a derivation of $!E \lif !A$source in first-order logic. So $!A$source is in $C$source.

On the other hand, if $!A$source is in $\Th{\bar Q}$source, then there is a proof of $!E \lif \lnot !A$source in first-order logic. If $\Th{T}$source also proves $!E \lif !A$source, then $\Th{T}$source proves $\lnot !E$source, in which case $\Th{T} \cup \Th{Q}$source is inconsistent. But we are assuming $\Th{T} \cup \Th{Q}$source is consistent, so $\Th{T}$source does not prove $!E \lif !A$source, and so $!A$source is not in $C$source.

We've shown that if $!A$source is in $\Th{Q}$source, then it is in $C$source, and if $!A$source is in $\Th{\bar Q}$source, then it is in $\Complement{C}$source. So $C$source is a computable separation, which is the contradiction we were looking for.

Undecidability of first order logic in the arithmetic language

First-order logic for the language of arithmetic (that is, the set $\Setabs{!A}{\text{$!A$ is provable in first-order logic}}$source) is undecidable.

Proof

First-order logic is the set of consequences of $\emptyset$source, which is consistent with $\Th{Q}$source.

Undecidability through interpretation of arithmetic

Suppose $\Th{T}$source is a theory in a language in which one can interpret the language of arithmetic, in such a way that $\Th{T}$source is consistent with the interpretation of $\Th{Q}$source. Then $\Th{T}$source is undecidable. If $\Th{T}$source proves the interpretation of the axioms of $\Th{Q}$source, then no consistent extension of $\Th{T}$source is decidable.

Source corollary concerning extensions of Z F C

There is no decidable extension of $\Th{ZFC}$source.

Incompleteness for computably axiomatizable extensions of Z F C

There is no complete, consistent, computably axiomatizable extension of $\Th{ZFC}$source.

Undecidability with a binary relation symbol

First-order logic for any language with a binary relation symbol is undecidable.