0
$\begingroup$

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

  • 0
    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. thanks2012-05-04

1 Answers 1

4

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