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. (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