FOM: Re: 2nd-order logic

[Marcin Mostowski]

I do not know what exactly Boolos was thinking of, but I know very well an
example because it is from my own papers. It is the logic with branched
(Henkin) quantifiers with dualization.

You take the following composition rules
1. for each variable x, the following are prefixes: Ex, Ax;
2. if Q and Q' are prefixes then the following are prefixes: (QQ') -
horizontal composition, (Q/Q') - vertical composition, and Q^d - the
dualization of Q.

The dualization means that Q^d is equivalent to ~Q~, which trivially is
first-order definable, but not in a context of vertical compositions.
Without dualization you will get the logic with Henkin quantifiers, but with
dualization you will obtain just the logic equivalent to the second order
logic.

 For the first time it was presented at LMPhS 1987 in Moscow. For a
reference with detailed discussion see "Quantifiers" (ed-s:
Krynicki-M.Mostowski-Szczerba) Kluwer 1995, in vol. 1 the survey by me and
M. Krynicki "Henkin Quantifiers", and in vol. 2 my paper "Quantifiers
definable by second order means". In the first paper you can find also some
philosophical comments.

Other - earlier - known to me example is the logic defined by David Harel
(ZMLGM year ?), about which he erroniousely has claimed that it was
equivalent to the logic with Henkin quantifiers L^*.

Actually it is known that is semantically strongly between boolean
combinations of Sigma^1_1 and Delta^1_2.

Anyway you can always obtain second order logic from the first order one by
adding countably many Lindstrom generalized quantifiers - but the
construction is slightly artificial one. The most natural (which I know) is
that mentioned at the begining.

Marcin Mostowski

----- Original Message -----
From: "Vann McGee" <vmcgee at mit.edu>
To: <fom at math.psu.edu>
Sent: Wednesday, March 14, 2001 1:39 AM
Subject: FOM: 2nd-order logic


> George Boolos told me about a result about second-order logic which was
> apparently known in the literature, though not know to me. I have,
> unfortunately, lost the reference, and my memory is sketchy, but it went
> something like this: There is an exotic form of quantification with the
> following property: for any second-order sentence, one can find a
logically
> equivalent sentence that uses the exotic quantifier as well as the logical
> operations from first-order logic, but doesn't use any second-order
> variables. George reported to me that Quine regarded this result as
> answering his principal objections to second-order logic.
>
> I am hoping that someone in the fom group will know what I'm talking about
> and can give me a citation. I would be very grateful.
>
> Yours,
> Vann McGee
>
>