[FOM] Compactness of second order propositional logic

Guillermo Badia guillebadia89 at gmail.com
Fri May 1 19:57:39 EDT 2015


Dear Prof. Urquhart,
But what about compactness with respect to the Routley-Meyer
semantics? I think with respect to your semantics you should be right
since Kremer gives a way to interpret material implication, which
makes the claim that second order propositional relevant logic is as
expressive as full second order logic much more plausible. However, in
the case of the Routley-Meyer semantics he doesn't do this, in fact he
conjectures it's impossible.
Kind regards,
Guillermo

On 5/1/15, Alasdair Urquhart <urquhart at cs.toronto.edu> wrote:
> 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