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
Sitemap
To content Read more about how we use cookies on gu.se

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
Links www.math.helsinki.fi/logic/sellc-20...
Keywords Logical constants, Borel, Generalized quantifiers
Subject categories Mathematical logic, Logic

Abstract

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
Share:

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?