Consistent but incomplete formal axiomatic systems

1.3k Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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