To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Non-Permutation Invariant… - University of Gothenburg, Sweden Till startsida
To content Read more about how we use cookies on

Non-Permutation Invariant Borel Quantifiers

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
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.

Page Manager: Webmaster|Last update: 9/11/2012

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?