# Q.E.D.Undecidability of Q: Proving Godel's First Incompleteness Theorem

• andrewkirk
In summary, the undecidability of Q is a result of Godel's first incompleteness theorem, which states that for any consistent formal system T, there exists a statement G in the language of T that is neither provable nor disprovable in T, thus making T undecidable. This proof relies on the assumption of ω-consistency, which ensures that a statement cannot be both true and false in the formal system, leading to a contradiction and proving the theorem. However, without this assumption, the proof falls apart and the theorem cannot be proven.
andrewkirk
Homework Helper
Gold Member
Undecidability of Q

Below is a proof of one of the key steps in Godel's first incompleteness theorem. It appears to prove the theorem. However, it doesn't assume that T⋃Q is ω-consistent, which I have read is necessary for the proof to work. The alternative is to use Rosser's Trick to avoid needing to assume ω-consistency. But the proof doesn't do that either.

This leads me to believe that my proof must have an invalid step in it, that requires ω-consistency to validate it. But I cannot see where that would be required. That's probably because my grasp of the concept of ω-consistency is very new and very tenuous.

I think my omission is probably in the part of the proof I've laid out in detail below. But it's possible that it lies somewhere else, like in the Representability Theorem or the couple of steps at the end.

If anybody can help me identify where I have gone wrong, I would appreciate it.

Strong Undecidability of Q
For a collection S of sentences in S, define:
Cn(S) = {#(θ) : Sentence(θ) ⋀ (S⊢ θ)}
where #(F) denotes the Godel number of formula F and Sentence(ψ) means that ψ is a well-formed sentence in formal language L.
The strong undecidability of Q theorem states that for any L-theory T, if T⋃Q is consistent in L, then T is undecidable, by which we mean that Cn(T) is not recursive.
Here Q denotes Robinson Arithmetic.
Proof
Assume T⋃Q is consistent in L and Cn(T⋃Q) is recursive (meaning that the relation that defines it as a subset of ω is recursive, aka μ-recursive).
Because of the recursivity of Cn(T⋃Q), the Representability Theorem tells us that the relation it defines must be representable in Q, which means there must exist a formula BewT⋃Q in wff(LN) with one free variable, say c, such that, for any θ in wff(LN):
(#(θ)∈Cn(T⋃Q)) ⇒ (Q⊢BewT⋃Q[c:=#(θ)] and
(#(θ)∉Cn(T⋃Q)) ⇒ (Q⊢¬BewT⋃Q[c:=#(θ)]).
Note that representability of Cn(T⋃Q) is a bigger requirement than it might at first seem, as any wff must have finite length and, since both sets Cn(T⋃Q) and ω - Cn(T⋃Q) are infinite, this precludes BewT⋃Q from being a simple infinite list of all numbers in Cn(T⋃Q). BewT⋃Q doesn't have to be recursive, but it must be concise.

Now by the Diagonal Lemma, applied to the wff (¬BewT⋃Q), we know there exists a sentence G in wff(LN) such that:

1. Q ⊢ (G↔¬BewT⋃Q[c:=#(G)])

This appears to be a theorem saying that G is true in T iff it is not provable in T, which immediately arouses suspicion. Let us examine this formally:

2. T ⊢G [Hypothesis]
3. #(G)∈Cn(T) [from previous line, by definition of Cn(T)]
4. #(G)∈Cn(T⋃Q) [as Cn(T)⊂Cn(T⋃Q)]
5. Q ⊢BewT⋃Q[c:=#(G)]) [by definition of BewT⋃Q]
6. Q ⊢¬G [from lines 1 and 5, via Modus Ponens]
7. T⋃Q ⊢¬G [as Q⊂T⋃Q]
8. T⋃Q ⊢¬G [from line 2, as Q⊂T⋃Q]

Hence T⋃Q⊢(G→(G⋀¬G)), so if T⋃Q is consistent, we must have:

9. T⋃Q⊬G

However it then follows that:

10. #(G)∉Cn(T⋃Q) [from previous line, by definition of Cn(T⋃Q)]
11. Q ⊢¬BewT⋃Q[c:=#(G)] [by definition of BewT⋃Q]
12. Q ⊢G [by lines 1 and 11, via Modus Ponens]
13. T⋃Q ⊢G [from previous line, as Q⊂T⋃Q]

So we have (T⋃Q⊢G)⋀¬(T⋃Q⊢G), which is a contradiction outside T.

Hence we must conclude that one of the assumptions we have made is false. If we insist on retaining the assumption of consistency then the only other available assumption is the one that Cn(T⋃Q) is recursive, so we must reject that assumption.

A bit more argument, which I've omitted here, shows that if Cn(T⋃Q) is not recursive then neither is Cn(T).

That means that T is undecidable and if we assume T is axiomatisable then it follows that T is not complete.

Hence Q is strongly undecidable.The flaw in this proof is that it does not assume that T⋃Q is ω-consistent. In order for Godel's first incompleteness theorem to be true, the proof must assume that T⋃Q is ω-consistent. This means that any sentence G in wff(LN) must satisfy either (T⋃Q⊢G) or (T⋃Q⊢¬G), but not both. In other words, the proof must assume that G cannot be both true and false in T⋃Q in order for the contradiction to hold. Without this assumption, there is no contradiction and hence no proof of the theorem.

## 1. What is the Q.E.D.Undecidability of Q: Proving Godel's First Incompleteness Theorem?

The Q.E.D.Undecidability of Q refers to a proof of Godel's First Incompleteness Theorem, which states that certain mathematical systems, such as arithmetic, cannot be proven to be true or false using only the rules and symbols within that system.

## 2. Who is Godel and what is his First Incompleteness Theorem?

Kurt Godel was a mathematician who proved the First Incompleteness Theorem in 1931. This theorem states that in any consistent formal system, there will always be statements that are true but cannot be proven within that system.

## 3. How does the Q.E.D.Undecidability of Q relate to Godel's First Incompleteness Theorem?

The Q.E.D.Undecidability of Q is a proof of Godel's First Incompleteness Theorem, using a technique known as diagonalization. It shows that there will always be statements within a formal system that are true but cannot be proven within that system.

## 4. What are the implications of Godel's First Incompleteness Theorem?

Godel's First Incompleteness Theorem has significant implications for mathematics and logic. It shows that there are limits to what can be proven within a formal system, and that there will always be statements that are undecidable. It also raises questions about the foundations of mathematics and the nature of truth.

## 5. Can Godel's First Incompleteness Theorem be applied to other areas besides mathematics?

While Godel's First Incompleteness Theorem is often discussed in the context of mathematics, it has also been applied to other fields such as computer science and philosophy. It demonstrates the limitations of formal systems and has implications for the study of knowledge, language, and reasoning.

• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Linear and Abstract Algebra
Replies
11
Views
2K
• Calculus
Replies
9
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
765
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
• Classical Physics
Replies
4
Views
834
• Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
• Calculus
Replies
4
Views
1K