How do we give a substitution for the formula?

Question

We have the following predicate logical formula $F$: $$\forall x(E(x,y)\rightarrow \neg \exists z(E(f(x,z),y)\land E(y,z)))$$

I want to give a substitution $\sigma$ that is not collision free for $F$.

Could you give me some hints how we could do that?

---

$$$$

EDIT:

Then I want to do the following:

Give an interpretation $(D_1,I_1)$ and a variable assignment $\beta_1$ so that it holds that $\text{val}_{D_1, I_1,\beta_1}(F) =w$.

By the definition we have that $\text{val}_{D, I,\beta}(1)=w$ and $\text{val}_{D, I,\beta}(0)=f$.

We want that $\text{val}_{D_1, I_1,\beta_1}(F) =w$.

We have that $\text{val}_{D_1, I_1,\beta_1}(x)=\beta_1 (x)$, right?

Does this have to be equal to $w$ ? Does this mean that it must hold that $\beta_1(x)=1$ ?

Answer 1

You have to find an interpretation (domain $D$ plus an interpreting $I$ for the binary predicate symbol $E$ and the binary function symbol $f$) that satisfy the formula $F$.

Due to the free occurrences of the var $y$ in $F$ you have to use a variable assignment function $β$ (that assigns an element of the domain $D$ to $y$) such that $F$ is true in $D$ with $I$ and $β$, i.e.: $D,I,β \vDash F$.

An "easy trick" is to falsify the antecedent of the conditional.

We can consider $D = \{ 0,1 \}$ as domain and interpret $E$ as: $>$ ("greater than").

Let $\beta(y)=0$; thus $E(x,y)$ is interpreted with $\beta$ as $x > 0$, which is not true for all numbers in $D$.

Thus, using $\beta$, the formula is interpeted as:

$\forall x [(x > 0) \to \lnot \exists z (f(x,z) > 0) \land (0 > z))]$

that is true in $D$, irrespective of the interpretation of $f$; i.e.:

$D, I, \beta \vDash F$.