The formula ∀x ∀y (R(x,y) → R(y,x)) is evaluated in two structures over the same domain D = {1, 2}. In structure M₁, R = {(1,2), (2,1)}. In structure M₂, R = {(1,2)}. What are the truth values?
ATrue in both M₁ and M₂, because the formula is a logical tautology
BFalse in both, because R is a binary relation and symmetry cannot be guaranteed
CTrue in M₁ (R is symmetric) and false in M₂ (R(1,2) holds but R(2,1) does not)
DThe formula has no truth value until a domain is specified
In M₁, every pair (x,y) with R(x,y) has its mirror (y,x) also in R, so the formula is true. In M₂, R(1,2) holds but R(2,1) does not, making R(1,2) → R(2,1) false, so the universal is false. The same formula can be true or false depending on the structure — this is the core semantic fact of predicate logic. The formula is not a tautology; it expresses a contingent property (symmetry) that some structures satisfy and others do not.
Question 2 Multiple Choice
A logician says: 'The formula ∀x P(x) is true.' What information is missing before you can agree or disagree?
AThe proof system being used to derive the formula
BWhether P is a unary or binary predicate
CWhich structure is being used — the domain D and the interpretation of P
DWhether the formula is in prenex normal form
∀x P(x) has no truth value until you specify a structure: a domain D and an interpretation of the predicate P as some subset of D. In the structure where D = {2,4,6} and P means 'is even,' the formula is true. In the structure where D = {1,2,3} and P means 'is even,' it is false (P(1) fails). Asking 'is the formula true?' without naming a structure is like asking 'is x > 0?' without specifying x.
Question 3 True / False
A closed first-order formula is either true in most structures or false in most structures — there is no middle ground.
TTrue
FFalse
Answer: False
Only logical tautologies (valid formulas) are true in every structure, and only contradictions are false in every structure. Most formulas are contingent — true in some structures and false in others. For example, ∃x ∃y (x ≠ y) is true in any domain with at least two elements but false in a singleton domain. The distinction between tautology, contingency, and contradiction is central to model theory.
Question 4 True / False
Changing the interpretation of a predicate symbol in a structure can change whether a formula is satisfied in that structure.
TTrue
FFalse
Answer: True
The satisfaction relation M ⊨ φ depends on both the domain and the interpretation function. If you change what predicate P means — that is, change which elements of D satisfy P — formulas involving P may flip from true to false or vice versa. This is why 'structure' bundles together both the domain and the interpretation: together they fully determine the truth value of every formula, and changing either component can change the outcome.
Question 5 Short Answer
Explain why the formula ∀x ∀y (R(x,y) → R(y,x)) is not simply 'true' or 'false.' What determines its truth value? Give an example of one structure where it is true and one where it is false.
Think about your answer, then reveal below.
Model answer: The formula has no intrinsic truth value; it is only true or false relative to a specific structure — a non-empty domain D together with an interpretation of R as a binary relation on D. In a structure where D = {1,2} and R = {(1,2),(2,1)}, R is symmetric and the formula is true. In a structure where D = {1,2} and R = {(1,2)}, R is not symmetric (R(1,2) holds but R(2,1) does not), so the formula is false. The formula expresses the property of symmetry — whether R happens to be symmetric depends entirely on how R is interpreted.
This relativization of truth to structures is the defining move of model-theoretic semantics. It separates the syntactic formula (which is fixed) from its semantic evaluation (which depends on the structure). The same insight underlies the satisfiability and validity questions that drive much of formal logic and computer science.