Conditionals and relations in first-order logic

Conditionals and the quantifiers

An important thing we noted in the last chapter was the interplay between the quantifiers and the conditional. The reason quantifiers and the conditional can result in unintuitive consequences is the zeroth-order equivalence between $X \rightarrow Y$ and $\neg X \vee Y$, and how pushing and pulling $\neg$ through the quantifiers functions. The following exercise demonstrates some unexpected equivalences in first-order logic regarding the often misleading sentence $\exists x (P(x) \rightarrow Q(x))$, which is neither equivalent to $\exists x (P(x) \wedge Q(x))$, nor to $\forall x (P(x) \rightarrow Q(x))$.

A related problem arises when we think about quantifier placement regarding conditionals. In particular, it should be noted that putting a quantifier in front of a conditional and in the antecedent of a conditional will result in formulas that do not mean the same thing. For example, $\forall x \exists y (R(x, y) \rightarrow P(x))$ and $\forall x (\exists y R(x, y) \rightarrow P(x))$ mean different things. This is, again, because in some sense, there is a hidden negation in a conditional $X \rightarrow Y$, given its equivalence to $\neg X \vee Y$, and pulling the quantifier over that negation changes it to the other quantifier, by negation pull-through. Accordingly, we can prove the following:

Here is the first one:

Properties of relations

Finally, let’s return to properties of relations. We already saw how we can formulate these in first-order logic. In particular:

1. Reflexivity: $\forall x R(x, x)$

2. Symmetricity: $\forall x \forall y (R(x, y) \rightarrow R(y, x))$

3. Transitivity: $\forall x \forall y \forall z ((R(x, y) \wedge R(y, z)) \rightarrow R(x, z))$

Using these formulations and first-order logic, we are now able to reason about these properties, and see what they entail.

One obvious thing we can show is that given these general properties, particular instances follow. For example, if reflexivity holds, then for any particular object $a$, we have $R(a,a)$. That is, $\forall x R(x,x) \vdash R(a, a)$ for any $a$.

We also have that $\{\forall x \forall y (R(x, y) \rightarrow R(y, x)), R(a, b)\} \vdash R(b,a)$.

Finally, we also have

$$\{\forall x \forall y \forall z ((R(x, y) \wedge R(y, z))\rightarrow R(x, z)), R(a, b), R(b, c) \vdash R(a, c)\}$$

In addition, we can also show some more general facts about relations. For example, if a relation $R$ is symmetric and transitive, and we know that some object $x$ relates by $R$ to some object $y$, then from this, it follows that some object relates to itself. That is: $$\{\forall x \forall y (R(x, y) \rightarrow R(y, x)), \forall x \forall y \forall z ((R(x, y) \wedge R(y, z))\rightarrow R(x, z)), \exists x \exists y R(x, y)\} \vdash \exists x R(x,x)$$

Thankfully, given our tableau system, this is not a particularly hard fact to prove, but it is somewhat tedious. The only trick is to realize that since universal quantifiers can be instantiated with any name independent of one another, the following is an instance of transitivity: $(R(a, b) \wedge R(b, a))\rightarrow R(a, a)$.