Most who are familiar with any sort of basic incompleteness result (like Gödel’s First Incompleteness Theorem) for formal systems are acquainted with a proof of the theorem which precisely states the result that demonstrates a single sentence of the language of the system that is neither provable nor whose negation is provable – that is undecidable by the system. Once such a proof and the techniques involved in it become familiar, one may wonder whether there are other sentences (which are not logically equivalent to each other) that are undecidable. If there are, can we say anything about these sentences? How many are there? What is their logical relation to each other? In this post, I propose that there are other such undecidable sentences for formal systems (which meet certain criteria). If my demonstration is successful, we should be able to see that there are in fact infinitely many undecidable sentences none of which is logically equivalent to any other. *Please note that I’m uncertain whether this demonstration succeeds; if it doesn’t I’m very curious why and where the problems are.* (And of course, I’m sure there are editing mistakes.)

We first review basic notions by way of showing that the phenomenon of incompleteness with regards to formal systems can be easily demonstrated in very general terms. Provided with the notion of formal language (call such a language ‘** L**‘), we need only four basic notions to give an abstract formulation of the incompleteness phenomenon and to demonstrate it.

(1) We need a method of referring to expressions of the language ** L** (call the set of expressions ‘

**Σ**‘) such that the names for the expressions of the language are themselves singular terms of the language. The most straightforward method is to consider languages whose singular terms include the numerals and then to create a method to number the expressions of the language (that is, assign each expression to a numeral) by means of a numbering function. Let the numbering function be

**:**

*g***Σ**→

**N**and

**is 1–1.**

*g*(2) Provided we have such a language ** L** and numbering function

**, we need a sort of diagonal function**

*g***:**

*d***N**→

**Σ**such that if

*n*is assigned by

**to a formula with one free variable (‘ψ(**

*g**x*)’ say), then

*(*

**d***n*) = σ and σ is a sentence which results from substituting

*n*for

*x*in the formula whose number code is

*n*, that is, σ = ψ(

*n*). In short,

**(**

*d**n*)=ψ(

*n*) if

**(ψ(**

*g**x*)) =

*n*.

(3) We need notion of two distinct sets of sentences of the formal language. These will, of course, be subsets of **Σ**. Call the sets (metalinguistically) ‘* P*‘ (a mnemonic for ‘provable’) and ‘

**‘ (a mnemonic for ‘refutable’).**

*R***can be defined in terms of**

*R***: for σ ∈**

*P***Σ**, σ ∈

**iff ~σ ∈**

*R***. Since we’ve assumed that the expressions of the language are numbered, we can define two other sets with the help of**

*P***and**

*P***. Let**

*R***P***be the set of numbers such that

*p*∈

**P***iff

*(*

**d***p*) ∈

**. Let**

*P***R***be the set of numbers such that

*r*∈

**R***iff

*(*

**d***r*) ∈

**. Aside from defining**

*R***in terms of**

*R***, we’ve given**

*P***and**

*P***only a minimum of interpretation, but if we make use of a fourth notion explicated in terms of the relation between**

*R***and**

*P***, then we have enough to get a general incompleteness result.**

*R*(4) Let the system ** S** (

**(**

*g***) expressed by the some one-place predicate of**

*P***) be consistent if**

*L**∩*

**P****= ∅. Intuitively, this is tantamount to claiming that no sentence is both provable and refutable. We can also phrase the incompleteness phenomenon with the help of the notions we’ve spelled out here. We can that a system**

*R***is incomplete if there is sentence σ ∈**

*S***Σ**such that σ ∉

*P**and*σ ∉

**.**

*R*We can see very simply how the demonstration of a general incompleteness theorem might go. Take for example, exercise #2 on page 12 of Raymond Smullyan’s Gödel’s Incompleteness Theorems.

2.We say that a predicate

