# Two approaches used to define first-order semantics are equivalent for sentences

Let $$L$$ be a first-order language with constant symbols ($$c,\ldots$$), operations ($$f,\ldots$$), predicates ($$R,\ldots$$) and equality symbol $$\dot{=}$$. Let $$M=(U_{M},R^{M},\ldots,f^{M},\ldots,c^{M},=)$$ be an $$L$$-structure (where $$\sigma^{M}$$ denotes the interpretation of the symbol $$\sigma$$ and $$=$$ denotes equality in the domain and is the interpretation of the $$\dot{=}$$ symbol). I have learned two approaches when defining valuation functions for $$M$$:

1. Assume that every element in the domain of $$M$$ has a name (i.e. for each $$u\in U_{M}$$ there is a constant $$a_{u}\in L$$ such that $$a_{u}^{M}=u$$) [another way of acomplishing the same is by adding to $$L$$ all the elements of $$U_{M}$$ as constants and work with this extended language]. Recall that a variable-free $$L$$-term $$t$$ is either a constant $$c$$ or has the form $$ft_{1}\ldots t_{n}$$ for some $$n$$-ary operation $$f\in L$$ and variable-free $$L$$-terms $$t_{1},\ldots, t_{n}$$. In the formar case $$t^{M} = c^{M}$$, while in the latter $$t^{M}=f^{M}(t_{1}^{M},\ldots,t_{n}^{M})$$. The valuation $$v_{M}:\{\text{L-sentences}\}\to\{\mathsf{T},\mathsf{F}\}$$ is defined as follows:
• $$v_{M}(t\dot{=}s)=\mathsf{T}$$ iff $$t^{M}=s^{M}$$, and $$v_{M}(Rt_{1}\ldots t_{n}) = \mathsf{T}$$ iff $$(t_{1}^{M},\ldots,t_{n}^{M})\in R^{M}$$ for atomic $$L$$-sentences (where $$t$$, $$s$$ and the $$t_{i}$$ are variable-free terms).
• $$v_{M}(\neg\phi)=\mathsf{T}$$ iff $$v_{M}(\phi)=\mathsf{F}$$.
• $$v_{M}(\phi\vee\psi)=\mathsf{T}$$ iff $$v_{M}(\phi)=\mathsf{T}$$ or $$v_{M}(\psi)=\mathsf{T}$$.
• $$v_{M}(\exists x\,\phi) = \mathsf{T}$$ iff $$v_{M}(\phi[x/c])=\mathsf{T}$$ for some constant $$c\in L$$ (where $$\phi[x/c]$$ denotes the $$L$$-sentence obtained by substituting every free occurrence of the variable $$x$$ in $$\phi$$ by the constant $$c$$).

For an $$L$$-sentence $$\varphi$$, we define $$M\vDash\varphi$$ iff $$v_{M}(\varphi)=\mathsf{T}$$. Note that we may have defined $$M\vDash\varphi$$ directly, using the obvious modification of the four clauses above.

