[FOM] Compactness of second order propositional logic

[Alasdair Urquhart]

I believe that the compactness theorem fails for second order 
propositional relevant logic, for the same reason it fails for
second order intuitionistic propositional logic.  The non-axiomatisability
result of Philip Kremer can, I think, be strengthened to a proof
that the system defined by the second order propositional model
theory for relevant logic is recursively isomorphic to full second order 
classical logic.

Assuming this, I believe that the classical failure of compactness
in second order classical logic can be transferred to the second
order propositional logic.  There is a simple proof of the
classical failure in the entry on second order logic in
the online Stanford Encyclopedia of Philosophy.

I haven't checked the details of these claims, but I think they
are likely correct, because the encoding technique used by
Kremer for second order intuitionistic propositional logic
is quite generally applicable.


On Tue, 28 Apr 2015, Guillermo Badia wrote:

> Dear Prof. Urquhart,
> Thanks very much for your answer. Let me just try to understand something. I was actually interested in the particular case of second order propositional relevant logic, so it's
> interesting that you mentioned Kremer's paper. From the fact that the validities of the second order proportional relevant language over your models for R is not recursively
> axiomatizable as shown in Kremer's paper, does it follow that compactness fails in the sense of there being a set of formulas which is finitely satisfiable but has no model? Could
> you help me see why?
> 
> Kindest regards,
> Guillermo
> 
> 
> 
> On Mon, Apr 27, 2015 at 4:13 AM, Alasdair Urquhart <urquhart at cs.toronto.edu> wrote:
>       Classical second order propositional logic is certainly compact,
>       since you can use quantifier elimination to reduce any
>       second order formula to an equivalent formula without
>       quantifiers.
>
>       If you take second order intuitionistic propositional logic to be defined
>       by Kripke models, with the quantifiers ranging over
>       increasing subsets of frames, then it is not recursively axiomatizable
>       (Skvortsov, APAL Volume 86, pp. 33-46).
>
>       Independently of Skvortsov, Philip Kremer proved that this logic
>       is recursively isomorphic to full second order classical logic
>       (JSL, Volume 62, pp. 529-544).  It follows that this logic
>       is not compact.
>
>       On Sun, 19 Apr 2015, Guillermo Badia wrote:
>
>       Dear all,
>       Are second order propositional languages compact?
>
>       Thanks,
>       Guillermo
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 
> 
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 
> 
> 
>