[FOM] Weak categorical theories of arithmetic

[Aatu Koskensilta]

   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