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$:
- 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.
- 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:
- 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}]$
- 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.
Best Answer
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:
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:
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,
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
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.