計算可能な次元の「リスト可能な」構造はありますか $\omega$？
言う（可算、計算言語）構造$\mathfrak{A}$計算可能な次元を持っています$\omega$ 計算可能なコピーが無限に多い場合 $\mathfrak{A}$計算可能な同型写像まで。このような構造の最も単純な例は、おそらく線形次数です。$\mathfrak{O}=(\omega;<)$。
今 $\mathfrak{O}$-そして私が知っているすべての「自然な」そのような構造-は一種の「生産性」条件を満たすものであり、計算可能なコピーの計算可能なシーケンスが与えられると、計算可能なコピーのいずれとも同型ではない新しい計算可能なコピーを計算可能に生成できます。シーケンス。一方で、計算可能な寸法の人工構造物が多くあります$\omega$計算可能なコピーの無限のセットがまったく存在しないため、もちろん生産性が妨げられます。（詳細はこちらをご覧ください。）
3番目の極端な動作が発生する可能性があるかどうかに興味があります。構造と言う$\mathfrak{A}$の計算可能なコピーの計算可能なシーケンスがある場合はリスト可能です$\mathfrak{A}$ そのようなすべての計算可能なコピー $\mathfrak{A}$それらのコピーの1つと計算上同型です。リスト可能性は、前の段落で述べた両方の動作と明らかに矛盾します。
計算可能な次元を持つリスト可能な構造はありますか $\omega$？
回答
はい。HirschfeldtとKhoussainovはそのような構造を構築しました。1208ページのセクション3の冒頭を参照してください。実際、それらのリストは単射です（計算可能な同型を法とする同値類に）。興味深いことに、彼らは生産的な構造のアイデアも検討していますが、それを「事実上無限の計算可能な次元」と呼んでいます。1200ページを参照してください。