Questions: Existential Formulas and Preservation under Embeddings

Question 1

Graph G satisfies the sentence ∃x ∃y (x ≠ y ∧ E(x,y)). Graph H is formed by taking G and adding new vertices and edges. Must H also satisfy this sentence?

• A. Not necessarily — H might be a different graph that assigns different meanings to the variables x and y
• B. Yes — the witness elements (the two adjacent vertices in G) are still present in H after embedding, so the existential sentence remains satisfied
• C. Only if H is isomorphic to G, since embeddings preserve structure only between isomorphic structures
• D. Not necessarily — adding edges to H might change the truth value of edge relation E for the original vertices

Answer: (B)

This is the key property of existential formulas: they are preserved under embeddings. The sentence requires witnesses — two vertices a, b with a ≠ b and E(a,b). These witnesses exist in G. Since H embeds G (injectively, preserving relations), the images of a and b in H still satisfy a ≠ b and E(a,b). The new vertices and edges added to form H cannot destroy the existence of witnesses already present. Option D is wrong because embeddings preserve relations: if E(a,b) holds in G, then E(f(a),f(b)) holds in H for any embedding f.

Question 2

Which of the following formulas is preserved under embeddings — meaning that if it holds in a structure A, it must hold in any structure B into which A embeds?

• A. ∀x ∀y (E(x,y) → E(y,x)) [the graph is symmetric]
• B. ∀x ¬E(x,x) [the graph has no self-loops]
• C. ∃x ∃y ∃z (E(x,y) ∧ E(y,z) ∧ E(z,x)) [the graph contains a triangle]
• D. ∀x ∃y E(x,y) [every vertex has at least one neighbor]

Answer: (C)

Only the existential sentence (option C) is preserved under embeddings. It asserts the existence of a triangle — three vertices with the required edges. If such witnesses exist in A, they persist in any embedding of A. The universal sentences (A, B, D) are not preserved: embedding A into B can add elements that violate universal conditions. For example, B might contain a non-symmetric edge (violating option A), a self-loop (violating B), or an isolated vertex (violating D), even though A had no such elements. Universal formulas are preserved in the other direction — downward, under substructures.

Question 3

The Łoś-Tarski theorem states that a formula is preserved under embeddings if and only if it is logically equivalent to an existential formula. This means the semantic property (preserved under embeddings) and the syntactic property (being existential) coincide exactly.

• T. True
• F. False

Answer: True

This is the content of the Łoś-Tarski theorem — a characterization result that bridges syntax and semantics. The 'if' direction is straightforward: existential formulas are preserved under embeddings because witness elements survive the injection. The 'only if' direction is deeper: any formula preserved under embeddings must be expressible as an existential formula. This means you cannot have a formula that is semantically preserved under embeddings but syntactically requires universal or nested quantifiers. Preservation properties directly characterize quantifier structure — one of the central achievements of preservation theory.

Question 4

The sentence 'this graph has no edges' — formally ∀x ∀y ¬E(x,y) — is an existential property because it makes a claim about the absence of witnesses.

• T. True
• F. False

Answer: False

Despite being about absence, this is a universal formula: it universally quantifies over all pairs of vertices and asserts a negative property. It cannot be expressed as a purely existential formula. This matters for preservation: the property 'no edges' is NOT preserved under embeddings. A graph with no edges embeds into any graph (since you add new vertices and edges but preserve the existing empty-edge relation on the original vertices) — but the larger graph likely has edges. So the embedded structure satisfies 'no edges' while the embedding target does not. Universal formulas are preserved under substructures (going to smaller structures), not under embeddings (going to larger ones).

Question 5

Explain in your own words why existential formulas are preserved upward under embeddings, while universal formulas are preserved downward under substructures. What is the underlying logical reason?

Model answer: Existential formulas say 'something exists' — they are satisfied by providing witnesses. An embedding injects the small structure into the large one and preserves all relations, so any witnesses present in the small structure are still present (as their images) in the large structure. You cannot 'lose' witnesses by adding more elements. Universal formulas say 'everything satisfies this condition' — they can be violated by adding new elements that fail the condition. Going to a smaller structure (substructure) cannot introduce new violating elements, so universal formulas are preserved downward.

The intuition is about what each quantifier type is 'at risk' of: existential claims risk losing witnesses (so they are stable when you add elements, i.e., going upward), while universal claims risk gaining counterexamples (so they are stable when you remove elements, i.e., going downward). An embedding is a passage to a potentially larger structure — safe for existential, dangerous for universal. A substructure passage removes elements — safe for universal, dangerous for existential (witnesses might be removed). The Łoś-Tarski theorem shows these intuitions are exact: the syntactic classification (∃ vs ∀) perfectly predicts the direction of preservation.