12 problems

Let $m\geq 1$. Write $\mathcal{A}_{m+1}$ for the canonical tree of rank $m+1$, and let $B^{(m)}_j:=[m+1:j]$ be the tree obtained by deleting all but $j$ of the level-one subtrees o…

The corresponding index set is $[?]$

The paper considers the preceding question, whose notation and precise formulation are not included in the supplied passage. Positive-answer conjecture. The question has a positive…

A Turing degree is low$_n$ if its $n$th Turing jump has the same degree as the $n$th jump of the computable degree. Consider spectra of structures, namely the sets of Turing degree…

A group is finitely generated if it has a finite generating set. A Scott sentence is an infinitary sentence whose countable models are exactly the structures isomorphic to the give…

Khoussainov's conjectures. (1) No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.…

Let $G$ be a finitely presented computable group. A computable $d$-$\Sigma_2$ Scott sentence is a Scott sentence for $G$ that is the conjunction of a computable $\Sigma_2$ sentence…

Let a typical group mean a randomly chosen finitely generated group with a single relator, in the sense of Kapovich and Schupp. A $d$-$\Sigma_2$ Scott sentence is a Scott sentence…

Index-set and optimal-Scott-sentence complexity conjecture. The complexity of the index set of $G$ should equal the complexity of an optimal Scott sentence for $G$.

The procedure concerns coding an undirected graph $G$ into a structure in a class $\mathcal{C}$. Suppose the relevant fibers and types satisfy the same conditions as in the graph-c…

Let $n\geq 1$ and let a countable $\omega^n$-automatic structure mean a structure with a countable domain admitting an $\omega^n$-automatic presentation. Injective presentation con…

Let $G$ be a computable connected graph whose distance function is intrinsically $n$-approximable from above, where $n>0$. A function is $n$-approximable from above if it has an ap…