Past exam of the logic and set theory course of the University of Oxford / 2009 / A / 2 / b / Solution

A first-order structure consists of a nonempty domain $A$, an interpretation $c^A\in A$ of each constant symbol, a total function $f^A:A^n\to A$ for each $n$-ary function symbol, and a relation $R^A\subseteq A^n$ for each $n$-ary predicate symbol. Logical equality is interpreted as actual identity.

An assignment in a first-order structure is a map $s$ from the variables into $A$. It extends recursively to terms: $x^A[s]=s(x)$, $c^A[s]=c^A$, and $f(t_1,\dots ,t_n{)}^A[s]=f^A(t_1^A[s],\dots ,t_n^A[s])$. Atomic truth is determined by membership of the resulting tuple in $R^A$, or equality of the two term values. Negation reverses the truth value, and an implication is false exactly when its antecedent is true and its consequent false.

For a universal quantifier,These clauses define a valuation on every formula by structural recursion. Only free-variable values affect a formula's truth; consequently a sentence has the same truth value under every assignment. This is a semantic assignment of domain elements, not a programming assignment operation.