4
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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$. $\endgroup$ Apr 24, 2023 at 21:30
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 24, 2023 at 21:31
  • 1
    $\begingroup$ @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? $\endgroup$
    – John
    Apr 24, 2023 at 21:52

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .