Gibt es eine "auflistbare" Struktur mit berechenbarer Dimension? $\omega$?

Nov 29 2020

Sagen Sie, dass eine (zählbare, berechenbare Sprache) Struktur$\mathfrak{A}$hat berechenbare Dimension$\omega$ Wenn es unendlich viele berechenbare Kopien von gibt $\mathfrak{A}$bis zum berechenbaren Isomorphismus. Das einfachste Beispiel für eine solche Struktur ist wahrscheinlich die lineare Ordnung$\mathfrak{O}=(\omega;<)$.

Jetzt $\mathfrak{O}$- und alle mir bekannten "natürlichen" Strukturen erfüllen eine Art "Produktivitäts" -Bedingung, bei der wir bei einer berechenbaren Folge berechenbarer Kopien eine neue berechenbare Kopie erstellen können, die nicht rechnerisch isomorph zu einer der Kopien in der ist Reihenfolge. Andererseits gibt es künstlichere Strukturen mit berechenbarer Dimension$\omega$für die es überhaupt keinen unendlichen Satz berechenbarer Kopien gibt, was natürlich die Produktivität verhindert. (Siehe hier für Details.)

Ich bin daran interessiert, ob ein drittes extremes Verhalten auftreten kann. Sagen Sie, dass eine Struktur$\mathfrak{A}$ist auflistbar, wenn es eine berechenbare Folge von berechenbaren Kopien von gibt$\mathfrak{A}$ so dass jede berechenbare Kopie von $\mathfrak{A}$ist rechnerisch isomorph zu einer dieser Kopien. Die Auflistbarkeit widerspricht eindeutig den beiden im vorherigen Absatz genannten Verhaltensweisen.

Gibt es eine auflistbare Struktur mit berechenbarer Dimension? $\omega$?

Antworten

4 DanTuretsky Nov 30 2020 at 06:39

Ja. Hirschfeldt und Khoussainov bauten eine solche Struktur. Siehe den Anfang von Abschnitt 3 auf Seite 1208. Tatsächlich ist ihre Auflistung injektiv (in Äquivalenzklassen modulo berechenbarer Isomorphismus). Interessanterweise betrachten sie auch die Idee einer produktiven Struktur, obwohl sie sie "effektiv unendlich berechenbare Dimension" nennen; siehe Seite 1200.