1. Use variable assignment functions to be able to work with unnamed elements of the domain of $$M$$ and $$L$$-formulas which are not sentences. This approach reduces the truth of sentences like $$\exists x\,\phi$$ to their components (this is sometimes called principle of strict compositionality). Therefore, let $$\alpha$$ be an assignment of the variables of $$L$$. Recall that an $$L$$-term $$t$$ is either a variable $$x$$, a constant $$c$$, or has the form $$ft_{1}\ldots t_{n}$$ for some $$n$$-ary operation $$f\in L$$ and $$L$$-terms $$t_{1},\ldots, t_{n}$$. In the first case $$t^{M}[\alpha] = \alpha(x)$$, in the second $$t^{M}[\alpha]=c^{M}$$, and in the third $$t^{M}[\alpha]=f^{M}(t_{1}^{M}[\alpha],\ldots,t_{n}^{M}[\alpha])$$. The valuation $$v_{M,\alpha}:\{\text{L-formulas}\}\to\{\mathsf{T},\mathsf{F}\}$$ is defined as follows:
• $$v_{M}(t\dot{=}s)=\mathsf{T}$$ iff $$t^{M}[\alpha]=s^{M}[\alpha]$$, and $$v_{M,\alpha}(Rt_{1}\ldots t_{n}) = \mathsf{T}$$ iff $$(t_{1}^{M}[\alpha],\ldots,t_{n}^{M}[\alpha])\in R^{M}$$ for atomic $$L$$-formulas (where $$t$$, $$s$$ and the $$t_{i}$$ are $$L$$-terms).
• $$v_{M,\alpha}(\neg\phi)=\mathsf{T}$$ iff $$v_{M,\alpha}(\phi)=\mathsf{F}$$.
• $$v_{M,\alpha}(\phi\vee\psi)=\mathsf{T}$$ iff $$v_{M,\alpha}(\phi)=\mathsf{T}$$ or $$v_{M,\alpha}(\psi)=\mathsf{T}$$.
• $$v_{M,\alpha}(\exists x\,\phi) = \mathsf{T}$$ iff $$v_{M,\alpha_{x}^{u}}(\phi)=\mathsf{T}$$ for some element $$u\in U_{M}$$ (where $$\alpha_{u}^{x}$$ denotes the function which sends $$x\mapsto u$$ and is otherwise the same as $$\alpha$$.

For an $$L$$-formula $$\varphi$$, we define $$M\vDash\varphi[\alpha]$$ iff $$v_{M,\alpha}(\varphi)=\mathsf{T}$$. Note that we may have defined $$M\vDash\varphi[\alpha]$$ directly, using the obvious modification of the four clauses above.

Now, I know how to prove (by term induction) that for any $$L$$-term $$t$$, if $$\alpha$$ and $$\beta$$ are two assignments agreeing on the variables of $$t$$, then $$t^{M}[\alpha]=t^{M}[\beta]$$. Also (by formula induction) if $$\alpha$$ and $$\beta$$ agree on all the variables occurring freely in the $$L$$-formula $$\phi$$, then $$v_{M,\alpha}(\phi)=v_{M,\beta}(\phi)$$.

Therefore, for any $$L$$-sentence $$\phi$$, if $$v_{M,\alpha}(\phi)=\mathsf{T}$$ for some assignment $$\alpha$$, then $$v_{M,\alpha}(\phi)=\mathsf{T}$$ for all assignments $$\alpha$$.

Question: How do I prove that if all elements of the domain of $$M$$ have names and $$\alpha$$ is any assignment, then for any $$L$$-sentence $$\phi$$, approach 1 and approach 2 give the same truth values? That is, $$v_{M}(\phi) = v_{M,\alpha}(\phi)$$.

Let $$X$$ be the set of $$L$$-sentences for which approach 1 and approach 2 give the same truth value. I was trying to use formula induction (for sentences) on $$X$$, but the reasoning breaks down for the valuation clause with the existential quantifier: $$v_{M}(\exists x,\phi)=\mathsf{T}$$ iff $$v_{M}(\phi[x/c])=\mathsf{T}$$ for some constant $$c\in L$$, but I cannot assume that $$\phi[x/c]\in X$$ (induction hypothesis).

Perhaps, I should attempt a proof by induction of the degree of sentences (number of connectives and quantifiers)? Or perhaps I need to show that $$v_{M}(\phi[x/c]) = v_{M,\alpha^{x}_{c^{M}}}(\phi)$$? (and just to be clear, $$\alpha^{x}_{c^{M}}$$ sends the variable $$x$$ to the element $$c^{M}$$ of our domain, i.e. to the interpretation of the constant $$c$$ for which $$v_{M}(\phi[x/c])=\mathsf{T}$$).

Update: As far as I can see, the idea suggested in the very last paragraph above should work. More formally,

Lemma: Let $$M$$ be any $$L$$-structure and $$\alpha$$ any assignment. Let $$t$$ and $$s$$ be $$L$$-terms, $$\phi$$ an $$L$$-formula, and $$x$$ a variable. Let $$a$$ denote $$s^{M}[\alpha]$$. The following holds:

1. If $$r$$ is the $$L$$-term $$t[x/s]$$ obtained by substituting each occurrence of the variable $$x$$ in $$t$$ by $$s$$, then $$r^{M}[\alpha] = t^{M}[\alpha^{x}_{a}]$$
2. If $$\varphi$$ is the $$L$$-formula $$\phi[x/s]$$ obtained by substituting each free occurrence of the variable $$x$$ in $$\phi$$ by $$s$$, then $$v_{M,\alpha}(\varphi)=v_{M,\alpha_{a}^{x}}(\phi)$$.

Once this is proven (which I think can be done by term and formula induction), the equivalence of approaches 1 and 2 should follow.

• For what it's worth, I dislike both of these approaches. My preferred approach is this: a variable context is a finite set of variables. For each variable context $x$, we define "term in context $x$" and "formula in context $x$", i.e., term/formula in which all free variables come from $x$. Now given a term $t$ in context $x$ and a variable assignment $a\colon x\to M$, we define an element $t(a)\in M$ by induction on $t$, and given a formula $\varphi$ in context $x$ and a variable assignment $a\colon x\to M$, we define the relation $M\models \varphi(a)$ by induction on $\varphi$. Apr 24, 2023 at 21:30
• The inductive step for $\exists$ is: $M\models (\exists y\,\varphi)(a)$ iff there exists $b\in M$ such that $M\models \varphi(a')$, where $a'$ is the extension of $a\colon x\to M$ which additionally assigns the variable $y$ to $b$. This way, to assign a truth value to a sentence, you only end up thinking about assignments of the variables which actually appear in the sentence, which seems much more natural to me. Apr 24, 2023 at 21:31
• @AlexKruckman Thank you. I see, you are essentially interpreting a term $t$ in context $x$ (say $k$ variables) as a function $t^{M}:U_{M}^{k}\rightarrow U_{M}$ (using my notation). And I understand your follow-up comment as well. I like your approach. In any case, since the two approaches I describe are standard and common on many textbooks, I would like to know how to prove they are equivalent for $L$-sentences. Do you have any suggestions on my question?
– John
Apr 24, 2023 at 21:52

The approach I suggested in the update works. In order to remove the question from the unanswered list here are the details.

The equivalence of approach A and approach B for $$L$$-sentences means the following:

Let $$M$$ be any $$L$$-structure such that every element in the domain of $$M$$ has a name in $$L$$. Let $$\alpha$$ be any assignment. Let $$\varphi$$ be any $$L$$-sentence. Then $$v_{M}(\varphi) = v_{M,\alpha}(\varphi)$$

The proof can be easily carried out by induction on the degree (number of connectives and quantifiers) of $$L$$-sentences once the lemma in the update of the question is proven. Indeed, for atomic $$L$$-sentences it is straightforward from part 1 of the lemma. For the inductive steps, it is also straightforward for the connectives. If $$\varphi$$ is of the form $$\exists x\,\phi$$, then $$v_{M}(\varphi) = \mathsf{T}$$ iff $$v_{M}(\phi[x/c])=\mathsf{T}$$ for some constant $$c\in L$$ iff (induction hypothesis) $$v_{M,\alpha}(\phi[x/c]) = \mathsf{T}$$ for some constant $$c\in L$$ iff (by part 2 of the lemma for $$s=c$$ and $$a=c^{M}$$) $$v_{M,\alpha_{u}^{x}}(\phi)=\mathsf{T}$$ for some $$u\in U_{M}$$ iff $$v_{M,\alpha}(\varphi)=\mathsf{T}$$. And we are done.

The proof of the lemma can be carried out as follows:

For part 1, by term induction: If $$t$$ is the variable $$x$$, then $$r$$ is simply $$x$$ and $$r^{M}[\alpha]=s^{M}[\alpha]=a=t^{M}[\alpha_{a}^{x}]$$. If $$t$$ is the variable $$y$$ (different from $$x$$) then $$r$$ is just $$y$$ and $$r^{M}[\alpha] = \alpha(y) = \alpha_{a}^{x}(y) = t^{M}[\alpha_{a}^{x}]$$. The case when $$t$$ is a constant $$c$$ is clear. Finally, if $$t$$ has the form $$ft_{1}\ldots t_{n}$$ for some $$n$$-ary operation $$f\in L$$ and $$L$$-terms $$t_{1},\ldots, t_{n}$$ for which part 1 holds, then $$r^{M}[\alpha] = f^{M}(t_{1}^{M}[\alpha_{a}^{x}],\ldots,t_{n}^{M}[\alpha_{a}^{x}]) = t^{M}[\alpha_{a}^{x}]$$, as desired. By term induction, we are done.

For part 2, by formula induction: The case of atomic $$L$$-formulas is a straightforward application of part 1 of the lemma, which we have just proven. Handling the connectives is also straightforward. Regarding the quantifier $$\exists$$, we have two posibilities:

1. $$\phi$$ is $$\exists x\,\psi$$. Then $$\phi[x/s]$$ is simply $$\phi$$ and $$v_{M,\alpha}(\phi[x,s]) = v_{M,\alpha}(\phi) = v_{M,\alpha_{a}^{x}}(\phi)$$ since $$x$$ is not free in $$\phi$$.
2. $$\phi$$ is $$\exists y\,\psi$$, where $$y$$ is different from $$x$$, $$y$$ does not occurr in $$s$$ (if it does we can always rename $$y$$), and part 2 holds for $$\psi$$. Then $$v_{M,\alpha}(\phi[x/s]) = v_{M,\alpha}(\exists y\,\psi[x/s])=\mathsf{T}$$ iff $$v_{M,\alpha_{b}^{y}}(\psi[x/s])=\mathsf{T}$$ for some $$b\in U_{M}$$ iff (induction hypothesis and letting $$\beta=\alpha_{b}^{y}$$) $$v_{M,\beta_{a}^{x}}(\psi)=\mathsf{T}$$ for some $$b\in U_{M}$$ iff (by * and letting $$\gamma=\alpha_{a}^{x}$$) $$v_{M,\gamma_{b}^{y}}(\psi)=\mathsf{T}$$ iff $$v_{M,\alpha_{a}^{x}}(\exists y\,\psi)=v_{M,\alpha_{a}^{x}}(\phi)=\mathsf{T}$$, as desired. Formula induction concludes the proof.

The * explains the equivalence: it needs the hypothesis that $$y$$ is not in $$s$$ and is different from $$x$$ so we can have $$a=s^{M}[\alpha] = s^{M}[\beta]$$ and $$\beta_{a}^{x} = \gamma_{b}^{y}$$.

For completion, and my own understanding, I will add the third approach outlined in the comments above. Some references for this are: David Marker's Model Theory: An Introduction (2000) pages 9-11. Wilfrid Hodges' A Shorter Model Theory (1997) pages 11-13. And Elliot mendelson's Introduction to Mathematical Logic, 6th ed. (2015) pages 53-57.

Approach C:

Let $$L$$ be a language, and $$M$$ an $$L$$-structure, as stated at the beginning of the question. A variable context $$\bar{x}$$ is defined to be a finite set $$\{x_{i_{1}},\ldots,x_{i_{m}}\}$$ of variables of $$L$$. Therefore, we say that an $$L$$-term $$t$$ has context $$\bar{x}$$, and we write $$t$$ as $$t[\bar{x}]$$, when $$\bar{x}$$ is the set of variables occurring in $$t$$. Now, if $$\bar{u}:\bar{x}\to U_{M}$$ denotes an assignment of the context of $$t$$ (that is, $$\bar{u}(x_{i_{j}}) = u_{i_{j}}\in U_{M}$$, for $$1\leq j\leq m$$), then $$t^{M}[\bar{u}]$$ is defined to be the element of $$U_{M}$$ which is named by $$t$$ via the assignment $$\bar{u}$$. More precisely,

• If $$t$$ is the variable $$x$$, then $$t^{M}[\bar{u}] = u$$.
• If $$t$$ is the constant $$c$$, then $$t^{M}[\bar{u}] = c^{M}$$.
• If $$t$$ has the form $$ft_{1}\ldots t_{n}$$ for some $$n$$-ary operation $$f$$ and $$L$$-terms $$t_{i}$$, each having context $$\bar{x}$$, then $$t^{M}[\bar{u}] = f^{M}(t_{1}^{M}[\bar{u}],\ldots,t_{n}^{M}[\bar{u}])$$.

Note that if $$t$$ is variable-free (i.e., it has empty context), then $$\bar{u}$$ plays no role and we can simply write $$t^{M}$$.

Just as with terms, an $$L-$$formula $$\varphi$$ has context $$\bar{x}$$ if the set of variables occurring freely in $$\varphi$$ is $$\bar{x}$$. We write $$\varphi$$ as $$\varphi[\bar{x}]$$. Therefore, for an assignment $$\bar{u}$$ of $$\bar{x}$$ we can determine the truth or falsity of $$\varphi[\bar{u}]$$ in $$M$$. More precisely,

The valuation $$V_{M}:\{\text{L-formulas}\}\to\{\mathsf{T},\mathsf{F}\}$$ is defined as follows: let $$\varphi$$ have context $$\bar{x}$$ and assignment $$\bar{u}$$. If $$\varphi$$ is

• $$t\dot{=}s$$, then $$V_{M}(\varphi[\bar{u}])=\mathsf{T}$$ iff $$t^{M}[\bar{u}] = s^{M}[\bar{u}]$$, where $$t,s$$ are $$L$$-terms having context $$\bar{x}$$.
• $$Rt_{1}\ldots t_{n}$$, then $$V_{M}(\varphi[\bar{u}]) = \mathsf{T}$$ iff $$(t^{M}_{1}[\bar{u}],\ldots,t_{n}^{M}[\bar{u}])\in R^{M}$$, where $$R$$ is an $$n$$-ary predicate and each $$t_{i}$$ is an $$L$$-term having context $$\bar{x}$$.
• $$\neg\phi$$, then $$V_{M}(\varphi[\bar{u}])=\mathsf{T}$$ iff $$V_{M}(\phi[\bar{u}])=\mathsf{F}$$.
• $$\phi\vee\psi$$, then $$V_{M}(\varphi[\bar{u}])=\mathsf{T}$$ iff $$V_{M}(\phi[\bar{u}])=\mathsf{T}$$ or $$V_{M}(\psi[\bar{u}])=\mathsf{T}$$.
• $$\exists y\,\phi$$, then $$V_{M}(\varphi[\bar{u}])=\mathsf{T}$$ iff there is some $$v\in U_{M}$$ such that $$V_{M}(\phi[\bar{v}])=\mathsf{T}$$, where $$\bar{v}$$ is the assignment which sends $$y\mapsto v$$ and is otherwise the same as $$\bar{u}$$.

We define $$M\vDash\varphi[\bar{u}]$$ iff $$V_{M}(\varphi[\bar{u}])=\mathsf{T}$$. Clearly we may have defined $$M\vDash\varphi[\bar{u}]$$ directly by modifying the four clauses above in the obvious way.

It is straightforward to see that approaches B and C yield the same truth values for $$L$$-formulas, since approach C is nothing more than approach B particularized to the contexts of $$L$$-terms and $$L$$-formulas. That is, an assigment $$\alpha$$ is restricted to to the finite context of each $$L$$-term and $$L$$-formula. Therefore, when we ask about the truth value of an $$L$$-formula, we only need to think about assignments of the variables which actually appear in the $$L$$-formula, as Alex Kruckman points out in the comments.