Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Note on Computable Embeddings for Ordinals and Their Reverses
67
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
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$.
We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $omega^{omega^omega}$. Then we show that the injectively $omega^n$-automatic ordinals, where $n>0$ is an integer, are the ordinals smaller than $omega^{omega^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11] the subclasses of finite word $omega^n$-automatic ordinals. As a by-product we obtain that the hierarchy of injectively $omega^n$-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.
Given a cardinal $kappa$ and a sequence $left(alpha_iright)_{iinkappa}$ of ordinals, we determine the least ordinal $beta$ (when one exists) such that the topological partition relation [betarightarrowleft(top,alpha_iright)^1_{iinkappa}] holds, including an independence result for one class of cases. Here the prefix $top$ means that the homogeneous set must have the correct topology rather than the correct order type. The answer is linked to the non-topological pigeonhole principle of Milner and Rado.
We study the topological version of the partition calculus in the setting of countable ordinals. Let $alpha$ and $beta$ be ordinals and let $k$ be a positive integer. We write $betato_{top}(alpha,k)^2$ to mean that, for every red-blue coloring of the collection of 2-sized subsets of $beta$, there is either a red-homogeneous set homeomorphic to $alpha$ or a blue-homogeneous set of size $k$. The least such $beta$ is the topological Ramsey number $R^{top}(alpha,k)$. We prove a topological version of the ErdH{o}s-Milner theorem, namely that $R^{top}(alpha,k)$ is countable whenever $alpha$ is countable. More precisely, we prove that $R^{top}(omega^{omega^beta},k+1)leqomega^{omega^{betacdot k}}$ for all countable ordinals $beta$ and finite $k$. Our proof is modeled on a new easy proof of a weak version of the ErdH{o}s-Milner theorem that may be of independent interest. We also provide more careful upper bounds for certain small values of $alpha$, proving among other results that $R^{top}(omega+1,k+1)=omega^k+1$, $R^{top}(alpha,k)< omega^omega$ whenever $alpha<omega^2$, $R^{top}(omega^2,k)leqomega^omega$ and $R^{top}(omega^2+1,k+2)leqomega^{omegacdot k}+1$ for all finite $k$. Our computations use a variety of techniques, including a topological pigeonhole principle for ordinals, considerations of a tree ordering based on the Cantor normal form of ordinals, and some ultrafilter arguments.
We define a collection of topological Ramsey spaces consisting of equivalence relations on $omega$ with the property that the minimal representatives of the equivalence classes alternate according to a fixed partition of $omega$. To prove the associated pigeonhole principles, we make use of the left-variable Hales-Jewett theorem and its extension to an infinite alphabet. We also show how to transfer the corresponding infinite-dimensional Ramsey results to equivalence relations on countable limit ordinals (up to a necessary restriction on the set of minimal representatives of the equivalence classes) in order to obtain a dual Ramsey theorem for such ordinals.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
