[FOM] Compactness of second order propositional logic
rzach at ucalgary.ca
Wed Apr 29 19:55:58 EDT 2015
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.
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
> 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?
>> FOM mailing list
>> FOM at cs.nyu.edu
Richard Zach ...... http://www.ucalgary.ca/rzach/
Professor, Department of Philosophy
University of Calgary, Calgary AB T2N 1N4, Canada
More information about the FOM