Take the 2-minute tour ×

Say that a class $\mathcal{C}$ of countable first-order structures in some finite signature has the effective substructure property if $\mathcal{C}$ is closed under isomorphism and whenever $A\in \mathcal{C}$ has domain $\subseteq\omega$ and $B\in\mathcal{C}$ is isomorphic to a substructure of $A$, then $B$ has a presentation computable relative to $A$. My question is: what are some natural classes of structures with the effective substructure property, and what is a good source to learn about this property?

Some examples. The ur-example is the class $\mathcal{W}$ of all countable well-orders. $\mathcal{W}$ has the effective substructure property since $B\subsetneq A\in \mathcal{W}$ implies that $B$ is isomorphic to $\lbrace a\in A: a < b\rbrace$ for some $b\in A$, and this latter set is computable relative to $A$. Conversely, the collection of dense linear orders has the effective substructure property since all such linear orders are computable. Basically, where I'm at right now is that the only non-trivial example of a class with the effective substructure property I can think of is $\mathcal{W}$ (or variants). I'm wondering, in particular, if there is some reasonably natural class of structures with the effective substructure property which doesn't just build off of $\mathcal{W}$? For example, some $\mathcal{C}$ such that $\mathcal{W}$ is not Borel reducible to $\mathcal{C}$?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Two more non-sophisticated examples would be the class of all countable algebraically closed fields and the class of all countable vector spaces over any collection of (not necessarily computable) fields.

Perhaps it is worth making the trivial observation that any member $A$ of such a class $\mathcal{C}$ can only have (up to isomorphism) countably many substructures. Thus, it is not surprising that many of the natural examples will have ordinal invariants giving the isomorphism type, as the examples so far do.

share|improve this answer
I think this is a good explanation of why the only nontrivial examples I know come from ordinals. I'm still interested in non-"ordinary" (sorry) examples, but I think this answers the question well. –  Noah S Jan 23 '13 at 18:40
add comment

Your Answer


