# Incompleteness Theroem

1. Dec 15, 2013

### baker0

Is any collection of axioms incomplete? This seems to be intuitively true.

Relating to Godel's Incompleteness theorem, Godel proved any consistent set of axioms based on the theory of natural numbers cannot be proved themselves, without leaving any assumptions.

So what I am wondering is if anyone has proved that any arbitrary set of consistent axioms is incomplete?

2. Dec 15, 2013

### R136a1

3. Dec 15, 2013

### pwsnafu

You need to nitpicky when you say "based on the theory of natural numbers". For example, if you take PA and throw out induction you get Robinson arithmetic which is incomplete. If you throw out multiplication you get Presburger arithmetic which is consistent, complete and decidable.

4. Dec 16, 2013

### baker0

True, you do have to be a little more rigorous. By incomplete I mean you cannot prove all the axioms to the point where nothing is left assumed or unproven. Of course Presburger Arithmetic is complete in the sense that you can deduce each proposition from the axioms. However, incomplete in that you cannot prove all the axioms. I am looking for a theorem where no matter what you assume, you are not going to be able to prove all the basic axioms completely. In other words, a generalization of Godel's Incompleteness theorem. One that extends beyond the natural numbers to perhaps any finite set of axioms.

5. Dec 16, 2013

### pwsnafu

Incompleteness has nothing to do with axioms, because every axiom proves itself in a trivial and vacuous manner: the sentence which is just itself.

6. Dec 17, 2013

### baker0

Incompleteness has everything to do with axioms. Axioms do not prove themselves. Axioms are things that are assumed to be true. Axioms are just propositions. In order to be complete, we must prove these axioms.

7. Dec 17, 2013

### jgens

Axioms cannot be proven in the abstract. But when you fix a system of axioms for your mathematical universe, then the axioms trivially verify themselves. This is what pwsnafu has already said.

Edit: Fixed an issue with the language. The wording of the earlier version contained a mistake.

Last edited: Dec 17, 2013
8. Dec 17, 2013

To put the above answers more explicitly: A proof of a sentence S in an axiom system means that (informally):
(a) there is some relation which can be interpreted as implication in the system
(b) there is some rule(s) (e.g., Modus Ponens) allowing the axioms to be combined to give other (not necessarily new) sentences.
(c) from the axioms and rules one can create a chain of implication that starts from a subset of the axioms and ends with your sentence S.
So, if you have a set of axioms, as long as "A implies A" is valid for all A (as it should be for implication), then your axioms are automatically proven.

Of course, it is possible to prove the axioms from other propositions in your theory (the set of consequences of the rules applied to the axioms), but this becomes circular.
If you want prove the axioms from some other basis besides those propositions in your theory, then you are running contrary to the definition of axioms.

9. Dec 26, 2013

### Hornbein

It would be more accurate to say that

any system of axioms from which contains arithmetic is incomplete or inconsistent.

"contains arithmetic" means that the system has to include the natural numbers, variables, addition, multiplication, and exponentiation. There are plenty of simpler systems that are both consistent and complete.

10. Dec 26, 2013

### Hornbein

No. A system is complete if any statement in the system can be determined to be either true or false within that system. The axioms are by definition true, assumed to be true. They require no further proof.

11. Dec 28, 2013

### Bob

Presburger Arithmetic is infinitely axiomatizable. infinitely many axioms included. the statement and it's negation can be deduced from axioms. So it's complete and consistent.

From Godel's Incompleteness theorem. any finite set of axioms cannot be both consistent and complete.
inconsistent and complete or consistent not complete.

12. Jan 1, 2014

### baker0

Presburger Arithmetic is not a good example. I claimed this was true for finite axioms.

13. Jan 1, 2014

### baker0

Right, I was trying to prove this rigorously.

14. Jan 1, 2014

### HallsofIvy

This is not true. That is why Godel included the requirement that the axioms be sufficient to include the properties of the integers.

A standard example is
1) Two points determine a line
2) Two lines determine a point
3) There exist exactly three points

A model for this consists of three points, A, B, and C and the three "lines", {A,B}, {A,C}, and {B,C}. Since it has a model, it is both complete and consistent.

15. Jan 2, 2014

### MLP

A set of well-formed formulas can have a model and not be complete. The set propositional tautologies has a model but is incomplete with respect to the deductive system that has only one axiom scheme p > (q > p) and modus ponens as its only rule.

16. Jan 3, 2014

### D H

Staff Emeritus
This is just wrong. Axioms are things you cannot prove. If you can prove an axiom it's not an axiom. It's a theorem.

Incompleteness has nothing to do per se with the axioms. It has to do with the expressiveness of the axioms. Can a set of axioms be used to prove all true mathematical statements? A sufficiently weak set of axioms cannot. There are some true statements that are out of that theory's reach. A sufficiently weak theory however can be proven to be internally consistent. Problems arise when recursion is allowed, e.g., induction. That's what Godel's incompleteness theorems are about. A sufficiently powerful theory is either inconsistent or incomplete. Pick your poison.

17. Jan 3, 2014

### pwsnafu

No. An axiom is a sentence with a trivial proof. You don't need to prove axioms, but that is different to saying you cannot prove axioms. Re-read nomadreid's post.

18. Jan 3, 2014

### jgens

This is silly. You are correct that the axioms cannot be verified in the abstract. But once you fix a given theory, the axioms of this theory trivially verify themselves. So in an important sense axioms are provable and they are theorems.

This is all good. But then you go somewhere silly again...

This is a mischaracterization of completeness. A theory (i.e. the set of consequences from the given axioms) is complete if and only if it is a maximal consistent set of sentences. So a complete theory can either prove or disprove every sentence in the language. When a theory is incomplete there are sentences whose truth is undecidable from our axioms. For example consider the Axiom of Choice. This statement is undecidable in ZF, and consequently, there are extensions of ZF where the axiom is true and yet other extensions of ZF where it fails.

Edit: Anyway unless you have some a priori notion of "truth" your statement is nonsense. I suspect the misinformation in this thread stems from the two notions of completeness in logic. One notion is every semantically provable sentence is syntactically provable. This is what is proved in the completeness theorems. The second notion is the one mentioned in my post above. That notion of completeness is the right one for the incompleteness theorems. All a matter of context.

Last edited: Jan 3, 2014
19. Jan 3, 2014

### lugita15

No, induction is neither necessary nor sufficient for a theory to be strong enough for Godel's theorem to apply. Godel's theorem does apply to Robinson's Q, which has no induction, and it does not apply to Presburger Arithmetic, which has induction.