|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2010, Volume 7, Pages 100–110
(Mi semr231)
|
|
|
|
Research papers
On automatic and decidable linear orderings
A. A. Gavryushkina Novosibirsk State University
Abstract:
Let $\EuScript A$ be the class of automatic linear orderings, $\EuScript{AA}$ be the class of linear orderings which are computably categorical in the class of automatic presentation, $\EuScript{AD}$ be the class of linear orderings which are computably categorical in the class of decidable presentations. Obviously,
$\EuScript{AD}\cap\EuScript A\subset\EuScript{AD}$. Since all automatic structures are decidable,
$\EuScript{AD}\cap\EuScript A\subset\EuScript{AA}$, and one can easily see that
$\EuScript{AD}\cap\EuScript A$ is nonempty. We show that there exist a linear order $\mathcal L_1\in\EuScript{AA}$ such that $\mathcal L_1\notin\EuScript{AD}$ and a linear order
$\mathcal L_2\in\EuScript{AD}$ such that $\mathcal L_2\notin\EuScript A$. By this, the inclusions
$\EuScript{AD}\cap\EuScript A\subset\EuScript{AD}$ and
$\EuScript{AD}\cap\EuScript A\subset\EuScript{AA}$ are proper. In addition, we construct an example of a non–automatic linear order which is decidable in the language with the additional quantifier $\exists^\infty$.
Keywords:
automatic structure, decidable structure, linear ordering, computable categoricity.
Received March 4, 2010, published April 20, 2010
Citation:
A. A. Gavryushkina, “On automatic and decidable linear orderings”, Sib. Èlektron. Mat. Izv., 7 (2010), 100–110
Linking options:
https://www.mathnet.ru/eng/semr231 https://www.mathnet.ru/eng/semr/v7/p100
|
Statistics & downloads: |
Abstract page: | 257 | Full-text PDF : | 60 | References: | 42 |
|