اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCohesive Powers of Linear Orders
85
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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)$.
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 m
ain 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$.
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 th
at 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.
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 th
at 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 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 tha
t 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
