We study the algorithmic complexity of isomorphic embeddings between computable structures. Suppose that L is a language. We say that L-structures A and B are bi-embeddable (denoted A ≈ B) if there are isomorphic embeddings f : A → B and g : B → A. The systematic investigation of the bi-embeddability relation in computable structure theory was initiated by Montalb´an [1, 2]: he proved that any hyperarithmetical linear order is bi-embeddable with a computable one. In [3], similar results were obtained for Abelian p-groups, Boolean algebras, and compact metric spaces. The paper [4] studies degree spectra with respect to bi-embeddability.
Bazhenov, N.A., Fokina, E.B., Rossegger, D., San Mauro, L. (2018). Computable Bi-Embeddable Categoricity. ALGEBRA AND LOGIC, 57(5), 392-396 [10.1007/s10469-018-9511-8].
Computable Bi-Embeddable Categoricity
San Mauro L.
2018-01-01
Abstract
We study the algorithmic complexity of isomorphic embeddings between computable structures. Suppose that L is a language. We say that L-structures A and B are bi-embeddable (denoted A ≈ B) if there are isomorphic embeddings f : A → B and g : B → A. The systematic investigation of the bi-embeddability relation in computable structure theory was initiated by Montalb´an [1, 2]: he proved that any hyperarithmetical linear order is bi-embeddable with a computable one. In [3], similar results were obtained for Abelian p-groups, Boolean algebras, and compact metric spaces. The paper [4] studies degree spectra with respect to bi-embeddability.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Bazhenov2018_Article_ComputableBi-EmbeddableCategor.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
162.46 kB
Formato
Adobe PDF
|
162.46 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1116002