I'm studying a mathematical introduction to logic by Enderton and I'm new to the predicate logic. Here's my problem: If $L$ is a language of predicate logic and $D$ is its domain we call a function $\lambda:\{v_1,v_2,...\}\to D$ a function value for $M$ where $M$ is an interpretation for the language. Now they introduce $\lambda(x/a)(v_i)$ like this: $$\lambda(x/a)(v_i)=\begin{cases} a & v_i=x\\ \lambda(v_i) & v_i\neq x \end{cases}$$ My understanding is that the function works the same as a function value on all variables except $x$.

We have two properties that I don't understand why they exist: $$\lambda(x/a)(x/b)=\lambda(x/b)$$ And $$\lambda(x/a)(y/b)=\lambda(y/b)(x/a)$$ And $x$ and $y$ are variables in $\{v_1,v_2,...\}$

  • $\begingroup$ $\lambda(x/a)(v_i)=\begin{cases} a & v_i=a\\ \lambda(v_i) & v_i\neq x \end{cases}$ - this doesn't seem well defined for all values that $v_i$ can take. In otherwords, what if $v_i=x$? $\endgroup$ – Rahul Madhavan Apr 7 at 10:03
  • 1
    $\begingroup$ @RahulMadhavan I made a mistake $\endgroup$ – Hassuni Apr 7 at 10:06

In the first case, we have two successive application of the "$x$-variant" operation:

In $\lambda(x/a)(x/b)$ we first change the value of function $\lambda$ for case $v_i=x$ from value $\lambda (v_i)$ (whatever it is) to the new value $a$.

Then we consider the function $\lambda(x/a)$ that has value $a$ for $v_i=x$ and we change it again to $b$.

Thus, the final result will be a function whose value for $v_i=x$ will be $b$, while for other variables different from $x$ is the original value of $\lambda$, and this exactly $\lambda (x/b)$.

The second is similar; either $x=y$, in which case it is simply the previous case, or $x \ne y$, in which case we change the value of $\lambda$ for two different variables, and the result is independent of the order, because they are different (if $x \ne y$, we have that there are $i,j$ with $i \ne j$ such that $x=v_i$ and $y=v_j$).

We can check them with a simple example of $\lambda: \text { Var } \to \mathbb N$ defined as $\lambda (v_i)=i$. This means that the "output" of $\lambda$ is $\{ 1,2,3, \ldots \}$.

With $x=v_1$ and $y=v_2$ we have that $\lambda(x/5)$ "outputs" $\{ 5,2,3, \ldots \}$ and for $\lambda(x/5)(x/10)$ we have $\{ 10,2,3, \ldots \}$, that is $\lambda(x/10)$.

If we consider instead $\lambda(x/5)(y/5)$ we get $\{ 5,5,3, \ldots \}$, and this is the sane with $\lambda(y/5)(x/5)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.