Exploring Incompleteness Theorem: Are All Collections of Axioms Incomplete?

[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?

 

[R136a1]

For example, Tarski formulated a set of axioms for euclidean geometry. This can be proven to be complete in some sense: http://en.wikipedia.org/wiki/Tarski's_axioms

 

[pwsnafu]

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.

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.

 

[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.

 

[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.

 

[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.

 

[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.

 

[nomadreid]

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.

 

[Hornbein]

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?

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.

 

[Hornbein]

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.

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.

 

[Bob]

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.

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.

 

[baker0]

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.

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

 

[baker0]

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.

Right, I was trying to prove this rigorously.

 

[HallsofIvy]

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

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.

 

[MLP]

Since it has a model, it is both complete and consistent.

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.

 

[D H]

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.

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.

 

[pwsnafu]

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.

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.

 

[jgens]

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.

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.

Incompleteness has nothing to do per se with the axioms. It has to do with the expressiveness of the axioms.

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

Can a set of axioms be used to prove all true mathematical statements?

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.

 

[lugita15]

Problems arise when recursion is allowed, e.g., induction. That's what Godel's incompleteness theorems are about.

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.