[FOM] Compactness of second order propositional logic
Guillermo Badia
guillebadia89 at gmail.com
Mon Apr 27 21:21:08 EDT 2015
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150428/86054a1e/attachment.html>
More information about the FOM
mailing list