اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدComputable embeddings for pairs of linear orders
83
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
We continue the study of 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 although ${omega cdot 2, omega^star cdot 2}$ is computably embeddable in ${omega^2, {(omega^2)}^star}$, the class ${omega cdot k,omega^star cdot k}$ is emph{not} computably embeddable in ${omega^2, {(omega^2)}^star}$ for any natural number $k geq 3$.
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 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.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
