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 g is 1–1.
(2) Provided we have such a language L and numbering function g, we need a sort of diagonal function d:N→Σ such that if n is assigned by g to a formula with one free variable (‘ψ(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 ‘R‘ (a mnemonic for ‘refutable’). R can be defined in terms of P: for σ ∈Σ, σ ∈ R iff ~σ ∈ P. Since we’ve assumed that the expressions of the language are numbered, we can define two other sets with the help of P and R. Let P* be the set of numbers such that p ∈ P* iff d(p) ∈ P. Let R* be the set of numbers such that r ∈ R* iff d(r) ∈ R. Aside from defining R in terms of P, we’ve given P and R only a minimum of interpretation, but if we make use of a fourth notion explicated in terms of the relation between P and R, then we have enough to get a general incompleteness result.
(4) Let the system S (g(P) expressed by the some one-place predicate of L) be consistent if P ∩ R = ∅. 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 S is incomplete if there is sentence σ ∈Σ 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 H represents a set A in L if for every number n, the sentence (of L) H(n) ∈ P if and only if n ∈ A. Show that if the set R* is representable in L, then [the system S based on P with language] L, if consistent, is incomplete.
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 K represents R*)
⇒ K(k) ∈ R. (by definition of diagonal function d)
⇒ K(k) ∉ P. (by consistency of the system, that is, P ∩ R = ∅.)
So K(k) can’t be in P. On the other hand,
K(k) ∈ R ⇒ K(k) ∉ P (by consistency of the system)
⇒ k ∉ R* (by assumption that K represents R*)
⇒ d(k) ∉ R (by definition of R*)
⇒ K(k) ∉ R (by definition of diagonal function d)
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 L which are undecidable for a system S’ which meets the following criteria:
- The system S’ is consistent.
- If σ∈P and σ is the sentence ‘α & β’ for sentences α and β, then α∈P and β∈P.
- If σ∈P and σ is the sentence ‘π(n)’ (where π “expresses” P in the following sense: z satisfies π (that is π(z)) if and only if z∈g(P)), then g-1(n)∈P. If σ∈P and σ is the sentence ‘~π(n)’ for some n, then g-1(n)∉P. (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 β.)
- For an arbitary one-place recursive function φ(…), g(φ(…)) is defined.
The approach takes inspiration from Stephen Yablo’s semantic liar-like paradox expressed by the infinite sequence of sentences for convenience labeled by s0, s1, s2, …
s0: For all i > 0, si is not true.
s1: For all i > 1, si is not true.
s2: For all i > 2, si is not true.
sj: For all i > j, sj is not true.
A paradox follows because if s0 is true, then each of s1, s2, s3, … is not true, but in this case each of s2, s3, s4, … is true. But since this is exactly what s1 claims s1 must be true after all – a contradiction. Similar reasoning can be used to show that for no i can si be true. Could each of these sentences be untrue? No, because in that case, each of s1, s2, s3, … is not true and since this is exactly what s0 claims, then s0 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 fh such that:
fh(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 ∉ P & … // by assumption 3.
σ1 ⇒ ~π(g(σ2)) ∈ P & ~π(g(σ3)) ∈ P & ~π(g(σ4)) ∈ P & …
⇒ σ2 ∉ P & σ3 ∉ P & σ4 ∉ P & … // by assumption 3.
σ2 ⇒ ~π(g(σ3)) ∈ P & ~π(g(σ4)) ∈ P & ~π(g(σ5)) ∈ P & …
⇒ σ3 ∉ P & σ4 ∉ P & σ5 ∉ P & … // by assumption 3.
Finally, we’re getting somewhere. Now, either σi ∈ P for some i or not. If not, then none of σ0, σ1, σ2, σ3 … are provable and for no j > i is it the case that σj is refutable because in that case,
σj ∈ R ⇒ ~σj ∈ P // definition of refutable
⇒ ~(∀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 ∈ P for some i, then for no j > i is σj ∈ P (by the consistency of S’) nor is σj ∈ R (as we’ve just seen) by the consistency of S’.
We see that in either case, there are infinitely many sentences of L that must be undecidable for system S’ which are not logically equivalent.