Is there any known consistent but incomplete formal axiomatic system apart of and simpler than one "capable of doing arithmetic"? Is it even possible?

Even if this capability of arithmetic were a necesary condition, then I think it can't be proven that it's the minimal formal axiomatic system for doing that, so there must be many examples of smaller and smaller system that allow it.

I am not asking for "undecidable mathematical statements" but minimal incomplete systems.

Thanks for any guide

  • $\begingroup$ There are many. For example, the empty set of axioms will always be consistent but incomplete (assuming your language is nontrivial, so there are nontrivial statements to be made). You'll need to impose some sort of extra condition on the axiomatic system to make your question at all interesting. $\endgroup$ – Chris Eagle May 4 '12 at 15:55
  • $\begingroup$ It's known for languages or machines to clasify for being "Turing complete" or not, if those are turing complete then they allow to do the question about the halting problem, and the answer is no, on the other hand there are complete examples like Chess game, it don't allow you to do an undecidable question, well, I wonder if there are any example between those. thanks $\endgroup$ – Hernán Eche May 4 '12 at 16:00

Consider the following system for propositional logic. It has one axiom, $P\to P$, and one rule of inference, which is that if $x$ is any theorem then $\lnot\lnot x$ is a theorem. This system proves infinitely many theorems of propositional logic, and it is sound and consistent, but it is clearly incomplete. It is also incapable of doing arithmetic.

If you want a less trivial example, look into Presburger arithmetic. This is the conventional axioms of arithmetic, with multiplication completely omitted. Now Presburger arithmetic is complete, because it cannot even express statements about multiplication. So add back to the language the formulas involving the multiplication symbol, but not the axioms for dealing with multiplication. This system can express the claims that $1\times1=1$ and that $6\times7=41$, but it is incomplete because can prove neither these claims nor their negations. (It is obviously consistent, and strictly weaker than conventional arithmetic.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.