Problem 3 - Predicate Logic

Consider the following formula:

$$\left[(\forall x)R(x,x)\wedge(\forall x)(\forall y)(\forall z)((R... ...y,z))\rightarrow R(x,z)) \wedge(\forall x)(\forall y)(R(x,y)\vee R(y,x))\right]$$

$$\rightarrow(\exists y)(\forall x)R(y,x).$$

1.

Show that every interpretation with a finite domain satisfies the formula.

2.

Find an interpretation which does not satisfy the formula.

1.

Let us assume that we have an interpretation $I$ such that $D_I$ is finite. We want to show that the above formula is always true under the valuation associated with $I$. To show that the implication is true, we just have to show that the truth of $(\forall x)R(x,x)\wedge(\forall x)(\forall y)(\forall z) ((R(x,y)\wedge R(y,z))\rightarrow R(x,z))\wedge(\forall x)(\forall y)(R(x,y)\vee R(y,x))$ implies the truth of $\rightarrow(\exists y)(\forall x)R(y,x)$. So, we assume that the left-hand side of the implication is true. It signifies in particular that:

$$(\forall x)(\forall y)(R(x,y)\vee R(y,x))$$

is true. Let us choose $y_0$ so that:

$$(\exists y_0)(\forall x)(R(x,y_0)\vee R(y_0,x))$$

If for the whole set of variable ranging over $D_I$ (which is finite), $R(y_0,x)$ is true, then it is over. If not, we consider one of the $x$ such that $R(x,y_0)$. We call it $y_1$ and for that $y_1$ we have:

$$(\exists y_1)(\forall x)(R(x,y_1)\vee R(y_1,x))$$

But now, we do know that the set of $x$ verifying $R(y_1,x)$ contains at least one element ($y_0$). In the same way we build $y_2$. Let us assume that the cardinality of $D_I$ is $n$ and that we have just built $y_n$, that is:

$$(\exists y_n)(\forall x)(R(x,y_n)\vee R(y_n,x))$$

Where the set of $x$ verifying $R(y_n,x)$ contains $y_0, y_1, \dots, y_{n-1}$. I have succeeded in finding a $y$ such that:

$$(\exists y)(\forall x)R(y,x)$$

We conclude by saying that all interpreation $I$ where $D_I$ is finite satisfies the wff.

2.

If you choose the interpreation $I$ with $D_I = \mathbb{Z}$ and $R=\leq$ then the wff states that:

$$(\exists y)(\forall x)(y \leq x)$$

which is obviously false.