Universal Horn Sentences and the Joint Embedding Property


Abstract in English

The finite models of a universal sentence $Phi$ 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 is binary.

Download