Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Chris Eagle May 4 '12 at 15:55
    
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 –  Hernán Eche May 4 '12 at 16:00

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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