Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe strength of compactness for countable complete linear orders
162
0
0.0
(
0
)
Authors
Paul Shafer
Ask ChatGPT about the research
No Arabic abstract
We investigate the statement the order topology of every countable complete linear order is compact in the framework of reverse mathematics, and we find that the statements strength depends on the precise formulation of compactness. If we require that open covers must be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to $mathsf{WKL}_0$ over $mathsf{RCA}_0$. If open covers need not be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to $mathsf{ACA}_0$ over $mathsf{RCA}_0$. This answers a question of Franc{c}ois Dorais.
rate research
Read More
We study computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that ${omega cdot k,omega^star cdot k}$ is computably embeddable in ${omega cdot t, omega^star cdot t}$ iff $k$ divides $t$.
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)$.
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.
We introduce the notion of tau-like partial order, where tau is one of the linear order types omega, omega*, omega+omega*, and zeta. For example, being omega-like means that every element has finitely many predecessors, while being zeta-like means that every interval is finite. We consider statements of the form any tau-like partial order has a tau-like linear extension and any tau-like partial order is embeddable into tau (when tau is zeta this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to BSigma^0_2 or to ACA_0 over the usual base system RCA_0.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
