Let φ: M → N be a homomorphism between two structures, and suppose relation R holds on tuple (a, b) in M. Which statement is guaranteed by the definition of homomorphism?
AR^N holds on (φ(a), φ(b)), and if R^N holds on any (φ(c), φ(d)) then R^M holds on (c, d)
BR^N holds on (φ(a), φ(b))
CR^M holds on (a, b) if and only if R^N holds on (φ(a), φ(b))
DR^N holds on every tuple of elements in the image of φ
A homomorphism only guarantees the FORWARD direction: if R holds in M on a tuple, its image satisfies R in N. It does NOT require the converse — R^N might hold on (φ(c), φ(d)) even when R^M does not hold on (c, d). Option C (biconditional preservation) is precisely the additional property that, combined with injectivity, makes a map an embedding rather than merely a homomorphism. Option A confuses this forward-only preservation with the stronger reflection property of embeddings.
Question 2 Multiple Choice
Which type of map between structures M and N guarantees that the image φ(M) is an isomorphic copy of M sitting inside N as a substructure?
AAny homomorphism φ: M → N
BAn injective homomorphism (embedding) φ: M → N
CA surjective homomorphism φ: M → N
DAny map φ: M → N between structures with the same cardinality
An embedding is an injective homomorphism that also reflects relations: R^M holds on a tuple if and only if R^N holds on the image tuple. The two-way preservation plus injectivity ensures the image φ(M) is an isomorphic copy of M — no relational facts are lost or gained, and no two elements of M collapse to the same image element. A mere homomorphism might be non-injective (collapsing elements) or fail to reflect relations, so its image need not mirror M's structure. Surjectivity (option C) produces an isomorphism of the whole of M to N, not a substructure relationship.
Question 3 True / False
If φ: M → N is a homomorphism and R^N holds on (φ(a), φ(b)), then R^M is expected to hold on (a, b) in M.
TTrue
FFalse
Answer: False
False. This backward direction — reflection of relations — is NOT required by a mere homomorphism. It is the extra property (along with injectivity) that makes a map an embedding. Homomorphisms preserve relations only forward: R in M implies R in N on the image. But R holding in N on image elements does not guarantee R held in M on the preimages. A homomorphism can map elements into N in a way that satisfies additional relations not present in M. This is why embeddings are strictly stronger: they prevent the image from 'gaining' relational facts that didn't exist in the source.
Question 4 True / False
An isomorphism between two structures M and N guarantees that any first-order sentence true in M is also true in N.
TTrue
FFalse
Answer: True
True. An isomorphism is a bijective embedding — a perfect, structure-preserving bijection in both directions. It preserves all elements, functions, and relations completely. Any first-order sentence quantifies over elements and applies function and relation symbols; since the isomorphism mirrors every element, function value, and relational fact between M and N, any sentence true in one is true in the other. Structures satisfying exactly the same first-order sentences are called elementarily equivalent; isomorphic structures are a special case that are both elementarily equivalent and structurally identical (not just logically indistinguishable).
Question 5 Short Answer
What is the key difference between a homomorphism and an embedding, and why does it matter for which logical sentences are preserved?
Think about your answer, then reveal below.
Model answer: A homomorphism preserves relations only in the forward direction: if R holds in M, it holds on the image in N, but R can hold in N on image elements without holding in M. An embedding is an injective homomorphism that also reflects relations: R holds in M if and only if R holds on the image in N. This matters because embeddings preserve all quantifier-free first-order sentences — both positive and negative relational facts — while homomorphisms preserve only positive existential sentences. Homomorphisms cannot preserve negations because they permit the image to satisfy relations absent in the source.
The logical characterization is central to model theory: each type of structure-preserving map corresponds to a class of first-order formulas it preserves. Homomorphisms preserve sentences of the form ∃x R(x) (positive existential), but not ¬R(x) or ∀x R(x) — because the image might satisfy R in ways the source does not. Embeddings preserve quantifier-free sentences, so both 'R(a, b) holds' and 'R(a, b) does not hold' are accurately reflected. For preservation of all first-order sentences, one needs elementary embeddings, a yet stronger condition. This layered picture — stronger maps preserve richer formula classes — organizes much of classical model theory.