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.
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.
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.”
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.
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.
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.
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.
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.
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:
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:
U v ~T
T
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.
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.
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.
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.