To the top

Page Manager: Webmaster

Last update: 9/11/2012 3:13 PM

- University of Gothenburg
- Research
- Non-Permutation Invariant…

To content
Read more about how we use cookies on gu.se
# Non-Permutation Invariant Borel Quantifiers

## Abstract

Conference paper

Authors |
Fredrik Engström Philipp Schlicht |
---|---|

Published in | Workshop on Logic, Language and Computation & The 9th International Conference on Logic and Cognition |

Publication year | 2010 |

Published at |
Department of Philosophy, Linguistics and Theory of Science |

Language | en |

Links |
www.math.helsinki.fi/logic/sellc-20... |

Keywords | Logical constants, Borel, Generalized quantifiers |

Subject categories | Mathematical logic, Logic |

Countable models in a given countable relational signature $\tau$ can be represented as elements of the logic space $$X_{\tau}=\prod_{R\in \tau} 2^{\mathbb{N}^{a(R)}}$$ where $a(R)$ denotes the arity of the relation $R$. The Lopez-Escobar theorem states that any invariant Borel subset of the logic space is defined by a formula in $\La_{\omega_{1}\omega}$. By generalizing Vaught's proof of the theorem to sets of countable structures invariant under the action of a closed subgroup of the permutation group of the natural numbers, we get the following: \begin{prop} Suppose $G\leq S_{\infty}$ is closed and $\mathcal{F}$ is the family of orbits of $G$. Then every $G$-invariant Borel subset of $X_{\tau}$ is definable in $\La_{\omega_{1}\omega}(\mathcal{F})$. \end{prop} A generalized quantifier of type $\langle k\rangle$ on the natural numbers is a subset of $2^{\mathbb{N}^k}$. We consider the logic $\La_{\omega_1\omega}(Q)$. This is $\La_{\omega_1\omega}$ augmented by the quantifier $Q$ where the formula $Qx\varphi(x)$ has the fixed interpretation $\{x\in\mathbb{N}^k:\varphi(x)\}\in Q$. We study non-permutation invariant generalized quantifiers on the natural numbers and prove a variant of the Lopez-Escobar theorem for a subclass, called good quantifiers, of the quantifiers which are closed and downwards closed. \begin{prop} Suppose $Q$ is good. Then a subset of $X_{\tau}$ is Borel and $\Aut(Q)$-invariant if and only if it is definable in $\La_{\omega_{1}\omega}(Q)$. \end{prop} Moreover for every closed subgroup $G$ of the symmetric group $S_{\infty}$, there is a closed binary quantifier $Q$ such that the $G$-invariant subsets of the space of countable structures are exactly the $\La_{\omega_1\omega}(Q)$-definable sets. \begin{prop} Suppose $G$ is a closed subgroup of $S_{\infty}$. There is a good binary quantifier $Q_G$ with $G=\Aut(Q_G)$. \end{prop} We show that there is a version of the Lopez-Escobar theorem for clopen quantifiers and for finite boolean combinations of principal quantifiers (a quantifier is principal if it is of the form $Q_A=\set{X\subseteq \N^k: A\subseteq X}$) . \begin{prop} Supppose $Q$ is clopen or a finite boolean combination $Q$ of principal quantifiers. Then a subset of $X_{\tau}$ is Borel and $\Aut(Q)$-invariant if and only if it is definable in $\La_{\omega_{1}\omega}(Q)$. \end{prop} This is joint work with Philipp Schlicht.