Hrepresentsa setinAif for every numberLn, the sentence (of)L(Hn) ∈if and only ifPn∈. Show that if the setAR*is representable in, then [the systemLbased onSwith language]P, if consistent, is incomplete.L

To see this, assume that the one-place predicate ** K** represents the set

**R***. Let

**(**

*g***(**

*K**x*)) =

*k*.

Now, we have

* K*(

*k*) ∈

**⇒**

*P**k*∈

**R***(by assumption that

*represents*

**K****R***)

⇒

*(*

**K***k*) ∈

**. (by definition of diagonal function**

*R***)**

*d*⇒

*(*

**K***k*) ∉

**. (by consistency of the system, that is,**

*P**∩*

**P****= ∅.)**

*R*So * K*(

*k*) can’t be in

**. On the other hand,**

*P***(**

*K**k*) ∈

**⇒**

*R**(*

**K***k*) ∉

**(by consistency of the system)**

*P*⇒

*k*∉

**R***(by assumption that K represents R*)

⇒

**(**

*d**k*) ∉

**(by definition of R*)**

*R*⇒

*(*

**K***k*) ∉

**(by definition of diagonal function d)**

*R*So the system is incomplete because * K*(

*k*) ∉

*R**and*

*(*

**K***k*) ∉

**.**

*P*On this sort of approach, the incompleteness theorem is demonstrated by showing that there is single sentence which is neither provable nor refutable. Of course, any sentence logically equivalent to this sentence will, on pain of contradiction, be neither provable nor refutable. One may wonder about whether there are sentences in the language ** L**, that are not logically equivalent that are neither provable nor refutable. If there are such sentences, how many are there and what might they look like? I propose that there are in fact infinitely many sentences of

**which are undecidable for a system**

*L***which meets the following criteria:**

*S’*- The system
is consistent.*S’* - If σ∈
and σ is the sentence ‘α & β’ for sentences α and β, then α∈*P*and β∈*P*.*P* - If σ∈
and σ is the sentence ‘π(*P**n*)’ (where π “expresses”in the following sense:*P**z*satisfies π (that is π(*z*)) if and only if*z*∈(*g*)), then**P***g*^{-1}(*n*)∈. If σ∈*P*and σ is the sentence ‘~π(*P**n*)’ for some*n*, then*g*^{-1}(*n*)∉. (Roughly, if it’s provable that it’s provable that β, then it’s provable that β and if it’s provable that it’s not provable that β, then it’s not provable that β.)*P* - For an arbitary one-place recursive function φ(…),
(φ(…)) is defined.*g*

The approach takes inspiration from Stephen Yablo’s semantic liar-like paradox expressed by the infinite sequence of sentences for convenience labeled by *s*_{0}, *s*_{1}, *s*_{2}, …

*s*_{0}: For all *i* > 0, *s _{i}* is not true.

*s*

_{1}: For all

*i*> 1,

*s*is not true.

_{i}*s*

_{2}: For all

*i*> 2,

*s*is not true.

_{i}…

*s*

_{j}: For all

*i*> j,

*s*is not true.

_{j}…

A paradox follows because if *s*_{0} is true, then each of *s*_{1}, *s*_{2}, *s*_{3}, … is not true, but in this case each of *s*_{2}, *s*_{3}, *s*_{4}, … is true. But since this is exactly what *s*_{1} claims *s*_{1} must be true after all – a contradiction. Similar reasoning can be used to show that for no *i* can *s _{i}* be true. Could each of these sentences be untrue? No, because in that case, each of

*s*

_{1},

*s*

_{2},

*s*

_{3}, … is not true and since this is exactly what

*s*

_{0}claims, then

*s*

_{0}would be true after all – a contradiction.

How might we use the Yablo’s result to generate an incompleteness result? Let’s start by considering a three-place relation **Φ** of the natural numbers:

**Φ**(** g**(

*h*(

*x*)),

*n*,

*m*) iff

*m*=

