[FOM] Compactness of second order propositional logic
Alasdair Urquhart
urquhart at cs.toronto.edu
Thu Apr 30 12:17:43 EDT 2015
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
>
>
>
>
More information about the FOM
mailing list