Variable Assignment (First-Order Logic)

first-order-logic

Definition

Variable Assignment (First-Order Logic)

Let $\mathcal{M}=(\mathcal{D},\mathcal{I})$ be a structure. A variable assignment is a function

$$\ell :\mathcal{V}\to \mathcal{D}$$

that maps each variable to an element of the domain.

Variants

$\ell [d/x]$

For a variable assignment $\ell$, a variable $x$, and an element $d\in \mathcal{D}$:

$$\ell [d/x](y)=\{\begin{array}{ll}d& \text{if }y=x\\ \ell (y)& \text{if }y\ne x\end{array}$$

$\ell [d/x]$ is the assignment identical to $\ell$ except it maps $x$ to $d$.

$\mathcal{D}=\mathbb{N}$ and let $\ell$ assign:

Let

$$\ell (x)=5,\ell (y)=3$$

Now take $\ell [7/x]$. This means: copy $\ell$, but overwrite $x$ with $7$:

$$\ell [7/x](x)=7,\ell [7/x](y)=3$$

Only $x$ changed. $y$ stays untouched.

$\stackrel{x}{\sim }$

When evaluating quantifiers, we often need an assignment that differs from $\ell$ only at $x$:

$${\ell }^{\prime }\stackrel{x}{\sim }\ell$$

This denotes that for all $y\in \mathcal{V}\setminus \{x\}$, ${\ell }^{\prime }(y)=\ell (y)$. The value ${\ell }^{\prime }(x)$ can be any element in $\mathcal{D}$.

$\mathcal{D}=\{a,b,c\}$ and let $\ell$ assign:

Let

$$\ell (x)=a,\ell (y)=b$$

Consider two candidates for ${\ell }^{\prime }$:

${\ell }^{\prime }$	${\ell }^{\prime }(x)$	${\ell }^{\prime }(y)$	${\ell }^{\prime }\stackrel{x}{\sim }\ell$?
one	$c$	$b$	yes — only $x$ differs
another	$c$	$a$	no — $y$ differs too

The relation only cares about variables other than $x$ staying the same.

$\ell [d/x]$ vs. $\stackrel{x}{\sim }$ $\ell [d/x]$ builds one specific variant: you pick the new value $d$ for $x$. $\stackrel{x}{\sim }$ relates any two assignments that agree everywhere except possibly $x$. The $\sim$ notation is used in quantifier semantics ("does there exist some $x$-variant such that...?") because ${\ell }^{\prime }(x)$ is not fixed to one value — it ranges over all of $\mathcal{D}$.

Dynamic Nature

Unlike a structure, which is fixed, a variable assignment changes as we traverse a formula — specifically when evaluating quantifiers.