**((∀**

*g**x*)((

*x*>

*n*)→(~π(

**(**

*g***(**

*h**x*))))

where ‘*h*(*x*)’ is an formula with only ‘*x*‘ free — ‘*h*(*x*)’ might express a one place function.

Now certainly, from this relation we could form the function *f** _{h}* such that:

*f** _{h}*(

*n*) =

*m*where

**Φ**(

**(**

*g**h*(

*x*)),

*n*,

*m*).

The value of *m* is generated recursively from the values of *n* and ** g**(

*h*(

*x*)) by means of figuring the gödel number of a sentence formed from a sentence schema into which singular terms with these values are substituted. If we assume that every recursive function can be assigned a gödel number, then for each of the one-place recursive functions φ

_{0}, φ

_{1}, φ

_{2}, … we can form the function

*f*_{φy}where φ

_{y}represents some one-place recursive function:

*f*_{φy}(*n*) = *m* where **Φ**(** g**(φ

_{y}(

*x*)),

*n*,

*m*).

Now presumably *f*_{φy} is one of the one-place recursive functions and so we can form a function call it *f*_{φf} such that:

*f*_{φf}(*n*) = *m* where **Φ**(** g**(φ

_{f}(

*x*)),

*n*,

*m*) and

*f*_{φf}

*is*φ

_{f}(for φ

_{f}one of φ

_{0}, φ

_{1}, φ

_{2}, …)

To see how we might get an incompleteness result from sentences of a formal language which imitate the behavior of the Yablo sentences, we make use of this function. Consider the sentences:

σ_{0}: (∀x)((x > 0)→(~π(*f*_{φf}(x))))

σ_{1}: (∀x)((x > 1)→(~π(*f*_{φf}(x))))

σ_{2}: (∀x)((x > 2)→(~π(*f*_{φf}(x))))

…

Since the *f*_{φf}(n) yields the gödel number of σ_{n}, we can claim somewhat metaphorically that the sentences σ_{0} “claims” that none of σ_{1}, σ_{2}, σ_{3} … are provable. None of σ_{0}, σ_{1}, σ_{2}, σ_{3} … are logically equivalent: for any i ≠ j, the logical consequences of σ_{i} are not the same as the logical consequences σ_{j}. Specifically,

σ_{0} ⇒ ~π(** g**(σ

_{1})) ∈

**& ~π(**

*P***(σ**

*g*_{2})) ∈

**& ~π(**

*P***(σ**

*g*_{3})) ∈

**& …**

*P*⇒ σ_{1} ∉ ** P** & σ

_{2}∉

**& σ**

*P*_{3}∉

**& … // by assumption 3.**

*P*σ_{1} ⇒ ~π(** g**(σ

_{2})) ∈

**& ~π(**

*P***(σ**

*g*_{3})) ∈

**& ~π(**

*P***(σ**

*g*_{4})) ∈

**& …**

*P*⇒ σ_{2} ∉ ** P** & σ

_{3}∉

**& σ**

*P*_{4}∉

**& … // by assumption 3.**

*P*σ_{2} ⇒ ~π(** g**(σ

_{3})) ∈

**& ~π(**

*P***(σ**

*g*_{4})) ∈

**& ~π(**

*P***(σ**

*g*_{5})) ∈

**& …**

*P*⇒ σ_{3} ∉ ** P** & σ

_{4}∉

**& σ**

*P*_{5}∉

**& … // by assumption 3.**

*P*…

Finally, we’re getting somewhere. Now, either σ* _{i}* ∈

**for some**

*P**i*or not. If not, then none of σ

_{0}, σ

_{1}, σ

_{2}, σ

_{3}… are provable

*and*for no

*j*>

*i*is it the case that σ

*is refutable because in that case,*

_{j}σ* _{j}* ∈

**⇒ ~σ**

*R**∈*

_{j}**// definition of refutable**

*P*⇒ ~(∀x)((x > j) →(~π(*f*_{φf}(x))) ∈ *P*

⇒ (∃x)~((x > j) →(~π(*f*_{φf}(x))) ∈ *P*

⇒ (∃x)((x > j) & π(*f*_{φf}(x))) ∈ *P*

but this contradicts our original assumption that none of σ_{0}, σ_{1}, σ_{2}, σ_{3} … are provable.

On the other hand, if σ* _{i}* ∈

**for some i, then for no**

*P**j*>

*i*is σ

*∈*

_{j}**(by the consistency of**

*P***) nor is σ**

*S’**∈*

_{j}**(as we’ve just seen) by the consistency of**

*R***.**

*S’*We see that in either case, there are infinitely many sentences of ** L** that must be undecidable for system

**which are not logically equivalent.**

*S’*-Jesse Butler

on February 16, 2007 at 12:29 am |Craig Ewertσi maybe be narrowly distinct, but if I were looking for distinct sentences that were undecidable I wouldn’t be satisfied with them.

In fact, when I search a formal system for undecidable sentences, I discount the once that were constructed for the purpose of being undecidable.

In the number domain, Fermat’s last theorem was a good candidate for such a sentence. I can’t remember offhand, but Poincare’s Conjecture may be left undecided.

on February 16, 2007 at 4:29 pm |Andrew BaconHi Jesse,

I think your construction does work. The explicit theorem is: if PA is Sigma_1 sound then we can get an omega sequence of undecidable sentences using Yablo’s paradox. As far as I know this idea hasn’t been published, but Richard Heck has turned it into a proof of Gödel’s incompleteness theorem out of print (try searching through the Foundations of Maths mailing list archives for that), and Graham Priest has mentioned the possibility of turning it into a proof as well (see Priest ‘Yablo’s Paradox’ 1997, Analysis)

Having said that, the result you mention can be reached by much less novel means. We can get an infinity of non-equivalent undecidable sentences simply with the sequence Gn := . Now, whenever n > m: PA + Gn |- Gm but: PA + Gm |- Gn doesn’t hold (so the Gn get logically stronger as n increases). So again we have an infinite sequence of non-equivalent undecidable sentences only by appealing to Gödel’s second incompleteness theorem iteratively.

*However*, the surprising thing about this version of the proof it seems, is that yields a sequence of sentences undecidable in PA augmented with the omega-rule! The omega rule is an extra rule of inference that can be added to PA which say that from phi(1), phi(2), phi(3)… we can deduce forall n phi(n) (it can be seen easily that this rule cannot always be applied – us being mortal finite beings and all).

With the omega rule you can prove the consistency of PA. Why? Because PA is reflexive, so for each axiom, phi, of PA, PA |- Con(‘phi’). However if we have the omega rule we can show that all the axioms of PA are consistent since we can apply it to the sequence stating each instance of the induction schema is consistent and conclude that the induction schema is consistent (and the rest is finitely axiomatizable). However the proof you’ve given here seems to extend nicely to PA with the omega rule. It seems simple self reference (as in Gödel’s original theorem) won’t cut it if you have the omega rule.

Just out of interest, in reply to Craig: for all we know Fermats last theorem may well be undecidable from PA. The methods used in proving FLT ranged far outside of the realm of number theory and I would be surprised if Wiles’ proof could be translated back to a proof in purely arithmetic terms! It seems that after Wiles’ proof people stopped using it as an example of something that might be undecidable from PA, but I expect that question is still wide open.

on February 16, 2007 at 4:31 pm |Andrew BaconSorry the HTML must have eaten my Gn sequence because I put it in angular brackets!!

It was supposed to be the sequence

Con(PA), Con(PA + Con(PA)), Con(PA + Con(PA + Con(PA)), …

on February 16, 2007 at 4:56 pm |Jesse ButlerAndrew —

Thanks for the encouragement! I’ll try to find Heck’s paper and I’ll review Priest’s 1997 again.