Properties preserved under homomorphism
Roger C. Lyndon · Pacific Journal of Mathematics · 1959
The main result of this paper is a characterization of those sentences of the predicate calculus whose validity is preserved under passage from an abstract algebraic system to any homomorphic image of the system.An algebraic system is here construed to be a set together with certain operations and relations, including identity, defined for elements of the set.The sentences under consideration will contain symbols for these operations and relations, and variables whose range is the set of elements of the system, together with the usual logical symbols, but will contain no variables whose range consists of sets, relations, or functions.Such a sentence will be called positive if it contains the logical symbols for conjunction, disjunction and quantification only, but not the symbol for negation.It will be shown that:(*) A sentence of the predicate calculus is preserved under homomorphism if and only if it is equivalent to a positive sentence.An example is provided by the usual statement of the commutative law for multiplicative systems:This is a positive sentence, and indeed every homomorphic image of a commutative system in commutative.As a second example, upon eliminating the symbol for " if then ", the left cancellation law takes the form \fxyz ~-(xy -xz) V y = z .This sentence is not positive, and, indeed, from the fact that the left cancellation property is not preserved under homomorphism we conclude that it is not expressible by any positive sentence.It is not difficult to show that every sentence equivalent to a positive sentence is preserved under homomorphism; although the converse seems nearly as obvious intuitively, to prove the converse appears to be a matter of considerable difficulty.That positive sentences are preserved was noted by the author [6], and also by E. Marczewski [9], who raised the question of the converse.A proof, by methods quite different from those used here, was announced by J. Los [5], but such a proof has not been published.The result has also been stated by A. I. Malcev [8], who appears to indicate a method of proof.