Why do these two properties hold in predicate logic?

32 Views Asked by At

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,...\}$

1

There are 1 best solutions below

0
On BEST ANSWER

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)$.