[FOM] IF logic (fwd)

[Marcin Mostowski]

_____________________

Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University


----------Forwarded message ----------
From: "Marcin Mostowski" <m.mostowski at uw.edu.pl>
To: fom at cs.nyu.edu
Subject: IF logic
Date: Sun, 28 Dec 2003 13:50:13 GMT
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-2"
Content-Transfer-Encoding: 7bit



 IF logic is - in a sense - a variant of the logic with Henkin quantifiers
with slightly exotic sematics. The truth of a formula is defined as
existence of a winning strategy, what implies that each sentence of this
logic is equivalent to an existential second order formula ($\Sigma_1^1$).
On the other hand simple formulae of the form Q\phi, where Q is a
quantifier prefix (in the sense of IF logic) and \phi is first order, are
equivalent to simple formulae with Henkin prefixes (in this case Q should
be treated as a Henkin prefix).
 In 1970, independently Enderton and Walkoe have proved that each
$\Sigma_1^1$-sentence is equivalent to a simple formula with Henkin prefix.
It follows that the expressive power of sentences of IF logic is exactly
the same as that of $\Sigma_1^1$ second order sentences. Therefore it is
essentially stronger than that of first order logic.
 By the way the first known example of a statement essentially using
nonlinear quantification non expressible in first order logic was given by
Andrzej Ehrenfeucht. His sentence says that the universe is Dedekind
infinite. This example was presented in the paper by Henkin in 1961.
 All these classical results and their improvements you can find in the
survey &#8220;Henkin Quantifiers&#8221; by M. Krynicki and M. Mostowski, in
Quantifiers vol. 1 (ed-s:  M. Krynicki, M. Mostowski, and L. W. Szczerba),
Kluwer Pub. Co. 1995.


_____________________

Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University