[FOM] Weak categorical theories of arithmetic
Aatu Koskensilta
Aatu.Koskensilta at uta.fi
Mon Jun 11 05:59:37 EDT 2012
I asked for an example of an axiomatizable, and preferably finitely
axiomatizable, second-order theory of arithmetic that's categorical
but proof-theoretically weak. Unless I'm mistaken, I can now answer
this question.
Here's an example with infinitely many axioms, using the failure of
compactness for second-order logic. We simply take as axioms every
sentence of the form
0 =/= 1 & 1 =/= 2 & 2 =/= 0 & 2 =/= 3 & 3 =/= 1 & 3 =/= 0 & ... ,
saying that the first n numerals name distinct objects, together with
If there are infinitely many objects, the usual axioms of
second-order arithmetic hold.
We also know that the set of sentences that have no finite models
is not recursively enumerable (by Trakhtenbroth's theorem). So for any
given system of (sound) rules of inference, there is necessarily a
sentence A such that A |= "there are infinitely many objects" but not
A |- "there are infinitely many objects". We get a proof-theoretically
weak but categorical finitely axiomatizable theory by taking as axioms
such an A and "if there are infinitely many objects, the usual axioms
of second-order arithmetic hold". Perhaps someone can think of a nice
A (for a standard deductive system for second-order logic)?
--
Aatu Koskensilta (aatu.koskensilta at uta.fi)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
More information about the FOM
mailing list