Authors: Manuel Bodirsky ; Jakub Rydval ; André Schrottenloher

The finite models of a universal sentence $\Phi$ in a finite relational signature are the age of a structure if and only if $\Phi$ has the joint embedding property. We prove that the computational problem whether a given universal sentence $\Phi$ has the joint embedding property is undecidable, even if $\Phi$ is additionally Horn and the signature of $\Phi$ only contains relation symbols of arity at most two.

• 03C13 - Model theory of finite structures
• 03D35 - Undecidability and degrees of sets of sentences
• 08A70 - Applications of universal algebra in computer science
• 68Q25 - Analysis of algorithms and problem complexity