Narrow Results

We prove that the class K(σ) of all algebraic structures of signature σ is Q-universal if and only if there is a class K ⊆ K(σ) such that the problem whether a finite lattice embeds into the lattice of K-quasivarieties is undecidable.

We find sufficient conditions guaranteeing that for a quasivariety $M$ of structures of finite type containing a $\mathrm{\text{B}}$-class with respect to $M$, there exists a subquasivariety $K\subseteq M$ and a structure ${𝒜}\in K$ such that the problems whether a finite lattice embeds into the lattice $\mathrm{\text{Lv}}(K)$ of $K$-varieties and into the lattice ${Con}_K{𝒜}$ are undecidable.

We consider a natural generalization of the concept of order of an element in a group $G$: an element $g\in G$ is said to have order $k$ in a subgroup $H$ (respectively, in a coset $Hu$) of $G$ if $k$ is the first strictly positive integer such that $g^k\in H$ (respectively, $g^k\in Hu$). We study this notion and its algorithmic properties in the realm of free groups and some related families.

Both positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (i.e. the set of elements of a given order) with respect to finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum; in particular, non-recursive and even not computably enumerable sets of natural numbers. Also, we take advantage of Mikhailova’s construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups.