Search

We study degree spectra of structures with respect to the bi‐embeddability relation. The bi‐embeddability spectrum of a structure is the family of Turing degrees of its bi‐embeddable copies. To facilitate our study we introduce the notions of bi‐embeddable triviality and basis of a spectrum. Using bi‐embeddable triviality we show that several known families of degrees are bi‐embeddability spectra of structures. We then characterize the bi‐embeddability spectra of linear orderings and study bases of bi‐embeddability spectra of strongly locally finite graphs. [ABSTRACT FROM AUTHOR]

We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type Inf Ex ≅ , consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is Inf Ex ≅ -learnable if and only if the structures can be distinguished in terms of their Σ 2 inf -theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable. [ABSTRACT FROM AUTHOR]