Till sidans topp

Sidansvarig: Webbredaktion

Non-Permutation Invariant… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

# Non-Permutation Invariant Borel Quantifiers

Paper i proceeding
Författare Fredrik Engström Philipp Schlicht Workshop on Logic, Language and Computation & The 9th International Conference on Logic and Cognition 2010 Institutionen för filosofi, lingvistik och vetenskapsteori en www.math.helsinki.fi/logic/sellc-20... Logical constants, Borel, Generalized quantifiers Matematisk logik, Logik

## Sammanfattning

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.