Имеет ли «продуктивность = измерение» $\omega$”Для вычислимых структур?
По аналогии с терминологией для множеств , скажем , что (счетная, вычислимый язык) структура$\mathfrak{A}$является продуктивным, если существует вычислимый способ правильно расширить любой вычислимый список типов вычислимого изоморфизма вычислимых копий$\mathfrak{A}$. То есть,$\mathfrak{A}$ является продуктивным, если существует некоторая частично вычислимая функция $F$ такой, что для всех $a,b$:
Если $W_a=\overline{W_b}$, и каждый элемент $W_a$ индекс вычислимой копии $\mathfrak{A}$, тогда $F(a,b)$ определен и является индексом для вычислимой копии $\mathfrak{A}$ не вычислимо изоморфна ни одной из копий с индексами в $W_a$.
("$W_a=\overline{W_b}$"-бит просто говорит, что $W_a$ на самом деле вычислимый, а не просто вычислимый набор имен для копий $\mathfrak{A}$, и мы передаем этот набор $F$ как вычислимое множество, а не перечислимое множество.)
Напомним, что вычислимая размерность структуры - это количество вычислимых копий, которые она имеет с точностью до изоморфизма. Очевидно, что любая продуктивная структура должна иметь вычислимую копию (возьмите$W_a=\emptyset$) и должен иметь вычислимую размерность $\omega$ (повторять $F$соответственно). Однако мне не ясно обратное. У меня вопрос:
Каждая вычислимая структура с вычислимой размерностью $\omega$ продуктивный?
Все «естественные» примеры, которые я могу придумать, легко увидеть как продуктивные, но я не вижу здесь работающих общих принципов. В литературе есть различные результаты схожего «вкуса», такие как работа Монтальбана по копированию / диагонализации игр, но ни один из тех, о которых я знаю, не имеет прямого отношения.
Я подозреваю, что ответ на этот вопрос «хрупкий» в том смысле, что существует вычислимая структура с бесконечной вычислимой размерностью, которая непродуктивна, но что каждая структура либо вычислимо категорична на конусе, либо «продуктивна на конусе» в соответствующем смысле; это мотивировано (общей извращенностью и) комбинацией теоремы Гончарова о том, что существуют вычислимые структуры вычислимой размерности строго между$1$ и $\omega$, и теорема МакКоя о том, что каждая структура либо вычислимо категорична на конусе, либо имеет вычислимую размерность $\omega$ на конусе.
Ответы
Ответ на ваш первый ответ - нет.
Мой ответ основан на моей конструкции , но может быть более простой подход. В этом случае вы берете вычислимое дерево в$\omega^{<\omega}$ и получить $\Delta^0_3$преобразование дерева и вычислимо категоричная структура, при которой нетривиальные автоморфизмы структуры в основном являются путями через преобразованное дерево. Если в вашем стартовом дереве нет$\Delta^0_3$путей, а затем вы помечаете конкретный элемент структуры константой, копии расширенной структуры по модулю вычислимого изоморфизма соответствуют конечным подмножествам расширяемых узлов высоты 1 в дереве. Если бы у вас была продуктивная функция, как вы описываете, это позволило бы вам перечислить бесконечный набор расширяемых узлов (в преобразованном дереве, из которого вы могли бы вернуться к исходному дереву через$\Delta^0_3$карта). Итак, если вы начнете с дерева с бесконечным числом расширяемых узлов высотой 1, но не$\Delta^0_3$ набор из них, он будет иметь размер $\omega$ но не быть продуктивным.
Разделяю вашу интуицию, что такое поведение должно исчезнуть на конусе.