Questions: Satisfaction Relation in First-Order Logic

Question 1

In structure M = (ℤ, <), consider the formula φ: 'x < y'. Which statement correctly evaluates M ⊨ φ[σ]?

• A. It is true in M, because in ℤ there always exist integers x and y with x < y
• B. It depends on the variable assignment σ — it is true when σ(x) < σ(y) and false otherwise
• C. It is false because x and y are not bound by quantifiers
• D. It cannot be evaluated until the domain of σ is specified separately from M

Answer: (B)

A formula with free variables does not have a fixed truth value in a structure alone — its truth depends on what the free variables are assigned. With σ(x) = 3 and σ(y) = 5, the formula is true; with σ(x) = 7 and σ(y) = 2, it is false — same structure, same formula, different variable assignments, different truth values. Option A is the classic confusion: existential quantification (∃x ∃y x < y) is true in ℤ, but the unquantified formula 'x < y' with free variables is a different claim entirely.

Question 2

Which of the following is a sentence — a formula that can be evaluated in a structure without any variable assignment?

• A. x < y + 1
• B. ∃x (x < y)
• C. ∀x ∀y (x < y ∨ y < x ∨ x = y)
• D. P(x) ∧ Q(y)

Answer: (C)

A sentence has no free variables — all variables are bound by quantifiers. Option C, ∀x ∀y (x < y ∨ y ≤ x), has every variable bound by ∀. Options A and D have free variables x and y with no quantifier. Option B has ∃x binding x, but y remains free — so it is not a sentence. Only option C can be evaluated as simply true or false in a structure without specifying what any variable refers to.

Question 3

A formula with free variables has a definite truth value in a structure M, regardless of which variable assignment is used.

• T. True
• F. False

Answer: False

Free variables are like parameters: their values are supplied by the variable assignment σ, not by the structure alone. The same formula 'x > 0' is true in (ℤ, >) under σ(x) = 5 and false under σ(x) = −2. Only sentences — formulas with no free variables — have truth values in a structure independent of any assignment.

Question 4

The formula ∀x ψ is satisfied under assignment σ if there exists at least one element a in the domain such that ψ is satisfied when x is mapped to a.

• T. True
• F. False

Answer: False

This describes the existential quantifier ∃x ψ, not the universal. For ∀x ψ to be satisfied, every element a of the domain must satisfy ψ when x is mapped to a. A single counterexample — one element a for which ψ fails — is enough to falsify ∀x ψ. The satisfaction clauses for ∃ and ∀ are duals: ∃ requires at least one witness; ∀ requires no exceptions.

Question 5

Explain the difference between a formula and a sentence in first-order logic, and why the satisfaction relation requires a variable assignment for formulas but not for sentences.

Model answer: A sentence has no free variables — every variable is bound by a quantifier. A formula may have free variables whose values are not determined by the formula itself. Free variables act as parameters: the satisfaction relation M ⊨ φ[σ] tracks the assignment σ to supply values for them. When φ is a sentence, truth depends only on the structure M and is written M ⊨ φ without σ, because no variables need external assignment.

This distinction is foundational for model theory. Sentences express properties of structures (e.g., 'this group is abelian'). Formulas with free variables express properties of elements relative to a structure (e.g., 'this element has a multiplicative inverse'). A theory — a set of sentences — is satisfiable if some structure makes all of them true; this notion depends on having sentences, not formulas.