First-order definable retraction problems for posets and reflexive graphs

Dalmau, V.; Krokhin, A.; Larose, B.

Abstract

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterzies all posets and all reflexive graphs Q such that the class of all posets or reflexive graphs, respectively, that admit a retraction onto Q is first-order definable.

Citation

Dalmau, V., Krokhin, A., & Larose, B. (2007). First-order definable retraction problems for posets and reflexive graphs. Journal of Logic and Computation, 17(1), 31-51. https://doi.org/10.1093/logcom/exl014

• Journal Article Type: Article
• Publication Date: Feb 1, 2007
• Deposit Date: Mar 26, 2010
• Publicly Available Date: Apr 7, 2010
• Journal: Journal of Logic and Computation
• Print ISSN: 0955-792X
• Electronic ISSN: 1465-363X
• Publisher: Oxford University Press
• Peer Reviewed: Peer Reviewed
• Volume: 17
• Issue: 1
• Pages: 31-51
• DOI: https://doi.org/10.1093/logcom/exl014
• Keywords: Retraction, Homomorphism, Graphs, Posets, First-order definability.
• Public URL: https://durham-repository.worktribe.com/output/1558806
• Publisher URL: http://logcom.oxfordjournals.org/cgi/reprint/17/1/31