Solutions to Exercises

1.

Is it true that

$$\models \forall x (\phi \wedge \psi) \leftrightarrow \forall x \phi \wedge \forall x \psi?$$

Yes.

2.

Is it true that

$$\models \exists x (\phi \wedge \psi) \leftrightarrow \exists x \phi \wedge \exists x \psi?$$

Prove that your answer is correct.

3.

Is it true that

$$\models \forall x (\phi \vee \psi) \leftrightarrow \phi \vee \forall x \psi?$$

Prove that your answer is correct.

4.

Is it true that

$$\models \exists x (\phi \wedge \psi) \leftrightarrow \phi \wedge \exists x \psi?$$

Prove that your answer is correct.

5.

A set $\Phi$ is called independent iff there is no $\phi \in \Phi$ such that $\Phi - \{\phi\} \models \phi$. Show that the axioms for equivalence relations,

(a)

$\forall x Rxx$

(b)

$\forall x \forall y (Rxy \rightarrow Ryx)$

(c)

$\forall x \forall y \forall z ((Rxy \wedge Ryz) \rightarrow Rxz),$

form an independent set.