\input zb-basic
\input zb-ioport
\iteman{io-port 05693393}
\itemau{Kontinen, Juha}
\itemti{Definability of second order generalized quantifiers.}
\itemso{Arch. Math. Logic 49, No. 3, 379-398 (2010).}
\itemab
The article introduces a notion of when a second-order generalized quantifier $Q$ is definable in a logic $L$. The structures considered are always finite and the logics are always extensions of first-order logic, \text{FO}, by generalized (first or second-order) quantifiers. First it is shown that if $Q$ is definable in $\text{FO}(B)$, where $B$ is a collection of Lindstr\"om quantifiers, then $\text{FO}(Q,B)\equiv\text{FO}(B)$, i.e. the logics $\text{FO}(Q,B)$ and $\text{FO}(B)$ have the same expressive power on finite structures.  Then the paper focuses mostly on second-order generalized quantifiers of `type ((1))'; such a quantifier $Q$ corresponds to a class of finite second-order structures of the form $(M,G)$ where $G$ is a subset of $P(M)$, the powerset of $M$, which is closed under isomorphism. The author proves that if $B$ is the collection of all Lindstr\"om quantifiers and $Q$ a second-order generalized quantifier of type ((1)), then $Q$ is definable in $\text{FO}(B)$ {\it by a flat formula} if and only if, for some positive integer $n$, membership of $(M,G)$ in $Q$ depends only on whether $(M,G(n))$ belongs to $Q$, where $G(n)$ is the set of all $X$ in $G$ such that $|X| < n$ or $|M - X| < n$. Roughly speaking, a formula in $\text{FO}(B)$ is {\it flat} if no nesting occurs of an auxiliary first-order quantifier symbol which plays a role in the definition of $Q$ being definable in $\text{FO}(B)$.  The author proves that if $B$ is the collection of all Lindstr\"om quantifiers, then there are several generalized second-order quantifiers which are not definable in $\text{FO}(B)$; examples include $n$-ary second-order existential quantification, for every $n$. Furthermore, for every countable collection $B$ of Lindstr\"om quantifiers, there is a second-order generalized quantifier $Q$ of type ((1)) such that $\text{FO}(Q,B)\equiv\text{FO}(B)$ and $Q$ is not definable in $\text{FO}(B)$. Hence, the converse of the first result mentioned above does not hold. Finally, it is proved that if $B$ is the collection of all Lindstr\"om quantifiers, then there is a generalized second order quantifier $Q$ of type ((1)) such that $\text{FO}(Q)\equiv \text{FO}$ and $Q$ is not definable in $\text{FO}(B)$.
\itemrv{Vera Koponen (Uppsala)}
\itemcc{}
\itemut{second-order generalized quantifiers; Lindstr\"om quantifiers; definability}
\itemli{doi:10.1007/s00153-010-0177-8}
\end