Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHanf Number for Scott Sentences of Computable Structures
121
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
In [13] the authors show that if $mu$ is a strongly compact cardinal, $K$ is an Abstract Elementary Class (AEC) with $LS(K)<mu$, and $K$ satisfies joint embedding (amalgamation) cofinally below $mu$, then $K$ satisfies joint embedding (amalgamation) in all cardinals $ge mu$. The question was raised if the strongly compact upper bound was optimal. In this paper we prove the existence of an AEC $K$ that can be axiomatized by an $mathcal{L}_{omega_1,omega}$-sentence in a countable vocabulary, so that if $mu$ is the first measurable cardinal, then (1) $K$ satisfies joint embedding cofinally below $mu$ ; (2) $K$ fails joint embedding cofinally below $mu$; and (3) $K$ satisfies joint embedding above $mu$. Moreover, the example can be generalized to an AEC $K^chi$ axiomatized in $mathcal{L}_{chi^+, omega}$, in a vocabulary of size $chi$, such that (1)-(3) hold with $mu$ being the first measurable above $chi$. This proves that the Hanf number for joint embedding is contained in the interval between the first measurable and the first strongly compact. Since these two cardinals can consistently coincide, the upper bound from [13] is consistently optimal. This is also the first example of a sentence whose joint embedding spectrum is (consistently) neither an initial nor an eventual interval of cardinals. By Theorem 3.26, it is consistent that for any club $C$ on the first measurable $mu$, JEP holds exactly on $lim C$ and everywhere above $mu$.
We obtain a computable structure of Scott rank omega_1^{CK} (call this ock), and give a general coding procedure that transforms any hyperarithmetical structure A into a computable structure A such that the rank of A is ock, ock+1, or < ock iff the same is true of A.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
