# Is this meaningful? On the incompleteness theorem
**URL:** https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193
**Category:** Factual Questions
**Created:** [March 16, 2007, 1:27pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193 "2007-03-16T13:27:31Z")
**Posts on this page:** 14
**Page:** 1
### Author:  [@Cryptoderk](https://boards.straightdope.com/u/Cryptoderk)
#### Post date: [March 16, 2007, 1:27pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/1 "2007-03-16T13:27:31Z")
Does the following, which I came up with walking down the street today, make any sense:
Seems to me that the incompleteness theorem can be extended to show that there are an infinite number of theories that cannot be proved in any system. Allow me to explain:
Assume that there is a finite set of theories that cannot be proved called T.
Let A be the set of all axioms in the theorem. Then, you could make a system where A union T would be the axioms, and then there would be no unprovable theories within the system, so contradiction.
If the incompleteness theorem already says this then sorry, it’s been a long time since I read about it.
---
### Author:  [@4.66](https://boards.straightdope.com/u/4.66)
#### Post date: [March 16, 2007, 3:36pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/2 "2007-03-16T15:36:04Z")
You’re assuming that there is a ‘theorie’ that cannot be proven in any system. Calling this ‘theorie’ _X_, one could build a new system comprised of just _X_ as an axiom. Thus, there is a system in which _X_ can be proven after all.
This means that your set _T_ is the empty set and that your argument does not lead to a contradiction.
---
### Author:  [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)
#### Post date: [March 16, 2007, 4:41pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/3 "2007-03-16T16:41:13Z")
[QUOTE=4.66]
You’re assuming that there is a ‘theorie’ that cannot be proven in any system.
[/QUOTE]
Where is he assuming this?
From “Godel’s Proof” by Nagel and Newman: “They show also that there is and endless number of true arithmetical statements which cannot be formally deduced from any given set of axioms by a closed set of rules by inference.”
---
### Author:  [@Crotalus](https://boards.straightdope.com/u/Crotalus)
#### Post date: [March 16, 2007, 4:53pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/4 "2007-03-16T16:53:13Z")
What **ZenBeam** said. From another, perhaps more accessible source:
[QUOTE=Wikipedia]
In fact, there are infinitely many statements in the theory that share with the Gödel sentence the property of being true but not provable from the theory.
[/QUOTE]
[Link.](http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorem)
---
### Author:  [@Voyager](https://boards.straightdope.com/u/Voyager)
#### Post date: [March 16, 2007, 5:07pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/5 "2007-03-16T17:07:12Z")
[QUOTE=4.66]
You’re assuming that there is a ‘theorie’ that cannot be proven in any system. Calling this ‘theorie’ _X_, one could build a new system comprised of just _X_ as an axiom. Thus, there is a system in which _X_ can be proven after all.
This means that your set _T_ is the empty set and that your argument does not lead to a contradiction.
[/QUOTE]
I think your misunderstanding is that the OP means any particular system. What you propose creates a new system, and thus says nothing about what can be proven in the original one.
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [March 16, 2007, 5:27pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/6 "2007-03-16T17:27:38Z")
As I read the OP, he is correct. If you start with any theory sufficiently expressive to do arithmetic (addition, multiplication, and, crucially, exponentiation), there is an undecidable statement (Goedel’s theorem). Add it as a new axiom and it is now decidable. But GT implies there is still an undecidable statement. Continue.
But you have to understand that these are fully formalized theories, which may or may not reflect common meaning. For example, most people (including me) “believe” that there is a set of integers that we know and love and in that set every statement is either true or false. But these “Platonic integers” are not fully formalizable.
There are a few statements that are known to be undecidable in Peano Arithmetic (the arithmetic of ordinary induction) but can be proved using set theory (a more powerful axiom set). Obviously they are true in the Platonic integers. The names Paris and Harrington are the place to start if you are interested.
---
### Author:  [@MonkeyMensch](https://boards.straightdope.com/u/MonkeyMensch)
#### Post date: [March 16, 2007, 5:48pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/7 "2007-03-16T17:48:23Z")
I would have thought that an extension of this sort to an greater system where all true theormens are provable would then include false theorems which are are “equally” provable to be true.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [March 16, 2007, 5:51pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/8 "2007-03-16T17:51:55Z")
Godel’s theorem (strictly the Godel-Rosser theorem) actually requires the theory in question to have some pretty specific properties before it applies. It doesn’t apply, for example, to axiomatizations of **R** and **C**. That’s not to say that there isn’t a similar issue for them, but not from this theorem.
---
### Author:  [@4.66](https://boards.straightdope.com/u/4.66)
#### Post date: [March 16, 2007, 6:24pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/9 "2007-03-16T18:24:15Z")
[QUOTE=ZenBeam]
You’re assuming that there is a ‘theorie’ that cannot be proven in any system
Where is he assuming this?
[/QUOTE]
Well, he sets out to \* show that there are an infinite number of theories that cannot be proved in any system. \* (underlining mine).
In order to arrive at a contradiction he then assumes that there are a finite number of them. Worded rather loosely, _Assume that there is a finite set of theories that cannot be proved called T_ must, in this context, mean “Assume that the set _T_ of theories that cannot be proved in any system is finite.”
The fact that _T_ is non-empty plays a vital role in his contradiction, and that’s where he’s assuming that there is such a theorie.
On the other hand, if **Cryptoderk** is assuming any system _A_ as a starting point and is looking at the set _T_ of theories that cannot be proven\* using _A_, then his proof is faulty for another reason. In this case, from the fact that statements from _T_ are provable in _T union A_ it does not follow that _T union A_ has no unprovable statements. That conclusion is only correct if _T_ refers to the set of theories that cannot be proved in any system.
It might be true that, in the second interpretation, _T_ is infinite, but it does not follow from **Cryptoderk** ’s argument.
I think he actually means ‘proven nor disproven’ here.
---
### Author:  [@CalMeacham](https://boards.straightdope.com/u/CalMeacham)
#### Post date: [March 16, 2007, 6:24pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/10 "2007-03-16T18:24:20Z")
Looking up something completely unrelated, I stumbled across this, which seems relevant to this thread. I’d never heard of **Tarski’s Indefinability Theorem** before. It’s apparently an independent formulation made nearly simultaneously with Godel’s more famous theorem:
> **[Tarski's undefinability theorem](https://en.wikipedia.org/wiki/Tarski%27s_indefinability_theorem)**
>
> Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that "arithmetical truth cannot be defined in arithmetic".
> The theorem applies more generally to any sufficiently strong formal system, showing that truth in the standard model of the system cannot be defined within the system.
> In 1931, Kurt Gödel published the incompleteness ...
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [March 16, 2007, 6:49pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/11 "2007-03-16T18:49:45Z")
[QUOTE=4.66]
On the other hand, if **Cryptoderk** is assuming any system _A_ as a starting point and is looking at the set _T_ of theories that cannot be proven\* using _A_, then his proof is faulty for another reason. In this case, from the fact that statements from _T_ are provable in _T union A_ it does not follow that _T union A_ has no unprovable statements. That conclusion is only correct if _T_ refers to the set of theories that cannot be proved in any system.
[/QUOTE]
This is basically right, although you need to modify it a bit to deal with the exact conditions of Godel’s theorem. Adding a finite number of axioms to a theory with those properties won’t change those properties, but adding an infinite number will.
So, here’s a proof that an incomplete theory of first-order predicate calculus with at least one theorem has an infinite number of undecidable true statements associated with it. Let U be the undecidable statement, and let T be the theorem. If U v ~T is decidable, here’s a short proof of U:
1. U v ~T
2. T
3. U
Clearly, U v ~T is true if U is. The remaining detail is to show that there are an infinite number of such statements. But this is easy: if T is a theorem, then so is T & T (and T & T & T, and T & T & T & T, and…). QED.
---
### Author:  [@4.66](https://boards.straightdope.com/u/4.66)
#### Post date: [March 16, 2007, 7:21pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/12 "2007-03-16T19:21:50Z")
[QUOTE=4.66]
On the other hand, if **Cryptoderk** is assuming any system _A_ as a starting point and is looking at the set _T_ of theories that cannot be proven\* using _A_, then his proof is faulty for another reason. In this case, from the fact that statements from _T_ are provable in _T union A_ it does not follow that _T union A_ has no unprovable statements. **That conclusion is only correct if _T_ refers to the set of theories that cannot be proved in any system.**
[/QUOTE]
Oops! The bolded part is not true. The conclusion is not correct in the described circumstances either. What I should have written:
On the other hand, if **Cryptoderk** is assuming any system _A_ as a starting point and is looking at the set _T_ of theories that cannot be proven\* using _A_, then his proof is still faulty, for another reason. It does not follow from the fact that statements from _T_ are provable in _T union A_ that _T union A_ has no unprovable statements. Also, the fact that we’ve found a (new) system in which the statements from _T_ are provable does not contitute a contradiction. It’s only in contradiction with the idea that these statements are unprovable in any system.
**ultrafilter** , at this point _T_ is, by assumption, a finite set. So I don’t think your concerns are applicable here.
---
### Author:  [@Frylock](https://boards.straightdope.com/u/Frylock)
#### Post date: [March 16, 2007, 7:45pm UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/13 "2007-03-16T19:45:35Z")
[QUOTE=Cryptoderk]
Does the following, which I came up with walking down the street today, make any sense:
Seems to me that the incompleteness theorem can be extended to show that there are an infinite number of theories that cannot be proved in any system. Allow me to explain:
Assume that there is a finite set of theories that cannot be proved called T.
Let A be the set of all axioms in the theorem. Then, you could make a system where A union T would be the axioms, and then there would be no unprovable theories within the system, so contradiction.
If the incompleteness theorem already says this then sorry, it’s been a long time since I read about it.
[/QUOTE]
Wouldn’t A Union T be the same thing for each A, here?
(I take it by “theory” you just mean a set of axioms plus their implications?)
So like, T might include axioms 1, 2, and 3. Then let A be the set consisting just of axiom 1. A U T would then be 1, 2, 3 and all their implications. Now let A be the set consisting of axioms 2 and 3. Then A U T would be, again, 1, 2, 3 and all their implications.
On my reading of your post, A is supposed to be a subset of T. But that may be where I’m misreading you.
-FrL-
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [March 17, 2007, 1:46am UTC](https://boards.straightdope.com/t/is-this-meaningful-on-the-incompleteness-theorem/396193/14 "2007-03-17T01:46:38Z")
[QUOTE=ultrafilter]
Godel’s theorem (strictly the Godel-Rosser theorem) actually requires the theory in question to have some pretty specific properties before it applies. It doesn’t apply, for example, to axiomatizations of **R** and **C**. That’s not to say that there isn’t a similar issue for them, but not from this theorem.
[/QUOTE]
I beg to differ, but Goedel’s theorem applies to any formal system that is sufficient to express arithmetic, including exponentiation. It is its very generality that makes it so powerful. But it does have to be formal.
Perhaps you are going to characterize the reals using an infinite sentence, such as: for all x, x \< 0 or x \< 1 or x \<2 or x \< 3 or … (Archimedes axiom) and that might do it, but that is not allowed in Goedel’s system. There is another infinite (and second order axiom) to state completeness.