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

, ,
Discrete Mathematics & Theoretical Computer Science
Algebraic Methods for Stronger Crypto

Bodirsky, M, Rydval, J, & Schrottenloher, A.C. (2022). Universal Horn sentences and the joint embedding property. Discrete Mathematics & Theoretical Computer Science, 23(2), 4.1–4.15. doi:10.46298/dmtcs.7435