Font Size:
Definable subsets of finite structures and applications
Last modified: 2014-02-01
Abstract
\documentclass[11pt]{article}
\usepackage{amsmath} \usepackage{amsthm} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{authblk} \theoremstyle{plain} \newtheorem*{theorem*}{Theorem} \newtheorem{theorem}{Theorem} \newtheorem*{cor*}{Corollary} \title{Definable subsets of finite structures and applications} \author[1]{\v Zarko Mijajlovi\'c} \author[2]{Aleksandar Pejovi\'c} \affil[1]{Faculty of Mathematics, Univ. of Belgrade, Serbia zarkom{@}matf.bg.ac.rs} \affil[2]{Institute of Mathematics, SASA, Belgrade, Serbia pejovica{@}mi.sanu.ac.rs}
\begin{document} \date{}
\maketitle
Let $\bf A$ be a model of a first-order language $L$ and $X\subseteq A$. We say that $X$ is definable in $\bf A$ if $X= \{a\in A| {\bf A}\models \varphi(a)\}$ where $\varphi(x)$ is a formula of $L$. Also, $X$ is absolutely invariant in $\bf A$ if for all $f\in {\rm Aut}({\bf A})$, $f(X)\subseteq X$. Using Svenonius definability theorem [\ref{Svenonius}], we describe various definable subsets of a finite model $\bf A$. For example we proved: \begin{theorem*} Let $\bf A$ be a finite model of $L$ and $X\subseteq A$. Then $X$ is absolutely invariant in $\bf A$ if and only if $X$ is definable in $\bf A$. \end{theorem*} \begin{cor*} Let $\bf A$ be a finite model of finite $L$. If $a\in A$ is fixed by all automorphisms of $\bf A$ then $a$ is definable in $\bf A$ by a formula $\varphi(x)$ of $L$. ${\rm Aut}({\bf A})= \{i_A\}$ if and only if every element of $A$ is definable in $\bf A$. \end{cor*} Using definability theory of finite structures, we developed a parallel program for computing related structures to finite models. Examples include finite labeled and unlabeled models of a first order theory, their numbers and ${\rm Aut}({\bf A})$ of a finite model $\bf A$.
\begin{thebibliography}{}
\bibitem{1}\label{Mijajlo} \v Z. Mijajlovi\'c, A. Pejovi\'c, {\it Computing finite models using free Boolean generators}, arXiv:1310.6978, 2013. \bibitem{2}\label{Svenonius} L. Svenonius {\it A theorem on permutations in models}, Theoria 25(3), 173-178, 1959.
\end{thebibliography}{}
\end{document}
\usepackage{amsmath} \usepackage{amsthm} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{authblk} \theoremstyle{plain} \newtheorem*{theorem*}{Theorem} \newtheorem{theorem}{Theorem} \newtheorem*{cor*}{Corollary} \title{Definable subsets of finite structures and applications} \author[1]{\v Zarko Mijajlovi\'c} \author[2]{Aleksandar Pejovi\'c} \affil[1]{Faculty of Mathematics, Univ. of Belgrade, Serbia zarkom{@}matf.bg.ac.rs} \affil[2]{Institute of Mathematics, SASA, Belgrade, Serbia pejovica{@}mi.sanu.ac.rs}
\begin{document} \date{}
\maketitle
Let $\bf A$ be a model of a first-order language $L$ and $X\subseteq A$. We say that $X$ is definable in $\bf A$ if $X= \{a\in A| {\bf A}\models \varphi(a)\}$ where $\varphi(x)$ is a formula of $L$. Also, $X$ is absolutely invariant in $\bf A$ if for all $f\in {\rm Aut}({\bf A})$, $f(X)\subseteq X$. Using Svenonius definability theorem [\ref{Svenonius}], we describe various definable subsets of a finite model $\bf A$. For example we proved: \begin{theorem*} Let $\bf A$ be a finite model of $L$ and $X\subseteq A$. Then $X$ is absolutely invariant in $\bf A$ if and only if $X$ is definable in $\bf A$. \end{theorem*} \begin{cor*} Let $\bf A$ be a finite model of finite $L$. If $a\in A$ is fixed by all automorphisms of $\bf A$ then $a$ is definable in $\bf A$ by a formula $\varphi(x)$ of $L$. ${\rm Aut}({\bf A})= \{i_A\}$ if and only if every element of $A$ is definable in $\bf A$. \end{cor*} Using definability theory of finite structures, we developed a parallel program for computing related structures to finite models. Examples include finite labeled and unlabeled models of a first order theory, their numbers and ${\rm Aut}({\bf A})$ of a finite model $\bf A$.
\begin{thebibliography}{}
\bibitem{1}\label{Mijajlo} \v Z. Mijajlovi\'c, A. Pejovi\'c, {\it Computing finite models using free Boolean generators}, arXiv:1310.6978, 2013. \bibitem{2}\label{Svenonius} L. Svenonius {\it A theorem on permutations in models}, Theoria 25(3), 173-178, 1959.
\end{thebibliography}{}
\end{document}
Keywords
finite model theory, parallel computing