Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe complexity of Scott sentences of scattered linear orders
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a countable scattered linear order $L$ of Hausdorff rank $alpha < omega_1$ we show that it has a $dtext{-}Sigma_{2alpha+1}$ Scott sentence. Ash calculated the back and forth relations for all countable well-orders. From this result we obtain that this upper bound is tight, i.e., for every $alpha < omega_1$ there is a linear order whose optimal Scott sentence has this complexity. We further show that for all countable $alpha$ the class of Hausdorff rank $alpha$ linear orders is $pmb Sigma_{2alpha+2}$ complete.
rate research
Read More
We give effecti
We give Scott sentences for certain computable groups, and we use index set calculations as a way of checking that our Scott sentences are as simple as possible. We consider finitely generated groups and torsion-free abelian groups of finite rank. For both kinds of groups, the computable ones all have computable $Sigma_3$ Scott sentences. Sometimes we can do better. In fact, the computable finitely generated groups that we have studied all have Scott sentences that are computable $d$-$Sigma_2$ (the conjunction of a computable $Sigma_2$ sentence and a computable $Pi_2$ sentence). This was already shown for the finitely generated free groups. Here we show it for all finitely generated abelian groups, and for the infinite dihedral group. Among the computable torsion-free abelian groups of finite rank, we focus on those of rank $1$. These are exactly the additive subgroups of $mathbb{Q}$. We show that for some of these groups, the computable $Sigma_3$ Scott sentence is best possible, while for others, there is a computable $d$-$Sigma_2$ Scott sentence.
The Hanf number for a set $S$ of sentences in $L_{omega_1,omega}$ (or some other logic) is the least infinite cardinal $kappa$ such that for all $varphiin S$, if $varphi$ has models in all infinite cardinalities less than $kappa$, then it has models of all infinite cardinalities. S-D. Friedman asked what is the Hanf number for Scott sentences of computable structures. We show that the value is $beth_{omega_1^{CK}}$. The same argument proves that $beth_{omega_1^{CK}}$ is the Hanf number for Scott sentences of hyperarithmetical structures.
Cohesive powers of computable structures can be viewed as effective ultraproducts over effectively indecomposable sets called cohesive sets. We investigate the isomorphism types of cohesive powers $Pi _{C}% mathcal{L}$ for familiar computable linear orders $mathcal{L}$. If $% mathcal{L}$ is isomorphic to the ordered set of natural numbers $mathbb{N}$ and has a computable successor function, then $Pi _{C}mathcal{L}$ is isomorphic to $mathbb{N}+mathbb{Q}times mathbb{Z}.$ Here, $+$ stands for the sum and $times $ for the lexicographical product of two orders. We construct computable linear orders $mathcal{L}_{1}$ and $mathcal{L}_{2}$ isomorphic to $mathbb{N},$ both with noncomputable successor functions, such that $Pi _{C}mathcal{L}_{1}mathbb{ }$is isomorphic to $mathbb{N}+% mathbb{Q}times mathbb{Z}$, while $Pi _{C}mathcal{L}_{2}$ is not$.$ While cohesive powers preserve all $Pi _{2}^{0}$ and $Sigma _{2}^{0}$ sentences, we provide new examples of $Pi _{3}^{0}$ sentences $Phi $ and computable structures $% mathcal{M}$ such that $mathcal{M}vDash Phi $ while $Pi _{C}mathcal{M}% vDash urcorner Phi .$
Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $omega$, $zeta$, and $eta$ denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of $omega$. If $mathcal{L}$ is a computable copy of $omega$ that is computably isomorphic to the standard presentation of $omega$, then every cohesive power of $mathcal{L}$ has order-type $omega + zetaeta$. However, there are computable copies of $omega$, necessarily not computably isomorphic to the standard presentation, having cohesive powers not elementarily equivalent to $omega + zetaeta$. For example, we show that there is a computable copy of $omega$ with a cohesive power of order-type $omega + eta$. Our most general result is that if $X subseteq mathbb{N} setminus {0}$ is either a $Sigma_2$ set or a $Pi_2$ set, thought of as a set of finite order-types, then there is a computable copy of $omega$ with a cohesive power of order-type $omega + sigma(X cup {omega + zetaeta + omega^*})$, where $sigma(X cup {omega + zetaeta + omega^*})$ denotes the shuffle of the order-types in $X$ and the order-type $omega + zetaeta + omega^*$. Furthermore, if $X$ is finite and non-empty, then there is a computable copy of $omega$ with a cohesive power of order-type $omega + sigma(X)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
