[FOM] Compactness of second order propositional logic

[Richard Zach]

This depends on what classes of Kripke models you take. With 
second-order quantifiers you can express properties that you can't 
express in first-order intuitionistic propositional logic. For instance, 
if your Kripke structures are trees -- for with propositional and fo 
logic are complete --, the logic is decidable.

Regards,
Richard

On 2015-04-26 12:13 PM, Alasdair Urquhart 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
>
>
>

-- 
Richard Zach ...... http://www.ucalgary.ca/rzach/
Professor,             Department  of  Philosophy
University of Calgary, Calgary AB T2N 1N4, Canada