首页 | 本学科首页   官方微博 | 高级检索  
     


Isomorphism of lattices of recursively enumerable sets
Authors:Todd Hammond
Affiliation:Division of Mathematics and Computer Science, Truman State University, Kirksville, Missouri 63501
Abstract:Let $omega = {,0,1,2,ldots ,}$, and for $Asubseteq omega$, let $mathcal E^A$ be the lattice of subsets of $omega $ which are recursively enumerable relative to the ``oracle' $A$. Let $(mathcal E^A)^*$ be $mathcal E^A/mathcal I$, where $mathcal I$ is the ideal of finite subsets of $omega $. It is established that for any $A,Bsubseteq omega$, $(mathcal E^A)^*$ is effectively isomorphic to $(mathcal E^B)^*$ if and only if $A'equiv _T B'$, where $A'$ is the Turing jump of $A$. A consequence is that if $A'equiv _T B'$, then $mathcal E^Acong mathcal E^B$. A second consequence is that $(mathcal E^A)^*$ can be effectively embedded into $(mathcal E^B)^*$ preserving least and greatest elements if and only if $A'leq _T B'$.

Keywords:Effective isomorphism   effectively isomorphic   recursively enumerable   oracle   Turing jump   effective embedding   effectively embeddable.
点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息
点击此处可从《Transactions of the American Mathematical Society》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号